\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
хСЛИ ВСТРЕЧАЕТСЯ ОДНА ИЗ УКАЗАННЫХ РЕДКИХ КАТЕГОРИЙ, МОЖНО ОТ
БОРОВОЙ ПАМЯТИ ПЕРЕЙТИ К НЕКОТОРОЙ ДРУГОЙ СХЕМЕ, НАПРИМЕР К
ПОСЛЕДОВАТЕЛЬНОМУ ПОИСКУ.

фРУГИМ СПОСОБОМ УМЕНЬШЕНИЯ ТРЕБУЕМОГО ДЛЯ СЛОВАРЯ ОБоЕМА  ПАМЯТИ ЯВЛЯЕТСЯ
ИСПОЛЬЗОВАНИЕ ПРИСТАВОК. эАПРИМЕР, ЕСЛИ ИЩЕТСЯ СЛОВО, НАЧИНАЮЩЕЕСЯ С 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" (ОРГАНИСТ)!

ьОЖНО ИСПОЛЬЗОВАТЬ ЦЕЛЫЙ РЯД ПРИЕМОВ ДЛЯ УМЕНЬШЕНИЯ ОБоЕМА ПАМЯТИ. эО КАК
В ЕДИНОЙ СИСТЕМЕ КОМПАКТНО ПРЕДСТАВИТЬ РАЗНООБРАЗИЕ МЕТОДОВ? юТВЕТ
СОСТОИТ В ТОМ, ЧТОБЫ ТРАКТОВАТЬ СЛОВАРЬ КАК \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 яРИМ. ПЕРЕВ.\/}},
ОСОБЕННО ПОДХОДИТ ДЛЯ РАБОТЫ С ОЧЕНЬ ДЛИННЫМИ КЛЮЧАМИ ПЕРЕМЕННОЙ ДЛИНЫ,
ТАКИМИ, КАК ЗАГОЛОВКИ ИЛИ ФРАЗЫ, ХРАНЯЩИЕСЯ В ФАЙЛЕ БОЛЬШОГО ОБоЕМА.

юСНОВНАЯ ИДЕЯ яАТРИЦИИ СОСТОИТ В ТОМ, ЧТОБЫ СТРОИТЬ БИНАРНОЕ ДЕРЕВО,
ИЗБЕГАЯ ОДНОПУТЕВЫХ РАЗВЕТВЛЕНИЙ, ДЛЯ ЧЕГО В КАЖДЫЙ УЗЕЛ ВКЛЮЧАЕТСЯ ЧИСЛО,
ПОКАЗЫВАЮЩЕЕ, СКОЛЬКО БИТОВ
%%584
НУЖНО ПРОПУСТИТЬ, ПЕРЕД ТЕМ КАК ДЕЛАТЬ СЛЕДУЮЩУЮ ПРОВЕРКУ. ёУЩЕСТВУЕТ
НЕСКОЛЬКО СПОСОБОВ РЕАЛИЗАЦИИ ЭТОЙ ИДЕИ; ВОЗМОЖНО, ПРОСТЕЙШИЙ С ТОЧКИ
ЗРЕНИЯ ОБоЯСНЕНИЯ ИЗОБРАЖЕН НА РИС.~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|---ЧИСЛО БИТОВ, КОТОРЫЕ НУЖНО ПРОПУСТИТЬ ПРИ ПОИСКЕ, КАК
ОБоЯСНЯЛОСЬ ВЫШЕ. ¤ТО ПОЛЕ ДОЛЖНО БЫТЬ ДОСТАТОЧНО БОЛЬШИМ ДЛЯ ТОГО, ЧТОБЫ
ВМЕСТИТЬ НАИБОЛЬШЕЕ ЧИСЛО~$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{-АРНЫЙ}$ ЦИФРОВОЙ ПОИСК). юБоЯСНИТЕ, КАК ИЗ АЛГОРИТМОВ~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