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

вершине как к самому левому пути. Например, дерево на рисунке 3 может быть

расширено напрямую как показано на рисунке 5. В этом примере дерево

полурасширяется вокруг листа C, используя полуобоpот для каждой пары внутренних

узлов на пути от C к корню. Нужно обратить внимание на то, что в результате этой

перемены каждый лист располагается на одинаковом расстоянии от корня, как если

бы деpево было сначала повернуто так, что C был самым левым листом, а затем

полурасширено обычным путем. Итоговое дерево отличается только метками

внутренних узлов и переменой местами наследников некоторых из них.

Необходимо отметить, что существуют два пути полурасширения дерева вокруг узла,

различающиеся между собой четной или нечетной длиной пути от корня к листу. В

случае нечетной длины узел на этом пути не имеет пары для участия в обоpоте или

полуобоpоте. Поэтому, если пары строятся снизу вверх, то будет пропущен корень,

если наоборот, то последний внутренний узел. Представленная здесь реализация

ориентирована на подход сверху-вниз.

Алгоритм расширяемого префикса.

Представленная здесь программа написана по правилам языка Паскаль с выражениями,

имеющими постоянное значение и подставляемыми в качестве констант для повышения

читаемости программы. Структуры данных, используемые в примере, реализованы на

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

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

работ по этой же тематике [5,10], а также позволяет осуществлять и простое

решение в более старых, но широко используемых языках, таких как Фортран, и

компактное представление указателей. Каждый внутренний узел в дереве кодов

должен иметь доступ к двум своим наследникам и к своему родителю. Самый простой

способ для этого - использовать для каждого узла 3 указателя: влево, вправо и

вверх. Такое представление, обсуждаемое в [9] было реализовано только при помощи

двух указателей на узел(2), но при этом компактное хранение их в памяти будет

компенсировано возрастанием длительности выполнения программы и запутанностью ее

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