2015-05-20
622
а) Пусть 
– оптимальный префиксный код, 
– префиксный код (по лемме), но пусть он не оптимальный. Тогда существует оптимальный код 
, такой что 
. Среди оптимальных кодов можно найти префиксный код 
, такой что 
.
Пусть 
. Построим код 
, он префиксный, цена кодирования его 
, то есть код 
имеет цену меньше, чем код , что невозможно, так как – оптимальный код.
б) Пусть – оптимальный префиксный код, – префиксный код, но пусть он не оптимальный, тогда существует оптимальный префиксный код 
и 
.
Пусть 
. Так как вероятности упорядочены по невозрастанию, по теореме о возможности построения упорядоченного оптимального кода, можно перестроить код и получить код 
, в котором кодовые слова расположены в порядке неубывания длин и два последних слова отличаются только в последнем разряде:
, 
.
По коду 
можно построить код ,
, то есть мы нашли код, цена кодирования которого меньше, чем у оптимального кода – противоречие.
Следствие. Теорема редукции дает алгоритм построения оптимального кода, который называется кодом Хаффмена.
|
|
|
Пример 8. Построить оптимальный двоичный префиксный код для упорядоченного набора вероятностей 
. Процедура Хаффмена выглядит следующим образом (табл. 26).
Таблица 26
| ||||||
| 0,3 | 0,3 | 0,3 |  
|  
| ||
| 0,3 | 0,3 | 0,3 | ||||
0,2
0,1
| 0,2
| 
| ||||
Для набора вероятностей 
, то есть для двух букв, оптимальным будет код 
. Он играет роль кода из теоремы редукции, тогда код, построенный из для набора вероятностей 
, играет роль кода и будет оптимальным. Повторяя этот процесс, мы получим оптимальный код для исходного набора вероятностей. Для этих «обратных» шагов удобнее строить кодовое дерево (рис. 53).
Рис. 53
На этом примере видно, что хотя шаги 1–4 стандартны, оптимальный код не будет единственным, например, для вероятности 0,6 можно было взять кодовое слово 1, для 0,4 взять 0. На рис. 54 показано другое кодовое дерево для этого же набора вероятностей и соответствующий ему набор кодовых слов 
Рис. 54
