Использование алгоритма расширяющегося префикса для кодирования и схожих пpоцессов

Как было первоначально описано, расширение применяется к деревьям, хранящим данные во внутренних узлах, а не в листьях. Деревья же кодов префикса несут все свои данные только в листьях. Существует, однако, вариант расширения, называемый полурасширением, который применим для дерева кодов префикса. При нем целевой узел не перемещается в корень и модификация его наследников не производится, взамен путь от корня до цели просто уменьшается вдвое. Полурасширение достигает тех же теоретических границ в пределах постоянного коэффициента, что и расширение. В случае зигзагообразного обхода лексикографического дерева, проведение как расширения, так и полурасширения усложняется, в отличие от прямого маршрута по левому или правому краю дерева к целевому узлу ( случаи зигзага рассмотрены в [8], [9] ). Этот простой случай показан на рисунке 2. Воздействие полурасширения на маршруте от корня ( узел w ) до листа узла A заключается в перемене местами каждой пары внутренних следующих друг за другом узлов, в результате чего длина пути от корня до узла-листа сокращается в 2 раза. В процессе полурасширения узлы каждой пары, более далекие от корня, включаются в новый путь ( узлы x и z ), а более близкие из него исключаются ( узлы w и y ). 0 0 0 0 . 0 0 A --------o---------o--------o---------o . A --------o-----------o z| y| x| w| . z| x| |1 |1 |1 |1 . |1 |1 | | | | . 0 | 0 | B C D E . B --------o D -------o . y| w| | . |1 |1 ||||||||> . | | . C E Рисунок 2: Полурасширение вокруг самого левого листа дерева кодов Сохранение операцией полурасширения лексикографического порядка в дерева кода префикса не является обязательным. Единственно важным в операциях с кодом префикса является точное соответствие дерева, используемого процедурой сжатия дереву, используемому процедурой развертывания. Любое его изменение, допущенное между последовательно идущими буквами, производится только в том случае, если обе процедуры осуществляют одинаковые изменения в одинаковом порядке. Hенужность поддержки лексикографического порядка значительно упрощает проведение операции полурасширения за счет исключения случая зигзага. Это может быть сделано проверкой узлов на пути от корня к целевому листу и переменой местами правых наследников с их братьями. Назовем это ПОВОРОТОМ дерева. Тепеpь новый код префикса для целевого листа будет состоять из одних нулей, поскольку он стал самым левым листом. На рисунке 3 дерево было повернуто вокруг листа C. Эта операция не нарушает никаких ограничений представления полурасширения. Доказательство этого просто выводится из потенциальной функции, приведенной в [9] для доказательства независимости ограничений представления от порядка следования поддеревьев узла. 0 0 . 0 0 0 0 A ----------o----------o . C ----------o----------o----------o----------o x| w| . z| y| x| w| |1 |1 . |1 |1 |1 |1 0 | | . | | | | B ----------o E . D B A E y| =====> |1 . 0 | . C ----------o . z| . |1 . | . D . Рисунок 3: Поворот вокруг C исключает необходимость зигзагообразного полурасширения Второе упрощение возникает, когда мы обнаруживаем, что можем по желанию менять между собой не только наследников одного узла, но и все внутренние узлы дерева кодов префиксов, поскольку они анонимны и не несут информации. Это позволяет заменить используемую в полурасширении операцию обоpота на операцию, требующую обмена только между двумя звеньями в цепи, которую будем называть ПОЛУОБОРОТОМ. Она показано на рисунке 4. Эта операция оказывает такое же влияние на длину пути от каждого листа до корня, как и полный обоpот, но уничтожает лексикографический порядок, выполняя в нашем примере отсечение и пересадку всего двух ветвей на дереве, в то время как полный обоpот осуществляет отсечение и пересадку 4 ветвей. 0 0 0 0 A ------ -----o------------o C ------------o------------o x| w| x| w| |1 |1 |1 |1 | =====> | | | | | | | | | | B C B A Рисунок 4: Полуобоpот вокруг A Настоящей необходимости поворачивать дерево перед операцией полурасширения нет. Вместо этого полурасширение может быть применено к маршруту от корня к целевой вершине как к самому левому пути. Например, дерево на рисунке 3 может быть расширено напрямую как показано на рисунке 5. В этом примере дерево полурасширяется вокруг листа C, используя полуобоpот для каждой пары внутренних узлов на пути от C к корню. Обратите внимание, что в результате этой перемены каждый лист располагается на одинаковом расстоянии от корня, как если бы деpево было сначала повернуто так, что C был самым левым листом, а затем полурасширено обычным путем. Итоговое дерево отличается только метками внутренних узлов и переменой местами наследников некоторых из них. Необходимо отметить, что существуют два пути полурасширения дерева вокруг узла, различающиеся между собой четной или нечетной длиной пути от корня к листу. В случае нечетной длины узел на этом пути не имеет пары для участия в обоpоте или полуобоpоте. Поэтому, если пары строятся снизу вверх, то будет пропущен корень, если наоборот, то последний внутренний узел. Представленная здесь реализация ориентирована на подход сверху-вниз. 0 0 . 0 0 A ----------o-----------o . A ----------o--------------o x| w| . x| w| |1 |1 . |1 |1 | . | | 0 | | . | 0 | B ----------o E . E C ---------o y| ===> y| |1 . |1 | . | 0 | . 0 | C ----------o . B ---------o z| . z| . |1 |1 . | | . | D . D Рисунок 5: Полурасширение вокруг C с использованием полуобоpота Алгоритм расширяемого префикса Представленная здесь программа написана по правилам языка Паскаль с выражениями, имеющими постоянное значение и подставляемыми в качестве констант для повышения читаемости программы. Структуры данных, используемые в примере, реализованы на основе массивов, даже если логическая структура могла быть более ясной при использовании записей и ссылок. Это соответствует форме представления из ранних работ по этой же тематике [5,10], а также позволяет осуществлять и простое решение в более старых, но широко используемых языках, таких как Фортран, и компактное представление указателей. Каждый внутренний узел в дереве кодов должен иметь доступ к двум своим наследникам и к своему родителю. Самый простой способ для этого - использовать для каждого узла 3 указателя: влево, вправо и вверх. Такое представление, обсуждаемое в [9] было реализовано только при помощи двух указателей на узел(2), но при этом компактное хранение их в памяти будет компенсировано возрастанием длительности выполнения программы и запутанностью ее кода. Нам потребуются следующие основные структуры данных:

const
 maxchar = ... { максимальный код символа исходного текста };
 succmax = maxchar + 1;
 twicemax = 2 * maxchar + 1;
 root = 1;
type
 codetype = 0..maxchar {кодовый интервал для символов исходного текста};
 bit = 0..1;
 upindex = 1..maxchar;
 downindex = 1..twicemax;
var
 left,right: array[upindex] of downindex;
 up: array[downindex] of upindex;
Типы upindex и downindex используются для указателей вверх и вниз по дерева кодов. Указатели вниз должны иметь возможность указывать и на листья, и на внутренние узлы, в то время как ссылки вверх указывают только на внутренние узлы. Внутренние узлы будут храниться ниже листьев, поэтому значения индексов между 1 и maxchar включительно будут применены для обозначения ссылок на внутренние узлы, когда как значения индексов между maxchar + 1 и 2 * maxchar + 1 включительно - ссылок на листья. Заметим что корень дерева всегда находится в 1-ой ячейке и имеет неопределенного родителя. Cоотвествующая листу буква может быть найдена вычитанием maxchar + 1 из его индекса.

Отправить комментарий

Проверка
Антиспам проверка
Image CAPTCHA
...