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

Автор книги: Джулиан Бакнелл

сообщить о нарушении

Текущая страница: 32 (всего у книги 36 страниц)

aInStream.ReadBuffer(Size, sizeof(longint));

{при отсутствии данных для восстановления выйти из подпрограммы}

if (Size = 0) then

Exit;

{подготовиться к восстановлению}

STree := nil;

BitStrm := nil;

try

{создать поток битов}

BitStrm := TtdInputBitStream.Create(aInStream);

BitStrm.Name := 'Splay compressed stream';

{создать скошенное дерево}

STree := TSplayTree.Create;

{восстановить символы входного потока с использованием скошенного дерева}

DoSplayDecompression(BitStrm, aOutStream, STree, Size);

finally

BitStrm.Free;

STree.Free;

end;

end;

В процессе восстановления потока вначале за счет проверки сигнатуры выполняется проверка того, что поток является сжатым с использованием скошенного дерева. Затем мы считываем размер несжатых данных и осуществляем выход из подпрограммы, если он равен нулю.

При наличии данных для восстановления мы создаем входной поток битов, который будет содержать входной поток и скошенное дерево. Затем для выполнения реального декодирования вызывается метод DoSplayDecompression (см. листинг 11.21).

Листинг 11.21. Цикл восстановления скошенного дерева

procedure DoSplayDecompression(aBitStream : TtdInputBitStream;

aOutStream : TStream;

aTree : TSplayTree;

aSize : longint);

var

CharCount : longint;

Ch : byte;

Buffer : PByteArray;

BufEnd : integer;

begin

GetMem(Buffer, SplayBufferSize);

try

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

BufEnd := 0;

CharCount := 0;

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

while (CharCount < aSize) do

begin {считать следующий байт}

Buffer^[BufEnd] := aTree.DecodeByte(aBitStream);

inc(BufEnd);

inc(CharCount);

{записать буфер в случае его заполнения}

if (BufEnd = SplayBufferSize) then begin

aOutStream.WriteBuffer(Buffer^,SplayBufferSize);

BufEnd := 0;

end;

end;

{записать любые оставшиеся в буфере данные}

if (BufEnd <> 0) then

aOutStream.WriteBuffer(Buffer^, BufEnd);

finally

FreeMem(Buffer, SplayBufferSize);

end;

end;

Как и в цикле декодирования дерева Хаффмана, буфер заполняется декодированными байтами с последующей их записью в выходной поток. Реальное декодирование и запись выполняется методом DecodeByte класса скошенного дерева.

Листинг 11.22. Метод TSplayTree.DecodeByte

function TSplayTree.DecodeByte(aBitStream : TtdInputBitStream): byte;

var

NodeInx : integer;

begin

{переместиться вниз по дереву в соответствии с битами потока битов, начиная с корневого узла}

NodeInx := 0;

while NodeInx < 255 do

begin

if not aBitStream.ReadBit then

NodeInx := FTree[NodeInx].hnLeftInx else

NodeInx := FTree[NodeInx].hnRightInx;

end;

{вычислить байт, исходя из значения индекса конечного узла}

Result := NodeInx – 255;

{выполнить скос узла}

stSplay(NodeInx);

end;

Этот метод всего лишь выполняет перемещение вниз по дереву, считывая биты из входного потока битов и осуществляя перемещение по левой или правой связи, в зависимости от того, является ли текущий бит нулевым или единичным. И, наконец, достигнутый узел листа скашивается по направлению к корневому узлу с целью повторения того, что произошло во время сжатия. Одинаковое выполнение скоса во время сжатия и восстановления гарантирует правильность декодирования данных.

Полный код реализации алгоритма сжатия с использованием скошенного дерева можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDSplyCm.pas.

Сжатие с использованием словаря

Вплоть до 1977 года, основные усилия в области исследования алгоритмов сжатия концентрировались вокруг алгоритмов кодирования с минимальной избыточностью, подобных алгоритмам Шеннона-Фано или Хаффмана, и были посвящены либо преобразованию их в динамические (чтобы таблица кодов не являлась частью сжатого файла), либо повышению быстродействия, уменьшению объема используемой памяти или увеличению эффективности. Затем неожиданно два израильских исследователя, Якоб Зив (Jacob Ziv) и Абрахам Лемпель (Abraham Lempel), представили принципиально иной метод сжатия и положили начало исследованиям в совершенно другом направлении. Их основная идея заключалась в кодировании не отдельных символов, а строк символов. Они задались целью использовать словарь ранее встречавшихся в сжимаемом файле фраз для кодирования последующих фраз.

