6.3.2. Алгоритм Лемпела-Зива

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

Словом в этом алгоритме называется последовательность символов (не обязательно совпадающая со словом естественного языка). Слова хранятся в

словаре, а их вхождения в исходные данные заменяются адресами (номерами) слов в словаре. Некоторые разновидности алгоритма хранят отдельно словарь и отдельно упакованные данные в виде последовательности номеров слов. Дру-

тый файл может состоять из записей вида [a,l,t], где a – адрес (номер позиции), с которой начинается такая же строка длины l, что и текущая строка. Если a>0, то запись считается ссылкой на словарь и поле t (текст) в ней – пустое. Если a =

0, то в поле t записаны l символов, которые до сих пор в такой последователь-

ности не встречались.

Алгоритм сжатия заключается в постоянном поиске в уже упакованной части данных максимальной последовательности символов, совпадающей с по- следовательностью, начинающейся с текущей позиции. Если такая последова- тельность (длины > 3) найдена, в результат записывается ее адрес и длина. Иначе в результат записывается 0, длина последовательности и сама (несжатая) последовательность.

6.3.3. Кодирование Шеннона-Фано

Методы эффективного кодирования сообщений для передачи по дискрет- ному каналу без помех, предложенные Шенноном и Фано, заложили основу статистических методов сжатия данных. Код Шеннона-Фано строится следую- щим образом: символы алфавита выписывают в таблицу в порядке убывания вероятностей. Затем их разделяют на две группы так, чтобы суммы вероятно- стей в каждой из групп были максимально близки (по возможности, равны). В кодах всех символов верхней группы первый бит устанавливается равным 0, в нижней группы – 1. Затем каждую из групп разбивают на две подгруппы с оди- наковыми суммами вероятностей, и процесс назначения битов кода продолжа- ется по аналогии с первым шагом. Кодирование завершается, когда в каждой группе останется по одному символу.

Качество кодирования по Шеннону-Фано сильно зависит от выбора раз- биений на подгруппы: чем больше разность сумм вероятностей подгрупп, тем более избыточным оказывается код. Для дальнейшего уменьшения избыточно- сти, используют кодирование крупными блоками – в качестве “символов” ис- пользуются комбинации исходных символов сообщения, но и этот подход име- ет те же ограничения. От указанного недостатка свободна методика кодирова- ния Хаффмана.

6.3.4. Алгоритм Хаффмана

Алгоритм Хаффмана гарантирует однозначное построение кода с наи- меньшим для данного распределения вероятностей средним числом символов кода на символ сообщения. На первом шаге подсчитываются частоты всех сим- волов в исходных данных. На втором шаге строятся новые коды (битовые по- следовательности) для каждого символа, так, чтобы никакие две разные после- довательности не имели общего начала, например, три последовательности 0,

10, 110. удовлетворяют этому требованию. Хаффман предложил строить дво- ичное дерево символов, в корне которого находится наиболее частый символ, на расстоянии 1 от корня – следующие по частоте символы, и так далее. На ос- нове такого дерева коды для символов получаются путем выполнения простой

процедуры обхода дерева. Код представляет собой путь от корня до символа, в котором 1 означает переход по левой ветви, а 0 – по правой. Такой способ по- строения гарантирует нужное свойство кодов. Наконец, на последнем шаге в выходные данные записывается построенное дерево, а за ним следуют закоди- рованные данные.

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