Лекция 9. Словарные методы кодирования. Кодирование длин повторений и дифференциальное кодирование. Методы сжатия с потерей информации

Словарные методы кодирования. Метод Лемпела-Зива

Методы Шеннона-Фэно, Хаффмена и арифметическое кодирование называются статистическими методами. Словарные алгоритмы, которые мы кратко рассмотрим, носят более практичный характер.

Практически все словарные методы кодирования пpинадлежат семье алгоритмов из работы Зива и Лемпела, опубликованной в 1977 году. Сущность их состоит в том, что фразы в сжимаемом тексте заменяются указателем на то место, где они в этом тексте уже pанее появлялись.

Это семейство алгоритмов (метод Зива-Лемпела) обозначается как LZ-сжатие. Этот метод быстpо приспосабливается к стpуктуpе текста и кодирует функциональные слова, так как они очень часто в нем появляются. Новые слова и фразы могут формируются из частей ранее встреченных слов.

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

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

Мы рассмотрим лишь одну из наиболее удачных версий данного метода кодирования – алгоритм LZ78.

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

Ключевым для размера получаемых кодов является размер словаря во фразах, потому что каждый код при кодировании по методу LZ78 содержит номер фразы в словаре. Отсюда следует, что эти коды имеют постоянную длину, равную округленному в большую сторону двоичному логарифму размера словаря (это количество бит в байт-коде расширенного ASCII).

Пример. Закодировать по алгоритму LZ78 строку "КРАСНАЯ КРАСКА", используя словарь длиной 16 фраз.

Указатель на любую фразу такого словаря - это число от 0 до 15, для его кодирования достаточно четырех бит.

В последнем примере длина полученного кода равна битам.

В 1984 г. Уэлчем (Welch) путем модификации LZ78 был создан алгоритм LZW, наиболее совершенный из алгоритмов данного семейства.

Пример распаковки данных с помощью алгоритма LZ78

Пусть длина словаря составляет 16 фраз. Коды сжатого сообщения -

Дата добавления: 2014-01-07