Файл: Технологии программирования (Возникновение теории кодирования).pdf

2.6 Алгоритмы Зива-Лемпеля

К словарным методам сжатия относятся алгоритмы Зива-Лемпеля, основанные на использовании словаря. Они были разработаны Якобом Зивом и Авраамом Лемпелом и опубликованы в 1977 и 1978 годах под названиями LZ77 и LZ78. [6]

2.6.1. Алгоритм LZ77

Основная идея LZ77 состоит в том, что повторные вхождения некоторой подстроки сообщения заменяются ссылкой на ее первое вхождение.

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

Обозначим длину словаря через W, и длину буфера через M. Для эффективности кодирования размер словаря должен быть существенно больше размера буфера.

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

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

Пример

Пусть длина словаря W=5, длина буфера M=3. Закодируем с помощью алгоритма LZ77 сообщение a = abbdcabdcaabdaa .

Процесс кодирования представим в виде следующей таблицы:

Таблица 14

Кодирование алгоритмом LZ77

В начале работы словарь пуст, а буфер содержит начальную подстроку сообщения abb. На первом шаге строится код (1,0,”a”). Так как символы буфера не встречаются в словаре, смещение равно 1 (отсчет ведется с самой правой позиции в словаре, она имеет номер 1, хотя это не принципиально), длина подстроки совпадения равна 0 – это значение второго элемента кода, третий элемент равен “a” – это код очередной буквы после найденной подстроки буфера (например, ASCII-код). После выполнения первого шага скользящее окно смещается вправо на 1 позицию.

На шаге 5 максимальное совпадение начальной подстроки буфера cо словарем равно ab, поэтому смещение равно 5 (это номер самой левой подстроки словаря), длина подстроки равна 2, и следующий после найденной подстроки в буфере – символ d. После выполнения шага 5 скользящее окно смещается вправо на 3 позиции.

На шаге 8, так как символ a последний в сообщении, словарь не используется.

Длину кода можно оценить следующим образом. Длина подстроки не может быть больше длины буфера M, а смещение не может быть больше размера словаря W.

Следовательно, для двоичного кода длины подстроки достаточно
|log2 M| битов, а для двоичного кода смещения достаточно |log2 W| битов.

При использовании ASCII-кода общая длина кода будет равна

N × (|log 2 W| + |log 2 M| + 8 ), где N – число шагов. Сжатие алгоритмом LZ77 достигается за счет шагов, аналогичных шагу 5. Различные модификации алгоритма позволяют увеличить степень сжатия.

К недостаткам алгоритма LZ77 следует отнести следующие:

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

Известны оценки избыточности кодирования LZ77 для источников с конечным числом состояний, приведем одну из них, принадлежащую Х.Морита и К.Кобояши:

R(f₇₇,X)=O|((loglogW)/logW)| при W → ∞

(здесь X – произвольный Марковский источник и W – длина скользящего окна).

2.6.2. Алгоритм LZ78

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

Размер получаемого кода определяется размером словаря, так как каждый код содержит номер строки в словаре.

Пример LZ78

Закодируем с помощью алгоритма LZ78 сообщение
a = abbdcabdcaabdaa . Процесс кодирования представим в виде следующей таблицы:

Таблица 15

Кодирование алгоритмом LZ78

Здесь Str – накапливаемая подстрока, которая целиком соответствует какой-либо фразе из словаря (притом максимальная).

На первом шаге построен код (0, “a”), так как словарь содержит только пустую строку, имеющую номер 0 в словаре, первый элемент в коде равен 0 (пустая строка является подстрокой любой другой строки). В словарь добавляется строка, получающаяся конкатенацией пустой строки и следующего после найденной подстроки символа сообщения. Это строка a, она записывается в словарь с номером 1.

На втором шаге так же, как и на первом, максимальная строка словаря, совпадающая с началом текущей строки сообщения, является пустой. Поэтому формируется код (0, “b”). В словарь под номером 2 добавляется строка b.

