Обзор алгоритмов сжатия без потерь

Алгоритм LZ77

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

В качестве модели данных LZ77 использует “скользящее” по сообщению окно, разделенное на две неравные части. Первая, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, является буфером, содержащим еще не закодированные символы входного потока. Обычно размер окна составляет несколько килобайтов. Буфер намного меньше, обычно не более ста байтов. Алгоритм пытается найти в словаре фрагмент, совпадающий с содержимым буфера.

Рассмотрим работу LZ77 на примере сообщения, приведенного в таблице:

Алгоритм LZ77 выдает коды, состоящие из трех элементов:

• смещение в словаре относительно его начала подстроки, совпадающей с содержимым буфера;
• длина подстроки;
• первый символ в буфере, следующий за подстрокой.

В нашем примере, просматривая словарь, алгоритм обнаружит, что совпадающей подстрокой будет “<МАХ”, в словаре она расположена по смещению 14, имеет длину 4 символа, а следующим символом в буфере является ';'. Таким образом, выходной код будет представлять собой тройку <14, 4, ';'>.

После этого алгоритм сдвигает все содержимое окна на длину совпадающей подстроки +1 символ влево и одновременно втягивает соответствующее количество очередных символов сообщения.

Если совпадение не обнаружено, то алгоритм выдает код <0, 0, первый символ в буфере> и продолжает свою работу. Хотя такое решение неэффективно, оно гарантирует, что алгоритм сможет закодировать любое сообщение.

УПРОЩЕННЫЙ АЛГОРИТМ LZ77

пока (буфер не пуст)
  найти наиболее длинное соответствие (позиция_начала, длина)
  в обработанной_части_сообщения и в буфере;
  если (длина > минимальной_длины ), то
    вывести в кодированные данные пару (позиция _начала, длина);
  иначе
    вывести в кодированные данные первый символ буфера;
  изменить указатель на начало буфера и продолжить.

Декодирование в LZ77 еще проще, так как не нужно осуществлять поиск в словаре.

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

Быстродействие и кодера, и декодера зависит от того, как реализовано “скольжение” окна по содержимому сообщения. Рационально было бы для работы с окном пользоваться кольцевым буфером, организованным на физически сплошном участке памяти, а не реальным сдвигом содержимого окна. Хотя для поддержания кольцевого буфера необходимы дополнительные затраты на сохранение целостности индексов в нем, в целом это дает очень существенный выигрыш потому, что отсутствует постоянное сдвигание большого блока памяти. Если размер кольцевого буфера равен степени двойки, то стандартная для кольцевого буфера операция “смещение по модулю размер”, может быть заменена побитовой логической операцией, что еще больше повышает эффективность.

Помимо проблем с быстродействием, у алгоритма LZ77 возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ. Если словарь имеет длину 4Кб, а буфер — 16 байтов, то код <0, 0, символ> будет занимать 3 байта. Кодирование одного байта в три имеет мало общего со сжатием и существенно понижает производительность алгоритма.