Оптимальное кодирование. Алгоритм Хаффмана

Одно и то же сообщение можно закодировать различными способами. Оптимально закодированным будем считать такой код, при котором на передачу сообщений затрачивается минимальное время. Если на передачу каждого элементарного символа (0 или 1) тратиться одно и то же время, то оптимальным будет такой код, который будет иметь минимально возможную длину.

Метод Хаффмана: буквы алфавита сообщений вписываются в столбец в порядке убывания вероятностей. Две последние буквы объе­диняются в одну вспомогательную букву, которой приписывается сум­марная вероятность. Вероятности букв, не участвовавших в объедине­нии, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце, а две последние буквы объединяются.

Кодирование методом Хаффмана.

В методе Хаффмана кодо­вые слова формируются, начиная с последнего символа.

Шаг 1. Переменной-счетчику t присваиваем значение 1: t:= 1. Рассмат­риваем вспомогательную последовательность символов A_t, полагая на пер­вом шаге a ₁ = А.

Шаг 2. Из последовательности A_t выбираем М символов a_i1,а_i2,..... a_im, которым соответствуют наименьшие вероятности появления

Шаг 3. Для выбранных символов формируются очередные (считая от конца) элементы кодовых слов: в кодовое слово, соответствующее символу a_i, (i= 1, 2,..., М), добавляется символ кодового алфавита b_i.

Шаг 4 Символы a_i1, a_i2,...., a_im объединяются в один вспомогательный

м символ a^t с вероятностью р(а^t) = S p(a_i)

Шаг 5. Из последовательности символов исходного алфавита A_t исклю­чаем символы a_i1, a_i2,...., a_im, вместо них добавляем а^t. Полученную после­довательность обозначим A_t+1.

Шаг 6. Если A_t+1 состоит из одного элемента, то алгоритм заканчивает работу. Иначе t:= t + 1 и переходим к шагу 2.

Процесс продолжается до тех пор, пока все символы исходного алфавита не будут заменены одним вспомогательным символом, которому должна соответствовать вероятность 1.