Прежде чем приступить к рассмотрению сжатия данных, реализуем алгоритм восстановления, поскольку его концепция проще для визуализации. В процессе восстановления мы считываем байт флага, а затем используем его для определе* ния способа считывания из потока следующих восьми кодов. Если текущий бит в байте флага является нулевым, мы считываем из потока 1 байт и интерпретируем его как литеральный символ, который должен быть записан непосредственно в выходной поток. И напротив, если текущий бит является единичным, мы считываем из входного потока 2 байта и разбиваем это значение на значения расстояния и длины. Затем эти значения используются с текущим скользящим окном ранее декодированных данных для определения того, какой символ должен быть записан в выходной поток.

При каждом декодировании отдельного символа или набора от трех до 10 символов, их нужно не только записать в выходной поток, но и добавить в конец буфера скользящего окна и сдвинуть начало скользящего окна на соответствующее расстояние, чтобы его размер не превышал 8192 байтов. Естественно, нежелательно, чтобы приходилось восстанавливать буфер при каждом декодировании символа или строки символов - это занимало бы слишком много времени. На практике используется циклическая очередь - очередь фиксированного размера, начало и конец которой определяются индексами. Поскольку на этапе сжатия будет использоваться аналогичное скользящее окно (как именно, мы вскоре рассмотрим), целесообразно создать реализацию класса, которая могла бы использоваться в обоих процессах.

Прежде чем приступить к описанию методов восстановления, которые потребуются для этого класса, я хочу описать небольшой прием, используемый методом Deflate программы FKZIP. Еще раз взгляните на пример предложения, сжатие которого было выполнено ранее. На одном из этапов описания алгоритма возникла следующая ситуация: -------+

a cat is I a cat is a cat

-------+A и мы вычислили пару значений расстояние/длина <9,9>. Однако можно применить небольшую хитрость. Почему мы должны прекращать сопоставление на 9 символах? В действительности можно сопоставить значительно больше символов, выйдя за пределы правой границы скользящего окна и продолжая сопоставление с текущим символом и с символами, расположенными справа от него. Фактически, можно было бы установить соответствие 14 символов, получив при этом код <9,14>, в котором значение длины превышает значение расстояния. Все это замечательно и достаточно разумно, но что при этом происходит во время декодирования? В момент декодирования кода <9,14> скользящее окно выглядит следующим образом:

--------+
a cat is I

--------+ А

Мы возвращаемся в скользящем окне на 9 символов назад и начинаем по одному копировать символы, пока не будет достигнут 14-й символ. В результате мы копируем символы, которые нам удалось определить в одной и той же операции.

После копирования девяти символов мы получаем --------+

a cat is I a cat is

_________|_ Л Л

ОТ ДО где показаны позиции, от которой и до которой выполняется копирование. Как видите, копирование остальных пяти символов может быть выполнено вообще без возникновения каких-либо проблем. Следовательно, значение длины вполне может превышать значение расстояния (хотя приходится признать, что для копирования данных нельзя было просто воспользоваться процедурой Move).

Во время восстановления мы передадим класс скользящего окна выходному потоку, в который должны записываться данные. В результате, когда объект определяет, что активные данные в буфере требуется передвинуть обратно к началу, вначале он копирует в поток данные, которые должны замещаться в буфере. Для выполнения восстановления требуются два основных метода: добавление одиночного символа и преобразование пары расстояние/длина. Обратите внимание, что эти действия выполняются классом скользящего окна, поскольку обновление скользящего окна и перемещение вперед по данным должны выполняться в обоих случаях. Кроме того, класс - лучший агент выполнения преобразования значений расстояния и длины. Код реализации интерфейса класса, служебных процедур и вывода соответствующего кода приведен в листинге 11.23.

Листинг 11.23. Код, связанный с выводом, класса скользящего окна

type TtdLZSlidingWindow = class private FBuffer : PAnsiChar; {циклический буфер} FBufferEnd : PAnsiChar; {конечная точка буфера} FCompressing : boolean; {Ьгие=сжатию данных} FCurrent : PAnsiChar; {текущий символ} FLookAheadEnd : PAnsiChar; {конец упреждающего просмотра} FMidPoint : PAnsiChar; {средняя точка буфера} FName : TtdNameString; {имя скользящего окна} FStart : PAnsiChar; {начало скользящего окна} FStartOffset : longint; {смещение потока для FStart} FStream : TStream; {базовый поток} protected procedure swAdvanceAfterAdd(aCount : integer); procedure swReadFromStream; procedure swSetCapacity(aValue : longint); procedure swWriteToStream(aFinalBlock : boolean); public

