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

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). Это означает, что, как правило, в текстовом файле более вероятно совпадение близко расположенных символов, а не расположенных вдали друг от друга. Например, в романе описываемые действующие лица и места протекания событий обычно группируются в главы или разделы глав. В то же время часто используемые слова и фразы типа "и", "в" и "он сказал" могут встречаться в любом месте романа.