Алгоритм LZ77

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

the brown fox jumped over the brown foxy jumping frog

Алгоритм обрабатывает этот текст слева направо. Вначале каждый символ преобразуется в 9-битовый код, состоящий из двоичной единицы, за которой следует 8-битовое ASCII-представление символа. Во время обработки текста алгоритм ищет повторяющиеся последовательности. Когда встречается повторяющаяся последовательность, алгоритм ищет конец такой последовательности, то есть каждый раз алгоритм отыскивает как можно больше символов. Первой такой последовательностью является the brown fox. Повторяю­щаяся последовательность заменяется указателем на первый экземпляр последо­вательности и длиной этой последовательности. В данном случае последователь­ность the brown fox встречается на 26 позиций раньше и имеет длину 13 символов. Для данного примера рассмотрим два варианта кодирования: 8-битовый указатель и 4-битовая длина или 12-битовый указатель и 6-битовая длина. При этом 2-бито­вый заголовок указывает, который вариант выбран: 00 означает первый вариант, а 01 — второй вариант. Таким образом, второй экземпляр последовательности the brown fox кодируется как <00_b><26_d><13_d> или 00 00011010 1101.

Оставшиеся части сжатого сообщения представляют собой букву у, последова­тельность <00_b><27_d><5_d>, заменяющую последовательность, состоящую из про­бела, за которым следует строка jump, и последовательность символов «ing frog».

На рис. 20.7 иллюстрируется преобразование алгоритма сжатия. Сжатое со­общение состоит из 35 9-битовых символов и двух кодов, то есть всего из 35 • 9 + + 2 • 14 = 343 бит. Таким образом, при 424 бит в несжатом сообщении коэффици­ент сжатия данного метода в этом примере составил 1,24.