Алгоритмы группы KWE

Алгоритмы словарного сжатия Зива-Лемпела появились во второй половине 1970-х годов. Это были так называемые алгоритмы LZ77 и LZ78, разработанные совместно Зивом (Ziv) и Лемпелом (Lempel). В дальнейшем первоначальные схемы подвергались множественным изменениям, в результате чего мы сегодня имеем десятки достаточно самостоятельных алгоритмов и бессчетное количество модификаций.

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

Алгоритм формулируется следующим образом: " если в прошедшем ранее выходном потоке уже встречалась подобная последовательность байт, причем запись о ее длине и смещении от текущей позиции короче чем сама эта последовательность, то в выходной файл записывается ссылка (смещение, длина), а не сама последовательность". Так фраза " КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ" закодируется как " КОЛО(-4, 3)_(-5, 4)О_(-14, 7)ЬНИ".

Например, указатель (7, 2) адресует 7-ой и 8-ой символы исходной строки.

Используя это обозначение, какая строка закодирована следующим образом:

abba(1, 3)(3, 2)(8, 3) – (abbaabbbabab).

Распространенный метод сжатия RLE (англ. Run Length Encoding), который заключается в записи вместо последовательности одинаковых символов одного символа и их количества, является подклассом данного алгоритма. Рассмотрим, например, последовательность " ААААААА". С помощью алгоритма RLE она будет закодирована как " (А, 7)", в то же время ее можно достаточно хорошо сжать и с помощью алгоритма LZ77: " А(-1, 6)". Действительно, степень сжатия именно такой последовательности им хуже (примерно на 30-40%), но сам по себе алгоритм LZ77 более универсален, и может намного лучше обрабатывать последовательности вообще несжимаемые методом RLE.

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

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