Реферат: Сжатие данных

узла A заключается в перемене местами каждой пары внутренних следующих друг за

другом узлов, в результате чего длина пути от корня до узла-листа сокращается в

2 раза. В процессе полурасширения узлы каждой пары, более далекие от корня,

включаются в новый путь ( узлы x и z ), а более близкие из него

исключаются ( узлы w и y ).

Сохранение операцией полурасширения лексикографического порядка в деревьях кода

префикса не является обязательным. Единственно важным в операциях с кодом

префикса является точное соответствие дерева, используемого процедурой сжатия

дереву, используемому процедурой развертывания. Любое его изменение, допущенное

между последовательно идущими буквами, производится только в том случае, если

обе процедуры осуществляют одинаковые изменения в одинаковом порядке.

Hенужность поддержки лексикографического порядка значительно упрощает проведение

операции полурасширения за счет исключения случая зигзага. Это может быть

сделано проверкой узлов на пути от корня к целевому листу и переменой местами

правых наследников с их братьями. Назовем это ПОВОРОТОМ дерева. Тепеpь новый код

префикса для целевого листа будет состоять из одних нулей, поскольку он стал

самым левым листом. На рисунке 3 дерево было повернуто вокруг листа C. Эта

операция не нарушает никаких ограничений представления полурасширения.

Второе упрощение возникает, когда мы обнаруживаем, что можем по желанию менять

между собой не только наследников одного узла, но и все внутренние узлы дерева

кодов префиксов, поскольку они анонимны и не несут информации. Это позволяет

заменить используемую в полурасширении операцию обоpота на операцию, требующую

обмена только между двумя звеньями в цепи, которую будем называть ПОЛУОБОРОТОМ.

Она показано на рисунке 4. Эта операция оказывает такое же влияние на длину пути

от каждого листа до корня, как и полный обоpот, но уничтожает лексикографический

порядок, выполняя в нашем примере отсечение и пересадку всего двух ветвей на

дереве, в то время как полный обоpот осуществляет отсечение и пересадку 4

ветвей.

Настоящей необходимости поворачивать дерево перед операцией полурасширения нет.