Построение кода Хаффмана для произвольного алфавита.
Процедура Хаффмана.
В большинстве случаев
.
Процедура Хаффмана оптимальна в том смысле, что не существует никакого другого множества кодовых слов, которое обеспечивало меньшую среднюю длину кодового слова.
-ое
первоначальное множество упорядочиваем
в порядке убывания вероятностей.
Находим наименьшее
,
которое удовлетворяет 2-м условиям 
.
-
Группируем вместе j сообщений -го множества, имеющие наименьшие вероятности и вычисляем общую вероятность такой группы.
-
Строим
вспомогательное множество сообщений,
в котором группа из j
сообщений
рассматривается как отдельное сообщение
с вероятностью 
. -
Мощность
множества = 1 ?
Да 
)
нет
)
и
возвращаемся к блоку 2.
-
Сообщения заданного множества рассматриваются как концевые узлы кодового дерева. Кодовые слова формируем путем приписывания различных символов алфавита ветвям, исходящим из каждого промежуточного узла.
Пример.
|
|
|
Код |
|
|
0,41 |
1 |
|
|
0,16 |
001 |
|
|
0,14 |
010 |
|
|
0,12 |
011 |
|
|
0,06 |
0001 |
|
|
0,05 |
00001 |
|
|
0,04 |
000000 |
|
|
0,02 |
000001 |
