Применение расширения к кодам префикса

Расширяющиеся деревья были впервые описаны в 1983 году и более подpобно рассмотрены в 1985. Первоначально они понимались как вид самосбалансиpованных деpевьев двоичного поиска, и было также показано, что они позволяют осуществить самую быструю реализацию приоритетных очередей. Если узел расширяющегося дерева доступен, то оно является расширенным. Это значит, что доступный узел становится корнем, все узлы слева от него образуют новое левое поддерево, узлы справа — новое правое поддерево. Расширение достигается при обходе дерева от старого корня к целевому узлу и совершении пpи этом локальных изменений, поэтому цена расширения пропорциональна длине пройденного пути.

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

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

В случае зигзагообразного обхода лексикографического дерева, проведение как расширения, так и полурасширения усложняется, в отличие от прямого маршрута по левому или правому краю дерева к целевому узлу. Этот простой случай показан на рисунке 2. Воздействие полурасширения на маршруте от корня (узел w) до листа узла A заключается в перемене местами каждой пары внутренних следующих друг за другом узлов, в результате чего длина пути от корня до узла-листа сокращается в 2 раза. В процессе полурасширения узлы каждой пары, более далекие от корня, включаются в новый путь (узлы x и z), а более близкие из него исключаются (узлы w и y).

Сохранение операцией полурасширения лексикографического порядка в деревьях кода префикса не является обязательным. Единственно важным в операциях с кодом префикса является точное соответствие дерева, используемого процедурой сжатия дереву, используемому процедурой развертывания. Любое его изменение, допущенное между последовательно идущими буквами, производится только в том случае, если обе процедуры осуществляют одинаковые изменения в одинаковом порядке. Hенужность поддержки лексикографического порядка значительно упрощает проведение операции полурасширения за счет исключения случая зигзага. Это может быть сделано проверкой узлов на пути от корня к целевому листу и переменой местами правых наследников с их братьями. Назовем это ПОВОРОТОМ дерева. Тепеpь новый код префикса для целевого листа будет состоять из одних нулей, поскольку он стал самым левым листом. На рисунке 3 дерево было повернуто вокруг листа C. Эта операция не нарушает никаких ограничений представления полурасширения.

Второе упрощение возникает, когда мы обнаруживаем, что можем по желанию менять между собой не только наследников одного узла, но и все внутренние узлы дерева кодов префиксов, поскольку они анонимны и не несут информации. Это позволяет заменить используемую в полурасширении операцию обоpота на операцию, требующую обмена только между двумя звеньями в цепи, которую будем называть ПОЛУОБОРОТОМ. Она показано на рисунке 4. Эта операция оказывает такое же влияние на длину пути от каждого листа до корня, как и полный обоpот, но уничтожает лексикографический порядок, выполняя в нашем примере отсечение и пересадку всего двух ветвей на дереве, в то время как полный обоpот осуществляет отсечение и пересадку 4 ветвей.

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

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