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 слов). Следовательно, независимо от реальной длины слова в текстовом файле, оно замещалось бы тремя байтами. Понятно, что сжатие коротких слов, таких как "в", "из", "на" и тому подобных, приводило бы к увеличению размера сжатых данных, а не к уменьшению, однако большинство слов содержит три и больше букв. Поэтому, как правило, общий размер сжатого файла должен быть меньше размера исходного файла.
В основе алгоритма, разработанного Зивом и Лемпелем, лежит сжатие с использованием строк словаря. Однако вместо того, чтобы использовать статический, заранее сгенерированный словарь, предложенный ими алгоритм генерирует словарь "на лету", на основе данных, которые программа сжатия уже встретила во входном файле. А вместо использования номеров страниц и слов они предложили выводить значения расстояния и длины. Работа алгоритма выполняется следующим образом: в ходе считывания входного файла предпринимается попытка сопоставить набор символов в текущей позиции с чем-либо уже встречавшимся во входном файле. При обнаружении совпадения вычисляется расстояние совпадающей строки от текущей позиции и количество совпадающих байтов (длина). В случае обнаружения нескольких совпадений выбирается самое длинное из них.
Рассмотрим краткий пример. Предположим, что мы выполняем сжатие предложения:
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>. Уверен, что читатели без труда смогут выполнить декодирование, используя описанный буфер.