Предположим, что имеется обычный словарь какого-либо языка. Каждое встречающееся в данном текстовом файле слово должно быть представлено в словаре. Если бы и программа сжатия, и программа восстановления имели доступ к электронной версии этого словаря, кодирование отдельных слов в текстовом файле можно было бы выполнить путем указания номера страницы и номера слова на этой странице. Вполне можно было считать, что 2-байтового целочисленного значения окажутся достаточно для хранения номеров страниц (найдется не особенно много словарей, содержащих более 65536 страниц), а байта должно быть достаточно для хранения номера слова на странице (как и в предыдущем случае, обычно на одной странице словаря приводится определение не более 256 слов). Следовательно, независимо от реальной длины слова в текстовом файле, оно замещалось бы тремя байтами. Понятно, что сжатие коротких слов, таких как "в", "из", "на" и тому подобных, приводило бы к увеличению размера сжатых данных, а не к уменьшению, однако большинство слов содержит три и больше букв. Поэтому, как правило, общий размер сжатого файла должен быть меньше размера исходного файла.

Описание сжатия LZ77

В основе алгоритма, разработанного Зивом и Лемпелем, лежит сжатие с использованием строк словаря. Однако вместо того, чтобы использовать статический, заранее сгенерированный словарь, предложенный ими алгоритм генерирует словарь «на лету», на основе данных, которые программа сжатия уже встретила во входном файле. А вместо использования номеров страниц и слов они предложили выводить значения расстояния и длины. Работа алгоритма выполняется следующим образом: в ходе считывания входного файла предпринимается попытка сопоставить набор символов в текущей позиции с чем-либо уже встречавшимся во входном файле. При обнаружении совпадения вычисляется расстояние совпадающей строки от текущей позиции и количество совпадающих байтов (длина). В случае обнаружения нескольких совпадений выбирается самое длинное из них.

Рассмотрим краткий пример. Предположим, что мы выполняем сжатие предложения:

a cat is a cat is a cat

Первый символ "а" не совпадает ни с одной уже встречавшейся строкой (да просто потому, что ни одна строка еще не встречалась!), поэтому мы выводим его в существующем виде в сжатый поток битов. Это же следовало бы сделать с последующим пробелом и символом "с". Следующий символ "а" совпадает с предшествующим символом "а", но на этом соответствие заканчивается. Мы не можем сопоставить никакие другие строки. Примем правило, что прежде чем делать что-нибудь другое, необходимо устанавливать соответствие не менее чем для трех символов. Поэтому мы выводим в выходной поток символ "а", а также символы "t", пробел, "i", "s" и пробел. Текущую ситуацию можно представить следующим образом:

–+

a cat is I a cat is a cat

–+^

где встретившиеся символы заключены в рамку (в программировании такую рамку называют скользящим окном (sliding window)), а текущая позиция обозначена знаком вставки ( ^ ).

Теперь становится действительно интересно. Набор символов "a cat is" в текущей позиции совпадает со строкой, уже встречавшейся ранее. Совпадающая строка начинается за девять символов до текущей позиции, причем совпадают девять символов. Поэтому можно вывести пару значений расстояние/длина, которые в данном случае представлены строкой < 9,9> (или определенной последовательностью битов), в выходной файл, а затем продвинуться на девять символов. Теперь текущее состояние можно представить следующим образом:

–+

a cat is a cat is I a cat

–+^

Но теперь снова набор символов в текущей позиции можно сопоставить с уже встречавшейся строкой. Можно сопоставить пять символов с пятью символами, расположенными либо на 9, либо на 18 символов раньше. Выберем первую возможность, <9,5>. В результате окончательно сжатый поток будет выглядеть следующим образом:

a cat is < 9,9> < 9,5>

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

Первые девять символов в сжатом потоке являются литеральными, поэтому они выводятся в восстановленный поток в существующем виде. Одновременно создается буфер (называемый скользящим окном). На этом этапе буфер выглядит следующим образом:

–+

a cat is I

–+

