Декодирование

Пpедположим, что все что декодер знает о тексте, – это конечный интеpвал [0,8030349772 - 0,8030349880]. Декодеру, как и кодеру, известна также таблица распределения выделенных алфавиту интервалов. Он сpазу же понимает, что пеpвый закодиpованный символ есть Р, так как результат кодирования целиком лежит в интеpвале [0.8 - 1), выделенном моделью символу Р согласно таблице .

Тепеpь повтоpим действия кодера:

вначале [0.0 - 1.0);

после пpосмотpа [0.8 - 1.0).

Исключим из результата кодирования влияние теперь уже известного первого символа Р, для этого вычтем из результата кодирования нижнюю границу диапазона, отведенного для Р, – 0,8030349772 – 0.8 = =0,0030349772 – и разделим полученный результат на ширину интервала, отведенного для Р, – 0.2. В результате получим 0,0030349772 / 0,2 = =0,015174886. Это число целиком вмещается в интервал, отведенный для буквы А, – [0 – 0,1) , следовательно, вторым символом декодированной последовательности будет А.

Поскольку теперь мы знаем уже две декодированные буквы - РА, исключим из итогового интервала влияние буквы А. Для этого вычтем из остатка 0,015174886 нижнюю границу для буквы А 0,015174886 – 0.0 = =0,015174886 и разделим результат на ширину интервала, отведенного для буквы А, то есть на 0,1. В результате получим 0,015174886/0,1=0,15174886. Результат лежит в диапазоне, отведенном для буквы Д, следовательно, очередная буква будет Д.

Исключим из результата кодирования влияние буквы Д. Получим (0,15174886 – 0,1)/0,1 = 0,5174886. Результат попадает в интервал, отведенный для буквы И, следовательно, очередной декодированный символ – И, и так далее, пока не декодируем все символы:

Декодируемое Символ Границы Ширина

число на выходе нижняя верхняя интервала

0,8030349772 Р 0.8 1.0 0.2

0,015174886 А 0.0 0.1 0.1

0,15174886 Д 0.1 0.2 0.1

0,5174886 И 0.3 0.6 0.3

0,724962 О 0,7 0,8 0,1

0,24962 В 0,2 0,2 0,1

0,4962 И 0,3 0,6 0,3

0,654 З 0,6 0,7 0,1

0,54 И 0,3 0,6 0,3

0,8 Р 0,6 0,8 0,2

0.0 Конец декодирования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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