Теория информации |
Конспект лекций |
7. АДАПТИВНЫЕ МЕТОДЫ КОДИРОВАНИЯ
7.2 Адаптивный код Хаффмана
В 1978 г. Р. Галлагер предложил метод кодирования источников с неизвестной или меняющейся статистикой, основанный на коде Хаффмана, и поэтому названный адаптивным кодом Хаффмана.
Адаптивный код Хаффмана используется как составная часть во многих методах сжатия данных. В нем кодирование осуществляется на основе информации, содержащейся в окне длины W . Алгоритм такого кодирования заключается в выполнении следующих действий:
1. В начале кодирования символы, входящие в окно кодируются кодом Хаффмана, который строится для оценочного распределения вероятностей. Оценка вероятностей происходит следующим образом: подсчитываются частоты
появления в окне всех символов исходного алфавита
и вероятности символов исходного алфавита оцениваются на основе значений частот символов в окне
2. Перед кодированием очередной буквы подсчитываются новые частоты появления в окне всех символов исходного алфавита и вероятности символов исходного алфавита оцениваются заново на основе значений частот символов в окне
3. По полученному распределению вероятностей строится код Хаффмана для алфавита A
4. Очередная буква кодируется при помощи построенного кода.
5. Окно передвигается на один символ вправо, вновь подсчитываются частоты встреч в окне букв алфавита, строится новый код для очередного символа, и так далее, пока не будет получен код всего сообщения.
Пример 7.2.1. Рассмотрим пример адаптивного кодирования с помощью метода Хаффмана для алфавита и длины окна W=6 (см. рис. 9).
Рисунок 9 Кодирование адаптивным кодом Хаффмана
Рассмотрим подробно этапы кодирования сообщения.
Перед началом кодирования символы в окне встречаются со следующими частотами . Тогда вероятности символов алфавита A оцениваются так
Построим код Хаффмана для этого распределения вероятностей и закодируем символы, входящие в окно построенным кодом (рис. 10а)
При кодировании буквы (буква находится вне окна) частоты пока не изменились, поэтому кодируем символ
кодовым символом 001.
a)
б)
в)
Рисунок 10 Построение адаптивного кода Хаффмана
Далее передвигаем окно на один символ вправо и снова подсчитываем частоты символов в окне и оцениваем вероятности:
Строим код на основе полученных оценок вероятностного распределения (см. рис. 10 (б)) и кодируем очередной символ другим кодовым словом - 00. В этом случае частота символа а3в окне увеличилась, соответственно уменьшилась длина его кодового слова.
Снова передвигаем окно на один символ вправо, подсчитываем частоты символов в окне и оцениваем вероятности:
Строим код на основе полученных оценок вероятностного распределения (см. рис. 10 (в)) и кодируем очередной символ кодовым словом - 101. Таким образом, сообщение
получаем кодовую последовательность 1 01 1 1 001 000 001 00 101.
Алгоритм на псевдокоде
Адаптивный код Хаффмана
Обозначим
w – окно
mas – массив вероятностей символов и кодовых слов
При декодировании закодированной последовательности необходимо знать начальное распределение частот появления символов в окне. Это позволяет раскодировать символы, входящие в окно и следующий символ. Затем частоты символов пересчитываются и это позволяет раскодировать следующий символ и т.д.