Словарные и словарно-статистические алгоритмы сжатия

Алгоритмы KWE

В основу алгоритмов кодирования по ключевым словам (KWE = Keyword Encoding) положено кодирование лексических единиц исходного документа группами байтов фиксированной длины. Примером лексической единицы может служить слово (последовательность символов, справа и слева ограниченная пробелами или символами конца абзаца). Результат кодирования сводится в таблицу, которая прикладывается к сжатому коду и представляет собой словарь. Обычно для англоязычных текстов принято использовать двухбайтную кодировку слов. Образующиеся при этом пары байтов называют токенами.

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

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

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

Сущность алгоритма сжатия данных LZ состоит в том, что повторяющиеся последовательности символов заменяются указателями на позиции, где они в тексте уже ранее появлялись. Одной из форм такого указателя может быть пара (n,m), которая ссылается на последовательность символов длиной m символов, начинающуюся с позиции n. В большинстве реализаций алгоритма Лепеля-Зива позиция в паре кодируется как смещение (разность) между позициями кодируемой строки и строки, на которую произведена ссылка.

Из-за ограниченного объема оперативной памяти компьютера обычно используется вариант алгоритма Лемпеля-Зива со скользящим окном, когда максимальное значение смещения ограничено некоторым значением.

Сжатие данных происходит следующим образом. В сжатые данные выдаются либо символы сжимаемых данных, либо ссылки на уже просмотренную часть сообщения. Эти ссылки указывают, что текущие символы некоторым количеством m совпадают с теми, что уже были прочитаны, начиная с позиции n. Распаковка начинается сначала сообщения.