constructor Create(aStream : TStream;
aCompressing : boolean);
destructor Destroy;
override;
{методы, используемые как во время сжатия, так и во время восстановления} procedure Clear;
{методы, используемые во время сжатия) procedure Advance(aCount : integer);
function Compare(aOffset : longint;
var aDistance : integer) : integer;
procedure GetNextSignature(var aMS : TtdLZSignature;
varaOffset : longint); {методы, используемые во время восстановления) procedure AddChar(aCh : AnsiChar);
procedureAddCode(aDistance : integer;
aLength : integer);
property Name : TtdNameString read FName write FName;
end;
constructor TtdLZSlidingWindow.Create(aStream : TStream;
aCompressing : boolean);
begin inherited Create; {сохранить параметры) FCompressing := aCompressing;
FStream : = aStream;
{установить размер скользящего окна: согласно принятого определения размер скользящего окна равен 8192 байтам плюс 10 байтов для упреждающего просмотра)
swSetCapacity(tdcLZSlidingWindowSize + tdcLZLookAheadSize) ;
{сбросить буфер и, если выполняется сжатие, считать определенные данные из сжимаемого потока) Clear;
if aCompressing then swReadFromStream;
end;
destructor TtdLZSlidingWindow.Destroy;
begin
if Assigned(FBuffer) then begin
{завершить запись в выходной поток, если выполняется сжатие) if not FCompressing then swWriteToStream(true); {освободить буфер)
FreeMem(FBuffer, FBufferEnd - FBuffer) ;
end;
inherited Destroy;
end;
procedure TtdLZSlidingWindow.AddChar(aCh : AnsiChar);
begin
{добавить символ в буфер) FCurrentA :=aCh;
{сместить скользящее окно на один символ) swAdvanceAfterAdd(1);
end;
procedure TtdLZSlidingWindow.AddCode(aDistance : integer;
aLength : integer); var
FromChar : PAnsiChar;
ToChar : PAnsiChar;
i : integer;
begin
{установить указатели для выполнения копирования данных; обратите внимание, что в данном случае нельзя использовать процедуру Move, поскольку часть копируемых данных может быть определена реальным копированием данных)
FromChar := FCurrent - aDistance;
ToChar := FCurrent;
for i : = 1 to aLength do begin ToChar* := FromChar*; inc(FromChar);
inc(ToChar);
end;
{сместить начало скользящего окна) swAdvanceAfterAdd(aLength) ;
end;
procedure TtdLZSlidingWindow.swAdvanceAfterAdd(aCount : integer);
begin
{при необходимости сместить начало скользящего окна) if ( (FCurrent - FStart) >= tdcLZSlidingWindowSize) then begin
inc(FStart, aCount);
inc(FStartOffset, aCount);
end;
{сместить текущий указатель)
inc(FCurrent, aCount);
{проверить смещение в зону переполнения)
if (FStart >= FMidPoint) then begin
{записать дополнительные данные в поток (от позиции FBuffer до позиции FStart)}
swWriteToStream(false);
{переместить текущие данные обратно в начало буфера) Move(FStart*, FBuffer*, FCurrent - FStart ) ; {сбросить различные указатели) dec(FCurrent, FStart - FBuffer);
FStart := FBuffer;
end;
end;
procedure TtdLZSlidingWindow. swSetCapacity(aValue : longint); var
NewQueue : PAnsiChar;
begin
{округлить запрошенный объем до ближайшего значения, кратного 64 байтам) aValue := (aValue + 63) and $7FFFFFC0; {распределить новый буфер) GetMem(NewQueue, aValue * 2);
{уничтожить старый буфер} if ( FBuffer о nil ) then
FreeMem(FBuffer, FBufferEnd - FBuffer) ; {установить начальный/конечный и другие указатели} FBuffer := NewQueue;
FStart := NewQueue;
FCurrent := NewQueue;
FLookAheadEnd := NewQueue;
FBuf ferEnd := NewQueue + (aValue * 2) ; FMidPoint := NewQueue + aValue;
end;
procedure TtdLZSlidingWindow.swWriteToStream(aFinalBlock : boolean); var
BytesToWrite : longint;
begin
{записать данные перед текущим скользящим окном} if aFinalBlock then
BytesToWrite := FCurrent - Fbuffer else
BytesToWrite := FStart - FBuffer;
FStream.WriteBuffer(FBufferA, BytesToWrite);
end;

