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

Code := ((Distance-1) shl 3) + (Length-3);

А для восстановления значений расстояния и длины потребовалось бы использовать следующий код:

Length := (Code and $7) +3;

Distance := (Code shr 3)+ 1;

Восстановление с применением алгоритма LZ77

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

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

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

– ------+

a cat is | a cat is a cat

– ------+^

и мы вычислили пару значений расстояние/длина <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;{true=сжатию данных}

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

{добавить символ в буфер}

FCurrent^ :=aCh;

{сместить скользящее окно на один символ}

swAdvanceAfterAdd(1);

end;

procedure TtdLZSlidingWindow.AddCode(aDistance : integer;

aLength : integer);

var

FromChar : PAnsiChar;

ToChar : PAnsiChar;

i : integer;

begin

{установить указатели для выполнения копирования данных; обратите внимание, что в данном случае нельзя использовать процедуру Move, поскольку часть копируемых данных может быть определена реальным копированием данных}