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

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)), а текущая позиция обозначена знаком вставки ( ^ ).