Метод AddChar добавляет одиночный литеральный символ в скользящее окно и сдвигает это окно вперед на один байт. Внутренний метод swAdvanceAfterAdd выполняет реальный сдвиг и после сдвига окна проверяет, может ли еще один блок быть записан в выходной поток. Метод AddCode добавляет пару расстояние/длина в скользящее окно, по одному копируя символы из уже декодированной части скользящего окна в текущую позицию. Затем скользящее окно сдвигается вперед.

Теперь достаточно легко создать код восстановления. (Создавать код восстановления раньше кода сжатия кажется несколько неестественным, но в действительности формат сжатых данных настолько определен, что это можно сделать. Кроме того, это проще!) Мы реализуем основной цикл в виде машины состояний с тремя состояниями: считывание и обработка байта флага, считывание и обработка символа и, наконец, считывание и обработка кода расстояния/длины. Код показан в листинге 11.24. Обратите внимание, что определение момента завершения восстановления осуществляется по количеству байтов в несжатом потоке, записанному программой сжатия в начало сжатого потока.

После проверки того, что входной поток является закодированным с применением алгоритма LZ77, программа считывает количество несжатых данных. Затем осуществляется вход в простую машину состояний, состояния которой определяются байтом флага, считываемого из входного потока. Если текущее состояние -dsGetFlagByte, программа считывает из входного потока следующий байт флага. Если состояние - dsGetChar, программа считывает из входного потока литеральный символ и добавляет его в скользящее окно. В противном случае состоянием будет dsGetDistLen, и программа считывает из входного потока пару расстояние/ длина и добавляет ее в скользящее окно. Этот процесс продолжается до тех пор, пока не будут восстановлены все данные входного потока.

Листинг 11.24. Основной код программы сжатия, использующей алгоритм LZ77

procedure TDLZDecompress (alnStream, aOutStream : TStream); type TDecodeState = (dsGetFlagByte, dsGetChar, dsGetDistLen); var
SlideWin : TtdLZSlidingWindow;
BytesUnpacked : longint;
TotalSize : longint;
LongValue : longint;
Decodestäte : TDecodeState;
FlagByte : byte;
FlagMask : byte;
NextChar : AnsiChar;
NextDistLen : longint;
CodeCount : integer;
Len : integer;
begin
SlideWin := TtdLZSlidingWindow.Create(aOutStream, false); try
SlideWin.Name := 'LZ77 Decompress sliding window';
{считать из потока заголовок: символы 'TDLZ', за которыми следует размер входного потока) alnStream.ReadBuffer(LongValue, sizeof(LongValue));
if (LongValue о TDLZHeader) then
RaiseError(tdeLZBadEncodedStream, 1TDLZDecompress');
alnStream.ReadBuffer(TotalSize, sizeof(TotalSize)); {подготовиться к восстановлению) BytesUnpacked := 0; NextDistLen := 0; Decodestäte := dsGetFlagByte;
CodeCount := 0; FlagMask := 1;
{до тех nop, пока остаются байты для восстановления. ..} while (BytesUnpacked <
TotalSize) do begin
{считывать следующий элемент в данном состоянии декодирования) case Decodes täte of dsGetFlagByte : begin
alnStream.ReadBuffer(FlagByte, 1);
CodeCount := 0; FlagMask := 1;
end;
dsGetChar : begin
aInStream.ReadBuffer(NextChar/ 1) ;
SlideWin.AddChar(NextChar);
inc(BytesUnpacked);
end;
dsGetDistLen : begin
aInStream.ReadBuffer(NextDistLen, 2) ;
Len := (NextDistLen and tdcLZLengthMask) + 3;
SlideWin.AddCode( (NextDistLen shr tdcLZDistanceShift) + 1, Len) ; inc(BytesUnpacked, Len);
end;
end;
{вычислить следующее состояние декодирования)
inc(CodeCount);
if (CodeCount > 8) then
DecodeState : = dsGetFlagByte else begin
if ((FlagByte and FlagMask) « 0) then DecodeState : = dsGetChar
else
DecodeState := dsGetDistLen;
FlagMask := FlagMask shl 1; ends-end;
finally
SlideWin.Free;
end; {try.. finally) end;

Особенности кодирования литеральных символов и пар расстояние/длина || Оглавление || Сжатие LZ77


Фундаментальные алгоритмы и структуры данных в Delphi



Новости за месяц

  • Июль
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс