Алгоритм Хаффмена

Пусть имеются распределения вероятностей

p₁ ≥ p₂ ≥… ≥ p_n (1)

причем =1,

Положим p_j =+, поместим p_j в соответствующее место (чтобы условие (1) выполнялось) распределения вероятностей и запомним позицию.

р₁,р₂, …,р_j, …, р_n-2, р_n-3 (2)

Сложим последние две вероятности =+и поместим его в соответствующее место распределения и запомним это место. Получили новое распределение. Здесь складываем последние две вероятности и помещаем в соответствующее место, и так далее, пока не получим две вероятности. Назначаем первой букве код 0, а второй 1. Если первая вероятность является суммой, то исключаем ее из распределения, код ее опускаем на второе и третье место (подняв код второй вероятности на первое место) и приписываем 0 и 1. Новая первая вероятность – сумма? Да. Все нижние вероятности сдвигаем вверх, вместе с кодами, а код являющейся суммой опускаем вниз на две последние строчки, приписав ему ноль в предпоследней строчке и 1 в последней. Если вероятность первой строки не является суммой, то код первой букве назначен, и мы переходим ко второй вероятности. Разбиваем её (если она является суммой) и переносим код вниз с приписыванием 0 и 1. И так до тех пор, пока не исчерпаем все суммы.

Пример.

вероятности

11 12 13 14 15 16 17 18 19

0,25 0,25 0,25 0,25 0,25 0,25 0,290,460,64

0,15 0,15 0,15 0,15 0,220,24 0,25 0,29 0,46

0,12 0,12 0,120,14 0,15 0,22 0,24 025

0,11 0,11 0,12 0,12 0,14 0,15 0,22

0,08 0,11 0,11 0,12 0,12 0,14

0,06 0,08 0,08 0,11 0,11

0,06 0,06 0,06 0,08

0,06 0,06 0,06

0,06 0,06

0,05

В каждом из столбцов подчеркнуты вероятности, являющиеся суммами двух вероятностей. Именно их будем разбивать на соответствующие слагаемые при построении схем оптимального кодирования, в соответствии с теоремой об оптимальном кодировании. Перейдем к назначению кодов. Столбец 19 содержит две вероятности, поэтому оптимальными будут коды длиной 1 (столбец 28).

Коды

28 27 26 25 24 23 22 21

0 1 00 01 01 01 01 01

1 00 01 10 11 11 11 11

01 10 11 000 001 100 100

11 000 001 100 101 0000

001 100 101 0000 0001

101 0000 0001 0010

0001 0010 0011

0011 1010

В первой строке 19 столбца вероятность подчеркнута. Это значит, что она является суммой. Разбиваем ее на два слагаемых и получаем 18 столбец.

Первый код столбца 28 опускаем в две строчки, следующие за последней, и приписываем 0 в одной строке и 1 в другой. Поднимем все строки вверх. Получим коды (столбец 27) для распределения 18 столбца.

В первой строке 18 столбца вероятность подчеркнута. Это значит, что она является суммой. Разбиваем ее на два слагаемых и получаем 17 столбец.

Первый код столбца 27 опускаем в две строчки, следующие за последней, и приписываем 0 в одной строке и 1 в другой. Поднимем все строки вверх. Получим коды (столбец 26) для распределения 17 столбца.

В первой строке 17 столбца вероятность подчеркнута. Это значит, что она является суммой. Разбиваем ее на два слагаемых и получаем 16 столбец.

Первый код столбца 26 опускаем в две строчки, следующие за последней, и приписываем 0 в одной строке и 1 в другой. Поднимем все строки вверх. Получим коды (столбец 25) для распределения 16 столбца.

В 16 столбце подчеркнута вторая вероятность. Это значит, что она является суммой. Разбиваем ее на два слагаемых и получаем 15 столбец.

Первый код столбца 25 уже назначен, поэтому мы его не трогаем, а опускаем второй в две строчки, следующие за последней, и приписываем 0 в одной строке и 1 в другой. Поднимем все строки ниже первой вверх. Получим коды (столбец 24) для распределения 15 столбца. Продолжая в том же духе, получим 21-ый столбец кодов, соответствующих распределению 11 столбца, т.е. исходному распределению.

Дата добавления: 2014-01-06