Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Предположим, что имеется обычный словарь какого-либо языка. Каждое встречающееся в данном текстовом файле слово должно быть представлено в словаре. Если бы и программа сжатия, и программа восстановления имели доступ к электронной версии этого словаря, кодирование отдельных слов в текстовом файле можно было бы выполнить путем указания номера страницы и номера слова на этой странице. Вполне можно было считать, что 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.
Особенности кодирования литеральных символов и пар расстояние/длина
В предыдущих разделах ничего не было сказано о небольшом нюансе реализации алгоритма: как в процессе считывания сжатых данных отличить литеральный символ от кода расстояние/длина? В конце концов, не существует никакого принципиального различия между литеральным символом и первым байтом кода пары значений расстояние/длина. Одно возможное решение - вывод одиночного бита флага перед литеральным символом или кодом расстояние/длина. Если бит флага является нулевым, следующий считываемый код будет литеральным символом. Если флаг является единичным, следующий считываемый код будет парой расстояние/длина. Однако применение этого метода привело бы к необходимости вывода одиночных битов, сводя на нет преимущество использования одних только байтов.