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

Работа добавлена: 2018-07-05






Во всех наших рассуждениях по поводу организации деревьев поиска до сих пор исходили из предположения, что частота обращения ко всем вершинам одинакова, т. е. все ключи с одинаковой вероятностью рассматриваются как аргументы поиска. Если нет других, то такое предположение является разумным. Но встречаются ситуации, когда есть информация о вероятности обращения к отдельным ключам. Обычно для таких ситуаций характерно постоянство множества ключей, т. е. в дерево не включаются новые ключи и не исключаются старые. Структура дерева остаётся неизменной  Типичный пример – сканер транслятора, определяющий не относится ли каждое слово исходного текста программы к классу ключевых для данного языка программирования.

Статистические измерения для 100 программ могут дать точную информацию об относительных частотах появления отдельных ключей.

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

Условимся, что корень находится на уровне 1. Тогда средняя длина (среднее значение) пути всего дерева представляет собой сумму всех путей от корня к каждой вершине, умноженной на вероятность обращения к этой вершине.

где h k – уровень вершины k.

Цель – минимизировать среднее значениеl ср.

Пример.

Задано множество ключей {ki}   {1 , 2 , 3}, n = 3, , ,

Количество бинарных деревьев, которые можно построить из n узлов вычисляется по формуле:

Приблизительное равенство верно при n³ 10.

a)                 d)

b)                e)

c)

При данном распределении вероятностей лучшим является вырожденный вариант ( вариант а ).

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

Обнаружение, что данное слово не является зарезервированным, можно считать обращением к некоторой специальной вершине.

Если известна вероятность gj того, что аргумент поиска х находится между двумя ключами k j и k j + 1 , эта информация существенно трансформирует структуру дерева оптимального поиска.

Обобщим задачу: учтём неудачный поиск. Средняя длина пути в этом случае

  - средняя длина пути

            ( * )

Специальная вершина обозначается квадратом и существует для всех пустых поддеревьев. Все эти специальные вершины являются внешними, остальные узлы – внутренними.

hi уровень внутренних вершин, который начинается с 1.

- уровень внешних вершин, который начинается с 0.

Эту среднюю длину путиРназываютценой дерева поиска, т. к. она представляет некоторую меру поиска ожидаемых затрат. Дерево поиска, имеющее минимальную для всех деревьев, заданных множеством ключей {k i} и вероятностямиpiиgj, где будет находиться специальная вершина, называетсяоптимальным деревом.

Вместо вероятностейpiиgj мы будем использовать счётчики частоты обращений. Введём переменныеai– число поисков с аргументом x = ki;

b j - число поисков с аргументом х , лежащим между ключами k j  и   k j + 1.

b 0 –  число поисков с аргументом x < k 1

b n –  число поисков с x > k n

        взвешенная длина пути дерева.

Учитывая, что число возможных конфигураций из n вершин растёт экспоненциально, задача построения оптимального дерева методом перебора является безнадёжной. Воспользуемся принципом: любое поддерево оптимального дерева оптимально. Этот принцип подсказывает вычислительную процедуру, с помощью которой находится всё большие и большие оптимальные поддеревья, таким образом дерево растёт от листьев к корню.

В основе этого алгоритма лежит следующее уравнение

P = P L + W + P R    ,

W – общее количество поисков, вес дерева

P L– взвешенная длина пути левого поддерева

P R – взвешенная длина пути правого поддерева.

Пример.

Р = 8*1 + 5*2 + 3* 3 = 5*1 + 3*2 + 8 + 5 + 3                    P = P L + W

                                                     P L              W

 Пусть теперь T i j   - оптимальное поддерево , состоящее из вершин

k i + 1 ,  k i + 2 ,  … ,  k  jи  частотa i + 1  ,  a i + 2  , … , a j ;

b i  , b i + 1  , … ,  b j

T o n   -  всё дерево

W o n   -  вес всего дерева

P o n      - взвешенный путь всего дерева

W i j   - общее число поисков для этого поддерева

P i j     - взвешенный путь для поддерева ( i j )

0£ i < j£ n

При начальных условиях Wii = bi, 0£ i£ n

T i i имеет только специальные вершины.

P i i= 0, 0£ i£ n

W i j= W i  j – 1 + a j + b j, 0£ i < j£ n

O( n 3 )  -  сложность вычисления P i j.

Алгоритм Гильберта – Мура.

Введём следующие определения:

Дано множество ключей; массив a [i], массив b[ j]. Определить W[ i , j ] , P[ i , j ].

r [ i , j ] – массив для записи значений k (индекс ключа) для поддерева T[ i , j ].

В  r o n будет записан ключ корня всего дерева.

Шаг 1 . Начальная установка:

Для   i = 0 , … , n   установить P [ i , i ] := 0 ; W [ i , i ] := b [ i ] ;

W [ i , j ] := W [ i , j -1 ] + a [ j ] + b [ j ]   при   j = i + 1 , i + 2 , … , n .

Для j = 1 , 2 , … , n    P [ i , j ]¬ W [ j – 1 , j ] и  r [ j – 1 , j ]¬ j

Этим определяются все деревья, состоящие из одного узла.

Шаг 2 .   Цикл по h . Выполнить шаг 3 для  h = 2 , 3 , … , n  и закончить алгоритм.

Шаг 3 .    Цикл по j . К этому моменту найдены оптимальные деревья с менее, чем h узлами.

Этот шаг определяет все оптимальные деревья с n  узлами.

Выполнить шаг 4     при      j = h , h + 1 , … , W.

Шаг 4 . Находятся матрицы    P i j  и   r ij.

Установить i¬ j – h      и   вычислить

r [ i , j ]¬ k ;




Возможно эти работы будут Вам интересны.

1. Антисциентизм. Антисциентистские аргументы

2. Второй способпередачи сеансового ключа заключается в использовании специального трехфазного протокола (предполагается, что отправитель А и получатель В имеют открытые ключи обмена

3. Работа с сервисами на сайте электронного правительства. Технология поиска информации в Интернете

4. Тема:Методика поиска неисправностей элементов БП ПК Цель:Изучить методику и порядок работы при.

5. Организация и поиск информации.Аппаратные средства поиска информации

6. Освоение саморазвивающихся синергетических систем и новые стратегии научного поиска. Нелинейность роста научного знания