Следующий код в сжатом потоке – пара расстояние/длина, <9,9>. Это означает, что нужно "вывести девять символов, расположенные в буфере в девяти байтах от его конца". Этими девятью символами являются "a cat is", поэтому они выводятся в восстановленный поток и добавляются в буфер. Иначе говоря, скользящее окно приобретает вид:

–+

a cat is a cat is |

–+

И снова, следующий код в сжатом потоке – пара расстояние/длина, < 9,5>. Уверен, что читатели без труда смогут выполнить декодирование, используя описанный буфер.

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

Между прочим, определение буфера ранее встречавшихся символов как "скользящего окна" означает, что при попытке найти возможное соответствие рассматриваются только n байт. Обычно n равно 4 или 8 Кб (используемый в программе PKZIP алгоритм Deflate (понижения порядка) может использовать скользящее окно размером до 32 Кб). При перемещении текущей позиции вперед скользящее окно перемещается вперед по уже просмотренным данным. Возникает вопрос, зачем это делается? Почему бы не использовать весь ранее просмотренный текст? Ответ на этот вопрос обусловлен общей структурой текста. В общем случае считываемый и записываемый текст подчиняются так называемому правилу локальности ссылок (locality of reference). Это означает, что, как правило, в текстовом файле более вероятно совпадение близко расположенных символов, а не расположенных вдали друг от друга. Например, в романе описываемые действующие лица и места протекания событий обычно группируются в главы или разделы глав. В то же время часто используемые слова и фразы типа "и", "в" и "он сказал" могут встречаться в любом месте романа.

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

Теперь рассмотрим, как выполняется кодирование пары значений расстояние/ длина. До сих пор мы не обращали на это внимание, однако целесообразно сжимать их как можно больше. Если скользящее окно охватывает последние 4 Кб текста, значение расстояния можно закодировать 12 битами (2(^12^) как раз и составляет 4 Кб). Если максимальную длину проверяемых и сопоставляемых строк ограничить 15 символами, это значение можно закодировать 4 битами, а пару расстояние/длина – двумя полными байтами. Можно было бы использовать также окно с размером равным 8 Кб и максимум семь сопоставляемых символов, и при этом длина кода по-прежнему не превышала бы 2 байтов. Сжатый поток можно рассматривать как поток байтов, а не как явно более сложный поток битов, который мы использовали при генерировании кодов минимальной длины. Кроме того, если длину кодов значений расстояние/длина ограничить 2 байтами, можно сжимать строки, содержащие, по меньшей мере, три символа и совпадающие с какими-то уже встречавшимися строками, при этом не обращать внимания на совпадения одного или двух символов, поскольку сжиматься они не будут.

Мы кратко описали суть алгоритма Зива и Лемпеля (Лемпеля-Зива), на который в настоящее время ссылаются как на алгоритм LZ77.

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

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

Общий способ избавления от этого недостатка состоит в применении флага, состоящего из восьми битов, указывающих, чем должны быть следующие восемь кодов. При этом первый бит определяет, чем тип первого кода, следующего за байтом флага, второй бит – второго кода, и так далее для 8 битов и кодов. Затем будет выводиться следующий байт флага. Используя эту схему, можно записывать (и считывать) сжатый поток в виде последовательности байтов.

Аналогичная схема использовалась в программе EXPAND.EXE компании Microsoft, которая применялась в составе M;

DOS и Windows 3.1 (в современных программных продуктах компании Microsoft вместо нее применяются CAB-файлы). Возможно, читатели помнят, что часто файлы на дискетах DOS имели имена наподобие FILENAME *ЕХ_, и программа EXPAND.EXE должна была их распаковывать и подставлять последний символ в расширении восстановленного файла. В версии алгоритма LZ77, применявшейся компанией Microsoft, коды пар значений расстояние/длина всегда имели размер, равный 2 байтам. При этом 12 бит использовались для указания значения расстояния (в действительности в этой версии использовалась циклическая очередь байтов, и значение расстояния представляло собой величину смещения от начала очереди), а остальные 4 бита служили для определения значения длины.

