РАЗДЕЛ 2
МЕТОДЫ АНАЛИЗА ЦИФРОВЫХ ДЕРЕВЬЕВ.
ПОСТАНОВКА ЗАДАЧИ АНАЛИЗА КЛАССА ДЕРЕВЬЕВ С АДАПТИВНЫМ МНОГОРАЗРЯДНЫМ ВЕТВЛЕНИЕМ
В этом разделе дается краткий обзор существующих методов анализа ожидаемого поведения стандартных цифровых деревьев. Показано, что прямолинейное использование данных методов для анализа адаптивных деревьев приводит к существенным техническим трудностям. Показано также, что анализ отдельных реализаций адаптивных деревьев (таких как LC- деревьев) не достаточен для описания возможностей всего класса таких деревьев. С целью получения такого описания будет предложена обобщенная модель класса случайных адаптивных многоразрядных деревьев, и поставлена задача анализа локализации их достижимых пространственно-временных характеристик.
2.1 Методы анализа цифровых деревьев
Существуют два, принципиально различных подхода к анализу структур данных: анализ наихудшего поведения (worst-case analysis) и анализ ожидаемого поведения (average-case analysis).
При анализе наихудшего поведения задача состоит в нахождении параметров структуры при наиболее неблагоприятном выборе последовательности данных используемых для ее построения. Хорошо известным примером такой ситуации являются случай вырождения бинарного поискового дерева в линейный список. Доступ к ключам в таком списке, очевидно, потребует шагов вместо шагов в сбалансированном дереве ( - общее число ключей).
Следует отметить, что будучи исторически первой попыткой формального изучения свойств программ [51], анализ наихудшего поведения имел колоссальный эффект на развитие алгоритмов и структур данных. Так, многие хорошо-известные структуры типа АВЛ-деревья, В-деревья, В+-деревья и т.п. - были построены с четко поставленной целью - минимизировать наихудшее время доступа к данным.
Вместе с тем, с последующим развитием компьютерных наук, стало ясно что оценки, получаемые с помощью анализа наихудшего поведения структур часто оказываются нереалистичными, и что алгоритмы, построенные для поддержания гарантированного поведения в худшем случае оказываются чересчур громоздкими (трудно-реализуемыми) и/или слишком медленными для решения ряда практических задач.
Анализ ожидаемого поведения алгоритмов представляет собой более новое и интенсивно развивающееся направление в теории программирования. Основы этого направления были заложены Д. Е. Кнутом в классическом 3-х томнике "Искусство программирования для ЭВМ" [50,51], и развиты такими известными учеными как А. В. Анисимов, Р. Сэджевик, Ф. Флажолет, Л. Дэврой, М. Хофри, Г. Продингер, В. Шпанковский и др.
2.1.1 Модели, использующиеся для анализа среднего поведения деревьев
Для получения средних (ожидаемых) величин этих парамеров, задается стохастическая модель источника производящего входные строки .
2.1.1.1 Модель процесса Бернулли. Наиболее простой моделью является модель процесса без памяти (или модель Бернулли). В этой модели символы из входного алфавита возникают независимо друг от друга, так что если - i-й символ, посланный источником, то для любого i: , . Если , источник называется симметричным, иначе - асимметричным.
В настоящей работе наиболее часто будет рассматриваться случай когда входной алфавит бинарный , и когда вероятности появлений цифр "0" и "1" равны , и соответственно.
2.1.1.2 Марковские процессы. В модели Марковского процесса предполагается, что вероятности появлений соседних символов в строках зависят друг от друга. Например, вероятность есть условная вероятность того, что символ появится непосредственно после символа . Для полной характеризации Марковского процесса задается матрица условных вероятностей (или матрица вероятностей переходов) и вектор начальных состояний , удовлетворяющий .
В общем случае, может зависеть от последних r символов. В таких ситуациях говорят, что имеет место Марковский процесс (или Марковская цепь) r-го порядка.
2.1.1.3. -смешанные процессы. С помощью обозначим множество всех возможных значений строк , , являющихся, в свою очередь, сегментами некоторой бесконечной последовательности . Процесс, порождающий такую последовательность, называется -смешанным (-mixed), если существует ограниченная функция , такая что для всех и любых , имеет место
.
Более того, если при этом функция такова что , то процесс называется сильно -смешанным (strongly -mixed) [122].
Помимо рассмотренных выше элементарных видов случайных процессов, особую важность имеют также классы стационарных и эргодических процессов [14,122]. Однако, в силу их общности (т.е. слабости ограничений на их параметры), нахождение результатов справедливых для данных классов процессов, как правило, оказывается очень сложным, и в ряде случаев - невозможным [14].
Как правило, при анализе алгоритмов начинают с простейшей модели - модели Бернулли, и затем пытаются найти обобщенное решение справедливое для Марковских процессов, и т.д. В частности, такая методика показала себя успешной при анализе традиционных цифровых деревьев: формулы их ожидаемой глубины и объема полученные для асимметричных Бернуллиевских процессов, оказались в общем виде справедливыми и для всех перечисленных выше процессов [10,11,80,122].
2.1.2. Основные параметры цифровых деревьев. Основными параметрами цифровых деревьев, построенных над набором из n строк, являются следующие величины:
число внутренних узлов;
число внешних узлов ();
число пустых указателей (т.е. указателей на пустые поддеревья);
общее число указателей в дереве:
; (1)
длина внешнего пути (т.е. сумма длин путей от корневого к внешним узлам);
глубина дерева:
. (2)
Глубина дерева (2) используется для оценки среднего времени успешного поиска в дереве. Для оценки объёма пространства, требуемого для представления дерева в основной памяти компьютера, используется общее число указателей в дереве (1).
В данной работе нас, как правило, будут интересовать средние (или ожидаемые) значения этих параметров при заданной модели