Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Модификация дерева

Основная идея заключается в проверке дерева при появлении каждого нового входного символа. Если дерево не является деревом Хаффмана, его следует подправить. Рис. 1.15 дает представление о том, как это делается. Дерево на рис. 1.15а содержит пять символов А, В, С, D и Е. Для всех символов указаны их текущие частоты (в круглых скобках). Свойство Хаффмана означает, что при изучении дерева по всем уровням слева направо и снизу вверх (от листьев к корню) частоты будут упорядочены по возрастанию (неубыванию). Таким образом, нижний левый узел (А) имеет наименьшую частоту, а верхний правый (корень) имеет наибольшую частоту. Это свойство принято называть свойством соперничества.

Причина этого свойства заключается в том, что символы с большими частотами должны иметь более короткие коды и, следовательно, находиться на дереве на более высоком уровне. Требование для частот быть упорядоченными на одном уровне устанавливается для определенности. В принципе, без него можно обойтись, но оно упрощает процесс построения дерева.

Приведем последовательность операций при модификации дерева. Цикл начинается в текущем узле (соответствующем новому входному символу). Этот узел будет листом, который мы обозначим X, а его частота пусть будет F. На каждой следующей итерации цикла требуется сделать три действия:

1. сравнить X с его ближайшими соседями на дереве (справа и сверху). Если непосредственный сосед имеет частоту F + 1 или выше, то узлы остаются упорядоченными и ничего делать не надо. В противном случае, некоторый сосед имеет такую же или меньшую частоту, чем X. В этом случае следует поменять местами X и последний узел в этой группе (за исключением того, что X не надо менять с его родителем);

2. увеличить частоту X с F до F +1. Увеличить на единицу частоту всех его родителей;

3. если X является корнем, то цикл останавливается; в противном случае он повторяется для узла, являющегося родителем X.

На рис. 1.15б показано дерево после увеличения частоты узла А с 1 до 2. Легко проследить, как описанные выше три действия влияют на увеличение частоты всех предков А. Места узлов не меняются в этом простом случае, так как частота узла А не превысила частоту его ближайшего соседа справа В.

На рис. 1.15с показано, что произойдет при следующем увеличении частоты А с 2 до 3. Три узла, следующие за А, а именно, В, С и D, имели частоту 2, поэтому А переставлен с D. После чего частоты всех предков А увеличены на 1, и каждый сравнен со своими соседями, но больше на дереве никого переставлять не надо.

Рис. 1.15d изображает дерево после увеличения частоты А до 4. Поскольку узел А является текущим, его частота (равная пока еще 3) сравнивается с частотой соседа сверху (4), и дерево не меняется. Частота А увеличивается на единицу вместе с частотами всех потомков.

На рис. 1.15е узел А опять является текущим. Его частота (4) равна частоте соседа сверху, поэтому их следует поменять местами.

Это сделано на рис. 1.15f, где частота А уже равна 5. Следующий шаг проверяет родителя А с частотой 10. Его следует переставить с его соседом справа Е, у которого частота 9. В итоге получается конечное дерево, изображенное на рис. 1.15g.