После того, как мы ознакомились с теорией, пора подумать о реализации и сформулировать ряд правил. Мы будем считать, что размер кода пары расстояние/длина будет всегда равен 2 байтам – длине одного слова – причем старшие 13 бит будут использоваться для указания значения расстояния, а 3 младших бита – для определения значения длины. Поскольку для указания значения расстояния используются 13 бит, теоретически можно закодировать расстояния от 0 до 8191 байта. Следовательно, размер скользящего окна составит 8 Кб. Обратите внимание, что при определении расстояния мы никогда не будем использовать значение, равное 0 (в противном случае соответствие устанавливалось бы с текущей позицией). Таким образом, эти 13 бит будут интерпретироваться как значения от 1 до 8192, а не от 0 до 8191, что будет достигаться за счет простого добавления единицы.

Теперь рассмотрим значение длины. Теоретически, тремя битами можно закодировать значения только от 0 до 7. Однако вспомним, что в пары значений расстояние/длина будут преобразовываться только совпадающие строки, состоящие из трех и более символов. Поэтому за счет простого добавления 3 целесообразно интерпретировать 3 бита как значения длины от 3 до 10 байтов.

Следовательно, чтобы преобразовать значение расстояния и длины в значение слова, нужно было бы записать определение, подобное следующему:

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, поскольку часть копируемых данных может быть определена реальным копированием данных}

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;

FBufferEnd := 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(FBuffer^, BytesToWrite);

end;

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

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

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

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

procedure TDLZDecompress(aInStream, aOutStream : TStream);

type

TDecodeState = (dsGetFlagByte, dsGetChar, dsGetDistLen);

var

SlideWin : TtdLZSlidingWindow;

BytesUnpacked : longint;

TotalSize : longint;

LongValue : longint;

DecodeState : 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', за которыми следует размер входного потока}

aInStream.ReadBuffer(LongValue, sizeof(LongValue));

if (LongValue <> TDLZHeader) then

RaiseError(tdeLZBadEncodedStream, 'TDLZDecompress');

aInStream.ReadBuffer(TotalSize, sizeof(TotalSize));

{подготовиться к восстановлению}

BytesUnpacked := 0;

NextDistLen := 0;

DecodeState := dsGetFlagByte;

CodeCount := 0;

FlagMask := 1;

{до тех nop, пока остаются байты для восстановления...}

while (BytesUnpacked < TotalSize) do

begin

{считывать следующий элемент в данном состоянии декодирования}

case DecodeState of

dsGetFlagByte : begin

aInStream.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;

end;

end;

finally

SlideWin.Free;

end;

{try.. finally}

end;

Сжатие LZ77

Теперь пора рассмотреть реализацию сжатия. При этом очень быстро мы сталкиваемся со следующей проблемой: поиском наиболее длинного соответствия между строкой в текущей позиции и предшествующими 8192 байтами. От одного возможного метода – поиска во всем буфере – придется полностью отказаться из-за его слишком низкой эффективности.

В своей первоначальной работе Зив и Лемпель не предложили почти никаких решений. Кое-кто использует дерево бинарного поиска, построенное поверх скользящего окна, для хранения максимальных встречавшихся совпадающих строк (примером может служить реализация, созданная Марком Нельсоном (Mark Nelson) [15]). Однако применение этого метода приводит к возникновению проблем, связанных с тем, что нужно беспокоиться о балансировке дерева и об избавлении от строк, которые должны быть удалены из скользящего окна. Поэтому мы воспользуемся советом, приведенным в онлайновом документе Deflate Compressed

Data Format Specification (Спецификация формата данных, сжатых методом Deflate) (RFC 1951) и применим хеш-таблицу.

Алгоритм выглядит следующим образом: мы просматриваем три символа в текущей позиции – будем называть их сигнатурой (signature). Сигнатура хешируется с применением одного из методов, а затем хеш-значение используется для доступа к элементу в хеш-таблице, использующему связывание. Цепочки или связные списки в каждом элементе хеш-таблицы будут состоять из последовательностей элементов, каждый из которых состоит из трехсимвольных сигнатур и значения смещения сигнатуры во входном потоке.

Итак, мы получаем сигнатуру текущей позиции и хешируем ее в связный список, представляющий собой – одну из цепочек в хеш-таблице. Затем мы просматриваем связный список и сравниваем хранящуюся в нем сигнатуру каждого элемента с имеющимися сигнатурами. При обнаружении совпадающей сигнатуры мы переходим в скользящее окно, используя значение смещения элемента, а затем сравниваем символы в скользящем окне с символами в текущей позиции. Мы повторяем этот процесс для каждого элемента в связном списке, совпадающего с данной сигнатурой, и запоминаем наиболее длинное найденное соответствие.