Кодовое дерево (ориентированный граф)

Алгоритм получения кода Хаффмана:

1) символы входного алфавита – список «листьев» в дереве (свободные узлы);

2) выбираем два свободных узла с наименьшими вероятностями;

3) создается узел, для которого вычисляется сумма вероятностей;

4) одной дуге присваивается значение 0, другой – 1;

5) полученные узлы («родители») добавляются в список свободных узлов;

6) шаги 2-5 повторяются до тех пор, пока в списке свободных узлов не останется один узел – это и есть корень.

Проверка элементарна – сумма вероятностей равна единице.

Н =2,171

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