в работе Н. Р. Luhn, Amer. Documentation 11 (1960), 288-295, а сам указатель полностью приведен в работе W. W. Youden, JACM 10 (1963), 583-646.

При подготовке указателя KWIC к сортировке нам, возможно, понадобилось бы воспользоваться бинарным деревом поиска, чтобы проверить, должно ли определенное слово быть внесенным в указатель. Другие слова, попадающие в алфавитном порядке между неиндексируемыми словами, показаны в виде внешних узлов на рис. 15. Так, в заглавиях статей JACM за 1954-1963 годы встретилось ровно 277 слов, расположенных по алфавиту между словами PROBLEMS и SOLUTION.

На рис. 15 показано оптимальное дерево, полученное согласно алгоритму К при п = 35. Вычисленные для j = 1,2,... ,35 значения r[0,j] равны (1,1,2,3,3,3,3,8,8,8, 8,8,8,11,11,..., 11,21,21,21,21,21,21); значения г[г,35] для г = 0,1,...,34 равны (21,21,..., 21,25,25,25,25,25,25,26,26,26,30,30,30,30,30,30,30, 33,33,33,35,35).

Рис. 16. Оптимальные бинарные деревья поиска, основанные на половине данных, которые представлены на рис. 15: (а) без учета внешних частот; (Ь) без учета внутренних частот.

"Промежуточные частоты" qj оказывают существенное влияние на структуру оптимального дерева; на рис. 16, (а) показано оптимальное дерево, которое было бы получено при всех qj, равных нулю. Точно так же важны и внутренние частоты Pi; на рис. 16, (Ь) представлено оптимальное дерево при р,, равных нулю. При полном наборе частот дерево, изображенное на рис. 15, требует в среднем только 4.15 сравнений; деревья на рис. 16 требуют 4.69 и 4.55 сравнений соответственно.

- 300

- 200

- 100

5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 Рис. 17. Поведение цены как функции корня к.

Поскольку для алгоритма К необходимы время и пространство, пропорциональные п, его использование непрактично при больших п. Конечно, при очень больших п мы можем отказаться от использования бинарных деревьев и подумать о других методах поиска, которые будут рассмотрены нами немного позже. А пока предположим, что надо найти оптимальное (или почти оптимальное) дерево при больших значениях п.

Мы видели, что идея вставки ключей в порядке уменьшения частот приводит к получению в среднем неплохих деревьев; впрочем, они могут оказаться и очень плохими (см. упр. 20), так как веса qj при таком методе построения не используются. Еще один подход состоит в выборе корня к таким образом, чтобы максимальный вес поддерева max(u;(0, fc - 1), w{k,n)) был настолько мал, насколько это возможно. Такой подход также может оказаться плохим (при выборе в качестве корня узла с малым значением рк). Впрочем, теорема М, приведенная ниже, показывает, что полученное в результате дерево будет не так уж далеко от оптимального.

Более успешная процедура может быть получена путем комбинирования описанных методов, как было предложено В. А. Волкером (W. А. Walker) и К. К. Готлибом (С. С. Gotlieb) (Graph Theory and Computing (Academic Press, 1972), 303-323). Попытайтесь уравнять "левые" и "правые" веса, однако будьте готовы переместить корень на несколько шагов вправо или влево для поиска узла с относительно ббльшим Pk- На рис. 17 показана "разумность" предложенного метода: если начер-

тить график с(0, к - 1) + с{к,п) как функции от к для данных KWIC (см. рис. 15), то увидим, что результат весьма чувствителен к величине р)..

Такой метод "сверху вниз" можно использовать при больших п для выбора корня и дальнейшей работы с левыми и правыми поддеревьями. При получении достаточно малого поддерева возможно применение алгоритма К. Результирующий метод дает неплохие деревья (по сообщениям отличающиеся от оптимальных на 2-3%), требуя при этом пространство 0{п) и время работы - 0{n\ogn) единиц. М. Фредманом (М. Fredman) было показано, что на самом деле достаточно 0{п) единиц времени при использовании подходящих структур данных {STOC 7 (1975), 240-244; см. также К. Mehlhorn , Data Structures and Algorithms 1 (Springer, 1984), Section 4.2).

Оптимальные деревья и энтропия. Минимальная цена очень близка к другому математическому понятию, именуемому энтропией, которое было введено Клодом Шенноном (Claude Shannon) в его знаменитой работе по теории информации {Bell System Tech. J. 27 (1948), 379-423, 623-656). Если pi, рз, Pn представляют собой вероятности, причем pi + р2 + • + Рп = 1, мы определяем энтропию H{pi,p2,.. ,Рп) как

н{р„Р2,..-,Рп) = ер*1§;г- (1)

Интуитивно понятно, что если происходит к-е событие (с вероятностью pk) из п возможных, мы получаем lg{l/pk) бит информации (так, событие, вероятность коврого равна , дает нам 5 бит информации). Значит, H{pi,p2,. . ,Рп) представляет собой ожидаемое число битов информации при наступлении случайного события. Если Рк = О, то определим рк lg{l/pk) - О, поскольку limf o+ elg 7 = Ишт- Igm = 0. Такое соглашение позволяет нам пользоваться формулой (18) даже в случае, когда некоторые вероятности равны нулю.

функция xlg(l/x) вогнута, т. е. ее вторая производная, -1/(х1п2), отрицательна*. Таким образом, при pi = р2 = = рп - 1/п достигается максимальное значение энтропии H{pi,p2,... ,Рп), равное

Н(-)=\gn. (19)

\п п п/

в общем случае, когда мы фиксируем значения pi, ..., рп-к и позволяем изменяться значениям pn~k+i, , Рп, справедливы неравенства

Hipi,. . . ,Рп-к,Рп-к+1,- ,Рп) < н(р1,.. .,Рп-к, f • • • f)

= H{p„...,pn-k,q)+qk, (20)

H{pi,- ,Рп-к,Рп-к+1,-,Pn)> H{pi,...,Pn-k,q,0,...,0)

= H{pi,...,Pr,-k,q), (21)

где g = 1 - (pi + ---+pnk)-

* Автор использует для описания этой функции термин concave, дословно переводимый как вогнутый. Следует отметить, что в отечественной математике зачастую используются более точные термины выпуклая вниз и выпуклая вверх функции (Бронштейн И. Н., Семендяев К. А. Справочник по математике для инженеров и учащихся втузов. - М.: Наука, 1981. - 720 с). Здесь и далее под вогнутой функцией подразумевается выпуклая вверх функция. - Прим. перев.