Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
if (Signature <> TDSplayHeader) then
raise EtdSplayException.Create(FmtLoadStr(tdeSplyBadEncodedStrm,
[UnitName, 'TDSplayDecompress']));
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" и пробел. Текущую ситуацию можно представить следующим образом: