\input style
\chapno=6\subchno=2\chapnotrue
\subchap{цИФРОВОЙ ПОИСК} % 6.3
вМЕСТО ТОГО ЧТОБЫ ОСНОВЫВАТЬ МЕТОД ПОИСКА НА СРАВНЕНИИ КЛЮЧЕЙ, МОЖНО
ВОСПОЛЬЗОВАТЬСЯ ИХ ПРЕДСТАВЛЕНИЕМ В ВИДЕ ПОСЛЕДОВАТЕЛЬНОСТИ ЦИФР ИЛИ
БУКВ. рАССМОТРИМ, НАПРИМЕР, ИМЕЮЩИЕСЯ ВО МНОГИХ СЛОВАРЯХ "ПОБУКВЕННЫЕ
ВЫСЕЧКИ"; ПО ПЕРВОЙ БУКВЕ ДАННОГО СЛОВА МЫ МОЖЕМ НЕМЕДЛЕННО НАЩУПАТЬ
СТРАНИЦЫ, СОДЕРЖАЩИЕ ВСЕ СЛОВА, НАЧИНАЮЩИЕСЯ С ЭТОЙ БУКВЫ.
еСЛИ РАЗВИТЬ ИДЕЮ "ПОБУКВЕННЫХ ВЫСЕЧЕК", МЫ ПРИДЕМ К СХЕМЕ ПОИСКА,
ОСНОВАННОЙ НА "ИНДЕКСИРОВАНИИ", КАК ПОКАЗАНО В ТАБЛ.~1. пРЕДПОЛОЖИМ,
ТРЕБУЕТСЯ ПРОВЕРИТЬ, ПРИНАДЛЕЖИТ ЛИ ДАННЫЙ АРГУМЕНТ ПОИСКА К 31~НАИБОЛЕЕ
УПОТРЕБИТЕЛЬНОМУ АНГЛИЙСКОМУ СЛОВУ (СР.~С~РИС.~12 И~13, П.~6.2.2). в
ТАБЛ.~1 ДАННЫЕ ПРЕДСТАВЛЕНЫ В ВИДЕ ТАК НАЗЫВАЕМОЙ СТРУКТУРЫ "БОРА";
ТЕРМИН ВВЕДЕН э.~фРЭДКИНОМ [{\sl CACM,\/} {\bf 3} (1960), 490--500]
КАК ЧАСТЬ СЛОВА ВЫ{\it БОР}КА\note{1}%
{в ОРИГИНАЛЕ СООТВЕТСТВЕННО trie (ИСКАЖЕННОЕ "tree") И
re{\it trie}val---{\sl пРИМ. ПЕРЕВ.\/}}
(ИНФОРМАЦИИ). бОР В СУЩНОСТИ ЯВЛЯЕТСЯ $M\hbox{-АРНЫМ}$ ДЕРЕВОМ, УЗЛЫ
КОТОРОГО СУТЬ $M\hbox{-МЕСТНЫЕ}$ ВЕКТОРЫ С КОМПОНЕНТАМИ, СООТВЕТСТВУЮЩИМИ
ЦИФРАМ ИЛИ БУКВАМ. кАЖДЫЙ УЗЕЛ УРОВНЯ~$l$ ПРЕДСТАВЛЯЕТ МНОЖЕСТВО ВСЕХ
КЛЮЧЕЙ, НАЧИНАЮЩИХСЯ С ОПРЕДЕЛЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ИЗ $l$~ЛИТЕР; УЗЕЛ
ОПРЕДЕЛЯЕТ $M\hbox{-ПУТЕВОЕ}$ РАЗВЕТВЛЕНИЕ В ЗАВИСИМОСТИ ОТ
$(l+1)\hbox{-Й}$ ЛИТЕРЫ.
нАПРИМЕР, БОР ТАБЛ.~1 ИМЕЕТ 12~УЗЛОВ; УЗЕЛ~1---КОРЕНЬ, И ПЕРВУЮ БУКВУ
СЛЕДУЕТ ИСКАТЬ ЗДЕСЬ. еСЛИ ПЕРВОЙ ОКАЗАЛАСЬ, СКАЖЕМ, БУКВА~|N|, ИЗ ТАБЛИЦЫ
ВИДНО, ЧТО НАШИМ СЛОВОМ БУДЕТ |NOT| (ИЛИ ЖЕ, ЧТО ЕГО НЕТ В ТАБЛИЦЕ). с
ДРУГОЙ СТОРОНЫ, ЕСЛИ ПЕРВАЯ БУКВА---|W|, УЗЕЛ~(1) НАПРАВИТ НАС К УЗЛУ~(9),
ГДЕ МЫ ДОЛЖНЫ АНАЛОГИЧНЫМ ОБРАЗОМ ОТЫСКАТЬ ВТОРУЮ БУКВУ; УЗЕЛ~(9) УКАЖЕТ,
ЧТО ЭТОЙ БУКВОЙ ДОЛЖНА БЫТЬ~|A|, |H| ИЛИ~|I|.
уЗЛЫ-ВЕКТОРЫ В ТАБЛ.~1 ОРГАНИЗОВАНЫ В СООТВЕТСТВИИ С КОДОМ ЛИТЕР, ПРИНЯТЫМ
ДЛЯ \MIX. эТО ОЗНАЧАЕТ, ЧТО ПОИСК ПО БОРУ БУДЕТ ДОВОЛЬНО БЫСТРЫМ, ТАК КАК
МЫ ДОЛЖНЫ ПРОСТО ВЫБИРАТЬ СЛОВА ИЗ МАССИВА, ИСПОЛЬЗУЯ В КАЧЕСТВЕ ИНДЕКСОВ
ЛИТЕРЫ НАШЕГО КЛЮЧА. мЕТОДЫ БЫСТРОГО МНОГОПУТЕВОГО РАЗВЕТВЛЕНИЯ С
ПОМОЩЬЮ ИНДЕКСИРОВАНИЯ НАЗЫВАЮТСЯ "ПРОСМОТРОМ ТАБЛИЦ" ("Table Look-At") В
ПРОТИВОПОЛОЖНОСТЬ "ПОИСКУ ПО ТАБЛИЦАМ" ("Table Look-Up")
[СМ.~P.~M.~Sherman, {\sl CACM,\/} {\bf 4} (1961), 172--173, 175].
\alg т.(пОИСК ПО БОРУ.) аЛГОРИТМ ПОЗВОЛЯЕТ НАЙТИ ДАННЫЙ АРГУМЕНТ~$K$ В
ТАБЛИЦЕ ЗАПИСЕЙ, ОБРАЗУЮЩИХ $M\hbox{-АРНЫЙ}$ БОР.
%%573
{
\catcode`\!=\active\def!#1.{\boxit{\hbox{\strut\bskip\tt\hbox to 2.5em{#1\hfill}\bskip}}}
\def\putpar#1{(#1)}
\def\@#1{\strut\hfill$(#1)$}
\catcode`\(=\active\def(#1){\boxit{\hbox{\bskip\tt\hbox to 2.5em{\strut$\putpar{#1}$\hfill}\bskip}}}
\offinterlineskip\tabskip=0pt\htable{тАБЛИЦА 1}%
{"бОР" ДЛЯ 31 НАИБОЛЕЕ УПОТРЕБИТЕЛЬНОГО АНГЛИЙСКОГО СЛОВА}%
{\vbox{\hbox{\strut\tt #}\hbox{}}&&#\hfill\cr
&\@{1} & \@{2}& \@{3}& \@{4}& \@{5}& \@{6}& \@{7}& \@{8}& \@{9}& \@{10}&\@{11}&\@{12}\cr
\] & !---.& !A.& !---.& !---.& !---.& !I.& !---.& !---.& !---.& !---.& !HE.& !---.\cr
A & (2)& !---.& !---.& !---.& (10)& !---.& !---.& !---.& !WAS.& !---.& !---.&!THAT.\cr
B & (3)& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
C & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
D & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !HAD.& !---.& !---.\cr
E & !---.& !---.& !BE.& !---.& (11)& !---.& !---.& !---.& !---.& !---.& !---.& !THE.\cr
F & (4)& !---.& !---.& !---.& !---.& !---.& !OF.& !---.& !---.& !---.& !---.& !---.\cr
G & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
H & (5)& !---.& !---.& !---.& !---.& !---.& !---.& (12)&!WHICH.& !---.& !---.& !---.\cr
I & (6)& !---.& !---.& !---.& !HIS.& !---.& !---.& !---.& !WITH.& !---.& !---.&!THIS.\cr
$\Theta$ & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
J & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
K & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
L & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
M & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
N & !NOT.& !AND.& !---.& !---.& !---.& !IN.& !ON.& !---.& !---.& !---.& !---.& !---.\cr
O & (7)& !---.& !---.& !FOR.& !---.& !---.& !---.& !TO.& !---.& !---.& !---.& !---.\cr
P & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
Q & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
R & !---.& !ARE.& !---.&!FROM.& !---.& !---.& !OR.& !---.& !---.& !---.& !HER.& !---.\cr
$\Phi$ & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
$\Pi$ & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
S & !---.& !AS.& !---.& !---.& !---.& !IS.& !---.& !---.& !---.& !---.& !---.& !---.\cr
T & (8)& !AT.& !---.& !---.& !---.& !IT.& !---.& !---.& !---.& !---.& !---.& !---.\cr
U & !---.& !---.& !BUT.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
V & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !HAVE.& !---.& !---.\cr
W & (9)& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
X & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
Y & !YOU.& !---.& !BY.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
Z & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.\cr
}
}
уЗЛЫ БОРА ПРЕДСТАВЛЯЮТ СОБОЙ ВЕКТОРЫ, ИНДЕКСЫ КОТОРЫХ ИЗМЕНЯЮТСЯ ОТ~$0$
ДО~$M-1$; КАЖДАЯ КОМПОНЕНТА ЭТИХ ВЕКТОРОВ ЕСТЬ ЛИБО КЛЮЧ, ЛИБО ССЫЛКА
(ВОЗМОЖНО, ПУСТАЯ).
\st[нАЧАЛЬНАЯ УСТАНОВКА.) уСТАНОВИТЬ УКАЗАТЕЛЬ~|P| ТАК, ЧТОБЫ ОН УКАЗЫВАЛ
НА КОРЕНЬ БОРА.
\st[рАЗВЕТВЛЕНИЕ.] зАНЕСТИ В~$k$ СЛЕДУЮЩУЮ (СТОЯЩУЮ ПРАВЕЕ) ЛИТЕРУ
АРГУМЕНТА~$K$. (еСЛИ АРГУМЕНТ ПОЛНОСТЬЮ ОБРАБОТАН, МЫ ЗАСЫЛАЕМ В~$k$
"ПРОБЕЛ" ИЛИ СИМВОЛ КОНЦА СЛОВА. лИТЕРА ДОЛЖНА БЫТЬ ПРЕДСТАВЛЕНА ЦЕЛЫМ
ЧИСЛОМ В ДИАПАЗОНЕ~$0\le k<M$.) чЕРЕЗ~$X$ ОБОЗНАЧИМ $k\hbox{-Й}$~ЭЛЕМЕНТ В УЗЛЕ~$|NODE|(|P|)$.
%%574
еСЛИ $X$---ССЫЛКА, ПЕРЕЙТИ НА \stp{3}; ЕСЛИ $X$---КЛЮЧ, ТО ПЕРЕЙТИ НА~\stp{4}.
\st[пРОДВИЖЕНИЕ.] еСЛИ $X\ne\NULL$, УСТАНОВИТЬ $P\asg X$ И
ВЕРНУТЬСЯ НА~\stp{2}; В ПРОТИВНОМ СЛУЧАЕ АЛГОРИТМ ЗАКАНЧИВАЕТСЯ НЕУДАЧНО.
\st[сРАВНЕНИЕ.] еСЛИ $K=X$, АЛГОРИТМ ЗАКАНЧИВАЕТСЯ УДАЧНО;
В ПРОТИВНОМ СЛУЧАЕ ОН ЗАКАНЧИВАЕТСЯ НЕУДАЧНО.
\algend
зАМЕТИМ, ЧТО, ЕСЛИ ПОИСК НЕУДАЧЕН, ВСЕ ЖЕ БУДЕТ НАЙДЕН ЭЛЕМЕНТ, ЛУЧШЕ
\emph{ВСЕГО СОВПАДАЮЩИЙ} С АРГУМЕНТОМ ПОИСКА. эТО СВОЙСТВО ПОЛЕЗНО ДЛЯ
НЕКОТОРЫХ ПРИЛОЖЕНИЙ.
чТОБЫ СРАВНИТЬ ВРЕМЯ РАБОТЫ АЛГОРИТМА И ДРУГИХ АЛГОРИТМОВ ДАННОЙ ГЛАВЫ,
МОЖНО НАПИСАТЬ КОРОТКУЮ ПРОГРАММУ ДЛЯ \MIX, ПРЕДПОЛАГАЯ, ЧТО ЛИТЕРА
ЗАНИМАЕТ ОДИН БАЙТ, А КЛЮЧИ--- НЕ БОЛЕЕ ПЯТИ БАЙТОВ.
\prog т.(пОИСК ПО БОРУ.) пРЕДПОЛАГАЕТСЯ, ЧТО ВСЕ КЛЮЧИ ЗАНИМАЮТ ОДНО СЛОВО
МАШИНЫ~\MIX; ЕСЛИ КЛЮЧ СОСТОИТ МЕНЕЕ ЧЕМ ИЗ ПЯТИ ЛИТЕР, ОН ДОПОЛНЯЕТСЯ
СПРАВА ПРОБЕЛАМИ. тАК КАК МЫ ИСПОЛЬЗУЕМ ДЛЯ ПРЕДСТАВЛЕНИЯ ЛИТЕР КОД~\MIX,
КАЖДЫЙ БАЙТ АРГУМЕНТА ПОИСКА ДОЛЖЕН СОДЕРЖАТЬ ЧИСЛО, МЕНЬШЕЕ~30.
сСЫЛКИ ПРЕДСТАВЛЕНЫ КАК ОТРИЦАТЕЛЬНЫЕ ЧИСЛА В ПОЛЕ~$0:2$.
зНАЧЕНИЯ РЕГИСТРОВ: $|rI1|\equiv|P|$, $|rX|\equiv\hbox{НЕОБРАБОТАННАЯ
ЧАСТЬ $K$}$.
\code
START &LDX &к &1& T1. нАЧАЛЬНАЯ УСТАНОВКА.
&ENT1 &ROOT &1& $|P|\asg\hbox{УКАЗАТЕЛЬ НА КОРЕНЬ БОРА}$.
2H &SLAX &1 &C& T2. рАЗВЕТВЛЕНИЕ.
&STA &*+1(2:2)&C& вЫДЕЛЕНИЕ СЛЕДУЮЩЕЙ ЛИТЕРЫ~$k$.
&ENT2 &0,1 &C& $|Q|\asg|P|+k$.
&LD1N &0,2(0:2)&C& $|P|\asg|LINK|(|Q|)$.
&J1P &2B &C& Tз. пРОДВИЖЕНИЕ. нА T2, ЕСЛИ |P|---ССЫЛКА $\ne\NULL$.
&LDA &0,2 &1& т4. сРАВНЕНИЕ. $|rA|\asg|KEY|(|Q|)$.
&CMPA &K &1
&JE &SUCCESS &1& уДАЧНЫЙ ВЫХОД, ЕСЛИ $|rA|=k$.
FAILURE&EQU &* &1& вЫХОД, ЕСЛИ $K$ НЕТ В БОРУ.
\endcode
вРЕМЯ РАБОТЫ ПРОГРАММЫ РАВНО $(8C+8)u$, ГДЕ $C$---ЧИСЛО ПРОВЕРЯЕМЫХ ЛИТЕР.
тАК КАК $C\le5$, ПОИСК НЕ ЗАЙМЕТ БОЛЕЕ 48~ЕДИНИЦ ВРЕМЕНИ.
еСЛИ ТЕПЕРЬ СРАВНИТЬ ЭФФЕКТИВНОСТЬ ЭТОЙ ПРОГРАММЫ (ИСПОЛЬЗУЮЩЕЙ БОР
ТАБЛ.~1) И ПРОГРАММЫ~6.2.2т (ИСПОЛЬЗУЮЩЕЙ \emph{ОПТИМАЛЬНОЕ} БИНАРНОЕ
ДЕРЕВО ПОИСКА (РИС.~13)), МОЖНО ЗАМЕТИТЬ СЛЕДУЮЩЕЕ:
1.~бОР ЗАНИМАЕТ ГОРАЗДО БОЛЬШЕ ПАМЯТИ: ДЛЯ ПРЕДСТАВЛЕНИЯ 31~КЛЮЧА
ИСПОЛЬЗОВАНО 360~СЛОВ, В ТО ВРЕМЯ КАК БИНАРНОЕ ДЕРЕВО ПОИСКА ЗАНИМАЕТ
62~СЛОВА ПАМЯТИ. (оДНАКО УПР.~4 ПОКАЗЫВАЕТ, ЧТО, ПРОЯВИВ ИЗВЕСТНУЮ
ИЗОБРЕТАТЕЛЬНОСТЬ, МОЖНО ВМЕСТИТЬ БОР ТАБЛ.~1 В 49 СЛОВ.)
%%575
\picture{рИС. 31. бОР ТАБЛ. 1, ПРЕОБРАЗОВАННЫЙ В "ЛЕС".}
%%576
2.~уДАЧНЫЙ ПОИСК В ОБОИХ СЛУЧАЯХ ТРЕБУЕТ ОКОЛО 26~ЕДИНИЦ ВРЕМЕНИ. нО
НЕУДАЧНЫЙ ПОИСК ОКАЗЫВАЕТСЯ БОЛЕЕ БЫСТРЫМ ДЛЯ БОРА И БОЛЕЕ МЕДЛЕННЫМ ДЛЯ
БИНАРНОГО ДЕРЕВА ПОИСКА. дЛЯ НАШИХ ДАННЫХ ПОИСК ЧАЩЕ БУДЕТ НЕУДАЧНЫМ,
НЕЖЕЛИ УДАЧНЫМ, ПОЭТОМУ С ТОЧКИ ЗРЕНИЯ СКОРОСТИ БОР БОЛЕЕ ПРЕДПОЧТИТЕЛЕН.
3.~еСЛИ ВМЕСТО 31~НАИБОЛЕЕ УПОТРЕБИТЕЛЬНОГО АНГЛИЙСКОГО СЛОВА РАССМОТРИМ
ПРИМЕНЕНИЕ УКАЗАТЕЛЯ~KWIC (РИС.~15), БОР ТЕРЯЕТ СВОИ ПРЕИМУЩЕСТВА
ВСЛЕДСТВИЕ ХАРАКТЕРА ДАННЫХ. нАПРИМЕР, БОР ТРЕБУЕТ 12~ИТЕРАЦИЙ, ЧТОБЫ
РАЗЛИЧИТЬ СЛОВА |COMPUTATION| И~|COMPUTATIONS|. (в ЭТОМ СЛУЧАЕ БЫЛО БЫ
ЛУЧШЕ ТАК ПОСТРОИТЬ БОР, ЧТОБЫ СЛОВА ОБРАБАТЫВАЛИСЬ СПРАВА НАЛЕВО, А НЕ
СЛЕВА НАПРАВО.)
пЕРВАЯ ПУБЛИКАЦИЯ О БОРОВОЙ ПАМЯТИ ПРИНАДЛЕЖИТ рЕНЕ ДЕ~ЛА~бРИАНДЕ
[Proc.~Western Joint Computer Conf., {\bf 15} (1959), 295--298]. оН УКАЗАЛ,
ЧТО МОЖНО СЭКОНОМИТЬ ПАМЯТЬ (ЗА СЧЕТ УВЕЛИЧЕНИЯ ВРЕМЕНИ РАБОТЫ), ЕСЛИ
ИСПОЛЬЗОВАТЬ СВЯЗАННЫЙ СПИСОК ДЛЯ КАЖДОГО УЗЛА-ВЕКТОРА, ТАК КАК
БОЛЬШИНСТВО ЭЛЕМЕНТОВ ЭТОГО ВЕКТОРА ОБЫЧНО ПУСТО. нА САМОМ ДЕЛЕ
ПРЕДЛОЖЕННАЯ ИДЕЯ ВЕДЕТ К ЗАМЕНЕ БОРА ТАБЛ.~1 НА ЛЕС ДЕРЕВЬЕВ,
ИЗОБРАЖЕННЫЙ НА РИС.~31. пРИ ПОИСКЕ В ТАКОМ ЛЕСУ МЫ НАХОДИМ КОРЕНЬ,
СООТВЕТСТВУЮЩИЙ ПЕРВОЙ ЛИТЕРЕ, ЗАТЕМ СЫНА ЭТОГО КОРНЯ, СООТВЕТСТВУЮЩЕГО
ВТОРОЙ ЛИТЕРЕ, И~Т.~Д.
фАКТИЧЕСКИ В СВОЕЙ СТАТЬЕ ДЕ ЛА бРИАНДЕ НЕ ПРЕРЫВАЛ РАЗВЕТВЛЕНИЯ ТАК,
КАК ПОКАЗАНО В ТАБЛ.~1 ИЛИ НА РИС.~31; ВМЕСТО ЭТОГО ОН ПРЕДСТАВЛЯЛ КАЖДЫЙ
КЛЮЧ ЛИТЕРА ЗА ЛИТЕРОЙ ДО ДОСТИЖЕНИЯ ПРИЗНАКА КОНЦА СЛОВА. тАКИМ ОБРАЗОМ,
В ДЕЙСТВИТЕЛЬНОСТИ ДЕ~ЛА~бРИАНДЕ ВМЕСТО ДЕРЕНА "|H|" (РИС.~31)
ИСПОЛЬЗОВАЛ БЫ
\picture{рИС. СТР. 576}
тАКОЕ ПРЕДСТАВЛЕНИЕ ТРЕБУЕТ БОЛЬШЕ ПАМЯТИ, НО ДЕЛАЕТ ОБРАБОТКУ ДАННЫХ
ПЕРЕМЕННОЙ ДЛИНЫ ОСОБЕННО ЛЕГКОЙ. еСЛИ ИСПОЛЬЗОВАТЬ НА ЛИТЕРУ ДВА ПОЛЯ
ССЫЛОК, МОЖНО ЛЕГКО ОРГАНИЗОВАТЬ ДИНАМИЧЕСКИЕ ВСТАВКИ И УДАЛЕНИЯ. бОЛЕЕ
ТОГО, ВО МНОГИХ ПРИЛОЖЕНИЯХ АРГУМЕНТ ПОИСКА ПОСТУПАЕТ В "РАСПАКОВАННОЙ"
ФОРМЕ, Т.~Е.~КАЖДАЯ ЛИТЕРА ЗАНИМАЕТ ЦЕЛОЕ СЛОВО, И ТАКОЕ ДЕРЕВО ПОЗВОЛЯЕТ
ИЗБЕЖАТЬ "УПАКОВКИ" ПЕРЕД ПРОВЕДЕНИЕМ ПОИСКА.
%%577
%%577
еСЛИ ИСПОЛЬЗОВАТЬ ОБЫЧНЫЙ СПОСОБ ПРЕДСТАВЛЕНИЯ ДЕРЕВЬЕВ В БИНАРНОМ ВИДЕ,
ТО (1) ПРЕОБРАЗУЕТСЯ В БИНАРНОЕ ДЕРЕВО
(дЛЯ ПРЕДСТАВЛЕНИЯ ПОЛНОГО ЛЕСА РИС.~31 НЕОБХОДИМО ДОБАВИТЬ УКАЗАТЕЛЬ,
ВЕДУЩИЙ ИЗ~|H| НАПРАВО, К СОСЕДНЕМУ КОРНЮ~|I|.) пРИ ПОИСКЕ В ЭТОМ БИНАРНОМ
ДЕРЕВЕ ЛИТЕРЫ АРГУМЕНТА СРАВНИВАЮТСЯ С ЛИТЕРАМИ ДЕРЕВА; МЫ СЛЕДУЕМ ПО
ССЫЛКАМ~|RLINK|, ПОКА НЕ НАЙДЕМ НУЖНУЮ ЛИТЕРУ; ЗАТЕМ БЕРЕМ ССЫЛКУ~|LLINK|
И СЛЕДУЮЩУЮ ЛИТЕРУ АРГУМЕНТА РАССМАТРИВАЕМ АНАЛОГИЧНЫМ ОБРАЗОМ.
пОИСК В ТАКОМ БИНАРНОМ ДЕРЕВЕ В БОЛЬШЕЙ ИЛИ МЕНЬШЕЙ СТЕПЕНИ СВОДИТСЯ К
СРАВНЕНИЯМ, ПРИЧЕМ РАЗВЕТВЛЕНИЕ ПРОИСХОДИТ НЕ ПО ПРИЗНАКУ "МЕНЬШЕ-БОЛЬШЕ",
А ПО "РАВНО-НЕРАВНО". эЛЕМЕНТАРНАЯ ТЕОРИЯ П.~6.2.1 ГЛАСИТ, ЧТО В СРЕДНЕМ
НА ТО, ЧТОБЫ РАЗЛИЧИТЬ $N$~КЛЮЧЕЙ, НУЖНО ПО КРАЙНЕЙ МЕРЕ $\log_2 N$~СРАВНЕНИЙ;
СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ, ПРОИЗВОДИМЫХ ПРИ ПОИСКЕ ПО
ДЕРЕВУ, ПОДОБНОМУ ИЗОБРАЖЕННОМУ НА РИС.~31, НЕ МЕНЬШЕ ЧИСЛА ПРОВЕРОК ПРИ
ИСПОЛЬЗОВАНИИ МЕТОДОВ БИНАРНОГО ПОИСКА, ИЗЛОЖЕННЫХ В \S~6.2.
с ДРУГОЙ СТОРОНЫ, БОР ТАБЛ.~1 ПОЗВОЛЯЕТ СРАЗУ
ПРОИЗВОДИТЬ $M\hbox{-ПУТЕВОЕ}$ РАЗВЕТВЛЕНИЕ; МЫ УВИДИМ, ЧТО ПРИ
БОЛЬШИХ~$N$ ПОИСК В СРЕДНЕМ ВКЛЮЧАЕТ ЛИШЬ ОКОЛО
$\log_M N=\log_2 N/\log_2 M$~ИТЕРАЦИЙ,
ЕСЛИ ИСХОДНЫЕ ДАННЫЕ---СЛУЧАЙНЫЕ ЧИСЛА. мЫ УВИДИМ ТАКЖЕ, ЧТО
ПРИМЕНЕНИЕ СХЕМЫ БОРА В "ЧИСТОМ" ВИДЕ (КАК В АЛГОРИТМЕ~T) ТРЕБУЕТ ПОРЯДКА
$N/\ln M$~УЗЛОВ, ЕСЛИ НУЖНО РАЗЛИЧИТЬ $N$~СЛУЧАЙНЫХ КЛЮЧЕЙ;
СЛЕДОВАТЕЛЬНО, РАЗМЕР ЗАНИМАЕМОЙ ПАМЯТИ ПРОПОРЦИОНАЛЕН $MN/\ln M$.
эТИ РАССУЖДЕНИЯ ПОКАЗЫВАЮТ, ЧТО ИДЕЯ БОРА ХОРОША ЛИШЬ ДЛЯ НЕБОЛЬШОГО ЧИСЛА
ВЕРХНИХ УРОВНЕЙ ДЕРЕВА. мОЖНО УЛУЧШИТЬ ХАРАКТЕРИСТИКИ, КОМБИНИРУЯ ДВЕ
СТРАТЕГИИ: ДЛЯ НЕСКОЛЬКИХ ПЕРВЫХ ЛИТЕР ИСПОЛЬЗОВАТЬ БОР, А ЗАТЕМ ПЕРЕЙТИ
НА ДРУГУЮ МЕТОДИКУ. нАПРИМЕР, э.~г.~сАССЕНГАТ, МЛ.\ [е.~н.~Sassenguth,
{\sl CACM,\/} {\bf 6} (1963), 272--279] ПРЕДЛОЖИЛ ИСПОЛЬЗОВАТЬ
ЛИТЕРНЫЙ АНАЛИЗ ДО ДОСТИЖЕНИЯ ТОЙ ЧАСТИ ДЕРЕВА, ГДЕ ОСТАЕТСЯ, СКАЖЕМ, НЕ
БОЛЕЕ ШЕСТИ КЛЮЧЕЙ, А ЗАТЕМ ПРОИЗВЕСТИ В ЭТОМ КОРОТКОМ СПИСКЕ
ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК. дАЛЕЕ МЫ УВИДИМ, ЧТО ТАКАЯ СМЕШАННАЯ СТРАТЕГИЯ
УМЕНЬШАЕТ КОЛИЧЕСТВО УЗЛОВ БОРА ПРИМЕРНО В ШЕСТЬ РАЗ БЕЗ СУЩЕСТВЕННОГО
ИЗМЕНЕНИЯ ВРЕМЕНИ РАБОТЫ.
%%578
\section пРИЛОЖЕНИЕ К АНГЛИЙСКОМУ ЯЗЫКУ. нАПРАШИВАЕТСЯ МНОГО ИЗМЕНЕНИЙ
ОСНОВНЫХ СТРАТЕГИЙ БОРА И ПОЛИТЕРНОГО ПОИСКА. чТОБЫ ПОЛУЧИТЬ ПРЕДСТАВЛЕНИЕ
О НЕКОТОРЫХ ИЗ ИМЕЮЩИХСЯ ВОЗМОЖНОСТЕЙ, РАССМОТРИМ ГИПОТЕТИЧЕСКОЕ
КРУПНОМАСШТАБНОЕ ПРИЛОЖЕНИЕ: ПРЕДПОЛОЖИМ, ЧТО В ПАМЯТИ эвм НУЖНО
ЗАПОМНИТЬ ДОВОЛЬНО ПОЛНЫЙ СЛОВАРЬ АНГЛИЙСКОГО ЯЗЫКА. дЛЯ ЭТОГО
ТРЕБУЕТСЯ ДОСТАТОЧНО БОЛЬШАЯ ВНУТРЕННЯЯ ПАМЯТЬ, СКАЖЕМ НА 50000~СЛОВ. нАША
ЦЕЛЬ СОСТОИТ В НАХОЖДЕНИИ ЭКОНОМНОГО СПОСОБА ПРЕДСТАВЛЕНИЯ СЛОВАРЯ,
ОБЕСПЕЧИВАЮЩЕГО ПРИ ЭТОМ ДОСТАТОЧНО БЫСТРЫЙ ПОИСК.
рЕАЛИЗАЦИЯ ТАКОГО ПРОЕКТА---ЗАДАЧА НЕПРОСТАЯ. тРЕБУЕТСЯ КАК ХОРОШЕЕ ЗНАНИЕ
СОДЕРЖАНИЯ СЛОВАРЯ, ТАК И ЗНАЧИТЕЛЬНАЯ ПРОГРАММИСТСКАЯ ИЗОБРЕТАТЕЛЬНОСТЬ.
дАВАЙТЕ НА НЕКОТОРОЕ ВРЕМЯ ПОСТАВИМ СЕБЯ В ПОЛОЖЕНИЕ ЧЕЛОВЕКА,
ПРИСТУПАЮЩЕГО К ТАКОМУ КРУПНОМУ ПРОЕКТУ.
оБЫЧНЫЙ УНИВЕРСИТЕТСКИЙ СЛОВАРЬ СОДЕРЖИТ СВЫШЕ 100000~СЛОВ; НАШИ ЗАПРОСЫ
НЕ СТОЛЬ ВЕЛИКИ, НО РАССМОТРЕНИЕ ПОДОБНОГО СЛОВАРЯ ПОЗВОЛЯЕТ НАМЕТИТЬ
ПУТИ К РЕШЕНИЮ. еСЛИ МЫ ПОПЫТАЕМСЯ ПРИМЕНИТЬ БОРОВУЮ ПАМЯТЬ, ТО ВСКОРЕ
ЗАМЕТИМ ВОЗМОЖНОСТЬ ВАЖНЫХ УПРОЩЕНИЙ. пРЕДПОЛОЖИМ, ЧТО СОБСТВЕННЫЕ ИМЕНА
И СОКРАЩЕНИЯ В РАСЧЕТ НЕ ПРИНИМАЮТСЯ. тОГДА, ЕСЛИ СЛОВО НАЧИНАЕТСЯ НА
БУКВУ~b, ЕГО ВТОРАЯ БУКВА ОБЯЗАТЕЛЬНО ОТЛИЧНА ОТ b, c, d, f, g, j, k, m, n,
p, q, s, t, v, w, x, z. [сЛОВО "bdellium" ("БДЕЛЛИЙ"--- РОД АРОМАТИЧЕСКОЙ
СМОЛЫ) МОЖНО И НЕ ВКЛЮЧАТЬ В СЛОВАРЬ!] нА САМОМ ДЕЛЕ, ТЕ ЖЕ 17~БУКВ
НЕ МОГУТ СТОЯТЬ НА ВТОРОМ МЕСТЕ В СЛОВАХ, НАЧИНАЮЩИХСЯ С c, d, f, g, h, j,
k, 1, m, n, p, r, t, v, w, x, z. иСКЛЮЧЕНИЕ СОСТАВЛЯЮТ НЕСКОЛЬКО СЛОВ,
НАЧИНАЮЩИХСЯ С ct, cz, dw, fj, gn, mn, nt, pf, pn, pt, tc, tm, ts, tz, zw,
И ЗАМЕТНОЕ КОЛИЧЕСТВО СЛОВ, НАЧИНАЮЩИХСЯ С kn, ps, tw. оДИН ИЗ СПОСОБОВ
ИСПОЛЬЗОВАТЬ ЭТОТ ФАКТ СОСТОИТ В КОДИРОВАНИИ БУКВ (НАПРИМЕР, МОЖНО ИМЕТЬ
ТАБЛИЦУ ИЗ 26~СЛОВ И ВЫПОЛНЯТЬ КОМАНДУ ВРОДЕ "|LD1 TABLE,1|") ТАКИМ
ОБРАЗОМ, ЧТОБЫ СОГЛАСНЫЕ b, c, d,~\dots, z ПЕРЕВОДИЛИСЬ В СПЕЦИАЛЬНОЕ
ПРЕДСТАВЛЕНИЕ, БОЛЬШЕЕ, ЧЕМ ЧИСЛОВОЙ КОД ОСТАВШИХСЯ БУКВ a, e, h, i, l,
o, r, u, y. тЕПЕРЬ МНОГИЕ УЗЛЫ БОРА МОГУТ БЫТЬ УКОРОЧЕНЫ ДО 9-ПУТЕВОГО
РАЗВЕТВЛЕНИЯ; СПЕЦИАЛЬНАЯ ЯЧЕЙКА ВЫХОДА ИСПОЛЬЗУЕТСЯ ДЛЯ РЕДКО
ВСТРЕЧАЮЩИХСЯ БУКВ. тАКОЙ ПОДХОД ПОЗВОЛЯЕТ СЭКОНОМИТЬ ПАМЯТЬ ВО МНОГИХ
ЧАСТЯХ БОРА, ПРЕДНАЗНАЧЕННОГО ДЛЯ АНГЛИЙСКОГО ЯЗЫКА, А НЕ ТОЛЬКО ПРИ
ОБРАБОТКЕ ВТОРОЙ БУКВЫ.
в ОБЫЧНОМ УНИВЕРСИТЕТСКОМ СЛОВАРЕ СЛОВА НАЧИНАЮТСЯ ЛИШЬ С~309 ИЗ
$26^2=676$~ВОЗМОЖНЫХ КОМБИНАЦИЙ ДВУХ БУКВ, А ИЗ ЭТИХ 309~ПАР 88~СЛУЖАТ
НАЧАЛОМ 15 ИЛИ МЕНЕЕ СЛОВ. (тИПИЧНЫЕ ПРИМЕРЫ ТАКИХ ПАР: aa, ah, aj, ak,
ao, aq, ay, az, bd, bh,~\dots, xr, yc, yi, yp, yt, yu, yw, za, zu, zw;
БОЛЬШИНСТВО ЛЮДЕЙ МОЖЕТ НАЗВАТЬ МАКСИМУМ ПО ОДНОМУ СЛОВУ ИЗ БОЛЬШИНСТВА
ЭТИХ КАТЕГОРИЙ.)
%%579
еСЛИ ВСТРЕЧАЕТСЯ ОДНА ИЗ УКАЗАННЫХ РЕДКИХ КАТЕГОРИЙ, МОЖНО ОТ
БОРОВОЙ ПАМЯТИ ПЕРЕЙТИ К НЕКОТОРОЙ ДРУГОЙ СХЕМЕ, НАПРИМЕР К
ПОСЛЕДОВАТЕЛЬНОМУ ПОИСКУ.
дРУГИМ СПОСОБОМ УМЕНЬШЕНИЯ ТРЕБУЕМОГО ДЛЯ СЛОВАРЯ ОБRЕМА ПАМЯТИ ЯВЛЯЕТСЯ
ИСПОЛЬЗОВАНИЕ ПРИСТАВОК. нАПРИМЕР, ЕСЛИ ИЩЕТСЯ СЛОВО, НАЧИНАЮЩЕЕСЯ С re-,
pre-, anti-, trans-, dis-, un- И~Т.~Д., МОЖНО ОТДЕЛИТЬ ПРИСТАВКУ И ИСКАТЬ
ОСТАТОК СЛОВА. тАКИМ ПУТЕМ МОЖНО УДАЛИТЬ МНОГО СЛОВ ТИПА reapply
(ПОВТОРНО ПРИМЕНЯТЬ), recompute (СНОВА ВЫЧИСЛИТЬ), redecorate
(ЗАНОВО ДЕКОРИРОВАТЬ), redesign (ПЕРЕПРОЕКТИРОВАТЬ), redeposit
(ПЕРЕКЛАДЫВАТЬ) И~Т.~Д.; ОДНАКО НУЖНО ОСТАВИТЬ СЛОВА ВРОДЕ
remainder (ОСТАТОК), requirement (ТРЕБОВАНИЕ), retain (СОХРАНЯТЬ),
remove (УДАЛЯТЬ), readily (ОХОТНО) И Т.~Д., ТАК КАК ИХ ЗНАЧЕНИЯ
БЕЗ ПРИСТАВКИ "re-" ПОКРЫТЫ ТАЙНОЙ. иТАК, СНАЧАЛА СЛЕДУЕТ ИСКАТЬ СЛОВО И
ЛИШЬ ЗАТЕМ ПЫТАТЬСЯ УДАЛИТЬ ПРИСТАВКУ, ЕСЛИ ПЕРВЫЙ ПОИСК ОКАЗАЛСЯ НЕУДАЧНЫМ.
еЩЕ ВАЖНЕЕ ИСПОЛЬЗОВАТЬ СУФФИКСЫ. нЕ ВЫЗЫВАЕТ СОМНЕНИЙ, ЧТО ДВУКРАТНОЕ
ВКЛЮЧЕНИЕ КАЖДОГО СУЩЕСТВИТЕЛЬНОГО И ГЛАГОЛА В ЕДИНСТВЕННОМ И
МНОЖЕСТВЕННОМ ЧИСЛЕ БЫЛО БЫ СЛИШКОМ РАСТОЧИТЕЛЬНЫМ; ИМЕЮТСЯ И ДРУГИЕ
ТИПЫ СУФФИКСОВ. нАПРИМЕР, СЛЕДУЮЩИЕ ОКОНЧАНИЯ МОЖНО ДОБАВЛЯТЬ КО МНОГИМ
ГЛАГОЛЬНЫМ ОСНОВАМ, ПОЛУЧАЯ НАБОР РОДСТВЕННЫХ СЛОВ:
\ctable{
-#\bskip\bskip\hfill&-#\bskip\bskip\hfill&-#\bskip\bskip\hfill\cr
e & es & ing\cr
ed & s & ings\cr
edlv & able & ingly\cr
er & ible & ion\cr
or & ably & ions\cr
ers & ibly & ional\cr
ors & ability & ionally\cr
\omit& abilities & \omit\cr
}
(мНОГИЕ ИЗ ЭТИХ СУФФИКСОВ САМИ СОСТАВЛЕНЫ ИЗ СУФФИКСОВ.) еСЛИ ПОПЫТАТЬСЯ
ДОБАВИТЬ ЭТИ СУФФИКСЫ К ОСНОВАМ
\ctable{
#-\hfill\cr
comput\cr
calculat\cr
search\cr
suffix\cr
translat\cr
interpret\cr
confus\cr
}
МЫ УВИДИМ, КАК МНОГО СЛОВ ПОЛУЧАЕТСЯ; ЭТО ЧРЕЗВЫЧАЙНО УВЕЛИЧИВАЕТ
ВМЕСТИМОСТЬ НАШЕГО СЛОВАРЯ. бЕЗУСЛОВНО, ПРИ ТАКОЙ
%% 580
ПРОЦЕДУРЕ ПОЛУЧАЕТСЯ И МНОГО НЕСУЩЕСТВУЮЩИХ СЛОВ, НАПРИМЕР "compution";
ОСНОВА computat- ОКАЗЫВАЕТСЯ СТОЛЬ ЖЕ НЕОБХОДИМОЙ, КАК И comput-. оДНАКО
ВРЕДА В ЭТОМ НЕТ, ПОСКОЛЬКУ ТАКИЕ КОМБИНАЦИИ И НЕ БУДУТ СЛУЖИТЬ
АРГУМЕНТАМИ ПОИСКА, А ЕСЛИ БЫ НЕКИЙ АВТОР ПРИДУМАЛ БЫ СЛОВО "computedly",
МЫ ИМЕЛИ БЫ ДЛЯ НЕГО ГОТОВЫЙ ПЕРЕВОД. зАМЕТИМ, ЧТО БОЛЬШИНСТВУ
ЛЮДЕЙ ПОНЯТНО СЛОВО "confusability" (СМУЩАЕМОСТЬ), ХОТЯ ОНО ВСТРЕЧАЕТСЯ
В НЕМНОГИХ СЛОВАРЯХ; НАШ СЛОВАРЬ БУДЕТ ДАВАТЬ ПОДХОДЯЩЕЕ ТОЛКОВАНИЕ. пРИ
ПРАВИЛЬНОЙ ОБРАБОТКЕ ПРИСТАВОК И СУФФИКСОВ НАШ СЛОВАРЬ СМОЖЕТ ИЗ ОДНОЙ
ЛИШЬ ГЛАГОЛЬНОЙ ОСНОВЫ "establish" ВЫВЕСТИ ЗНАЧЕНИЕ СЛОВА
"antidisestablishmentarianism".
рАЗУМЕЕТСЯ, НУЖНО ЗАБОТИТЬСЯ О ТОМ, ЧТОБЫ ЗНАЧЕНИЕ СЛОВА ПОЛНОСТЬЮ
ОПРЕДЕЛЯЛОСЬ ОСНОВОЙ И СУФФИКСОМ; ИСКЛЮЧЕНИЯ ДОЛЖНЫ БЫТЬ ВНЕСЕНЫ В СЛОВАРЬ
ТАКИМ ОБРАЗОМ, ЧТОБЫ ИХ МОЖНО БЫЛО НАЙТИ ДО ОБРАЩЕНИЯ К ПОИСКУ СУФФИКСА.
нАПРИМЕР, СХОДСТВО МЕЖДУ СЛОВАМИ "socialism" (СОЦИАЛИЗМ) И "socialist"
(СОЦИАЛИСТ) СПОСОБНО ТОЛЬКО СБИТЬ С ТОЛКУ ПРИ АНАЛИЗЕ СЛОВ
"organism" (ОРГАНИЗМ) И "organist" (ОРГАНИСТ)!
мОЖНО ИСПОЛЬЗОВАТЬ ЦЕЛЫЙ РЯД ПРИЕМОВ ДЛЯ УМЕНЬШЕНИЯ ОБRЕМА ПАМЯТИ. нО КАК
В ЕДИНОЙ СИСТЕМЕ КОМПАКТНО ПРЕДСТАВИТЬ РАЗНООБРАЗИЕ МЕТОДОВ? оТВЕТ
СОСТОИТ В ТОМ, ЧТОБЫ ТРАКТОВАТЬ СЛОВАРЬ КАК \emph{ПРОГРАММУ}, НАПИСАННУЮ
НА СПЕЦИАЛЬНОМ МАШИННОМ ЯЗЫКЕ ДЛЯ СПЕЦИАЛЬНОЙ \emph{ИНТЕРПРЕТИРУЮЩЕЙ
СИСТЕМЫ} (СР.~С~П.~1.43); ЗАПИСИ В УЗЛЕ БОРА МОЖНО ТРАКТОВАТЬ
КАК \emph{ИНСТРУКЦИИ}. нАПРИМЕР, В ТАБЛ.~1 МЫ ИМЕЕМ ДВА ВИДА
"ИНСТРУКЦИЙ", А ПРОГРАММА~T ИСПОЛЬЗУЕТ ЗНАКОВЫЙ БИТ КАК КОД ОПЕРАЦИИ;
ЗНАК МИНУС ОЗНАЧАЕТ ОТВЕТВЛЕНИЕ К ДРУГОМУ УЗЛУ И ПЕРЕХОД К СЛЕДУЮЩЕЙ
ЛИТЕРЕ ЗА СЛЕДУЮЩЕЙ ИНСТРУКЦИЕЙ, В ТО ВРЕМЯ КАК ЗНАК ПЛЮС ВЫЗЫВАЕТ
СРАВНЕНИЕ АРГУМЕНТА С ОПРЕДЕЛЕННЫМ КЛЮЧОМ.
в ИНТЕРПРЕТИРУЮЩЕЙ СИСТЕМЕ ДЛЯ НАШЕГО СЛОВАРЯ МЫ МОГЛИ БЫ ИМЕТЬ ОПЕРАЦИИ
СЛЕДУЮЩИХ ТИПОВ:
\medskip
\item{$\bullet$}~пРОВЕРКА $n$, $\alpha$, $\beta$. "еСЛИ СЛЕДУЮЩАЯ ЛИТЕРА
АРГУМЕНТА КОДИРУЕТСЯ ЧИСЛОМ~$k\le n$, ПЕРЕЙТИ В ЯЧЕЙКУ~$\alpha+k$ ЗА
СЛЕДУЮЩЕЙ ИНСТРУКЦИЕЙ; В ПРОТИВНОМ СЛУЧАЕ ПЕРЕЙТИ В ЯЧЕЙКУ~$\beta$".
\item{$\bullet$}~сРАВНЕНИЕ $n$, $\alpha$, $\beta$. "сРАВНИТЬ ОСТАВШИЕСЯ
ЛИТЕРЫ АРГУМЕНТА С $n$~СЛОВАМИ, РАСПОЛОЖЕННЫМИ В ЯЧЕЙКАХ~$\alpha$,
$\alpha+1$,~\dots, $\alpha+n-1$. еСЛИ ПОДХОДЯЩЕЕ СЛОВО ИМЕЕТ
АДРЕС~$\alpha+k$, ПОИСК КОНЧАЕТСЯ УДАЧНО И "ЗНАЧЕНИЕ" ЛЕЖИТ В
ЯЧЕЙКЕ~$\beta+k$,
НО ЕСЛИ ПОДХОДЯЩЕГО СЛОВА НЕТ, ПОИСК КОНЧАЕТСЯ НЕУДАЧНО".
\item{$\bullet$}~рАСЩЕПЛЕНИЕ $\alpha$, $\beta$. "сЛОВО, ОБРАБОТАННОЕ ДО
ДАННОГО МЕСТА, ВОЗМОЖНО, ЯВЛЯЕТСЯ ПРИСТАВКОЙ ИЛИ ОСНОВОЙ. в ПРОДОЛЖЕНИЕ
ПОИСКА НУЖНО НАПРАВИТЬСЯ В ЯЧЕЙКУ А ЗА СЛЕДУЮЩЕЙ ИНСТРУКЦИЕЙ. еСЛИ ЭТОТ
ПОИСК НЕУДАЧЕН, НЕОБХОДИМО ПРОДОЛЖИТЬ
%%681
ПОИСК, РАССМАТРИВАЯ ОСТАВШИЕСЯ ЛИТЕРЫ АРГУМЕНТА КАК НОВЫЙ АРГУМЕНТ.
еСЛИ ЭТОТ ПОИСК УДАЧЕН, СКОМБИНИРОВАТЬ НАЙДЕННОЕ "ЗНАЧЕНИЕ" СО
"ЗНАЧЕНИЕМ"~$\beta$".
\noindent оПЕРАЦИЯ ПРОВЕРКИ РЕАЛИЗУЕТ КОНЦЕПЦИЮ ПОИСКА ПО БОРУ, А ОПЕРАЦИЯ
СРАВНЕНИЯ ОБОЗНАЧАЕТ ПЕРЕХОД К ПОСЛЕДОВАТЕЛЬНОМУ ПОИСКУ. оПЕРАЦИЯ
РАСЩЕПЛЕНИЯ СЛУЖИТ ДЛЯ ОБРАБОТКИ ПРИСТАВОК И СУФФИКСОВ. мОЖНО,
ОСНОВЫВАЯСЬ НА БОЛЕЕ ДЕТАЛЬНОМ ИЗУЧЕНИИ СПЕЦИФИЧЕСКИХ ЧЕРТ АНГЛИЙСКОГО
ЯЗЫКА, ПРЕДЛОЖИТЬ НЕКОТОРЫЕ ДРУГИЕ ОПЕРАЦИИ. дАЛЬНЕЙШАЯ ЭКОНОМИЯ ПАМЯТИ
ДОСТИГАЕТСЯ ЗА СЧЕТ ИСКЛЮЧЕНИЯ ПАРАМЕТРА~$\beta$ ИЗ КАЖДОЙ ИНСТРУКЦИИ,
ТАК КАК ПАМЯТЬ МОЖЕТ БЫТЬ ОРГАНИЗОВАНА ТАК, ЧТОБЫ $\beta$~ВЫЧИСЛЯЛОСЬ С
ПОМОЩЬЮ~$\alpha$, $n$ ИЛИ АДРЕСА ИНСТРУКЦИИ.
бОЛЕЕ ПОЛНАЯ ИНФОРМАЦИЯ ОБ ОРГАНИЗАЦИИ СЛОВАРЯ ИМЕЕТСЯ В ИНТЕРЕСНЫХ
СТАТЬЯХ сИДНЕЯ лЭМБА И уИЛЬЯМА яКОБСЕНА,~МЛ.\
[{\sl Mechanical Translation,\/} {\bf 6} (1961), 76--107]; ю.~с.~шВАРЦА
[{\sl JACM,\/} {\bf 10} (1963), 413--439]; гАЛЛИ И~яМАДЫ
[{\sl IBM Systems J.,\/} {\bf 6} (1967), 192--207].
\section бИНАРНЫЙ СЛУЧАЙ. рАССМОТРИМ ТЕПЕРЬ ЧАСТНЫЙ СЛУЧАЙ~$M=2$, КОГДА В
КАЖДЫЙ МОМЕНТ ВРЕМЕНИ ОБРАБАТЫВАЕТСЯ ОДИН БИТ АРГУМЕНТА ПОИСКА.
рАЗРАБОТАНЫ ДВА ИНТЕРЕСНЫХ МЕТОДА, ОСОБЕННО ПОДХОДЯЩИЕ ДЛЯ ДАННОГО СЛУЧАЯ.
пЕРВЫЙ МЕТОД, КОТОРЫЙ МЫ БУДЕМ НАЗЫВАТЬ \emph{ЦИФРОВЫМ ПОИСКОМ ПО ДЕРЕВУ},
ПРЕДЛОЖЕН кОФФМАНОМ И~иВОМ
[{\sl CACM,\/} {\bf 13} (1970), 427--432, 436].
тАК ЖЕ КАК И В АЛГОРИТМАХ ПОИСКА ПО ДЕРЕВУ ИЗ П.~6.2.2, В УЗЛАХ ДЕРЕВА
ХРАНЯТСЯ ПОЛНЫЕ КЛЮЧИ, НО ДЛЯ ВЫБОРА ЛЕВОЙ ИЛИ ПРАВОЙ ВЕТВИ ИСПОЛЬЗУЮТСЯ
НЕ РЕЗУЛЬТАТ СРАВНЕНИЯ КЛЮЧЕЙ, А БИТЫ АРГУМЕНТА. нА РИС.~32
ИЗОБРАЖЕНО ДЕРЕВО, ПОСТРОЕННОЕ ЭТИМ МЕТОДОМ; ОНО СОСТАВЛЕНО ИЗ
31~НАИБОЛЕЕ УПОТРЕБИТЕЛЬНОГО АНГЛИЙСКОГО СЛОВА, ПРИЧЕМ СЛОВА
ВСТАВЛЯЛИСЬ В ПОРЯДКЕ УМЕНЬШЕНИЯ ЧАСТОТ. чТОБЫ ПОЛУЧИТЬ БИНАРНЫЕ ДАННЫЕ
ДЛЯ ЭТОЙ ИЛЛЮСТРАЦИИ, СЛОВА ЗАПИСЫВАЛИСЬ В ЛИТЕРНОМ КОДЕ МАШИНЫ~\MIX\ С
ПОСЛЕДУЮЩИМ ПРЕОБРАЗОВАНИЕМ В ДВОИЧНЫЕ ЧИСЛА, СОДЕРЖАЩИЕ ПО 5~БИТОВ В
БАЙТЕ. тАКИМ ОБРАЗОМ, СЛОВО |WHICH| ПРЕВРАТИТСЯ В "11010\ 01000\ 01001\
00011\ 01000".
чТОБЫ НАЙТИ |WHICH| НА РИС.~32, МЫ СНАЧАЛА СРАВНИВАЕМ ЕГО СО СЛОВОМ~|THE|
В КОРНЕ ДЕРЕВА. тАК КАК ОНИ НЕ СОВПАДАЮТ И ПЕРВЫЙ БИТ СЛОВА~|WHICH|
РАВЕН~1, НУЖНО ИДТИ ВПРАВО И ПРОИЗВЕСТИ СРАВНЕНИЕ СО СЛОВОМ~|OF|. тАК КАК
СОВПАДЕНИЯ НЕ ПРОИЗОШЛО И ВТОРОЙ БИТ |WHICH| РАВЕН~1, МЫ ИДЕМ ВПРАВО
И СРАВНИВАЕМ НАШ АРГУМЕНТ СО СЛОВОМ |WITH| И Т.~Д.
дЕРЕВО РИС.~32 ПОСТРОЕНО СПОСОБОМ, ПОХОЖИМ НА СПОСОБ ПОСТРОЕНИЯ ДЕРЕВА
РИС.~12 ИЗ П.~6.2.2, ЛИШЬ ДЛЯ РАЗВЕТВЛЕНИЯ ВМЕСТО СРАВНЕНИЙ ИСПОЛЬЗОВАЛИСЬ
БИТЫ КЛЮЧЕЙ, ПОЭТОМУ ИНТЕРЕСНО ОТМЕТИТЬ РАЗНИЦУ МЕЖДУ НИМИ. еСЛИ
РАССМОТРЕТЬ ЗАДАННЫЕ ЧАСТОТЫ, ЦИФРОВОЙ ПОИСК ПО ДЕРЕВУ РИС.~32 ТРЕБУЕТ
%%582
В СРЕДНЕМ $3.42$~СРАВНЕНИЯ НА УДАЧНЫЙ ПОИСК; ЭТО НЕСКОЛЬКО ЛУЧШЕ, ЧЕМ
$4.04$~СРАВНЕНИЯ, ТРЕБУЮЩЕГОСЯ ДЛЯ РИС.~12, ХОТЯ, РАЗУМЕЕТСЯ, ВРЕМЯ САМОГО
СРАВНЕНИЯ БУДЕТ РАЗЛИЧНЫМ В ДВУХ ЭТИХ СЛУЧАЯХ.
\picture{рИС. 32. дЕРЕВО ЦИФРОВОГО ПОИСКА ДЛЯ 31 НАИБОЛЕЕ УПОТРЕБИТЕЛЬНОГО
АНГЛИЙСКОГО СЛОВА, СЛОВА ВСТАВЛЕНЫ В ПОРЯДКЕ УМЕНЬШЕНИЯ ЧАСТОТ.}
\alg D.(цИФРОВОЙ ПОИСК ПО ДЕРЕВУ.) эТОТ АЛГОРИТМ ПОЗВОЛЯЕТ НАЙТИ ДАННЫЙ
АРГУМЕНТ~$K$ В ТАБЛИЦЕ ЗАПИСЕЙ, ОБРАЗУЮЩИХ ОПИСАННЫМ ВЫШЕ СПОСОБОМ
БИНАРНОЕ ДЕРЕВО. еСЛИ $K$ НЕТ В ТАБЛИЦЕ, В ДЕРЕВО В ПОДХОДЯЩЕМ МЕСТЕ
ВСТАВЛЯЕТСЯ НОВЫЙ УЗЕЛ, СОДЕРЖАЩИЙ~$K$.
кАК И В АЛГОРИТМЕ~6.2.2т, ЗДЕСЬ ПРЕДПОЛАГАЕТСЯ, ЧТО ДЕРЕВО НЕПУСТО, А ЕГО
УЗЛЫ СОДЕРЖАТ ПОЛЯ~|KEY|, |LLINK| И~|RLINK|. чИТАТЕЛЬ УВИДИТ, ЧТО ЭТИ
АЛГОРИТМЫ ПОЧТИ ИДЕНТИЧНЫ.
\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $|P|\asg|ROOT|$, $K1\asg K$.
\st[сРАВНЕНИЕ.] еСЛИ $K=|KEY| (|P|)$, ПОИСК ОКАНЧИВАЕТСЯ УДАЧНО;
В ПРОТИВНОМ СЛУЧАЕ ЗАНЕСТИ В~$b$ САМЫЙ ЛЕВЫЙ БИТ~$K1$ И СДВИНУТЬ~$K1$ НА
ЕДИНИЦУ ВЛЕВО (Т.~Е.\ УДАЛИТЬ ЭТОТ БИТ И ДОБАВИТЬ СПРАВА~0). еСЛИ $b=0$,
ПЕРЕЙТИ НА~\stp{3}; В ПРОТИВНОМ СЛУЧАЕ ПЕРЕЙТИ НА~\stp{4}.
\st[шАГ ВЛЕВО.] еСЛИ $|LLINK|(|P|)\ne\NULL$, УСТАНОВИТЬ
$|P|\asg|LLINK|(|P|)$ И ВЕРНУТЬСЯ НА~\stp{2}; В ПРОТИВНОМ СЛУЧАЕ ПЕРЕЙТИ НА~\stp{5}.
\st[шАГ ВПРАВО.] еСЛИ $|RLINK|(|P|)\ne\NULL$, УСТАНОВИТЬ
$|P|\asg|RLINK|(|P|)$ И ВЕРНУТЬСЯ НА~\stp{2}.
%%583
\st[вСТАВКА В ДЕРЕВО.] вЫПОЛНИТЬ $|Q|\Asg|AVAIL|$, $|KEY|(|Q|)\asg K$,
$|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$. еСЛИ~$b=0$,
УСТАНОВИТЬ $|LLINK|(|P|)\asg |Q|$; В ПРОТИВНОМ СЛУЧАЕ $|RLINK| (|P|)\asg|Q|$.
\algend
аЛГОРИТМ~6.2.2T ПО СУТИ СВОЕЙ БИНАРНЫЙ, ОДНАКО ПРИВЕДЕННЫЙ АЛГОРИТМ, КАК
НЕТРУДНО ЗАМЕТИТЬ, МОЖНО ЛЕГКО РАСПРОСТРАНИТЬ НА $M\hbox{-АРНЫЙ}$
ЦИФРОВОЙ ПОИСК ДЛЯ ЛЮБОГО $M\ge2$ (СМ.~УПР.~13).
\picture{рИС. 33. пРИМЕР ТЕКСТА И ДЕРЕВА пАТРИЦИИ.}
дОНАЛЬД мОРРИСОН [{\sl JACM,\/} {\bf 15} (1968), 514--534] ПРИДУМАЛ ОЧЕНЬ
ПРИВЛЕКАТЕЛЬНЫЙ СПОСОБ ФОРМИРОВАНИЯ $N\hbox{-УЗЛОВЫХ}$ ДЕРЕВЬЕВ ПОИСКА,
ОСНОВАННЫЙ НА БИНАРНОМ ПРЕДСТАВЛЕНИИ КЛЮЧЕЙ, БЕЗ ЗАПОМИНАНИЯ КЛЮЧЕЙ В
УЗЛАХ. еГО МЕТОД, НАЗВАННЫЙ "пАТРИЦИЯ" (пРАКТИЧЕСКИЙ АЛГОРИТМ ДЛЯ ВЫБОРКИ
ИНФОРМАЦИИ, ЗАКОДИРОВАННОЙ БУКВАМИ И ЦИФРАМИ)\note{1}%
{в ОРИГИНАЛЕ "Patricia"---Practical Algorithm To Retrieve Information Coded
In Alphanumeric.---{\sl пРИМ. ПЕРЕВ.\/}},
ОСОБЕННО ПОДХОДИТ ДЛЯ РАБОТЫ С ОЧЕНЬ ДЛИННЫМИ КЛЮЧАМИ ПЕРЕМЕННОЙ ДЛИНЫ,
ТАКИМИ, КАК ЗАГОЛОВКИ ИЛИ ФРАЗЫ, ХРАНЯЩИЕСЯ В ФАЙЛЕ БОЛЬШОГО ОБRЕМА.
оСНОВНАЯ ИДЕЯ пАТРИЦИИ СОСТОИТ В ТОМ, ЧТОБЫ СТРОИТЬ БИНАРНОЕ ДЕРЕВО,
ИЗБЕГАЯ ОДНОПУТЕВЫХ РАЗВЕТВЛЕНИЙ, ДЛЯ ЧЕГО В КАЖДЫЙ УЗЕЛ ВКЛЮЧАЕТСЯ ЧИСЛО,
ПОКАЗЫВАЮЩЕЕ, СКОЛЬКО БИТОВ
%%584
НУЖНО ПРОПУСТИТЬ, ПЕРЕД ТЕМ КАК ДЕЛАТЬ СЛЕДУЮЩУЮ ПРОВЕРКУ. сУЩЕСТВУЕТ
НЕСКОЛЬКО СПОСОБОВ РЕАЛИЗАЦИИ ЭТОЙ ИДЕИ; ВОЗМОЖНО, ПРОСТЕЙШИЙ С ТОЧКИ
ЗРЕНИЯ ОБRЯСНЕНИЯ ИЗОБРАЖЕН НА РИС.~33. иМЕЕТСЯ МАССИВ БИТОВ |TEXT|
(ОБЫЧНО ДОВОЛЬНО ДЛИННЫЙ); ОН МОЖЕТ ХРАНИТЬСЯ ВО ВНЕШНЕМ ФАЙЛЕ С ПРЯМЫМ
ДОСТУПОМ, ТАК КАК ПРИ КАЖДОМ ПОИСКЕ ОБРАЩЕНИЕ К НЕМУ ПРОИСХОДИТ ЛИШЬ
РАЗ. кАЖДЫЙ КЛЮЧ, КОТОРЫЙ ДОЛЖЕН ХРАНИТЬСЯ В НАШЕЙ ТАБЛИЦЕ, ОПРЕДЕЛЯЕТСЯ
МЕСТОМ НАЧАЛА В ТЕКСТЕ; МОЖНО СЧИТАТЬ, ЧТО ОН ИДЕТ ОТ МЕСТА НАЧАЛА ДО
КОНЦА ТЕКСТА. (пАТРИЦИЯ НЕ ИЩЕТ ТОЧНОГО РАВЕНСТВА МЕЖДУ КЛЮЧОМ И
АРГУМЕНТОМ, А ОПРЕДЕЛЯЕТ, СУЩЕСТВУЕТ ЛИ КЛЮЧ, \emph{НАЧИНАЮЩИЙСЯ} С АРГУМЕНТА.)
в ПРИМЕРЕ, ИЗОБРАЖЕННОМ НА РИС.~33, ИМЕЕТСЯ СЕМЬ КЛЮЧЕЙ, НАЧИНАЮЩИХСЯ С
КАЖДОГО ВХОДЯЩЕГО В ТЕКСТ СЛОВА, А ИМЕННО "|THIS| |IS| |THE| |HOUSE|
|THAT| |JACK| |BUILT|.", "|IS| |THE| |HOUSE| |THAT| |JACK| |BUILT|.",
~\dots, "|BUILT|.". нАЛАГАЕТСЯ ВАЖНОЕ ОГРАНИЧЕНИЕ, СОСТОЯЩЕЕ В ТОМ, ЧТО
\emph{ОДИН КЛЮЧ НЕ МОЖЕТ СЛУЖИТЬ НАЧАЛОМ ДРУГОГО;} ЭТО УСЛОВИЕ ВЫПОЛНЯЕТСЯ,
ЕСЛИ МЫ ОКАНЧИВАЕМ ТЕКСТ СПЕЦИАЛЬНЫМ КОДОМ КОНЦА ТЕКСТА (В ДАННОМ СЛУЧАЕ
"|.|"), КОТОРЫЙ НИГДЕ БОЛЬШЕ НЕ ПОЯВЛЯЕТСЯ. тО ЖЕ ОГРАНИЧЕНИЕ
ПОДРАЗУМЕВАЕТСЯ В СХЕМЕ БОРА АЛГОРИТМА~T, ГДЕ ПРИЗНАКОМ КОНЦА СЛУЖИЛ "\] ".
дЕРЕВО, ИСПОЛЬЗУЕМОЕ пАТРИЦИЕЙ ДЛЯ ПОИСКА, ДОЛЖНО ЦЕЛИКОМ ПОМЕЩАТЬСЯ В
ОПЕРАТИВНОЙ ПАМЯТИ, ИЛИ ЕГО НУЖНО ОРГАНИЗОВАТЬ ПО СТРАНИЧНОЙ СХЕМЕ,
ОПИСАННОЙ В П.~6.2.4. оНО СОСТОИТ ИЗ ГОЛОВЫ И $N-1$~УЗЛОВ, ПРИЧЕМ УЗЛЫ
СОДЕРЖАТ НЕСКОЛЬКО ПОЛЕЙ:
\medskip
{\narrower
\noindent|KEY|---УКАЗАТЕЛЬ НА ТЕКСТ. эТО ПОЛЕ ДОЛЖНО ИМЕТЬ ДЛИНУ НЕ МЕНЕЕ
$\log_2 C$~БИТОВ, ГДЕ $C$---ЧИСЛО ЛИТЕР В ТЕКСТЕ. сЛОВА, ИЗОБРАЖЕННЫЕ НА
РИС.~33 ВНУТРИ УЗЛОВ, НА САМОМ ДЕЛЕ ДОЛЖНЫ БЫТЬ ПРЕДСТАВЛЕНЫ УКАЗАТЕЛЯМИ
НА ТЕКСТ; НАПРИМЕР, ВМЕСТО "|(JACK)|" УЗЕЛ СОДЕРЖИТ ЧИСЛО~24
(НАЧАЛЬНУЮ ТОЧКУ КЛЮЧА "|JACK BUILT|.").
\noindent|LLINK| И~|RLINK|---ССЫЛКИ ВНУТРИ ДЕРЕВА. оНИ ДОЛЖНЫ ИМЕТЬ ДЛИНУ НЕ
МЕНЕЕ $\log_2 N$~БИТОВ.
\noindent|LTAG| И~|RTAG|---ОДНОБИТОВЫЕ ПОЛЯ, ПО КОТОРЫМ МЫ МОЖЕМ СУДИТЬ,
ЯВЛЯЮТСЯ ЛИ |LLINK| И~|RLINK| СООТВЕТСТВЕННО ССЫЛКАМИ НА СЫНОВЕЙ ИЛИ НА
ПРЕДКОВ. пУНКТИРНЫЕ ЛИНИИ НА РИС.~33 СООТВЕТСТВУЮТ ССЫЛКАМ, ДЛЯ КОТОРЫХ $|TAG|=1$.
\noindent|SKIP|---ЧИСЛО БИТОВ, КОТОРЫЕ НУЖНО ПРОПУСТИТЬ ПРИ ПОИСКЕ, КАК
ОБRЯСНЯЛОСЬ ВЫШЕ. эТО ПОЛЕ ДОЛЖНО БЫТЬ ДОСТАТОЧНО БОЛЬШИМ ДЛЯ ТОГО, ЧТОБЫ
ВМЕСТИТЬ НАИБОЛЬШЕЕ ЧИСЛО~$k$, ДЛЯ КОТОРОГО В ДВУХ РАЗЛИЧНЫХ КЛЮЧАХ
НАЙДУТСЯ СОВПАДАЮЩИЕ ПОДЦЕПОЧКИ ИЗ $k$~БИТОВ; ОБЫЧНО ДЛЯ
ПРАКТИЧЕСКИХ ЦЕЛЕЙ ДОСТАТОЧНО СЧИТАТЬ, ЧТО $k$ НЕ СЛИШКОМ ВЕЛИКО, И
ПРИ ПРЕВЫШЕНИИ РАЗМЕРОВ ПОЛЯ |SKIP| ВЫДАВАТЬ СООБЩЕНИЕ ОБ
%%585
ОШИБКЕ. нА РИС.~33 ПОЛЯ |SKIP| ИЗОБРАЖЕНЫ ВНУТРИ КАЖДОГО УЗЛА ЧИСЛАМИ.
\par}
гОЛОВА СОДЕРЖИТ ЛИШЬ ПОЛЯ KEY, LLINK И LTAG.\medskip
пОИСК В ДЕРЕВЕ пАТРИЦИИ ВЫПОЛНЯЕТСЯ СЛЕДУЮЩИМ ОБРАЗОМ:
ПРЕДПОЛОЖИМ, МЫ ИЩЕМ СЛОВО~|THAT| (БИНАРНОЕ ПРЕДСТАВЛЕНИЕ $10111\ 01000\
00001\ 10111$). пО СОДЕРЖИМОМУ ПОЛЯ |SKIP| В КОРНЕВОМ УЗЛЕ~$\alpha$ МЫ
ЗАКЛЮЧАЕМ, ЧТО СНАЧАЛА НУЖНО ПРОВЕРИТЬ ПЕРВЫЙ БИТ АРГУМЕНТА. оН РАВЕН~1,
ПОЭТОМУ НАДО ДВИГАТЬСЯ ВПРАВО. пОЛЕ |SKIP| СЛЕДУЮЩЕГО УЗЛА ПОБУЖДАЕТ НАС
ПРОВЕРИТЬ $1+11=12\hbox{-Й}$~БИТ АРГУМЕНТА. оН РАВЕН~0, И МЫ ИДЕМ ВЛЕВО.
иЗУЧИВ ПОЛЕ |SKIP| СЛЕДУЮЩЕГО УЗЛА, ВИДИМ, ЧТО НУЖНО ПРОВЕРИТЬ
$12+1=13\hbox{-Й}$~БИТ, КОТОРЫЙ РАВЕН~0. тАК КАК $|LTAG|=1$, МЫ ИДЕМ НА
УЗЕЛ~$\gamma$, КОТОРЫЙ ОТСЫЛАЕТ НАС К МАССИВУ |TEXT|. пО ТОМУ ЖЕ ПУТИ
ПОЙДЕТ ПОИСК ДЛЯ ЛЮБОГО АРГУМЕНТА, ИМЕЮЩЕГО БИНАРНОЕ ПРЕДСТАВЛЕНИЕ $1xxxx\
xxxxx\ x00~\ldots$, ПОЭТОМУ НУЖНО СРАВНИТЬ АРГУМЕНТ С НАЙДЕННЫМ КЛЮЧОМ.
пРЕДПОЛОЖИМ, С ДРУГОЙ СТОРОНЫ, ЧТО МЫ ИЩЕМ НЕКОТОРЫЙ КЛЮЧ, НАЧИНАЮЩИЙСЯ
С~|TH|, ИЛИ ВСЕ ТАКИЕ КЛЮЧИ. пОИСК НАЧИНАЕТСЯ, КАК И РАНЬШЕ, НО В КОНЦЕ
КОНЦОВ МЫ ОБРАТИМСЯ К (НЕСУЩЕСТВУЮЩЕМУ) 12-МУ~БИТУ ДЕСЯТИБИТОВОГО
АРГУМЕНТА. тЕПЕРЬ НУЖНО СРАВНИТЬ АРГУМЕНТ С ФРАГМЕНТОМ МАССИВА |TEXT|,
КОТОРЫЙ СПЕЦИФИЦИРУЕТСЯ В ТЕКУЩЕМ УЗЛЕ (В ДАННОМ СЛУЧАЕ~$\gamma$);
ЕСЛИ СОВПАДЕНИЯ НЕ ПРОИЗОШЛО, ТО НЕ СУЩЕСТВУЕТ КЛЮЧА, НАЧАЛОМ КОТОРОГО
СЛУЖИТ АРГУМЕНТ ПОИСКА; ЕСЛИ СОВПАДЕНИЕ ИМЕЛО МЕСТО, АРГУМЕНТ ЯВЛЯЕТСЯ
НАЧАЛОМ ЛЮБОГО КЛЮЧА, НА КОТОРЫЙ УКАЗЫВАЮТ ПУНКТИРНЫЕ ЛИНИИ, ВЫХОДЯЩИЕ
ИЗ УЗЛА~$\gamma$ И ЕГО ПОТОМКОВ.
бОЛЕЕ ТОЧНО ЭТОТ ПРОЦЕСС ОПИСЫВАЕТСЯ СЛЕДУЮЩИМ ОБРАЗОМ.
\alg P.(пАТРИЦИЯ.) аЛГОРИТМ, ИСПОЛЬЗУЯ МАССИВ |TEXT| И ДЕРЕВО С ОПИСАННЫМИ
ВЫШЕ ПОЛЯМИ |KEY|, |LLINK|, |RLINK|, |LTAG|, |RTAG| И~|SKIP| В УЗЛАХ,
ПОЗВОЛЯЕТ ОПРЕДЕЛИТЬ, СУЩЕСТВУЕТ ЛИ В МАССИВЕ |TEXT| КЛЮЧ, НАЧИНАЮЩИЙСЯ
С АРГУМЕНТА~$K$. (еСЛИ ИМЕЕТСЯ $r\ge1$ ТАКИХ КЛЮЧЕЙ, МОЖНО ЗА $O(r)$~ШАГОВ
ОПРЕДЕЛИТЬ РАСПОЛОЖЕНИЕ КАЖДОГО ИЗ НИХ; СМ.~УПР.~14.) пРЕДПОЛАГАЕТСЯ,
ЧТО ЕСТЬ ПО КРАЙНЕЙ МЕРЕ ОДИН КЛЮЧ.
\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $|P|\asg|HEAD|$
И~$j\asg0$ (пЕРЕМЕННАЯ~|P| ЯВЛЯЕТСЯ УКАЗАТЕЛЕМ, КОТОРЫЙ БУДЕТ ДВИГАТЬСЯ
ВНИЗ ПО ДЕРЕВУ, А $j$---ЭТО СЧЕТЧИК, ОПРЕДЕЛЯЮЩИЙ ПОЗИЦИИ БИТОВ АРГУМЕНТА.)
зАНЕСТИ В $n$ КОЛИЧЕСТВО БИТОВ АРГУМЕНТА~$K$.
\st[шАГ ВЛЕВО.] уСТАНОВИТЬ $|Q|\asg|P|$ И~$|P|\asg|LLINK| (|Q|)$. еСЛИ
$|LTAG|(|Q|)=1$, ПЕРЕЙТИ НА~\stp{6}.
\st[пРОПУСК БИТОВ.] (в ЭТОТ МОМЕНТ МЫ ЗНАЕМ, ЧТО, ЕСЛИ ПЕРВЫЕ $j$~БИТОВ
АРГУМЕНТА СООТВЕТСТВУЮТ НЕКОТОРОМУ КЛЮЧУ, ОНИ СООТВЕТСТВУЮТ КЛЮЧУ,
НАЧИНАЮЩЕМУСЯ В~$|KEY|(|P|)$.) уСТАНОВИТЬ $j\asg j+|SKIP|(|P|)$.
еСЛИ~$j>n$, ПЕРЕЙТИ НА~\stp{6}.
%%586
\st[пРОВЕРКА БИТА.] в ЭТОТ МОМЕНТ МЫ ЗНАЕМ, ЧТО, ЕСЛИ ПЕРВЫЕ $(j-1)$~БИТОВ
СООТВЕТСТВУЮТ НЕКОТОРОМУ КЛЮЧУ, ОНИ СООТВЕТСТВУЮТ КЛЮЧУ, НАЧИНАЮЩЕМУСЯ
В~$|KEY|(|P|)$. еСЛИ $j\hbox{-Й}$~БИТ~$K$ РАВЕН~0, ПЕРЕЙТИ НА~\stp{2}; В
ПРОТИВНОМ СЛУЧАЕ ПЕРЕЙТИ НА~\stp{5}.
\st[шАГ ВПРАВО.] уСТАНОВИТЬ $|Q|\asg|P|$ И~$|P|\asg|RLINK|(|Q|)$.
еСЛИ~$|RTAG|(|Q|)=0$, ПЕРЕЙТИ НА~\stp{3}.
\st[сРАВНЕНИЕ.] (в ЭТОТ МОМЕНТ МЫ ЗНАЕМ, ЧТО, ЕСЛИ~$K$ СООТВЕТСТВУЕТ
НЕКОТОРОМУ КЛЮЧУ, ОН СООТВЕТСТВУЕТ КЛЮЧУ, НАЧИНАЮЩЕМУСЯ В~$|KEY|(|P|)$.)
сРАВНИТЬ~$K$ С КЛЮЧОМ, НАЧИНАЮЩИМСЯ В ПОЗИЦИИ~$|KEY|(|P|)$
МАССИВА~|TEXT|. еСЛИ ПРОИЗОШЛО СОВПАДЕНИЕ $n$~ПЕРВЫХ БИТОВ, АЛГОРИТМ
ЗАКАНЧИВАЕТСЯ УДАЧНО;
В СЛУЧАЕ НЕСОВПАДЕНИЯ ОН ЗАКАНЧИВАЕТСЯ НЕУДАЧНО.
\algend
в УПР.~15 ПРЕЖДЕ ВСЕГО ПОКАЗАНО, КАК МОЖНО ОСУЩЕСТВИТЬ ПОСТРОЕНИЕ ДЕРЕВА
пАТРИЦИИ. иМЕЕТСЯ ТАКЖЕ ВОЗМОЖНОСТЬ ДОБАВЛЯТЬ К ТЕКСТУ И ВСТАВЛЯТЬ НОВЫЕ
КЛЮЧИ ПРИ УСЛОВИИ, ЧТО НОВЫЙ ТЕКСТОВОЙ МАТЕРИАЛ ОКАНЧИВАЕТСЯ ОПРЕДЕЛЕННЫМ
РАЗДЕЛИТЕЛЕМ (НАПРИМЕР, СИМВОЛОМ КОНЦА ТЕКСТА, ЗА КОТОРЫМ
СЛЕДУЕТ ПОРЯДКОВЫЙ НОМЕР).
хАРАКТЕР пАТРИЦИИ СЛЕГКА ПРИЧУДЛИВ, И ВСЕ ЕЕ ДОСТОИНСТВА ЗАМЕТНЫ ЛИШЬ
ВНИМАТЕЛЬНОМУ НАБЛЮДАТЕЛЮ.
\section аНАЛИЗ АЛГОРИТМОВ. зАВЕРШИМ ЭТОТ РАЗДЕЛ МАТЕМАТИЧЕСКИМ
ИЗУЧЕНИЕМ БОРОВ, ДЕРЕВЬЕВ ЦИФРОВОГО ПОИСКА И пАТРИЦИИ. вАЖНЕЙШИЕ
ВЫВОДЫ ИЗ ЭТОГО АНАЛИЗА ПРИВЕДЕНЫ В САМОМ КОНЦЕ.
\picture{рИС. 34. пРИМЕР СЛУЧАЙНОГО БИНАРНОГО БОРА.}
рАССМОТРИМ СНАЧАЛА БИНАРНЫЕ БОРЫ, Т.~Е.~БОРЫ С~$M=2$. нА РИС.~34 ИЗОБРАЖЕН
БИНАРНЫЙ БОР, ОБРАЗУЮЩИЙСЯ, ЕСЛИ 16~КЛЮЧЕЙ ИЗ ПРИМЕРОВ СОРТИРОВКИ ГЛ.~5
РАССМАТРИВАТЬ КАК ДЕСЯТИБИТОВЫЕ ДВОИЧНЫЕ ЧИСЛА. (кЛЮЧИ ПРИВЕДЕНЫ В
ВОСЬМЕРИЧНОЙ
%%587
ЗАПИСИ, ТАК ЧТО, НАПРИМЕР, $1144$ ПРЕДСТАВЛЯЕТ ДЕСЯТИБИТОВОЕ ЧИСЛО
$(1001100100)_2$.) кАК И В АЛГОРИТМЕ~T, МЫ ИСПОЛЬЗУЕМ БОР ДЛЯ ХРАНЕНИЯ
ИНФОРМАЦИИ О ЛЕВЫХ БИТАХ КЛЮЧЕЙ ДО ТЕХ ПОР, ПОКА ВПЕРВЫЕ ДОСТИГАЕТСЯ ТОЧКА,
ГДЕ КЛЮЧ ОПРЕДЕЛЯЕТСЯ ОДНОЗНАЧНО; ТАМ ОН ЗАПИСЫВАЕТСЯ ПОЛНОСТЬЮ.
еСЛИ СРАВНИТЬ РИС.~34 С ТАБЛ.~5.2.2-3, ОБНАРУЖИТСЯ УДИВИТЕЛЬНАЯ
ВЗАИМОСВЯЗЬ МЕЖДУ БОРОВОЙ ПАМЯТЬЮ И ОБМЕННОЙ ПОРАЗРЯДНОЙ СОРТИРОВКОЙ.
(вОЗМОЖНО, ЭТА ВЗАИМОСВЯЗЬ ЯВЛЯЕТСЯ ОЧЕВИДНОЙ.) 22~УЗЛА РИС.~34 В ТОЧНОСТИ
СООТВЕТСТВУЮТ 22~СТАДИЯМ РАСЧЛЕНЕНИЯ В ТАБЛ.~5.2.2-3 (УЗЛЫ СЛЕДУЕТ
НУМЕРОВАТЬ В ПРЯМОМ ПОРЯДКЕ). чИСЛО ПРОВЕРЯЕМЫХ БИТОВ В СТАДИИ
РАСЧЛЕНЕНИЯ РАВНО ЧИСЛУ КЛЮЧЕЙ В СООТВЕТСТВУЮЩЕМ УЗЛЕ-И ЕГО ПОДБОРАХ;
ТАКИМ ОБРАЗОМ, МОЖНО СФОРМУЛИРОВАТЬ СЛЕДУЮЩИЙ РЕЗУЛЬТАТ.
\proclaim тЕОРЕМА T. еСЛИ $N$ РАЗЛИЧНЫХ ДВОИЧНЫХ ЧИСЕЛ ПОМЕЩЕНЫ В
БИНАРНЫЙ БОР, КАК ОПИСАНО ВЫШЕ, ТО (i)~ЧИСЛО УЗЛОВ БОРА РАВНО ЧИСЛУ СТАДИЙ
РАСЧЛЕНЕНИЯ, НУЖНЫХ ПРИ ОБМЕННОЙ ПОРАЗРЯДНОЙ СОРТИРОВКЕ ЭТИХ ЧИСЕЛ;
(ii)~СРЕДНЕЕ ЧИСЛО ПРОВЕРОК БИТОВ, ТРЕБУЕМЫХ ДЛЯ ВЫБОРКИ КЛЮЧА С ПОМОЩЬЮ
АЛГОРИТМА~T, РАВНО~$1/N$, УМНОЖЕННОМУ НА ЧИСЛО ПРОВЕРОК БИТОВ ПРИ.
ОБМЕННОЙ ПОРАЗРЯДНОЙ СОРТИРОВКЕ.\endmark
бЛАГОДАРЯ ТЕОРЕМЕ МЫ МОЖЕМ ИСПОЛЬЗОВАТЬ ВЕСЬ МАТЕМАТИЧЕСКИЙ АППАРАТ,
РАЗВИТЫЙ В П.~5.2.2 ДЛЯ ОБМЕННОЙ ПОРАЗРЯДНОЙ СОРТИРОВКИ. пРЕДПОЛОЖИМ,
НАПРИМЕР, ЧТО КЛЮЧАМИ ЯВЛЯЮТСЯ СЛУЧАЙНЫЕ, РАВНОМЕРНО РАСПРЕДЕЛЕННЫЕ
МЕЖДУ~0 И~1 ВЕЩЕСТВЕННЫЕ ЧИСЛА, ПРЕДСТАВЛЕННЫЕ С БЕСКОНЕЧНОЙ ТОЧНОСТЬЮ.
тОГДА КОЛИЧЕСТВО ПРОВЕРОК БИТОВ, НЕОБХОДИМЫХ ДЛЯ ВЫБОРКИ ИНФОРМАЦИИ,
БУДЕТ РАВНО~$\log_2 N+\gamma/(\ln2)+1/2+f(N)+O(N^{-1})$, А ЧИСЛО УЗЛОВ
БОРА СОСТАВИТ~$N/(\ln2)+Ng(N)+O(1)$. зДЕСЬ~$f(N)$ И~$g(N)$---СЛОЖНЫЕ ФУНКЦИИ,
КОТОРЫМИ МОЖНО ПРЕНЕБРЕЧЬ, ТАК КАК ИХ ЗНАЧЕНИЯ ВСЕГДА МЕНЬШЕ~$10^{-6}$
(СМ.~УПР.~5.2.2-38,48).
рАЗУМЕЕТСЯ, ПЕРЕД НАМИ СТОИТ БОЛЕЕ ТРУДНАЯ ЗАДАЧА: ОБОБЩИТЬ ПОЛУЧЕННЫЕ
РЕЗУЛЬТАТЫ НА СЛУЧАЙ $M\hbox{-АРНЫХ}$ БОРОВ. мЫ ОПИШЕМ ЛИШЬ ОТПРАВНУЮ
ТОЧКУ ИССЛЕДОВАНИЙ, ОСТАВЛЯЯ ПОУЧИТЕЛЬНЫЕ ДЕТАЛИ В КАЧЕСТВЕ УПРАЖНЕНИЙ.
пУСТЬ $A_N$---СРЕДНЕЕ ЧИСЛО УЗЛОВ В СЛУЧАЙНОМ $M\hbox{-АРНОМ}$ БОРУ ПОИСКА,
СОДЕРЖАЩЕМ $N$~КЛЮЧЕЙ. тОГДА $A_0=A_1=0$, А ДЛЯ $N\ge2$ МЫ ИМЕЕМ
$$
A_N=1+\sum_{k_1+\cdots+k_M=N}\left({N!\over k_1!\ldots k_M!}
M^{-N}\right)(A_{k_1}+\cdots+A_{k_M}),
\eqno(3)
$$
ТАК КАК $N!M^{-N}/k_1!\ldots k_M!$~ЕСТЬ ВЕРОЯТНОСТЬ ТОГО, ЧТО $k_1$~КЛЮЧЕЙ
СОДЕРЖИТСЯ В ПЕРВОМ ПОДБОРУ,~\dots, $k_M$---В~$M\hbox{-М}$. вОСПОЛЬЗОВАВШИСЬ
СООБРАЖЕНИЯМИ СИММЕТРИИ И ПРОВЕДЯ СУММИРОВАНИЕ ПО
%%588
$k_2$,~\dots, $k_M$, ПЕРЕПИШЕМ ЭТО СООТНОШЕНИЕ ТАК:
$$
\eqalignno{
A_N&=1+M^{1-N}\sum_{k_1+\cdots+k_M=N}
\left({N!\over k_1!\ldots k_M!}\right) A_{k_1}=\cr
&=1+M^{1-N}\sum_k\perm{N}{k}(M-1)^{N-k}A_k, \qquad N\ge2.&(4)\cr
}
$$
аНАЛОГИЧНО, ЕСЛИ ЧЕРЕЗ $C_N$~ОБОЗНАЧИТЬ СРЕДНЕЕ СУММАРНОЕ КОЛИЧЕСТВО
ПРОВЕРОК БИТОВ, НУЖНЫХ ДЛЯ ПОИСКА В БОРУ ВСЕХ $N$~КЛЮЧЕЙ, ТО
$C_0=C_1=0$, А
$$
C_N=N+M^{1-N}\sum_k\perm{N}{k}(M-1)^{N-k} C_k,\qquad N\ge 2.
\eqno (5)
$$
в УПР.~17 ПОКАЗАНО, КАК РАБОТАТЬ С РЕКУРРЕНТНЫМИ СООТНОШЕНИЯМИ ТАКОГО
ВИДА, А В УПР.~18--25 РАЗРАБАТЫВАЕТСЯ СООТВЕТСТВУЮЩАЯ ТЕОРИЯ СЛУЧАЙНЫХ
БОРОВ. [с ДРУГОЙ ТОЧКИ ЗРЕНИЯ К АНАЛИЗУ~$A_N$ ВПЕРВЫЕ ПОДОШЛИ
л.~р.~дЖОНСОН И м.~мАК-эНДРЮ [{\sl IBM J.~Res.~and~Devel.,\/} {\bf 8}
(1964), 189--193] В СВЯЗИ С ЭКВИВАЛЕНТНЫМ АППАРАТНО-ОРИЕНТИРОВАННЫМ
АЛГОРИТМОМ СОРТИРОВКИ.]
пЕРЕХОДЯ ТЕПЕРЬ К ИЗУЧЕНИЮ ДЕРЕВЬЕВ ЦИФРОВОГО ПОИСКА, МЫ ОБНАРУЖИВАЕМ, ЧТО,
С ОДНОЙ СТОРОНЫ, ФОРМУЛЫ ПОХОЖИ, А С ДРУГОЙ---ДОСТАТОЧНО РАЗЛИЧНЫ, И СРАЗУ
НЕ ЯСНО, КАК ИССЛЕДОВАТЬ АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ. нАПРИМЕР, ЕСЛИ $\bar
C_N$~ОБОЗНАЧАЕТ СРЕДНЕЕ СУММАРНОЕ КОЛИЧЕСТВО ПРОВЕРОК БИТОВ,
ПРОИЗВОДИМЫХ ПРИ ПОИСКЕ ВСЕХ $N$~КЛЮЧЕЙ В БИНАРНОМ ДЕРЕВЕ ЦИФРОВОГО ПОИСКА,
НЕТРУДНО ВЫВЕСТИ, КАК И РАНЬШЕ, ЧТО $\bar C_0=\bar C_1=0$ И
$$
\bar C_{N+1}=N+M^{1-N}\sum_k\perm{N}{k}(M-1)^{N-k}\bar C_k,
\qquad N\ge0.
\eqno(6)
$$
эТО ПОЧТИ ИДЕНТИЧНО ВЫРАЖЕНИЮ~(5), НО ПОЯВЛЕНИЯ $N+1$ ВМЕСТО~$N$ В ЛЕВОЙ,
ЧАСТИ УРАВНЕНИЯ ДОСТАТОЧНО ДЛЯ ТОГО, ЧТОБЫ ИЗМЕНИТЬ ОБЩИЙ ХАРАКТЕР
РЕКУРРЕНТНОСТИ, ТАК ЧТО МЕТОДЫ, ИСПОЛЬЗУЕМЫЕ ДЛЯ ИЗУЧЕНИЯ~(5), В ДАННОМ
СЛУЧАЕ НЕПРИГОДНЫ.
рАССМОТРИМ СНАЧАЛА БИНАРНЫЙ СЛУЧАЙ. нА РИС.~35 ИЗОБРАЖЕНО ДЕРЕВО ЦИФРОВОГО
ПОИСКА, СООТВЕТСТВУЮЩЕЕ 16~КЛЮЧАМ РИС.~34, ВСТАВЛЕННЫМ В ПОРЯДКЕ,
ИСПОЛЬЗОВАННОМ В ПРИМЕРАХ ИЗ ГЛ.~5. сРЕДНЕЕ ЧИСЛО ПРОВЕРОК БИТОВ ПРИ
СЛУЧАЙНОМ УДАЧНОМ ПОИСКЕ НАЙТИ ЛЕГКО---ОНО РАВНО ДЛИНЕ ВНУТРЕННЕГО ПУТИ
ДЕРЕВА, ДЕЛЕННОЙ НА~$N$, ТАК КАК НУЖНО $l$~ПРОВЕРОК, ЧТОБЫ НАЙТИ УЗЕЛ,
РАСПОЛОЖЕННЫЙ НА УРОВНЕ~$l$. зАМЕТИМ, ОДНАКО, ЧТО СРЕДНЕЕ ЧИСЛО ПРОВЕРОК
БИТОВ ПРИ СЛУЧАЙНОМ \emph{НЕУДАЧНОМ} ПОИСКЕ \emph{НЕ ТАК} ПРОСТО СВЯЗАНО С
ДЛИНОЙ ВНЕШНЕГО ПУТИ ДЕРЕВА, ИБО НЕУДАЧНЫЙ ПОИСК С БОЛЬШЕЙ ВЕРОЯТНОСТЬЮ
ОКАНЧИВАЕТСЯ ВБЛИЗИ КОРНЯ; НАПРИМЕР, ВЕРОЯТНОСТЬ ДОСТИЖЕНИЯ ЛЕВОЙ ВЕТВИ
УЗЛА~$0075$ (РИС.~35) РАВНА~$1/8$ (РАССМАТРИВАЮТСЯ БЕСКОНЕЧНО ТОЧНЫЕ
КЛЮЧИ), А В ЛЕВУЮ ВЕТВЬ
%%589
УЗЛА~$0232$ МЫ ПОПАДАЕМ С ВЕРОЯТНОСТЬЮ, РАВНОЙ ЛИШЬ~$1/32$. (пО ЭТОЙ
ПРИЧИНЕ ПРИ РАВНОМЕРНОМ РАСПРЕДЕЛЕНИИ КЛЮЧЕЙ ДЕРЕВЬЯ ЦИФРОВОГО ПОИСКА,
КАК ПРАВИЛО, ЛУЧШЕ СБАЛАНСИРОВАНЫ, ЧЕМ БИНАРНЫЕ ДЕРЕВЬЯ ПОИСКА,
ИСПОЛЬЗОВАВШИЕСЯ В АЛГОРИТМЕ~6.2.2T.)
дЛЯ ОПИСАНИЯ СООТВЕТСТВУЮЩИХ ХАРАКТЕРИСТИК ДЕРЕВЬЕВ ЦИФРОВОГО ПОИСКА
МОЖНО ИСПОЛЬЗОВАТЬ ПРОИЗВОДЯЩУЮ ФУНКЦИЮ. пУСТЬ НА УРОВНЕ~$l$ РАСПОЛОЖЕНО
$a_l$~УЗЛОВ; РАССМОТРИМ ПРОИЗВОДЯЩУЮ ФУНКЦИЮ~$a(z)=\sum a_l z^l$.
нАПРИМЕР, РИС.~35 СООТВЕТСТВУЕТ
\picture{рИС. 35 сЛУЧАЙНОЕ ДЕРЕВО ЦИФРОВОГО ПОИСКА, ПОСТРОЕННОЕ С ПОМОЩЬЮ
АЛГОРИТМА D.}
ФУНКЦИЯ~$a(z)=1+2z+4z^2+5z^3+4z^4$. еСЛИ $b_l$~УЗЛОВ УРОВНЯ~$l$ ЯВЛЯЮТСЯ
ВНЕШНИМИ И~$b(z)=\sum b_l z^l$, ТО В СИЛУ УПР.~6.2.1-25 ИМЕЕМ
$$
b(z)=1+(2z-1)a(z).
\eqno(7)
$$
нАПРИМЕР, $1+(2z-1)(1+2z+4z^2+5z^3+4z^4)=3z^3+6z^4+8z^5$. сРЕДНЕЕ ЧИСЛО
ПРОВЕРОК БИТОВ ПРИ СЛУЧАЙНОМ УДАЧНОМ ПОИСКЕ РАВНО~$a'(1)/a(l)$, ТАК КАК
$a'(1)$~ЕСТЬ ДЛИНА ВНУТРЕННЕГО ПУТИ ДЕРЕВА, А $a(1)$---КОЛИЧЕСТВО ВНУТРЕННИХ
УЗЛОВ. сРЕДНЕЕ ЧИСЛО ПРОВЕРОК БИТОВ ДЛЯ СЛУЧАЙНОГО \emph{НЕУДАЧНОГО}
ПОИСКА
РАВНО~$\sum l b_l 2^{-l}={1\over2}b'\left({1\over2}\right)=
a\left({1\over2}\right)$, ТАК КАК МЫ ДОСТИГАЕМ ДАННОГО
ВНЕШНЕГО УЗЛА УРОВНЯ~$l$ С ВЕРОЯТНОСТЬЮ~$2^{-l}$. пРИ НЕУДАЧНОМ ПОИСКЕ
ЧИСЛО СРАВНЕНИЙ СОВПАДАЕТ С ЧИСЛОМ ПРОВЕРОК БИТОВ, А ПРИ "УДАЧНОМ"---НА
ЕДИНИЦУ БОЛЬШЕ ЭТОГО ЧИСЛА. дЛЯ ДЕРЕВА
РИС.~35 УДАЧНЫЙ ПОИСК В СРЕДНЕМ ТРЕБУЕТ $2{9\over16}$~ПРОВЕРОК БИТОВ
И~$3{9\over16}$~СРАВНЕНИЙ; В ПРОЦЕССЕ НЕУДАЧНОГО ПОИСКА
ПРОИЗВОДИТСЯ $3{7\over8}$~СРАВНЕНИЙ И ПРОВЕРОК (В СРЕДНЕМ).
%%590
вВЕДЕМ ТЕПЕРЬ "УСРЕДНЕННУЮ" ПО ВСЕМ ДЕРЕВЬЯМ С $N$~УЗЛАМИ ФУНКЦИЮ~$a(z)$ И
ОБОЗНАЧИМ ЕЕ ЧЕРЕЗ~$g_N(z)$. иНЫМИ СЛОВАМИ, $g_N(z)=\sum p_T a_T(z)$, ГДЕ
СУММА БЕРЕТСЯ ПО ВСЕМ БИНАРНЫМ ДЕРЕВЬЯМ ЦИФРОВОГО ПОИСКА~$T$ С
$N$~ВНУТРЕННИМИ УЗЛАМИ; $a_T(z)$ ЕСТЬ ПРОИЗВОДЯЩАЯ ФУНКЦИЯ ДЛЯ
ВНУТРЕННИХ УЗЛОВ~$T$, А $p_T$~ЕСТЬ ВЕРОЯТНОСТЬ ТОГО, ЧТО ПРИ ВСТАВКЕ
$N$~СЛУЧАЙНЫХ ЧИСЕЛ С ПОМОЩЬЮ АЛГОРИТМА~D ПОЛУЧАЕТСЯ ДЕРЕВО~$T$. тАКИМ
ОБРАЗОМ, ДЛЯ УДАЧНОГО ПОИСКА СРЕДНЕЕ ЧИСЛО ПРОВЕРОК БИТОВ
РАВНО~$g'_N(1)/N$, А ДЛЯ
НЕУДАЧНОГО---$g_N\left({1\over2}\right)$.
иМИТИРУЯ ПРОЦЕСС ПОСТРОЕНИЯ ДЕРЕВА, $g_N(z)$ МОЖНО ВЫЧИСЛИТЬ СЛЕДУЮЩИМ
ОБРАЗОМ. еСЛИ $a(z)$ ЕСТЬ ПРОИЗВОДЯЩАЯ ФУНКЦИЯ ДЛЯ ДЕРЕВА С $N$~УЗЛАМИ,
МОЖНО ОБРАЗОВАТЬ $N+1$~ДЕРЕВЬЕВ, ДЕЛАЯ ВСТАВКУ В ПОЗИЦИЮ ЛЮБОГО ВНЕШНЕГО
УЗЛА. эТА ВСТАВКА ПРОИЗВОДИТСЯ В ДАННЫЙ ВНЕШНИЙ УЗЕЛ УРОВНЯ~$l$ С
ВЕРОЯТНОСТЬЮ~$2^{-l}$; СЛЕДОВАТЕЛЬНО, СУММА ПРОИЗВОДЯЩИХ ФУНКЦИЙ ДЛЯ
$N+1$~НОВЫХ ДЕРЕВЬЕВ, УМНОЖЕННЫХ НА ВЕРОЯТНОСТЬ ИХ ПОЯВЛЕНИЯ, РАВНА
$a(z)+b\left({1\over2}z\right)=a(z)+1 +(z-1)a\left({1\over2}z\right)$.
уСРЕДНЯЯ ПО ВСЕМ ДЕРЕВЬЯМ С $N$~УЗЛАМИ, ПОЛУЧАЕМ
$$
g_{N+1}(z)=g_N(z)+1+(z-1)g_N\left({1\over2}z\right);\qquad
g_0(z)=0.
\eqno(8)
$$
с СООТВЕТСТВУЮЩЕЙ ПРОИЗВОДЯЩЕЙ ФУНКЦИЕЙ ДЛЯ ВНЕШНИХ
УЗЛОВ $h_N(z)=1+(2z-1)g_N(z)$ РАБОТАТЬ НЕСКОЛЬКО ЛЕГЧЕ, ТАК КАК
(8)~ЭКВИВАЛЕНТНО ФОРМУЛЕ
$$
h_{N+1}(z)=h_N(z)+(2z-1)h_N\left({1\over2}z\right);
h_0(z)=1.
\eqno(9)
$$
мНОГОКРАТНО ПРИМЕНЯЯ ЭТО ПРАВИЛО, НАХОДИМ, ЧТО
$$
\eqalign{
& h_{N+1}(z)=\cr
&=h_{N-1}(z)+2(2z-1)h_{N-1}\left({1\over2}\right)+(2z-1(z-1)h_{N-1}
\left({1\over4}z\right)=\cr
&=h_{N-2}(z)+3(2z-1)h_{N-2}\left({1\over2}\right)+3(2z-l)(z-l)h_{N-2}
\left({1\over4}z\right)+\cr
&\phantom{=}+(2z-1)(z-1)
\left({1\over2}-1\right)h_{N-2}
\left({1\over8}z\right)\cr
}
$$
И Т.~Д.; ОКОНЧАТЕЛЬНО ИМЕЕМ
$$
\eqalignno{
h_N(z)&=\sum_k\perm{N}{k}\prod_{0\le j<k} (2^{1-j}z-1); & (10)\cr
g_N(z)&=\sum_{k\ge0}\perm{N}{k+1}
\prod_{0\le j<k}(2^{-j}z-1). & (11)\cr
}
$$
нАПРИМЕР, $g_4(z)=4+6(z-l)+4(z-l)\left({1\over2}z-l\right)+(z-1)\times
%%591
\left({1\over2}z-1\right)\left({1\over4}z-1\right)$. эТИ ФОРМУЛЫ ПОЗВОЛЯЮТ
ВЫРАЗИТЬ ИСКОМЫЕ ВЕЛИЧИНЫ В ВИДЕ СУММ ПРОИЗВЕДЕНИЙ:
$$
\eqalignno{
\overline{C}_N&=g'_N(1)=\sum_{k\ge0}\perm{N}{k+2}
\prod_{1\le j\le k} (2^{-j}-1); & (12) \cr
g_N\left({1\over2}\right)&=\sum_{k\ge 0}\perm{N}{k+1}
\prod_{1\le j\le k}(2^{-j}-1)=\overline{C}_{N+1}-\overline{C}_N.&(13)\cr
}
$$
сОВСЕМ НЕ ОЧЕВИДНО, ЧТО ЭТИ ФОРМУЛЫ ДЛЯ $\overline{C}_N$ УДОВЛЕТВОРЯЮТ~(Б)!
к СОЖАЛЕНИЮ, НАЙДЕННЫЕ ВЫРАЖЕНИЯ НЕПРИГОДНЫ ДЛЯ ВЫЧИСЛЕНИЙ ИЛИ ПОЛУЧЕНИЯ
АСИМПТОТИЧЕСКИХ ОЦЕНОК, ТАК КАК $2^{-j}-1<0$; ПОЛУЧИТСЯ БОЛЬШОЕ КОЛИЧЕСТВО
ЧЛЕНОВ, МНОГИЕ ИЗ КОТОРЫХ СОКРАТЯТСЯ. бОЛЕЕ ПОЛЕЗНЫЕ ФОРМУЛЫ ДЛЯ
$\overline{C}_N$ МОЖНО ВЫВЕСТИ, ПРИМЕНЯЯ ТОЖДЕСТВА УПР.~5.1.1-16. иМЕЕМ
$$
\eqalign{
\overline{C}_N&=\left(\prod_{j\ge1}(1-2^{-j})\right)
\sum_{k\ge0}\perm{N}{k+2}(-1)^k\prod_{l\ge0}(1-2^{-l-k-1})^{-1}=\cr
&=\left(\prod_{j\ge1}(1-2^{-j})\right)
\sum_{k\ge0}\perm{N}{k+2}(-1)^k\sum_{m\ge0}(2^{-k-1})^m
\times\prod_{1\le r\le m}(1-2^{-r})^{-1}=\cr
&=\sum_{m\ge0}2^m\left(\sum_k\perm{N}{k}(-2^{-m})^k-1+2^{-m}N\right)
\prod_{j\ge0}(1-2^{-j-m-1})=\cr
&=\sum_{m\ge0}2^m((1-2^{-m})^N-1+2^{-m}N)\sum_{n\ge0}(-2^{-m-1})^n
2^{-n(n-1)/2}\times\prod_{1\le r\le n}(1-2^{-r})^{-1}.\cr
}
\eqno(14)
$$
сРАЗУ НЕ ЯСНО, ЧЕМ ЭТО ЛУЧШЕ ВЫРАЖЕНИЯ~(12), НО ВЫВЕДЕННАЯ ФОРМУЛА ИМЕЕТ
ТО ВАЖНОЕ ПРЕИМУЩЕСТВО, ЧТО ОНА БЫСТРО СХОДИТСЯ ДЛЯ ЛЮБОГО
ФИКСИРОВАННОГО~$n$. в ТОЧНОСТИ АНАЛОГИЧНАЯ СИТУАЦИЯ ВОЗНИКАЕТ И В СЛУЧАЕ
БОРА [ФОРМУЛА (5.2.2-38)]; В САМОМ ДЕЛЕ, ЕСЛИ РАССМОТРЕТЬ В~(14) ЛИШЬ
ЧЛЕНЫ С~$n=0$, ПОЛУЧАЕТСЯ РОВНО $N-1$~ПЛЮС ЧИСЛО ПРОВЕРОК В БИНАРНОМ
БОРУ. дАЛЬНЕЙШИЙ ВЫВОД АСИМПТОТИЧЕСКОЙ ОЦЕНКИ МОЖНО ПРОВЕСТИ УЖЕ ИЗВЕСТНЫМ
НАМ СПОСОБОМ; СМ.~УПР.~27. пРИВЕДЕННЫЙ ВЫВОД В БОЛЬШОЙ СТЕПЕНИ ОСНОВАН
НА ПОДХОДЕ, ПРЕДЛОЖЕННОМ э.~г.~кОНХЕЙМОМ И~д.~дЖ.~нЬЮМЭНОМ [{\sl Discrete
Mathematics,\/} {\bf 4} (1973), 56--63].
и НАКОНЕЦ, ВЗГЛЯНЕМ НА пАТРИЦИЮ С ТОЧКИ ЗРЕНИЯ МАТЕМАТИКА. еЕ БИНАРНОЕ
ДЕРЕВО ПОХОЖЕ НА СООТВЕТСТВУЮЩИЙ БИНАРНЫЙ БОР С ТЕМИ ЖЕ КЛЮЧАМИ, НО
СЖАТЫМИ ВМЕСТЕ (ИБО ПОЛЯ~|SKIP| УСТРАНЯЮТ ОДНОПУТЕВЫЕ РАЗВЕТВЛЕНИЯ), ТАК
ЧТО ИМЕЕТСЯ $N-1$~ВНУТРЕННИХ
%%592
И $N$~ВНЕШНИХ УЗЛОВ. нА РИС.~36 ИЗОБРАЖЕНО ДЕРЕВО пАТРИЦИИ,
СООТВЕТСТВУЮЩЕЕ ШЕСТНАДЦАТИ КЛЮЧАМ В БОРУ РИС.~34. чИСЛА, ЗАКЛЮЧЕННЫЕ ВО
ВНУТРЕННИХ УЗЛАХ, ОБОЗНАЧАЮТ СОДЕРЖИМОЕ ПОЛЕЙ |SKIP|; КЛЮЧИ УКАЗАНЫ
ВМЕСТЕ С ВНЕШНИМИ УЗЛАМИ, ХОТЯ ПОСЛЕДНИЕ НЕ ПРИСУТСТВУЮТ ЯВНО (В
ДЕЙСТВИТЕЛЬНОСТИ ВМЕСТО ВНЕШНИХ УЗЛОВ СУЩЕСТВУЮТ ПОМЕЧЕННЫЕ ССЫЛКИ НА
ВНУТРЕННИЕ УЗЛЫ, КОТОРЫЕ В СВОЮ ОЧЕРЕДЬ ССЫЛАЮТСЯ НА МАССИВ
|TEXT|). оДНАКО ДЛЯ ЦЕЛЕЙ АНАЛИЗА МОЖНО СЧИТАТЬ, ЧТО ВНЕШНИЕ
УЗЛЫ СУЩЕСТВУЮТ В ТОМ ВИДЕ, КАК ОНИ ИЗОБРАЖЕНЫ НА РИС.~36.
тАК КАК УДАЧНЫЙ ПОИСК С ИСПОЛЬЗОВАНИЕМ пАТРИЦИИ ОКАНЧИВАЕТСЯ ВО ВНЕШНИХ
УЗЛАХ, СРЕДНЕЕ ЧИСЛО ПРОВЕРОК БИТОВ, ПРОИЗВОДИМЫХ ПРИ СЛУЧАЙНОМ УДАЧНОМ
ПОИСКЕ, РАВНО ДЛИНЕ
\picture{рИС. 36. пАТРИЦИЯ СТРОИТ ЭТО ДЕРЕВО ВМЕСТО РИС. 34.}
ВНЕШНЕГО ПУТИ, ДЕЛЕННОЙ НА~$N$. еСЛИ, КАК И ВЫШЕ, ВВЕСТИ ПРОИЗВОДЯЩУЮ
ФУНКЦИЮ~$b(z)$ ДЛЯ ВНЕШНИХ УЗЛОВ, ЭТО ЧИСЛО БУДЕТ РАВНО~$b'(1)/b(1)$.
\emph{нЕУДАЧНЫЙ} ПОИСК ТАКЖЕ КОНЧАЕТСЯ ВО ВНЕШНЕМ УЗЛЕ, НО С
ВЕРОЯТНОСТЬЮ~$2^{-l}$ ($l$---НОМЕР УРОВНЯ, НА КОТОРОМ РАСПОЛОЖЕН УЗЕЛ),
ТАК ЧТО СРЕДНЕЕ ЧИСЛО ПРОВЕРОК БИТОВ
СОСТАВЛЯЕТ~${1\over2}b'\left({1\over2}\right)$. нАПРИМЕР, ДЛЯ РИС.~36
$b(z)=3z^3+8z^4-3z^5+2z^6$; В СРЕДНЕМ УДАЧНЫЙ ПОИСК ТРЕБУЕТ
$4{1\over4}$~ПРОВЕРОК БИТОВ, А НЕУДАЧНЫЙ---$3{25\over32}$.
пРОИЗВОДЯЩУЮ ФУНКЦИЮ~$b(z)$, УСРЕДНЕННУЮ ПО ВСЕМ ДЕРЕВЬЯМ пАТРИЦИИ,
ПОСТРОЕННЫМ С $N$~ВНЕШНИМИ УЗЛАМИ С ИСПОЛЬЗОВАНИЕМ РАВНОМЕРНО
РАСПРЕДЕЛЕННЫХ КЛЮЧЕЙ, ОБОЗНАЧИМ ЧЕРЕЗ~$h_N(z)$.
%%593
рЕКУРРЕНТНОЕ СООТНОШЕНИЕ
$$
h_n(z)=2^{1-N}\sum_k\perm{n}{k}h_k(z)(z+\delta_{kn}(1-z)),
\qquad h_0(z)=0, \qquad h_1(z)=1,
\eqno(15)
$$
ПО-ВИДИМОМУ, НЕ ИМЕЕТ ПРОСТОГО РЕШЕНИЯ. нО, К СЧАСТЬЮ, СУЩЕСТВУЕТ
ПРОСТОЕ РЕКУРРЕНТНОЕ СООТНОШЕНИЕ ДЛЯ СРЕДНЕЙ ДЛИНЫ ВНЕШНЕГО ПУТИ~$h'_n(1)$,
ПОСКОЛЬКУ
$$
\eqalignno{
h'_n(1)&=2^{1-n}\sum_k\perm{n}{k}h'_k(1)+2^{1-n}
\sum_k\perm{n}{k}(1-\delta_{kn})=&\cr
&=n-2^{n-1}n+2^{1-n}\sum_k\perm{n}{k}h'_k(1).&(16)\cr
}
$$
тАК КАК ОНО ИМЕЕТ ВИД~(6), ДЛЯ НАХОЖДЕНИЯ~$h'_n(1)$ МОЖНО ИСПОЛЬЗОВАТЬ УЖЕ
РАЗВИТЫЕ МЕТОДЫ; ОКАЗЫВАЕТСЯ, ЧТО $h'_n(1)$ РОВНО НА~$n$ МЕНЬШЕ
СООТВЕТСТВУЮЩЕГО ЧИСЛА ПРОВЕРОК БИТОВ В СЛУЧАЙНОМ БИНАРНОМ БОРУ. тАКИМ
ОБРАЗОМ, ПОЛЕ |SKIP| ПОЗВОЛЯЕТ СЭКОНОМИТЬ ПРИМЕРНО ОДНУ ПРОВЕРКУ БИТА ДЛЯ
УДАЧНОГО ПОИСКА ПРИ СЛУЧАЙНЫХ ДАННЫХ. (сМ.~УПР.~31.) нА САМОМ ЖЕ ДЕЛЕ
ИЗБЫТОЧНОСТЬ ТИПИЧНЫХ ДАННЫХ ПРИВЕДЕТ К БОЛЬШЕЙ ЭКОНОМИИ.
еСЛИ МЫ ПОПЫТАЕМСЯ НАЙТИ СРЕДНЕЕ ЧИСЛО ПРОВЕРОК БИТОВ ДЛЯ СЛУЧАЙНОГО
НЕУДАЧНОГО ПОИСКА, ПРОИЗВОДИМОГО пАТРИЦИЕЙ, ТО ПОЛУЧИМ СООТНОШЕНИЕ
$$
a_n=1+{1\over 2^n-2}\sum_{k<n}\perm{n}{k}a_k,
\qquad n\ge2; \qquad a_0=a_1=0.
\eqno(17)
$$
(зДЕСЬ $a_n={1\over2}h'_n\left({1\over2}\right)$.) оНО \emph{НЕ} ПОХОЖЕ НИ
НА ОДНО ИЗ ИЗУЧЕННЫХ СООТНОШЕНИЙ, И СВЕСТИ ЕГО К НИМ НЕ ПРОСТО. нА САМОМ
ДЕЛЕ ОКАЗЫВАЕТСЯ, ЧТО РЕШЕНИЕ СОДЕРЖИТ ЧИСЛА бЕРНУЛЛИ:
$$
{na_{n-1}\over2}-n+2=\sum_{2\le k<n}\perm{n}{k}{B_k\over 2^{k-1}-1}.
\eqno(18)
$$
эТА ФОРМУЛА ЯВЛЯЕТСЯ, ВЕРОЯТНО, НАИБОЛЕЕ СЛОЖНОЙ АСИМПТОТИЧЕСКОЙ ОЦЕНКОЙ
ИЗ ВСЕХ, КОТОРЫЕ НАМ НУЖНО БЫЛО ПОЛУЧИТЬ;
РЕШЕНИЕ В УПР.~34 ДАЕТ ПОУЧИТЕЛЬНЫЙ ОБЗОР МНОГИХ РАНЕЕ ИЗУЧЕННЫХ ВЕЩЕЙ С
НЕКОТОРЫМИ НЮАНСАМИ.
\section вЫВОДЫ ИЗ АНАЛИЗА. сЛЕДУЮЩИЕ РЕЗУЛЬТАТЫ ЗАСЛУЖИВАЮТ НАИБОЛЬШЕГО
ВНИМАНИЯ:
\item{(a)}~чИСЛО УЗЛОВ, НЕОБХОДИМЫХ ДЛЯ ХРАНЕНИЯ $N$~СЛУЧАЙНЫХ КЛЮЧЕЙ В
$M\hbox{-АРНОМ}$ БОРУ, РАЗВЕТВЛЕНИЯ В КОТОРОМ ПРОИСХОДЯТ ДО ТЕХ.ПОР, ПОКА
НЕ ОСТАНЕТСЯ ПОДФАЙЛ ИЗ $\le s$~КЛЮЧЕЙ, ПРИМЕРНО РАВНО~$N/(s\ln M)$. (эТО
ПРИБЛИЖЕНИЕ СПРАВЕДЛИВО ДЛЯ БОЛЬШИХ~$N$
%%594
И МАЛЫХ~$s$ И~$M$.) тАК КАК УЗЕЛ БОРА СОДЕРЖИТ $M$~ПОЛЕЙ ССЫЛОК, ТО, ЕСЛИ
ВЫБРАТЬ $s=M$, ВСЕГО ПОТРЕБУЕТСЯ ЛИШЬ ОКОЛО $N/(\ln M)$~ПОЛЕЙ ССЫЛОК.
\item{(b)}~дЛЯ ВСЕХ РАССМОТРЕННЫХ МЕТОДОВ КОЛИЧЕСТВО ЦИФР ИЛИ ЛИТЕР,
ПРОВЕРЯЕМЫХ В ПРОЦЕССЕ СЛУЧАЙНОГО ПОИСКА, ПРИМЕРНО РАВНО~$\log_M N$. пРИ
$M=2$ РАЗЛИЧНЫМИ МЕТОДАМИ МОЖНО ПОЛУЧИТЬ СЛЕДУЮЩИЕ БОЛЕЕ ТОЧНЫЕ
ПРИБЛИЖЕНИЯ ДЛЯ ЧИСЛА ПРОВЕРОК БИТОВ:
\ctable{
#\hfill\bskip &&\bskip \hfill$#$\hfill \cr
& \hbox{уДАЧНЫЙ} &\hbox{нЕУДАЧНЫЙ} \cr
пОИСК ПО БОРУ &\log_2N+1.33275 &\log_2N-0.10995\cr
цИФРОВОЙ ПОИСК ПО ДЕРЕВУ &\log_2N-1.71665 &\log_2N-0.27395\cr
пАТРИЦИЯ &\log_2N+0.33275 &\log_2N-0.31875\cr
}
[вСЕ ЭТИ ПРИБЛИЖЕННЫЕ ЗНАЧЕНИЯ МОЖНО ВЫРАЗИТЬ ЧЕРЕЗ ФУНДАМЕНТАЛЬНЫЕ
МАТЕМАТИЧЕСКИЕ ПОСТОЯННЫЕ; НАПРИМЕР, ЧИСЛО~$0.31875$ ПОЛУЧИЛОСЬ ИЗ~$(\ln \pi-\gamma)/(\ln2)-1/2$.]
\item{(c)}~"сЛУЧАЙНОСТЬ" ДАННЫХ ЗДЕСЬ ОЗНАЧАЕТ ТО, ЧТО $M\hbox{-ИЧНЫЕ}$
ЦИФРЫ ЯВЛЯЮТСЯ РАВНОМЕРНО РАСПРЕДЕЛЕННЫМИ, КАК ЕСЛИ БЫ КЛЮЧАМИ БЫЛИ
ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА МЕЖДУ~0 И~1, ЗАПИСАННЫЕ В $M\hbox{-ИЧНОЙ}$ СИСТЕМЕ
СЧИСЛЕНИЯ. мЕТОДЫ ЦИФРОВОГО ПОИСКА НЕ ЧУВСТВИТЕЛЬНЫ К ПОРЯДКУ, В КОТОРОМ
КЛЮЧИ ПОМЕЩЕНЫ В ФАЙЛ (ИСКЛЮЧЕНИЕМ ЯВЛЯЕТСЯ АЛГОРИТМ~D, ЛИШЬ В МАЛОЙ
СТЕПЕНИ ЧУВСТВИТЕЛЬНЫЙ К ПОРЯДКУ); НО ОНИ ОЧЕНЬ ЧУВСТВИТЕЛЬНЫ К
РАСПРЕДЕЛЕНИЮ ЦИФР. нАПРИМЕР, ЕСЛИ НУЛЕВЫЕ БИТЫ ВСТРЕЧАЮТСЯ ГОРАЗДО ЧАЩЕ
ЕДИНИЧНЫХ, ДЕРЕВЬЯ БУДУТ ГОРАЗДО БОЛЕЕ АСИММЕТРИЧНЫМИ ПО СРАВНЕНИЮ С
ДЕРЕВЬЯМИ, ПОЛУЧЕННЫМИ ДЛЯ СЛУЧАЙНЫХ ДАННЫХ. (в УПР.~5.2.2-53 РАЗОБРАН
ПРИМЕР ТОГО, ЧТО ПРОИСХОДИТ ПРИ ТАКОМ ВОЗДЕЙСТВИИ НА ДАННЫЕ.)
\excercises
\ex[00] еСЛИ ДЕРЕВО ИМЕЕТ ЛИСТЬЯ, ТО ЧТО ИМЕЕТ БОР?
\ex[20] пОСТРОЙТЕ АЛГОРИТМ ВСТАВКИ НОВОГО КЛЮЧА В $M\hbox{-АРНЫЙ}$ БОР,
ПРИДЕРЖИВАЯСЬ СОГЛАШЕНИЙ АЛГОРИТМА~T.
\ex[21] пОСТРОЙТЕ АЛГОРИТМ УДАЛЕНИЯ КЛЮЧА ИЗ $M\hbox{-АРНОГО}$ БОРА,
ПРИДЕРЖИВАЯСЬ СОГЛАШЕНИЙ АЛГОРИТМА~T.
\rex[21] бОЛЬШИНСТВО ИЗ 360~ЭЛЕМЕНТОВ ТАБЛ.~1---ПРОБЕЛЫ (ПУСТЫЕ
ССЫЛКИ). оДНАКО МОЖНО СЖАТЬ ТАБЛИЦУ ДО 49~ЭЛЕМЕНТОВ, ДОПУСКАЯ ПЕРЕКРЫТИЕ
НЕПУСТЫЕ И ПУСТЫХ ЭЛЕМЕНТОВ:
\picture{рИС. НА СТР. 594}
%% 595
[уЗЛЫ (1), (2),~\dots, (12) ТАБЛ.~1 НАЧИНАЮТСЯ СООТВЕТСТВЕННО С ПОЗИЦИЙ 20,
19, 3, 14, 1, 17, 1, 7, 3, 20, 18, 4 СЖАТОЙ ТАБЛИЦЫ.]
пОКАЖИТЕ, ЧТО, ЕСЛИ ЗАМЕНИТЬ ТАКОЙ СЖАТОЙ ТАБЛИЦЕЙ ТАБЛ.~1,
ПРОГРАММА~T БУДЕТ РАБОТАТЬ И В ЭТОМ СЛУЧАЕ, ПРАВДА, НЕ СТОЛЬ БЫСТРО.
\rex[м26] (й.~н.~пЭТТ.) в ДЕРЕВЬЯХ РИС.~31 БУКВЫ УПОРЯДОЧЕНЫ ПО АЛФАВИТУ
ВНУТРИ КАЖДОГО СЕМЕЙСТВА. эТО НЕ ЯВЛЯЕТСЯ НЕОБХОДИМЫМ, И ЕСЛИ МЫ, ПРЕЖДЕ
ЧЕМ СТРОИТЬ БИНАРНОЕ ДЕРЕВО ТИПА~(2), ИЗМЕНИМ ПОРЯДОК УЗЛОВ ВНУТРИ КАЖДОГО
СЕМЕЙСТВА, ПОИСК МОЖЕТ УСКОРИТЬСЯ. кАКОЕ ПЕРЕУПОРЯДОЧЕНИЕ РИС.~31 БУДЕТ
ОПТИМАЛЬНЫМ С ЭТОЙ ТОЧКИ ЗРЕНИЯ? (иСПОЛЬЗУЙТЕ ЧАСТОТЫ, ДАННЫЕ НА РИС.~32,
И НАЙДИТЕ ЛЕС, КОТОРЫЙ, БУДУЧИ ПРЕДСТАВЛЕН В ВИДЕ БИНАРНОГО ДЕРЕВА,
МИНИМИЗИРУЕТ ВРЕМЯ УДАЧНОГО ПОИСКА.)
\ex[15] кАКОЕ ДЕРЕВО ЦИФРОВОГО ПОИСКА ПОЛУЧИТСЯ, ЕСЛИ ПЯТНАДЦАТЬ
ЧЕТЫРЕХБИТОВЫХ БИНАРНЫХ КЛЮЧЕЙ 0001, 0010, 0011,~\dots, 1111 ВСТАВИТЬ В
ВОЗРАСТАЮЩЕМ ПОРЯДКЕ С ПОМОЩЬЮ АЛГОРИТМА~D? (нАЧНИТЕ С КЛЮЧА~0001 В
КОРНЕВОМ УЗЛЕ И ЗАТЕМ ПРОИЗВЕДИТЕ ЧЕТЫРНАДЦАТЬ ВСТАВОК.)
\rex[M26] еСЛИ ПЯТНАДЦАТЬ КЛЮЧЕЙ ИЗ УПР.~6 ВСТАВЛЯЮТСЯ В ДРУГОМ ПОРЯДКЕ,
МОЖЕТ ПОЛУЧИТЬСЯ ДРУГОЕ ДЕРЕВО. кАКОВА НАИХУДШАЯ СРЕДИ ВСЕХ
$15!$~ВОЗМОЖНЫХ ПЕРЕСТАНОВОК ЭТИХ КЛЮЧЕЙ В ТОМ СМЫСЛЕ, ЧТО ОНА ПОРОЖДАЕТ
ДЕРЕВО С НАИБОЛЬШЕЙ ДЛИНОЙ ВНУТРЕННЕГО ПУТИ?
\ex[20] рАССМОТРИМ СЛЕДУЮЩИЕ ИЗМЕНЕНИЯ АЛГОРИТМА~D, ВЕДУЩИЕ К ИСКЛЮЧЕНИЮ
ПЕРЕМЕННОЙ~$K1$: ЗАМЕНИТЬ "$K1$" НА "$K$" В ШАГЕ~D2 И УСТРАНИТЬ
ОПЕРАЦИЮ~"$K1\asg K$" ИЗ ШАГА~D1. гОДИТСЯ ЛИ ПОЛУЧЕННЫЙ АЛГОРИТМ ДЛЯ
ПОИСКА И ВСТАВКИ?
\ex[21] нАПИШИТЕ \MIX-ПРОГРАММУ ДЛЯ АЛГОРИТМА~D И СРАВНИТЕ ЕЕ С
ПРОГРАММОЙ~6.2.2T. вЫ МОЖЕТЕ ИСПОЛЬЗОВАТЬ БИНАРНЫЕ ОПЕРАЦИИ ВРОДЕ
|SLB| (БИНАРНЫЙ СДВИГ ВЛЕВО |AX|), |JAE| (ПЕРЕХОД, ЕСЛИ |A|~ЧЕТНО) И Т.~Д.,
ЕСЛИ СОЧТЕТЕ НУЖНЫМ. вЫ МОЖЕТЕ ТАКЖЕ ИСПОЛЬЗОВАТЬ ИДЕЮ УПР.~8.
\ex[23] иМЕЕТСЯ ФАЙЛ, ВСЕ КЛЮЧИ КОТОРОГО СУТЬ $n\hbox{-БИТОВЫЕ}$
ДВОИЧНЫЕ ЧИСЛА, И АРГУМЕНТ ПОИСКА $K=b_1\ b_2\ \ldots\ b_n$. пРЕДПОЛОЖИМ,
ЧТО МЫ ХОТИМ НАЙТИ МАКСИМАЛЬНОЕ ЧИСЛО~$k$, ТАКОЕ, ЧТО В ФАЙЛЕ СУЩЕСТВУЕТ
КЛЮЧ, НАЧИНАЮЩИЙСЯ С $b_1b_2\ldots b_k$. кАК СДЕЛАТЬ ЭТИ ЭФФЕКТИВНО, ЕСЛИ
ФАЙЛ ПРЕДСТАВЛЕН В ВИДЕ: (a)~БИНАРНОГО ДЕРЕВА ПОИСКА
(СР.~С~АЛГОРИТМОМ 6.2.2T); (b)~БИНАРНОГО БОРА (СР.~С АЛГОРИТМОМ~T);
(c)~БИНАРНОГО ДЕРЕВА ЦИФРОВОГО ПОИСКА (СР. С АЛГОРИТМОМ~D)?
\ex[21] мОЖНО ЛИ ИСПОЛЬЗОВАТЬ АЛГОРИТМ~6.2.2D БЕЗ ИЗМЕНЕНИЙ ДЛЯ УДАЛЕНИЯ
УЗЛА ИЗ ДЕРЕВА ЦИФРОВОГО ПОИСКА?
\ex[25] бУДЕТ ЛИ СЛУЧАЙНЫМ ДЕРЕВО, ПОЛУЧЕННОЕ В РЕЗУЛЬТАТЕ
УДАЛЕНИЯ СЛУЧАЙНОГО ЭЛЕМЕНТА ИЗ СЛУЧАЙНОГО ДЕРЕВА ЦИФРОВОГО ПОИСКА,
ПОСТРОЕННОГО С ПОМОЩЬЮ АЛГОРИТМА~D? (сР.~С~УПР.~11 И С ТЕОРЕМОЙ~6.2.2H.)
\ex[20] ($M\hbox{-АРНЫЙ}$ ЦИФРОВОЙ ПОИСК). оБRЯСНИТЕ, КАК ИЗ АЛГОРИТМОВ~T
И~D СОСТАВИТЬ СООБЩЕННЫЙ АЛГОРИТМ, СВОДЯЩИЙСЯ К АЛГОРИТМУ~D ПРИ~$M=2$.
кАК СЛЕДУЕТ ИЗМЕНИТЬ ТАБЛ.~1, ЕСЛИ ИСПОЛЬЗОВАТЬ ВАШ АЛГОРИТМ ПРИ~$M=30?$
\rex[25] пОСТРОЙТЕ ЭФФЕКТИВНЫЙ АЛГОРИТМ, С ПОМОЩЬЮ КОТОРОГО СРАЗУ ПОСЛЕ
УДАЧНОГО ЗАВЕРШЕНИЯ АЛГОРИТМА~P МОЖНО БЫЛО БЫ НАЙТИ ВСЕ МЕСТА В МАССИВЕ
|TEXT|, ГДЕ ВСТРЕЧАЕТСЯ~$K$.
\ex[28] пРИДУМАЙТЕ, ЭФФЕКТИВНЫЙ АЛГОРИТМ, КОТОРЫЙ МОЖНО ИСПОЛЬЗОВАТЬ ДЛЯ
ПОСТРОЕНИЯ ДЕРЕВА пАТРИЦИИ ИЛИ ДЛЯ ВСТАВКИ НОВОЙ ССЫЛКИ НА |TEXT| В УЖЕ
СУЩЕСТВУЮЩЕЕ ДЕРЕВО. вАШ АЛГОРИТМ ВСТАВКИ ДОЛЖЕН ОБРАЩАТЬСЯ К МАССИВУ
|TEXT| НЕ БОЛЕЕ ДВУХ РАЗ.
\ex[22] пОЧЕМУ ДЛЯ пАТРИЦИИ ХОТЕЛОСЬ БЫ ИМЕТЬ ТАКОЕ ОГРАНИЧЕНИЕ, ЧТО НИ
ОДИН КЛЮЧ НЕ ДОЛЖЕН СЛУЖИТЬ НАЧАЛОМ ДРУГОГО?
\ex[м25] нАЙДИТЕ СПОСОБ ВЫРАЗИТЬ РЕШЕНИЕ РЕКУРРЕНТНОГО СООТНОШЕНИЯ
$$
x_0=x_1=0; \qquad x_n=a_n+m^{1-n}\sum_k\perm{n}{k}(m-1)^{n-k}x_k,
\qquad n\ge2,
$$
С ПОМОЩЬЮ БИНОМИАЛЬНЫХ ПРЕОБРАЗОВАНИЙ, ОБОБЩАЯ МЕТОД УПР.~5.2.2-36.
\ex[M21] иСПОЛЬЗУЯ РЕЗУЛЬТАТ УПР.~17, ВЫРАЗИТЕ РЕШЕНИЯ УРАВНЕНИЙ~(4) И~(5)
ЧЕРЕЗ ФУНКЦИИ~$U_n$ И~$V_n$, АНАЛОГИЧНЫЕ ВВЕДЕННЫМ В УПР.~5.2.2-38.
%%596
\ex[вм23] нАЙДИТЕ АСИМПТОТИЧЕСКОЕ ЗНАЧЕНИЕ ФУНКЦИИ
$$
K(n,s,m)=\sum_{k\ge2}\perm{n}{k}\perm{k}{s}{(-1)^k\over m^{k-1}-1}
$$
С ТОЧНОСТЬЮ ДО~$O(1)$ ПРИ~$n\to\infty$ ДЛЯ ФИКСИРОВАННЫХ ЗНАЧЕНИЙ~$s\ge0$
И~$m>1$. [сЛУЧАЙ~$s=0$ РАССМОТРЕН В УПР.~5.2.2-50,
А СЛУЧАЙ~$s=l$, $m=2$---В УПР.~5.2.2-48.]
\rex[M30] рАССМОТРИМ $M\hbox{-АРНУЮ}$ БОРОВУЮ ПАМЯТЬ, В КОТОРОЙ,
ДОСТИГНУВ ПОДФАЙЛА, СОДЕРЖАЩЕГО НЕ БОЛЕЕ $s$~КЛЮЧЕЙ, МЫ ИСПОЛЬЗУЕМ
ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК. (сЛУЧАЮ~$s=1$ СООТВЕТСТВУЕТ АЛГОРИТМ~T.) пРИМЕНИТЕ
РЕЗУЛЬТАТЫ ПРЕДЫДУЩИХ УПРАЖНЕНИЙ, ЧТОБЫ ПРОАНАЛИЗИРОВАТЬ: (a)~СРЕДНЕЕ
ЧИСЛО УЗЛОВ БОРА;
(b)~СРЕДНЕЕ ЧИСЛО ПРОВЕРЯЕМЫХ ЦИФР ИЛИ ЛИТЕР ПРИ УДАЧНОМ ПОИСКЕ;
(c)~СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ, ПРОИЗВОДИМЫХ ПРИ УДАЧНОМ ПОИСКЕ.
сФОРМУЛИРУЙТЕ ОТВЕТЫ В ВИДЕ АСИМПТОТИЧЕСКИХ ФОРМУЛ~($N\to\infty$) ДЛЯ
ФИКСИРОВАННЫХ~$M$ И~$s$,
ОТВЕТ ДЛЯ~(a) ДОЛЖЕН БЫТЬ ДАН С ТОЧНОСТЬЮ ДО~$O(1)$, ОТВЕТЫ ДЛЯ~(b)
И~(c)---С ТОЧНОСТЬЮ ДО~$O(N^{-1})$. [еСЛИ~$M=2$, ЭТОТ АНАЛИЗ ПРИМЕНИМ ТАКЖЕ
К МОДИФИЦИРОВАННОЙ ОБМЕННОЙ ПОРАЗРЯДНОЙ СОРТИРОВКЕ, КОГДА ПОДФАЙЛЫ
РАЗМЕРА~$<s$ СОРТИРУЮТСЯ ПОСРЕДСТВОМ ВСТАВОК].
\ex[м25] сКОЛЬКО УЗЛОВ В СЛУЧАЙНОМ $M\hbox{-АРНОМ}$ БОРУ, СОДЕРЖАЩЕМ $N$~КЛЮЧЕЙ,
ИМЕЮТ ПУСТУЮ ССЫЛКУ В КАЧЕСТВЕ НУЛЕВОЙ КОМПОНЕНТЫ? (нАПРИМЕР, 9 ИЗ 12~УЗЛОВ
ТАБЛ.~1 В ПОЗИЦИИ "\]" ИМЕЮТ ПУСТУЮ ССЫЛКУ. "сЛУЧАЙНЫЙ" В
ЭТОМ УПРАЖНЕНИИ, КАК И ОБЫЧНО, ОЗНАЧАЕТ, ЧТО ЛИТЕРЫ КЛЮЧЕЙ РАВНОМЕРНО
РАСПРЕДЕЛЕНЫ МЕЖДУ~$0$ И~$M-1$.)
\ex[м25] сКОЛЬКО УЗЛОВ РАСПОЛОЖЕНО НА 1-М УРОВНЕ СЛУЧАЙНОГО
$M\hbox{-apНoro}$ БОРА, СОДЕРЖАЩЕГО $N$~КЛЮЧЕЙ, ПРИ $l=0$, 1, 2,~\dots?
\ex[м26] сКОЛЬКО ПРОВЕРОК ЦИФР ПРОИЗВОДИТСЯ В СРЕДНЕМ ПРИ
НЕУДАЧНОМ ПОИСКЕ В $M\hbox{-АРНОМ}$ БОРУ, СОДЕРЖАЩЕМ $N$~СЛУЧАЙНЫХ КЛЮЧЕЙ?
\ex[M30] рАССМОТРИМ $M\hbox{-АРНЫЙ}$ БОР, ПРЕДСТАВЛЕННЫЙ В ВИДЕ ЛЕСА
(СР.~С~РИС.~31). нАЙДИТЕ ТОЧНЫЕ И АСИМПТОТИЧЕСКИЕ ВЫРАЖЕНИЯ ДЛЯ:
(a)~СРЕДНЕГО ЧИСЛА УЗЛОВ В ЛЕСУ; (b)~СРЕДНЕГО КОЛИЧЕСТВА ВЫПОЛНЕНИИ
ПРИСВАИВАНИЯ~$|P|\asg|RLINK|(|P|)$ В ПРОЦЕССЕ СЛУЧАЙНОГО УДАЧНОГО ПОИСКА.
\rex[м24] мАТЕМАТИЧЕСКИЙ ВЫВОД АСИМПТОТИЧЕСКИХ ЗНАЧЕНИЙ, СДЕЛАННЫЙ В ДАННОМ
ПУНКТЕ, ВЕСЬМА ТРУДЕН; ИСПОЛЬЗОВАЛАСЬ ДАЖЕ ТЕОРИЯ КОМПЛЕКСНОГО ПЕРЕМЕННОГО.
дЕЛО В ТОМ, ЧТО МЫ НЕ ХОТЕЛИ ОГРАНИЧИВАТЬСЯ ГЛАВНЫМ ЧЛЕНОМ АСИМПТОТИКИ, А
ВТОРОЙ ЧЛЕН ДЕЙСТВИТЕЛЬНО СЛОЖЕН. цЕЛЬ ЭТОГО УПРАЖНЕНИЯ СОСТОИТ В ТОМ, ЧТОБЫ
ЭЛЕМЕНТАРНЫМИ МЕТОДАМИ ПОЛУЧИТЬ НЕКОТОРЫЕ РЕЗУЛЬТАТЫ В ОСЛАБЛЕННОЙ ФОРМЕ,
(a)~дОКАЖИТЕ ПО ИНДУКЦИИ, ЧТО РЕШЕНИЕ УРАВНЕНИЯ~(4) ПРИ~$N\ge1$
УДОВЛЕТВОРЯЕТ НЕРАВЕНСТВУ~$A_N\le M(N-1)/(M-1)$.
(b)~пУСТЬ~$D_N=C_N-NH_{N-1}/(\ln M)$, ГДЕ $C_N$~НАХОДИТСЯ ИЗ~(5).
дОКАЖИТЕ, ЧТО~$D_N=O(N)$, СЛЕДОВАТЕЛЬНО, $C_N=N\log_MN+O(N)$.
[\emph{уКАЗАНИЕ:} ИСПОЛЬЗУЙТЕ~(a) И ТЕОРЕМУ~1.2.7A.]
\ex[23] оПРЕДЕЛИТЕ ВРУЧНУЮ ЗНАЧЕНИЕ БЕСКОНЕЧНОГО ПРОИЗВЕДЕНИЯ
$$
\left(1-{1\over2}\right)\left(1-{1\over4}\right)
\left(1-{1\over8}\right)\left(1-{1\over16}\right)\cdots
$$
С ТОЧНОСТЬЮ ДО~$10^{-5}$. [\emph{уКАЗАНИЕ:} СР.~С~УПР.~5.1.1-16.]
\ex[вм31] с ПОМОЩЬЮ СООТНОШЕНИЯ~(14) НАЙДИТЕ АСИМПТОТИЧЕСКОЕ
ЗНАЧЕНИЕ~$\overline{C}_N$ С ТОЧНОСТЬЮ ДО~$O(1)$.
\ex[вм26] нАЙДИТЕ АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ СРЕДНЕГО ЧИСЛА ПРОВЕРОК ЦИФР
ПРИ ПОИСКЕ В СЛУЧАЙНОМ ДЕРЕВЕ ЦИФРОВОГО ПОИСКА, $M\ge2$. рАССМОТРИТЕ КАК
УДАЧНЫЙ, ТАК И НЕУДАЧНЫЙ ПОИСК. дАЙТЕ ОТВЕТ С ТОЧНОСТЬЮ ДО~$O(N^{-1})$.
\ex[м46] нАЙДИТЕ АСИМПТОТИКУ СРЕДНЕГО ЧИСЛА УЗЛОВ В $M\hbox{-АРНОМ}$
ДЕРЕВЕ ЦИФРОВОГО ПОИСКА, ВСЕ $M$~ССЫЛОК КОТОРЫХ ПУСТЫ. (иСКЛЮЧИВ ТАКИЕ УЗЛЫ,
МЫ МОГЛИ БЫ СЭКОНОМИТЬ ПАМЯТЬ; СР.~С~УПР.~13.)
%% 597
\ex[M24] пОКАЖИТЕ, ЧТО ПРОИЗВОДЯЩУЮ ФУНКЦИЮ пАТРИЦИИ~$h_n(z)$,
ОПРЕДЕЛЕННУЮ В~(15), МОЖНО ВЫРАЗИТЬ В ТАКОМ ДОСТАТОЧНО "УЖАСНОМ" ВИДЕ:
$$
n\sum_{m\ge1} z^m \left(
\sum_{\scriptstyle a_1+\cdots+a_m=n-1\atop\scriptstyle a_1, \ldots, a_m\ge1}
\perm{n-1}{a_1,\ldots, a_m}\times
{1\over (2^{a_1}-1)(2^{a_1+a_2}-1)\ldots(2^{a_1+\cdots+a_m}-1)}\right).
$$
[тАКИМ ОБРАЗОМ, ЕСЛИ БЫ СУЩЕСТВОВАЛА ПРОСТАЯ ФОРМУЛА ДЛЯ~$h_n(z)$, МЫ
МОГЛИ БЫ УПРОСТИТЬ ЭТО ДОВОЛЬНО ГРОМОЗДКОЕ ВЫРАЖЕНИЕ.]
\ex[M21] нАЙДИТЕ~$h'_n(1)$ ИЗ СООТНОШЕНИЯ~(16).
\ex[M21] чЕМУ РАВНО СРЕДНЕЕ ЗНАЧЕНИЕ СУММЫ ВСЕХ ПОЛЕЙ |SKIP| В СЛУЧАЙНОМ
ДЕРЕВЕ пАТРИЦИИ С $N-1$ ВНУТРЕННИМИ УЗЛАМИ?
\ex[M30] дОКАЖИТЕ, ЧТО~[18] УДОВЛЕТВОРЯЕТ РЕКУРРЕНТНОМУ СООТНОШЕНИЮ~(17).
[\emph{уКАЗАНИЕ:} РАССМОТРИТЕ ПРОИЗВОДЯЩУЮ
ФУНКЦИЮ~$A(z)=\sum_{n\ge0} a_nz^n/n!$.]
\ex[вм40] цЕЛЬЮ ЭТОГО УПРАЖНЕНИЯ ЯВЛЯЕТСЯ НАХОЖДЕНИЕ АСИМПТОТИЧЕСКОГО
ПОВЕДЕНИЯ ФУНКЦИИ~(18).
\item{(a)}~дОКАЖИТЕ, ЧТО ПРИ $n\ge2$
$$
{1\over n}\sum_{2\le k<n}\perm{n}{k}{B_k\over 2^{k-1}-1}=
\sum_{j\ge1}\left({1^{n-1}+2^{n-1}+\cdots+(2^j-1)^{n-1}\over 2^{j(n-1)}}
-{2^j\over n}+{1\over 2}\right).
$$
\item{(b)}~пОКАЖИТЕ, ЧТО СЛАГАЕМЫЕ В ПРАВОЙ ЧАСТИ~(a) МОЖНО ПРИБЛИЗИТЬ
ФУНКЦИЯМИ~$1/(e^x-1)-1/x+1/2$, ГДЕ~$x=n/2^j$; ПОЛУЧАЮЩАЯСЯ ПРИ ЭТОМ
СУММА ОТЛИЧАЕТСЯ ОТ ПЕРВОНАЧАЛЬНОЙ НА~$O(n^{-1})$.
\item{(c)}~пОКАЖИТЕ, ЧТО ДЛЯ ДЕЙСТВИТЕЛЬНОГО~$x>0$
$$
{1\over e^x-1}-{1\over x}+{1\over2}=
{1\over 2\pi
i}\int_{-{1\over2}-i\infty}^{-{1\over2}+i\infty}\zeta(z)\Gamma(z)x^{-z}\,dx.
$$
\item{(d)}~сЛЕДОВАТЕЛЬНО, РАССМАТРИВАЕМАЯ СУММА РАВНА
$$
{1\over 2\pi i}\int_{-{1\over2}-i\infty}^{-{1\over2}+i\infty}
{\zeta(z)\Gamma(z)n^{-z}\over 2^{-z}-1}\,dx+O(n^{-1});
$$
ОЦЕНИТЕ ЭТОТ ИНТЕГРАЛ.
\rex[м20] кАКОВА ВЕРОЯТНОСТЬ ТОГО, ЧТО ДЕРЕВО пАТРИЦИИ, СОДЕРЖАЩЕЕ ПЯТЬ
КЛЮЧЕЙ, ИМЕЕТ ВИД
\picture{рИС. СТР. 597}
%%598
ПРИЧЕМ ПОЛЯ |SKIP| СОДЕРЖАТ $a$, $b$, $c$, $d$, КАК ПОКАЗАНО НА РИСУНКЕ?
(пРЕДПОЛАГАЕТСЯ, ЧТО КЛЮЧИ ИМЕЮТ НЕЗАВИСИМЫЕ СЛУЧАЙНЫЕ БИТЫ; ОТВЕТ НУЖНО
ПРЕДСТАВИТЬ В ВИДЕ ФУНКЦИИ ОТ $a$, $b$, $c$ И~$d$.)
\ex[M25] иМЕЕТСЯ ПЯТЬ БИНАРНЫХ ДЕРЕВЬЕВ С ТРЕМЯ ВНУТРЕННИМИ УЗЛАМИ. еСЛИ
МЫ РАССМОТРИМ, КАК ЧАСТО КАЖДОЕ ИЗ НИХ СЛУЖИТ ДЕРЕВОМ, ПОИСКА В
РАЗЛИЧНЫХ АЛГОРИТМАХ (ДАННЫЕ ПРЕДПОЛАГАЮТСЯ СЛУЧАЙНЫМИ), ТО ПОЛУЧИМ
СЛЕДУЮЩИЕ РАЗЛИЧНЫЕ ВЕРОЯТНОСТИ:
\picture{рИС. СТР. 598 --- В ТАБЛИЦУ ПО ЧАСТЯМ:}
\ctable{
# &$#$&$#$&$#$&$#$&$#$\cr
&&&&&\cr
пОИСК ПО ДЕРЕВУ (АЛГОРИТМ 6.2.2.T) & 1\over 6 & 1\over6 & 1\over3 &
1\over6 & 1\over6\cr
цИФРОВОЙ ПОИСК ПО ДЕРЕВУ (АЛГОРИТМ D)&1\over8 & 1\over8 & 1\over2 &
1\over8 & 1\over8\cr
пАТРИЦИЯ (АЛГОРИТМ р) & 1\over7 & 1\over7 & 3\over7 & 1\over7 & 1\over7\cr
}
(зАМЕТИМ, ЧТО ДЕРЕВО ЦИФРОВОГО ПОИСКА ИМЕЕТ НАИБОЛЬШУЮ ТЕНДЕНЦИЮ К
СБАЛАНСИРОВАННОСТИ.) в УПР.~6.2.2-5 МЫ НАШЛИ ФОРМУЛУ ДЛЯ ВЕРОЯТНОСТИ В
СЛУЧАЕ ПОИСКА ПО ДЕРЕВУ: $\prod(1/s(x))$, ГДЕ ПРОИЗВЕДЕНИЕ БЕРЕТСЯ ПО
ВСЕМ ВНУТРЕННИМ УЗЛАМ~$x$, a~$s(x)$---ЧИСЛО ВНУТРЕННИХ УЗЛОВ В ПОДДЕРЕВЕ,
КОРНЕМ КОТОРОГО СЛУЖИТ~$x$. нАЙДИТЕ АНАЛОГИЧНЫЕ ФОРМУЛЫ ДЛЯ ВЕРОЯТНОСТИ
В СЛУЧАЕ: (a)~АЛГОРИТМА~D; (b)~АЛГОРИТМА~р.
\rex[м22] рАССМОТРИМ БИНАРНОЕ ДЕРЕВО, НА $l\hbox{-М}$ УРОВНЕ КОТОРОГО
РАСПОЛОЖЕНО $b_l$~ВНЕШНИХ УЗЛОВ. в ТЕКСТЕ УКАЗЫВАЛОСЬ, ЧТО ВРЕМЯ
НЕУДАЧНОГО ПОИСКА В ДЕРЕВЬЯХ ЦИФРОВОГО ПОИСКА НЕ СВЯЗАНО НЕПОСРЕДСТВЕННО С
ДЛИНОЙ ВНЕШНЕГО ПУТИ~$\sum lb_l$, А, ПО СУЩЕСТВУ, ПРОПОРЦИОНАЛЬНО
\emph{МОДИФИЦИРОВАННОЙ ДЛИНЕ ВНЕШНЕГО ПУТИ}~$\sum l b_l 2^{-l}$.
дОКАЖИТЕ ИЛИ ОПРОВЕРГНИТЕ СЛЕДУЮЩЕЕ УТВЕРЖДЕНИЕ:
СРЕДИ ВСЕХ ДЕРЕВЬЕВ С $N$~ВНЕШНИМИ УЗЛАМИ НАИМЕНЬШУЮ
МОДИФИЦИРОВАННУЮ ДЛИНУ ВНЕШНЕГО ПУТИ ИМЕЕТ ТО ДЕРЕВО, ВСЕ ВНЕШНИЕ УЗЛЫ
КОТОРОГО РАСПОЛОЖЕНЫ НЕ БОЛЕЕ ЧЕМ НА ДВУХ СМЕЖНЫХ УРОВНЯХ (СР.~С УПР.~5.3.1-20).
\ex[м40] рАЗРАБОТАЙТЕ АЛГОРИТМ ДЛЯ НАХОЖДЕНИЯ $n\hbox{-УЗЛОВОГО}$ ДЕРЕВА,
ИМЕЮЩЕГО МИНИМАЛЬНОЕ ЗНАЧЕНИЕ ВЕЛИЧИНЫ
$\alpha\times\hbox{(ДЛИНА ВНУТРЕННЕГО ПУТИ)}+
\beta\times\hbox{(МОДИФИЦИРОВАННАЯ ДЛИНА ВНЕШНЕГО ПУТИ)}$, $\alpha$
И~$\beta$---ДАННЫЕ ЧИСЛА (СР.~С~УПР.~37).
\ex[м43] пРИДУМАЙТЕ АЛГОРИТМ НАХОЖДЕНИЯ ОПТИМАЛЬНЫХ ДЕРЕВЬЕВ ЦИФРОВОГО
ПОИСКА, АНАЛОГИЧНЫХ ОПТИМАЛЬНЫМ БИНАРНЫМ ДЕРЕВЬЯМ ПОИСКА, РАССМОТРЕННЫМ
В П.~6.2.2.
\ex[25] пУСТЬ $a_0a_1a_2\ldots$---ПЕРИОДИЧЕСКАЯ БИНАРНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ;
$a_{N+k}=a_k$ ПРИ ВСЕХ~$k\ge0$. пОКАЖИТЕ, ЧТО ЛЮБУЮ ФИКСИРОВАННУЮ
ЦЕПОЧКУ ЭТОГО ТИПА МОЖНО ПРЕДСТАВИТЬ В $O(N)$~ЯЧЕЙКАХ ПАМЯТИ ТАКИМ ОБРАЗОМ,
ЧТО СЛЕДУЮЩАЯ ОПЕРАЦИЯ ТРЕБУЕТ ЛИШЬ $O(n)$~ШАГОВ: ИМЕЯ БИНАРНУЮ
ЦЕПОЧКУ $b_0b_1\ldots b_{n-1}$, НУЖНО ОПРЕДЕЛИТЬ, СКОЛЬКО РАЗ ОНА
ВСТРЕЧАЕТСЯ В ПЕРИОДЕ (Т.~Е.~НАЙТИ КОЛИЧЕСТВО ЗНАЧЕНИЙ~$p$, $0\le p<N$,
ТАКИХ, ЧТО~$b_k=a_{p+k}$ ПРИ~$0\le k<n$). (дЛИНА ЦЕПОЧКИ~$n$, КАК И САМА
ЦЕПОЧКА, ЯВЛЯЕТСЯ ПЕРЕМЕННОЙ. пРЕДПОЛАГАЕТСЯ, ЧТО КАЖДАЯ ЯЧЕЙКА ПАМЯТИ
ДОСТАТОЧНО ВЕЛИКА, ЧТОБЫ ВМЕСТИТЬ ПРОИЗВОЛЬНОЕ ЦЕЛОЕ ЧИСЛО ОТ~$0$ ДО~$N$.)
%%599
\ex[вм28] \exhead(пРИЛОЖЕНИЕ К ТЕОРИИ ГРУПП.) пУСТЬ $G$---СВОБОДНАЯ
ГРУППА НАД СИМВОЛАМИ~$\set{a_1,~\ldots, a_n}$, Т.~Е.~МНОЖЕСТВО ВСЕХ
ЦЕПОЧЕК $\alpha=b_1\ldots{}b_r$, ГДЕ $b_i$~ЕСТЬ ЛИБО~$a_j$,
ЛИБО~$a_j^{-1}$, И НЕТ СМЕЖНЫХ ПАР~$a_ja_j^{-1}$ ИЛИ~$a_j^{-1}a_j$.
оБРАТНЫМ К~$\alpha$ ЭЛЕМЕНТОМ ЯВЛЯЕТСЯ~$b_r^{-1}\ldots{}b_1^{-1}$; МЫ
ПЕРЕМНОЖАЕМ ДВЕ ТАКИЕ ЦЕПОЧКИ ПУТЕМ КОНКАТЕНАЦИИ И СОКРАЩЕНИЯ СМЕЖНЫХ
ВЗАИМНООБРАТНЫХ ЭЛЕМЕНТОВ. пУСТЬ $H$---ПОДГРУППА ГРУППЫ~$G$, ПОРОЖДЕННАЯ
ЦЕПОЧКАМИ~$\set{\beta_1,~\ldots, \beta_p}$, Т.~Е.~МНОЖЕСТВО ВСЕХ ЭЛЕМЕНТОВ
ИЗ~$G$, КОТОРЫЕ МОЖНО ЗАПИСАТЬ В ВИДЕ ПРОИЗВЕДЕНИЙ~$\beta_i$
И~$\beta_j^{-1}$. мОЖНО ПОКАЗАТЬ (СМ.~а.~г.~кУРОШ, тЕОРИЯ ГРУПП (м.,
"нАУКА", 1967), ГЛ.~9], ЧТО ВСЕГДА СУЩЕСТВУЕТ СИСТЕМА
ОБРАЗУЮЩИХ~$\theta_1$,~\dots,$\theta_m$ ДЛЯ~$H$, $m\le p$, УДОВЛЕТВОРЯЮЩАЯ
"СВОЙСТВУ нИЛЬСЕНА", КОТОРОЕ ГЛАСИТ, ЧТО СРЕДНИЙ СИМВОЛ В~$\theta_i$ (ИЛИ
НЕ МЕНЕЕ ЧЕМ ОДИН ИЗ ДВУХ ЦЕНТРАЛЬНЫХ СИМВОЛОВ, ЕСЛИ $\theta_i$~ИМЕЕТ
ЧЕТНУЮ ДЛИНУ) НИКОГДА НЕ СОКРАЩАЕТСЯ В ВЫРАЖЕНИЯХ~$\theta_i\theta^e_j$
ИЛИ~$\theta^e_j\theta_i$, $e=\pm1$ (КРОМЕ ОЧЕВИДНОГО ИСКЛЮЧЕНИЯ~$i=j$,
$e=-1$). иЗ ЭТОГО СВОЙСТВА, ВЫТЕКАЕТ, ЧТО СУЩЕСТВУЕТ ПРОСТОЙ АЛГОРИТМ
ПРОВЕРКИ ПРИНАДЛЕЖНОСТИ ПРОИЗВОЛЬНОГО ЭЛЕМЕНТА~$G$ ПОДГРУППЕ~$H$:
ИСПОЛЬЗУЯ $2n$~СИМВОЛОВ $a_1$,~\dots, $a_n$, $a^{-1}_1$,~\dots, $a^{-1}_n$,
ЗАПИШЕМ $2m$~КЛЮЧЕЙ $\theta_1$,~\dots, $\theta_m$, $\theta^{-1}_1$,~\dots,
$\theta^{-1}_m$ В ДЕРЕВО, ОРИЕНТИРОВАННОЕ НА ПОИСК ПО СИМВОЛАМ. пУСТЬ
$\alpha=b_1\ldots{}b_r$---ДАННЫЙ ЭЛЕМЕНТ ИЗ~$G$; ЕСЛИ~$r=0$, ТО
ЭЛЕМЕНТ~$\alpha$, РАЗУМЕЕТСЯ, ПРИНАДЛЕЖИТ~$H$. в ПРОТИВНОМ СЛУЧАЕ
ИЩЕМ~$\alpha$, НАХОДЯ САМУЮ ДЛИННУЮ ПРИСТАВКУ~$b_1\ldots{}b_k$,
СООТВЕТСТВУЮЩУЮ КЛЮЧУ. еСЛИ БОЛЕЕ ЧЕМ ОДИН КЛЮЧ НАЧИНАЕТСЯ
С~$b_1\ldots{}b_k$, ТО ЭЛЕМЕНТ~$\alpha$ НЕ ПРИНАДЛЕЖИТ~$H$; В ПРОТИВНОМ
СЛУЧАЕ ОБОЗНАЧИМ ЭТОТ ЕДИНСТВЕННЫЙ КЛЮЧ
ЧЕРЕЗ~$b_1\ldots{}b_kc_1\ldots{}c_l=\theta^e_l$ И ЗАМЕНИМ~$\alpha$
НА~$\theta^{-e}_l\alpha=c^{-1}_l\ldots{}c^{-1}_1b_{k+1}\ldots{}b_r$. еСЛИ
ЭТО НОВОЕ ЗНАЧЕНИЕ~$\alpha$ ДЛИННЕЕ СТАРОГО (Т.~Е.\ ЕСЛИ~$l>k$),
$\alpha$~НЕ ПРИНАДЛЕЖИТ~$H$; В ПРОТИВНОМ СЛУЧАЕ ПОВТОРЯЕМ ПРОЦЕСС С НОВЫМ
ЗНАЧЕНИЕМ~$\alpha$. сВОЙСТВО нИЛЬСЕНА ГАРАНТИРУЕТ КОНЕЧНОСТЬ ЭТОГО
АЛГОРИТМА. еСЛИ УДАЛОСЬ СВЕСТИ~$\alpha$ К ПУСТОЙ ЦЕПОЧКЕ, МЫ МОЖЕМ
ВОССТАНОВИТЬ ИСХОДНОЕ ПРЕДСТАВЛЕНИЕ~$\alpha$ В ВИДЕ ПРОИЗВЕДЕНИЙ~$\theta_i$.
нАПРИМЕР, ПУСТЬ $\set{\theta_1, \theta_2, \theta_3}=\set{bbb,
b^{-1}a^{-1}b^{-1}, ba^{-1}b}$ И~$\alpha=bbabaab$. лЕС
\picture{рИС. СТР. 599}
ВМЕСТЕ С ОПИСАННЫМ АЛГОРИТМОМ ПОЗВОЛЯЕТ
ПОЛУЧИТЬ~$\alpha=\theta_1\theta_3^{-1}\theta_1\theta_3^{-1}\theta_2^{-1}$.
рЕАЛИЗУЙТЕ ЭТОТ АЛГОРИТМ, ИСПОЛЬЗУЯ В КАЧЕСТВЕ ВХОДНЫХ ДАННЫХ ДЛЯ ВАШЕЙ
ПРОГРАММЫ~$\theta_i$.
\ex[23] \exhead(сЖАТИЕ СПЕРЕДИ И СЗАДИ.) еСЛИ НАБОР БИНАРНЫХ КЛЮЧЕЙ
ИСПОЛЬЗУЕТСЯ В КАЧЕСТВЕ УКАЗАТЕЛЯ ДЛЯ РАСЧЛЕНЕНИЯ БОЛЕЕ КРУПНОГО ФАЙЛА,
ТО НЕТ НУЖДЫ ХРАНИТЬ ПОЛНЫЕ КЛЮЧИ. нАПРИМЕР, ШЕСТНАДЦАТЬ КЛЮЧЕЙ РИС.~34
МОЖНО УРЕЗАТЬ СПРАВА ТАК, ЧТОБЫ ОСТАВАЛОСЬ ДОСТАТОЧНО ЦИФР ДЛЯ ИХ
ОДНОЗНАЧНОГО ОПРЕДЕЛЕНИЯ: $0000$, $0001$, $00100$, $00101$, $010$,~\dots,
$1110001$. тАКИЕ УРЕЗАННЫЕ КЛЮЧИ МОЖНО ИСПОЛЬЗОВАТЬ ДЛЯ РАСЧЛЕНЕНИЯ ФАЙЛА
НА СЕМНАДЦАТЬ ЧАСТЕЙ; НАПРИМЕР, ПЯТАЯ ЧАСТЬ СОСТОИТ ИЗ ВСЕХ КЛЮЧЕЙ,
НАЧИНАЮЩИХСЯ С~$0011$ ИЛИ~$010$, А ПОСЛЕДНЯЯ ЧАСТЬ СОДЕРЖИТ ВСЕ КЛЮЧИ,
НАЧИНАЮЩИЕСЯ С~$111001$, $11101$ ИЛИ~$1111$. уРЕЗАННЫЕ КЛЮЧИ МОЖНО
ПРЕДСТАВИТЬ БОЛЕЕ КОМПАКТНО, ЕСЛИ ОПУСТИТЬ ЛЕВЫЕ ЦИФРЫ, ОБЩИЕ С ПРЕДЫДУЩИМ
КЛЮЧОМ: $0000$, $***1$, $**100$, $****1$, $*10$,~\dots, $******1$. зА
ЗВЕЗДОЧКАМИ ВСЕГДА СЛЕДУЕТ ЕДИНИЦА, ПОЭТОМУ ЕЕ МОЖНО ОПУСТИТЬ в БОЛЬШОМ
ФАЙЛЕ БУДЕТ МНОГО ЗВЕЗДОЧЕК, И МЫ ДОЛЖНЫ ХРАНИТЬ ЛИШЬ ИХ ЧИСЛО И
ЗНАЧЕНИЯ СЛЕДУЮЩИХ БИТОВ. (нА ЭТОТ СПОСОБ СЖАТИЯ АВТОРУ УКАЗАЛИ
р.~э.~гЕЛЛЕР И~р.~л.~йОНСЕН.)
%%600
пОКАЖИТЕ, ЧТО СУММАРНОЕ ЧИСЛО БИТОВ В СЖАТОМ ФАЙЛЕ, ИСКЛЮЧАЯ ЗВЕЗДОЧКИ И
СЛЕДУЮЩУЮ ЗА НИМИ ЕДИНИЦУ, РАВНО ЧИСЛУ УЗЛОВ В БИНАРНОМ БОРУ, СОДЕРЖАЩЕМ
ЭТИ КЛЮЧИ.
(сЛЕДОВАТЕЛЬНО, СРЕДНЕЕ СУММАРНОЕ ЧИСЛО ТАКИХ БИТОВ ВО ВСЕМ
УКАЗАТЕЛЕ ПРИМЕРНО РАВНО~$N/(\ln 2)$, ЧТО СОСТАВЛЯЕТ ЛИШЬ ОКОЛО
$1.44$~БИТА НА КЛЮЧ. вОЗМОЖНО И ЕЩЕ БОЛЬШЕЕ СЖАТИЕ, ТАК КАК НАМ НУЖНО
ПРЕДСТАВИТЬ ЛИШЬ СТРУКТУРУ БОРА, СР.~С~ТЕОРЕМОЙ 2.3.1A).
\bye