26. Дерево оптимального поиска и его построение

 

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

 

 Предположим, что в дереве поиска вероятность обращения  К вершине i такова:

 Pr{x=ki}=pi        (Si:  1 <= i <= n : pi)=1                                                                          (4.56)

 

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

PI=Si: 1 <= i <= n : pi * hi,                                                                                               (4.57)

где hi — уровень вершины i. Наша цель — минимизировать при заданном распределении вероятностей взвешенную длину пути. В качестве примера рассмотрим множество из трех ключей 1,2,3 со следующими вероятностями обращений к ним: р1 = l/7, р2 = = 2/7 и р3 = 4/7. Эти три ключа можно расставить в дереве поиска пятью различными способами (как это показано на рис. 4.36, а-д). Взвешенные длины путей деревьев, вычисленные по формуле (4.57), составят соответственно 11/7. 12/7. 12/7. 15/7 и 17/7- Таким образом, оптимальным оказывается не идеально сбалансированное дерево (рис. 4.36, в), а вырожденное (рис. 4.36, а).

 

Рис. 4.36. Дерево поиска с тремя вершинами

 

Упомянутый сканер транслятора сразу наводит на мысль, что задачу следует ставить при несколько более общих условиях: ведь слова, встречающиеся в исходном тексте, не всегда бывают ключевыми словами, на самом деле эта ситуация скорее исключение, чем правило. Обнаружение, что данный ключ не есть ключ дерева поиска, можно считать обращением к некоторой гипотетической "специальной вершине", включенной между следующей меньшей и следующей большей вершинами (см. рис. 4.19) с соответствующей длиной внешнего пути. Если известна вероятность qi того, что аргумент поиска х находится между двумя ключами ki и ki+1 , то эта информация может существенно трансформировать структуру дерева оптимального поиска. Поэтому мы обобщим задачу и будем учитывать возможность неудачного поиска. Общая средняя взвешенная длина пути в этом случае имеет вид:

 Р = (Si : 1 <= i <= n : pi * hi) + (Sj : 0 <= j <= m: qj * h'j),                                                                                     (4.58)

где

 (Si : 1 <= i <= n : pi) +  (Sj : 0 <= j <= m: qj) = 1

причем hi — уровень внутренней вершины i, a h'j — уровень внешней вершины j. Среднюю взвешенную длину пути можно назвать ценой дерева поиска, поскольку она представляет собой некоторую меру для ожидаемых затрат на поиск. Дерево поиска, имеющее минимальную для всех деревьев с заданным множеством ключей ki и вероятностями рi и qj цену, называется оптимальным деревом.

 

 При построении оптимального дерева мы не будем требовать, чтобы сумма всех р и q равнялась 1 . Ведь обычно эти вероятности определяются экспериментально, подсчетом обращений к вершинам. Поэтому вместо вероятностей рi и qj мы далее будем пользоваться просто "счетчиками" частоты обращений. Обозначим их следующим образом:

ai = число поисков с аргументом х, равным ki

bj = число поисков с аргументом х, лежащим между ki и kj+1.

 

 Условимся, что b0 — число поисков с аргументом х, меньшим k1, а bn — число поисков с х, большим чем kn (рис. 4.37). Далее, вместо средней длины пути мы будем обозначать через Р общую взвешенную длину пути:

Р = (Si : 1 <= i <= n :  ai * hi) + (Sj : 0 <= j <= m: bj *hj)                                                                  (4.59)

 

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

Рис. 4.37.  Дерево поиска с указанием частот обращения

 

 Учитывая, что число возможных конфигураций из n вершин растет экспоненциально с ростом n, задача построения оптимального дерева при больших n кажется совершенно безнадежной. Однако оптимальные деревья обладают одним важным свойством, которое помогает их обнаруживать: все их поддеревья тоже оптимальны. Если, например, дерево на рис. 4.37 оптимально, то поддерево с ключами k3 и k1, как показано, также оптимально. Такая особенность предполагает алгоритм, который систематически находит все большие и большие деревья, начиная с отдельных вершин как наименьших возможных поддеревьев. Таким образом, дерево растет "от листьев к корню", "снизу вверх", если учесть, что мы рисуем деревья сверху вниз [4.7].

 В основе нашего алгоритма лежит уравнение (4.60). Пусть Р — взвешенная длина пути всего дерева, а PL и PR — соответствующие длины для левого и правого поддеревьев его корня.

Ясно, что Р — сумма PL и PR и числа случаев W, когда поиск проходит по единственному пути к корню, т. е. W — просто общее число поисков:

 

P = PL + W + PR                                                                                                                                             (4.60)

 

W = (Si: 1 <= i <= n:ai) + (Sj: 0 <= j <= m: bj)                                                                      (4.61)

 

Назовем W весом дерева. Тогда средняя длина пути будет Р/ W.

 Из этих рассуждений видно, что необходимо ввести обозначения для веса и длины пути любого из поддеревьев, включающего "соседние" ключи. Пусть Тij — оптимальное поддерево, состоящее из вершин с ключами ki+1, ki+2, …, kj. Тогда обозначим его вес через wij, а длину пути — через рij-. Ясно, что Р = р0,n и W= wo,n. Эти величины определяются следующими рекуррентными соотношениями:

wii = bi                                                                                 (0 <= i <= n),

wij = wi,j-1 +aj + bj                                             (0 <= i < j <= n),                                      (4.62)

 

pii = wii,                                                           (0 <= i <= n),                                            (4.63)

pij = wij + MIN k : i < <= j : (pi,k-1 + pkj)            (0 <= i < j <= n)

 

 Последнее равенство следует непосредственно из (4.60) и определения оптимальности. Поскольку существует около n2/2 значений рij, а (4.63) требует выбора одного из 0 <j-i<=n значений, то весь процесс минимизации будет занимать приблизительно n3/6 операций. Кнут отмечает, что можно избавиться от одного множителя n и тем самым сохранить практическую ценность данного алгоритма. Делается это так.

 

  Пусть rij — значение k, при котором в (4.63) достигается минимум. Поиск rij можно ограничить значительно меньшим интервалом, т. е. сократить число вычислений до j-i. Это можно сделать, поскольку если мы нашли корень rij оптимального поддерева Tij, то ни расширение при добавлении к дереву справа новой вершины, ни сжатие при отбрасывании самого левого узла не могут сдвинуть вправо, этот оптимальный корень. Такое свойство выражается отношением

ri,j-1 <= rij <= ri+1,j,                                                                                                                                                (4.64)

которое и ограничивает поиск возможных решений для rij диапазоном ri,j-1ri+1,j. Это в конце концов и ограничивает число элементарных шагов — около n2.

 

Теперь мы уже готовы составить детальный алгоритм оптимизации. Введем следующие определения исходя из того, что Tij -оптимальные деревья, содержащие узлы с ключами ki+1 ... kj:

1.       ai  —  частота  поиска ki

2.       bj  —  частота поиска аргумента х, лежащего между kj и kj+1

3.       wij  — вес Tij

4.       pij   — взвешенная длина пути Tij

5.       nij   — индекс корня Tij.

 

После описания TYPE  index = [0. .n] вводим следующие массивы:

a:         ARRAY  [1. .n]  OF CARDINAL;

b:         ARRAY  index OF CARDINAL;                                                                            (4.65)

p.w:     ARRAY  index,   index OF CARDINAL;

r:         ARRAY  index,   index OF index;

 

 Предположим, что вес wij уже вычислен непосредственно по a и b (см. (4.62)). Будем считать w аргументом процедуры OptTree, которую нужно создать. Значение же r будет ее результатом, ведь этот массив полностью описывает структуру дерева. Причем р можно рассматривать как некоторый промежуточный результат. Начав с наименьших возможных поддеревьев, т. е. деревьев, не содержащих никаких вершин, мы переходим все к большим и большим деревьям. Обозначим ширину j-i поддерева Тij через h. После этого мы можем просто определить по (4.63) значения рij для всех деревьев с h = 0:

FOR i := 0 ТО n DO  p[i,i] := b[i]  END;                                             (4.66)

В случае h = 1 мы имеем дело с деревьями, содержащими одну-единственную вершину, которая к тому же будет и корнем (рис. 4.38);

FOR i := 0 ТО n-1  DO

i := i+1;   p[i,j]  := w[i, j ] + p[i, i] + p[ j , j ];   r[i,j]  := j     (4.67)

END;

Подпись: Рис. 4.38 Оптимальное дерево с одной вершинойЗаметим, что в рассматриваемом Дереве Тij через i обозначена левая граница индекса, а через j — правая. Для вариантов h > 1 мы используем оператор цикла с параметром h, пробегающим значения от 2 до n, причем при h = n перекрывается все дерево To,n. В каждом случае минимальная Длина пути рij и соответствующий Индекс корня rij определяются с помощью простого оператора цикла с индексом k, изменяющимся в интервале, заданном в (4.64):

FOR h   := 2 ТО n DO

FOR      i  := 0 ТО n-h DO

J:=  i+h;

найти k и minMIN k:   i  < k <= j  :   (pi,k-1 + pkj)                                 (4.68)

такие,   что  ri,j-1 <= k <=  ri+1,j

p[i,j]   := min + w[i. j];   r[i,j]  := k

END

END;

 

В листинге 4.6 приводится детальное описание операторов, выделенных выше курсивом. Средняя длина пути в Т0,n здесь задается частным р0,n /w0,n, а его корень — вершина с индексом r0,n.

 Теперь опишем структуру листинга 4.6. Она состоит из двух основных компонент: процедуры для построения при заданном распределении весов w дерева оптимального поиска и процедуры печати дерева, определенного индексами r. Вначале из входного потока читаются значения a и b и ключи. В вычислении структуры дерева эти ключи не употребляются, они нужны лишь для последующей печати полученного дерева. После того как будет напечатана информация о частотах (статистика), программа начинает вычислять длину пути идеально сбалансированного дерева, определяя по пути корни его поддеревьев. После всего печатается средняя взвешенная длина пути и изображение дерева.

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

 

Рис. 4.39. Изображение дерева с помощью надлежащих отступов

 

 

В табл. 4.4 и на рис. 4.40-4.42 приведены результаты применения программы листинга 4.6 к самой себе, т. е. к ее собственному тексту. Различия в этих трех рисунках наглядно демонстрируют, что сбалансированное дерево нельзя считать даже приближением к оптимальному дереву, а учет частот "других" (не служебных) слов сильно влияет на выбор оптимальной структуры.

Из алгоритма (4.68) ясно, что затраты на определение оптимальной структуры пропорциональны n2, размер необходимой памяти также порядка n2. Если n слишком велико, то такой подход уже неприемлем. Поэтому желательно иметь дело с более эффективными алгоритмами. Один из таких алгоритмов — алгоритм, созданный Ху и Таккером [4.6], он требует памяти порядка O(n), а затраты на вычисления — порядка O(n * log(n)). Однако рассчитан лишь на случаи нулевых частот для ключевых слов, т. e. в нем фиксируются только неудачные попытки отыскать слово. Еще один алгоритм был описан Уолкером и Готлибом [4.10], для него нужна память порядка О(n), а затраты на вычисления — порядка O(n * log(n)). В этом алгоритме ищется не оптимальное дерево, а дерево, близкое к оптимальному, и он построен на эвристических принципах. Основная идея следующая.

 

Будем считать, что вершины (подлинные и специальные) распределены по линейной шкале с весами, соответствующими частоте (или вероятности) обращения к ним. Найдем вершину, расположенную ближе всего к "центру тяжести". Такую вершину будем называть центроидом. Его индекс равен округленному до ближайшего целого значения выражению:

((Si:l <= i <= n: i*ai) + (Sj: 0<= j <= m: j*bj))/W.                                                                  (4.69)

 

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