Архиватор

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

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

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

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

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

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

1.3.2 Недостатки

Перед тем, как  обсуждать алгоритм LZ78, остановимся  на недостатках метода LZ77 и его  вариантов. Было уже отмечено, что  этот алгоритм основывается на предположении, что похожие образцы сжимаемых  данных находятся близко друг от друга. Если содержимое файла не удовлетворяет  этому условию, то он будет сжиматься  плохо. Простой пример это текст, в котором слово «economy» встречается часто и равномерно распределено по всему тексту. Может случиться, что когда это слово попадает в упреждающий буфер, его предыдущая копия уже вышла из буфера просмотра. Более лучший алгоритм мог бы сохранять часто встречающиеся слова в словаре, а не сдвигал бы их все время.

Другой недостаток метода - это ограниченные размеры  упреждающего буфера. Размер совпадающей  строки лимитирован числом , но  приходится держать маленьким, так как процесс сравнения строк основан на сравнении индивидуальных символов. Если удвоить , то степень сжатия могла бы возрасти, но одновременно с этим произойдет замедление процесса поиска совпадений. Размер  буфера поиска тоже ограничен. Большой буфер поиска мог бы тоже улучшить компрессию, но опять возрастет сложность поиска по дереву, даже двоичному. Увеличение буферов также означает удлинение меток, что сокращает фактор сжатия. Двухбайтовые метки сжимают последовательности из 2-х символов в два байта плюс один флаговый бит. Запись двух байтов кода ASCII в виде этого же кода плюс два флаговых бита дает весьма малую разницу в размере по сравнению с записью метки. Это будет лучший выбор для кодера в смысле экономии времени, а плата всего один лишний бит. Мы будем говорить, что в этом случае кодер имеет 2-х байтовую точку безызбыточности. Для более длинных меток точка безызбыточности вырастает до 3 байтов.  

1.3.3 LZ78

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

Словарь начинает строиться из пустой строки в позиции  нуль. По мере поступления и кодирования  символов, новые строки добавляются  в позиции 1, 2 и т.д. Когда следующий  символ  читается из входного файла, в словаре ищется строка из одного символа . Если такой строки нет, то  добавляется в словарь, а на выход подается метка . Эта метка означает строку «нуль » (соединение нулевой строки и ). Если вхождение символа  обнаружено (скажем, в позиции 37), то читается следующий символ , и в словаре ищется вхождение двухсимвольной строки . Если такое не найдено, то в словарь записывается строка , а на выход подается метка . Такая метка означает строку , так как позицию 37 в словаре занимает символ . Процесс продолжается до конца входного файла.

В общем случае текущий символ читается и становится однобуквенной строкой. Затем кодер  пытается найти ее в словаре. Если строка найдена, читается следующий  символ и присоединяется к текущей  строке, образуя двухбуквенную строку, которую кодер опять пытается найти в словаре. До тех пор  пока такие строки находятся в  словаре, происходит чтение новых символов и их присоединение к текущей  строке. В некоторый момент такой  строки в словаре не оказывается. Тогда кодер добавляет ее в  словарь и строит метку, в первом поле которой стоит указатель  на последнюю найденную в словаре  строку, а во втором поле записан  последний символ строки (на котором  произошел обрыв успешных поисков). В табл. 1.1 показаны шаги при декодировании последовательности «sir_sid_eastman_easily_teases_sea_sick_seals».

Табл. 1.1. Шаги кодирования LZ78.

На каждом шаге строка, добавленная в словарь, совпадает  с кодируемой строкой минус последний  символ. В типичном процессе сжатия словарь начинается с коротких строк, но по мере продвижения по кодируемому  тексту, все более и более длинные  строки добавляются в словарь. Размер словаря может быть фиксированным  или определяться размером доступной  памяти каждый раз, когда запускается  программа сжатия LZ78. Большой словарь  позволяет делать глубокий поиск  длинных совпадений, но ценой этого  служит длина поля указателей (а, значит, и длина метки) и замедление процесса словарного поиска.

Возникающие деревья  относятся к специальному типу деревьев, в которых образование новых  веток и их дальнейшее ветвление  зависит только от части поступающих  новых данных, а не от всех данных. В случае LZ78, новая ветвь соответствует  всего одному новому добавляемому символу.

Поскольку размер дерева ничем не ограничен, может  возникнуть переполнение. На самом  деле, это всегда происходит, за исключением  тех случаев, когда входной файл имеет малый размер. Первоначальный LZ78 метод не устанавливает, что делать в этом случае. Он является, скорее, теоретическим методом, который  удобно исследовать, но трудно использовать на практике. Ниже приводятся некоторые  возможные решения этой проблемы.

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

2. Удалить все  дерево при переполнении и  начать строить новое. Это решение  эффективно разбивает данные  на блоки, и в каждом блоке  используется свой собственный  словарь. Если содержимое сжимаемых  данных меняется от блока к  блоку, то этот метод дает  хорошие результаты, поскольку в  словаре не хранятся строки, которые  с малой вероятностью поступят  в дальнейшем. Здесь опять, как  и в LZ77 неявно предполагается, что похожие данные будут группироваться  близко друг к другу. 

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

Декодер LZ78 работает примерно так же, как и кодер, строя  словарь и оперируя с ним. Поэтому  он более сложен, чем декодер LZ77.

1.3.4 LZW

Это весьма популярный вариант алгоритма LZ78, который был  разработан Терри Уэлчем (Terry Welch) в 1984 ([Welch 84] и [Phillips 92]). Его главной особенностью является удаление второго поля из метки. Метка LZW состоит только из указателя на место в словаре. Для лучшего понимания алгоритма LZW мы временно забудем, что словарь является деревом и будем предполагать, что словарь - это просто массив, состоящий из строк разной длины. Метод LZW начинается инициализацией словаря всеми символами исходного алфавита. В общем случае 8-битного алфавита, первые 256 записей (отдельные символы с номерами от 0 до 255) заносятся в словарь до поступления сжимаемых данных. Поскольку словарь уже частично заполнен, первые поступившие символы всегда будут обнаружены в словаре, поэтому метка может состоять всего лишь из указателя, и нет надобности дополнительно хранить код символа, как в алгоритмах LZ77 и LZ78.

Метод LZW накапливает  поступающие на вход символы в  строке I. После каждого нового символа, добавленного в строку I, кодер ищет I в словаре. Если строка обнаружена, то процесс удлинения I продолжается. В некоторый момент добавление нового символа х приводит к необнаружению строки Iх (символ х был добавлен к I). Тогда кодер (1) записывает в выходной файл указатель в словаре на строку I, (2) сохраняет строку Iх (которая теперь будет называться фразой) в словаре на следующей допустимой позиции и (3) инициализирует (присваивает) строке I новое значение х. Чтобы проиллюстрировать процесс кодирования, мы еще раз воспользуемся последовательностью «alf_eats_alfalf а». Последовательность шагов отображена в табл. 1.2. Кодер выдает на выход файл:

97 (а), 108 (1), 102 (f), 32 (_), 101 (е), 97 (а), 116 (t), 115 (s), 32 (_), 256 (al), 102 (f), 265 (alf), 97 (a),

а в словаре  появляются следующие новые записи: (256: al), (257: lf), (258: f_), (259: _е), (260: ea), (261: at), (262: ts), (263: s_), (264: _a), (265: alf), (266: fa), (267: alfa).