2.1. LZ77 (скользящее окно)

Основная идея этого метода (его еще часто называют методом LZ1, см. [Ziv 77]) состоит в использовании ранее прочитанной части входного файла в качестве словаря. Кодер создает окно для входного файла и двигает его справа налево в виде строки символов, требующих сжатие. Таким образом, метод основан на скользящем окне. Окно разбивается на две части. Часть слева называется буфером поиска. Она будет служить текущим словарем, и в ней всегда содержатся символы, которые недавно поступили и были закодированы. Правая часть окна называется упреждающим буфером, содержащим текст, который будет сейчас закодирован. На практике буфер поиска состоит из нескольких тысяч байт, а длина упреждающего буфера равна нескольким десяткам символов. Вертикальная черта | между символами t и е означает текущее разделение между двумя буферами. Итак, предположим, что текст «sir_sid_eastman_easily_t» уже сжат, а текст «eases_sea_sick_seals» нуждается в сжатии.

sir_sid_eastman_easily_t

eases_sea_sick_seals

Кодер просматривает буфер поиска в обратном порядке (справа налево) и ищет в нем первое появление символа е из упреждающего буфера. Он обнаруживает такой символ в начале слова easily. Значит, е находится (по смещению) на расстоянии 8 от конца буфера поиска. Далее кодер определяет, сколько совпадающих символов следует за этими двумя символами е. В данном случае совпадение по символам eas имеет длину 3. Кодер продолжает поиск, пытаясь найти более длинные совпадающие последовательности. В нашем (лучае имеется еще одна совпадающая последовательность той же длины 3 в слове eastman со смещением 16. Декодер выбирает самую длинную из них, а при совпадении длин - самую удаленную, и готовит метку (16, 3, «е»).

Выбор более удаленной ссылки упрощает кодер. Интересно отметить, что выбор ближайшего совпадения, несмотря на некоторое усложнение программы, также имеет определенные преимущества. При этом выбирается наименьшее смещение. Может показаться, что в этом нет преимущества, поскольку в метке будет предусмотрено достаточно разрядов для хранения самого большого смещения. Однако, можно следовать LZ77 с кодированием Хаффмана или другого статистического кодирования меток, при котором более коротким смещениям присваиваются более короткие коды. Этот метод, предложенный Бернардом Хердом (Bernard Herd), называется LZH. Если получается много коротких смещений, то при LZH достигается большее сжатие.

Следующую идею очень легко усвоить. Декодер не знает, какое именно совпадение выбрал кодер, ближайшее или самое дальнее, но ему это и не надо знать! Декодер просто читает метки и использует смещение для нахождения текстовой строки в буфере поиска. Для него не важно, первое это совпадение или последнее.

В общем случае, метка из LZ77 имеет три поля: смещение, длина и следующий символ в упреждающем буфере (в нашем случае, это будет второе е в слове teases. Эта метка записывается в выходной файл, а окно сдвигается вправо (или входной файл сдвигается влево) на четыре позиции: три позиции для совпадающей последовательности и одна позиция для следующего символа.

… sir

_sid_eastman_easily_tease

s_sea_sick_seals …

…

Если обратный поиск не обнаружил совпадение символов, то записывается метка со смещением 0 и длиной 0. По этой же причине метка будет иметь третью компоненту. Метки с нулевыми смещением и длиной всегда стоят в начале работы, когда буфер поиска пуст или почти пуст. Первые семь шагов кодирования нашего примера приведены ниже.

	sir_sid_eastman_r		(0,0,«s»)
s	ir_sid_eastman_e		(0,0,«i»)
si	r_sid_eastman_ea		(0,0, «r»)
sir	_sid_eastman_eas		(0,0,«_»)
sir_	sid_eastman_easi		(4,2,«d»)
sir_sid	_eastman_easily		(4,1,«e»)
sir_sid_e	astman_easily_te		(0,0,«а»)

Ясно, что метки вида (0,0,...), которые кодируют единичные символы, не обеспечивают хорошее сжатие. Легко оценить их длину. Размер смещения равен , где  - длина буфера поиска. На практике этот буфер имеет длину в несколько сотен байт, поэтому смещение имеет длину 10 - 12 бит. Поле «длина» имеет размер равный , где  - длина упреждающего буфера (в следующем абзаце будет объяснено почему надо вычитать 1). Обычно упреждающий буфер имеет длину нескольких десятков байтов. Поэтому длина этого поля равна нескольким битам. Размер поля «символ», обычно, равен 8 бит, но в общем случае - , где  - размер алфавита. Полный размер метки (0,0,...) одиночного символа равен  бит, что много больше длины 8 «сырого» символа без нулевых элементов кода.

Следующий пример показывает, почему поле «длина» может быть длиннее размера упреждающего буфера:

…Mr…

alf_eastman_easily_grows_alf

alfa_in_his_

garden…

Первый символ а в упреждающем буфере совпадает с 5-ым а буфера поиска. Может показаться, что оба крайних а подходят с длиной совпадения 3, поэтому кодер выберет самый левый символ и создаст метку (28,3,«а»). На самом деле кодер образует метку (3,4,«_»). Строка из четырех символов «alfa» из упреждающего буфера совпадает с тремя символами «alf» буфера поиска и первым символом «а» упреждающего буфера. Причина этого заключается в том, что декодер может обращаться с такой меткой очень естественно безо всяких модификаций. Он начинает с позиции 3 буфера поиска и копирует следующие 4 символа, один за другим, расширяя буфер вправо. Первые 3 символа копируются из старого содержимого буфера, а четвертый является копией первого из этих новых трех. Следующий пример еще более убедителен (хотя он немного надуман):

…

alf_eastman_easily_yells_A

AAAAAAAAAA

AAAAAH…

Кодер создает метку (1,9,«А») для совпадения первых девяти копий символа «А» в упреждающем буфере, включая десятый символ А. Вот почему длина совпадения, в принципе, может быть равна размеру упреждающего буфера минус 1.

Декодер метода LZ77 гораздо проще кодера (то есть, метод LZ77 является асимметричным методом сжатия). Он должен соорудить такой же буфер поиска, как и кодер. Декодер вводит метку, находит совпадение в своем буфере, записывает совпадающие символы и символ из третьего поля в буфер. Этот метод или его модификация хорошо работает, если файл сжимается один раз (или несколько раз), но часто разжимается. Часто используемый архив старых сжатых файлов может служить хорошим примером использования этого алгоритма.

На первый взгляд в описанном методе сжатия не делается никаких предположений относительно входных данных. В частности, не обращается внимание на частоты появления отдельных символов. Однако, немного подумав, видно, что из-за природы скользящего окна метод LZ77 всегда сравнивает упреждающий буфер с недавним содержимым буфера поиска, но не с данными, поступившими очень давно (и которые уже покинули буфер поиска). Следовательно, неявно предполагается, что похожие участки входного файла повторяются близко друг от друга. Данные, удовлетворяющие этому свойству будут хорошо сжиматься.

Базисный метод LZ77 улучшался исследователями и программистами многими способами в течение 80-х и 90-х годов прошлого века. Один возможный путь это использование кодов переменной длины при кодировании полей смещения и длины в метке. Другой путь - увеличение размеров обоих буферов. Увеличение буфера поиска дает возможность искать больше совпадений, но ценой будет служить увеличение времени поиска. Очевидно, большой буфер поиска потребует более изощренной структуры данных для ускорения поиска (см. § 2.4.2). Третье улучшение относится к скользящему окну. Простейший подход заключается в перемещении всего текста влево после каждого совпадения. Более быстрый прием заключается в замене линейного окна на циклическую очередь, в которой скольжение окна делается переустановкой двух указателей (см. § 2.1.1). Еще одно улучшение состоит в добавлении одного бита (флага) в каждую метку, что исключает третье поле (см. § 2.2).