На третьем шаге начальная подстрока сообщения длины 1 встречается в словаре под номером 2. Поэтому создается код (2, “d”), в котором первый элемент равен номеру найденной строки в словаре, а второй элемент является кодом следующей буквы. К найденной строке b из словаря приписывается буква d, и строка bd добавляется в словарь.

• рассматриваемом примере наибольший вклад в сжатие сообщения дает шаг 7, поскольку строка совпадения имеет длину 2.

Кодируемое сообщение имеет длину 15. Для сообщения длины 15 словарь может содержать 16 строк, включая пустую строку. Поэтому для записи номера строки в словаре требуется 4 бита. Для записи второго элемента в коде требуется 2 бита, так как алфавит сообщения содержит 4 символа. Для кодирования сообщения потребовалось 8 шагов. Поэтому общая длина кода равна 48 битам.

Алгоритм LZ78 так же, как LZ77, является асимптотически оптимальным для марковских источников с конечным числом состояний.

Известна оценка избыточности для LZ77, полученная С.Савари:

R_n(f₇₈,X) ≤0|(1/log_n)| при n → ∞

где X – произвольный марковский источник и n – длина кодируемого сообщения. Алгоритм LZ78 нашел свое практическое применение только после реализации LZW, предложенной Велчем (Welch) в 1984 г. Некоторые изменения коснулись устройства словаря и формирования кодов. Рассмотрим эти изменения.

В начале производится инициализация словаря всеми возможными односимвольными строками (обычно 256 символами расширенного ASCII-кода). В процессе работы словарь разрастается до своего максимального объема Vmax строк (слов). Обычно объем словаря достигает нескольких десятков тысяч слов. Алгоритм работает практически аналогично алгоритму LZ78: символы сообщения считываются до тех пор, пока накапливаемая подстрока входит целиком в одну из фраз словаря Str. Так как словарь первоначально не пустой, такое слово всегда найдется. Как только эта строка перестанет соответствовать хотя бы одной фразе словаря, генерируется код - индекс строки в словаре, которая до последнего введенного символа содержала входную строку (длина кода равна |logV_max|), а словарь пополняется новым словом: Str + символ S, нарушивший совпадение. И далее алгоритм продолжает свою работу по указанной схеме, начиная с символа S. Таким образом, пропала необходимость передавать один символ в чистом виде (в результате того, что словарь изначально не пустой).

Рассмотрим работу алгоритма на строке колокол:

Таблица 16

Кодирование алгоритмом LZ77. Пример

Str – накапливаемая подстрока, которая целиком соответствует какой-либо фразе из словаря (притом максимальная). Как только появляется символ S, нарушающий совпадение, генерируется Код – индекс слова в словаре.

StrS – строка Str + символ S, на котором и нарушается совпадение накапливаемой подстроки. Словарь пополняется этим новым словом, которому присваивается соответствующий индекс.

Теперь сравним размер исходной строки и закодированной. Для представления кода (а это индекс в словаре) требуется 9 бит, получаем размер закодированной строки = 6*9 = 54 бита. Тогда как размер исходной строки – 8*7 = 56 бит. Как видим, даже на такой короткой последовательности символов достигается сжатие, которое по мере увеличения размера последовательности будет увеличиваться.

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

Чтобы алгоритмы сжатия были эффективными, важна не только степень сжатия информации, но и скорость работы кодера и декодера, поэтому главная проблема – устройство словаря.

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

Еще одна серьезная проблема алгоритмов семейства LZ78 - переполнение словаря: если словарь полностью заполнен, прекращается его обновление и процесс сжатия может быть заметно ухудшен. Отсюда следует вывод - словарь нужно иногда обновлять, но когда и как значительно? Этому вопросу посвящено множество публикаций. Самый простой способ - как только словарь заполнился, его полностью обновляют. Недостаток очевиден - кодирование начинается на пустом месте, как бы сначала, и пока словарь не накопится, сжатие будет незначительным. Поэтому словарь можно обновлять не сразу после его заполнения, а только после того, как степень сжатия начала падать. Еще более сложными являются эвристические методы обновления словарей в зависимости от частоты использования тех или иных слов.