Основные отличия от статистических методов. Основные методы

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

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

Тип словаря выбирается в зависимости от того, какие данные мы хотим сжимать и для чего. Словари подразделяются на статические и динамические. Разница их в том, что из динамического словаря можно удалять данные по мере чтения файла, статический же является постоянным.

Допустим, при сжатии программных кодов на Си очевидно, что часто будут встречаться слова cout, int, return и другие. В таком случае удобно пользоваться при сжатии небольшим статическим словарем, состоящим из нужных слов.

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

Активные разработки в области словарных методов принадлежат ученым Абрахаму Лемпелю и Якобу Зиву. В 1970-х годах они разработали основные принципы словарных методов сжатия и основополагающие алгоритмы. Прежде чем перейти к основной теме нашего проекта, кратко рассмотрим их.

LZ77 – принцип «скользящего окна», опубликован, как нетрудно догадаться, в 1977 году. Основная идея алгоритма - это замена повторного вхождения строки ссылкой на одну из предыдущих позиций вхождения. Кодер создает окно для входного файла и двигает его справа налево в виде строки символов, требующих сжатие. Скользящее окно состоит из текущего словаря – уже сжатого текста (буфер поиска) – и текста, который нужно сжать (буфер предпросмотра). Например, предположим, что в строке «колом_колено_колет_в_вены» левая часть «колом_колено_» уже сжата, а «колет_в_вены» ожидает сжатия. Проверяем первый символ «к» и, просматривая левую часть в обратном порядке, находим его в начале слова «колено» - расстояние 7 до конца буфера поиска. Проверяем, нет ли более длинной совпадающей последовательности символов – и видим, что совпадают вслед за символом «к» в обоих буферах еще символы «о», «л» и «е» (длина последовательности – 4 символа). Теперь проверим, нет ли более длинной последовательности. В буфере поиска есть еще символ «к», но там последовательность совпадающих символов меньше – «кол». Декодер выбирает самую длинную последовательность и кодирует символ меткой (7, 4, к). Так кодируется весь текст.

LZ78, опубликованный в 1978 году, в отличие от предыдущего алгоритма, хранит словарь из уже прочитанных фраз. Алгоритм считывает символы сообщения до тех пор, пока накапливаемая подстрока входит целиком в одну из фраз словаря. Как только эта строка перестанет соответствовать хотя бы одной фразе словаря, алгоритм генерирует код, состоящий из индекса строки в словаре, которая до последнего введенного символа содержала входную строку, и символа, нарушившего совпадение. Затем в словарь добавляется введенная подстрока. Например, возьмем строку «топоткопыта» и покажем работу этого алгоритма.

Впоследствии большое количество ученых разрабатывали свои модификации этих алгоритмов. Одним из наиболее популярных является алгоритм LZW.