\input style
\chapno=6\subchno=2\chapnotrue
\subchap{cIFROVOJ POISK} % 6.3
vMESTO TOGO CHTOBY OSNOVYVATX METOD POISKA NA SRAVNENII KLYUCHEJ, MOZHNO
VOSPOLXZOVATXSYA IH PREDSTAVLENIEM V VIDE POSLEDOVATELXNOSTI CIFR ILI
BUKV. rASSMOTRIM, NAPRIMER, IMEYUSHCHIESYA VO MNOGIH SLOVARYAH "POBUKVENNYE
VYSECHKI"; PO PERVOJ BUKVE DANNOGO SLOVA MY MOZHEM NEMEDLENNO NASHCHUPATX
STRANICY, SODERZHASHCHIE VSE SLOVA, NACHINAYUSHCHIESYA S |TOJ BUKVY.

eSLI RAZVITX IDEYU "POBUKVENNYH VYSECHEK", MY PRIDEM K SHEME POISKA,
OSNOVANNOJ NA "INDEKSIROVANII", KAK POKAZANO V TABL.~1. pREDPOLOZHIM,
TREBUETSYA PROVERITX, PRINADLEZHIT LI DANNYJ ARGUMENT POISKA K 31~NAIBOLEE
UPOTREBITELXNOMU ANGLIJSKOMU SLOVU (SR.~S~RIS.~12 I~13, P.~6.2.2). v
TABL.~1 DANNYE PREDSTAVLENY V VIDE TAK NAZYVAEMOJ STRUKTURY "BORA";
TERMIN VVEDEN e.~fR|DKINOM [{\sl CACM,\/} {\bf 3} (1960), 490--500]
KAK CHASTX SLOVA VY{\it BOR}KA\note{1}%
{v ORIGINALE SOOTVETSTVENNO trie (ISKAZHENNOE "tree") I
re{\it trie}val---{\sl pRIM. PEREV.\/}}
 (INFORMACII). bOR V SUSHCHNOSTI YAVLYAETSYA $M\hbox{-ARNYM}$ DEREVOM, UZLY
KOTOROGO SUTX $M\hbox{-MESTNYE}$ VEKTORY S KOMPONENTAMI, SOOTVETSTVUYUSHCHIMI
CIFRAM ILI BUKVAM. kAZHDYJ UZEL UROVNYA~$l$ PREDSTAVLYAET MNOZHESTVO VSEH
KLYUCHEJ, NACHINAYUSHCHIHSYA S OPREDELENNOJ POSLEDOVATELXNOSTI IZ $l$~LITER; UZEL
OPREDELYAET $M\hbox{-PUTEVOE}$ RAZVETVLENIE V ZAVISIMOSTI OT
$(l+1)\hbox{-J}$ LITERY.

nAPRIMER, BOR TABL.~1 IMEET 12~UZLOV; UZEL~1---KORENX, I PERVUYU BUKVU
SLEDUET ISKATX ZDESX. eSLI PERVOJ OKAZALASX, SKAZHEM, BUKVA~|N|, IZ TABLICY
VIDNO, CHTO NASHIM SLOVOM BUDET |NOT| (ILI ZHE, CHTO EGO NET V TABLICE). s
DRUGOJ STORONY, ESLI PERVAYA BUKVA---|W|, UZEL~(1) NAPRAVIT NAS K UZLU~(9),
GDE MY DOLZHNY ANALOGICHNYM OBRAZOM OTYSKATX VTORUYU BUKVU; UZEL~(9) UKAZHET,
CHTO |TOJ BUKVOJ DOLZHNA BYTX~|A|, |H| ILI~|I|.

uZLY-VEKTORY V TABL.~1 ORGANIZOVANY V SOOTVETSTVII S KODOM LITER, PRINYATYM
DLYA \MIX. eTO OZNACHAET, CHTO POISK PO BORU BUDET DOVOLXNO BYSTRYM, TAK KAK
MY DOLZHNY PROSTO VYBIRATX SLOVA IZ MASSIVA, ISPOLXZUYA V KACHESTVE INDEKSOV
LITERY NASHEGO KLYUCHA. mETODY BYSTROGO MNOGOPUTEVOGO RAZVETVLENIYA S
POMOSHCHXYU INDEKSIROVANIYA NAZYVAYUTSYA "PROSMOTROM TABLIC" ("Table Look-At") V
PROTIVOPOLOZHNOSTX "POISKU PO TABLICAM" ("Table Look-Up")
[SM.~P.~M.~Sherman, {\sl CACM,\/} {\bf 4} (1961), 172--173, 175].

\alg t.(pOISK PO BORU.) aLGORITM POZVOLYAET NAJTI DANNYJ ARGUMENT~$K$ V
TABLICE ZAPISEJ, OBRAZUYUSHCHIH $M\hbox{-ARNYJ}$ BOR.
%%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{tABLICA 1}%
{"bOR" DLYA 31 NAIBOLEE UPOTREBITELXNOGO ANGLIJSKOGO SLOVA}%
{\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
}
}
uZLY BORA PREDSTAVLYAYUT SOBOJ VEKTORY, INDEKSY KOTORYH IZMENYAYUTSYA OT~$0$
DO~$M-1$; KAZHDAYA KOMPONENTA |TIH VEKTOROV ESTX LIBO KLYUCH, LIBO SSYLKA
(VOZMOZHNO, PUSTAYA).
\st[nACHALXNAYA USTANOVKA.) uSTANOVITX UKAZATELX~|P| TAK, CHTOBY ON UKAZYVAL
NA KORENX BORA.

\st[rAZVETVLENIE.] zANESTI V~$k$ SLEDUYUSHCHUYU (STOYASHCHUYU PRAVEE) LITERU
ARGUMENTA~$K$. (eSLI ARGUMENT POLNOSTXYU OBRABOTAN, MY ZASYLAEM V~$k$
"PROBEL" ILI SIMVOL KONCA SLOVA. lITERA DOLZHNA BYTX PREDSTAVLENA CELYM
CHISLOM V DIAPAZONE~$0\le k<M$.) chEREZ~$X$ OBOZNACHIM $k\hbox{-J}$~|LEMENT V UZLE~$|NODE|(|P|)$.
%%574
eSLI $X$---SSYLKA, PEREJTI NA \stp{3}; ESLI $X$---KLYUCH, TO PEREJTI NA~\stp{4}.

\st[pRODVIZHENIE.] eSLI $X\ne\NULL$, USTANOVITX $P\asg X$ I
VERNUTXSYA NA~\stp{2}; V PROTIVNOM SLUCHAE ALGORITM ZAKANCHIVAETSYA NEUDACHNO.

\st[sRAVNENIE.] eSLI $K=X$, ALGORITM ZAKANCHIVAETSYA UDACHNO;
V PROTIVNOM SLUCHAE ON ZAKANCHIVAETSYA NEUDACHNO.
\algend

zAMETIM, CHTO, ESLI POISK NEUDACHEN, VSE ZHE BUDET NAJDEN |LEMENT, LUCHSHE
\emph{VSEGO SOVPADAYUSHCHIJ} S ARGUMENTOM POISKA. eTO SVOJSTVO POLEZNO DLYA
NEKOTORYH PRILOZHENIJ.

chTOBY SRAVNITX VREMYA RABOTY ALGORITMA I DRUGIH ALGORITMOV DANNOJ GLAVY,
MOZHNO NAPISATX KOROTKUYU PROGRAMMU DLYA \MIX, PREDPOLAGAYA, CHTO LITERA
ZANIMAET ODIN BAJT, A KLYUCHI--- NE BOLEE PYATI BAJTOV.

\prog t.(pOISK PO BORU.) pREDPOLAGAETSYA, CHTO VSE KLYUCHI ZANIMAYUT ODNO SLOVO
MASHINY~\MIX; ESLI KLYUCH SOSTOIT MENEE CHEM IZ PYATI LITER, ON DOPOLNYAETSYA
SPRAVA PROBELAMI. tAK KAK MY ISPOLXZUEM DLYA PREDSTAVLENIYA LITER KOD~\MIX,
KAZHDYJ BAJT ARGUMENTA POISKA DOLZHEN SODERZHATX CHISLO, MENXSHEE~30.
sSYLKI PREDSTAVLENY KAK OTRICATELXNYE CHISLA V POLE~$0:2$.
zNACHENIYA REGISTROV: $|rI1|\equiv|P|$, $|rX|\equiv\hbox{NEOBRABOTANNAYA
CHASTX $K$}$.
\code
START  &LDX  &k       &1& T1. nACHALXNAYA USTANOVKA.
       &ENT1 &ROOT    &1& $|P|\asg\hbox{UKAZATELX NA KORENX BORA}$.
2H     &SLAX &1       &C& T2. rAZVETVLENIE.
       &STA  &*+1(2:2)&C& vYDELENIE SLEDUYUSHCHEJ LITERY~$k$.
       &ENT2 &0,1     &C& $|Q|\asg|P|+k$.
       &LD1N &0,2(0:2)&C& $|P|\asg|LINK|(|Q|)$.
       &J1P  &2B      &C& Tz. pRODVIZHENIE. nA T2, ESLI |P|---SSYLKA $\ne\NULL$.
       &LDA  &0,2     &1& t4. sRAVNENIE. $|rA|\asg|KEY|(|Q|)$.
       &CMPA &K       &1
       &JE   &SUCCESS &1& uDACHNYJ VYHOD, ESLI $|rA|=k$.
FAILURE&EQU  &*       &1& vYHOD, ESLI $K$ NET V BORU.
\endcode
vREMYA RABOTY PROGRAMMY RAVNO $(8C+8)u$, GDE $C$---CHISLO PROVERYAEMYH LITER.
tAK KAK $C\le5$, POISK NE ZAJMET BOLEE 48~EDINIC VREMENI.

eSLI TEPERX SRAVNITX |FFEKTIVNOSTX |TOJ PROGRAMMY (ISPOLXZUYUSHCHEJ BOR
TABL.~1) I PROGRAMMY~6.2.2t (ISPOLXZUYUSHCHEJ \emph{OPTIMALXNOE} BINARNOE
DEREVO POISKA (RIS.~13)), MOZHNO ZAMETITX SLEDUYUSHCHEE:

1.~bOR ZANIMAET GORAZDO BOLXSHE PAMYATI: DLYA PREDSTAVLENIYA 31~KLYUCHA
ISPOLXZOVANO 360~SLOV, V TO VREMYA KAK BINARNOE DEREVO POISKA ZANIMAET
62~SLOVA PAMYATI. (oDNAKO UPR.~4 POKAZYVAET, CHTO, PROYAVIV IZVESTNUYU
IZOBRETATELXNOSTX, MOZHNO VMESTITX BOR TABL.~1 V 49 SLOV.)

%%575
\picture{rIS. 31. bOR TABL. 1, PREOBRAZOVANNYJ V "LES".}
%%576

2.~uDACHNYJ POISK V OBOIH SLUCHAYAH TREBUET OKOLO 26~EDINIC VREMENI. nO
NEUDACHNYJ POISK OKAZYVAETSYA BOLEE BYSTRYM DLYA BORA I BOLEE MEDLENNYM DLYA
BINARNOGO DEREVA POISKA. dLYA NASHIH DANNYH POISK CHASHCHE BUDET NEUDACHNYM,
NEZHELI UDACHNYM, PO|TOMU S TOCHKI ZRENIYA SKOROSTI BOR BOLEE PREDPOCHTITELEN.

3.~eSLI VMESTO 31~NAIBOLEE UPOTREBITELXNOGO ANGLIJSKOGO SLOVA RASSMOTRIM
PRIMENENIE UKAZATELYA~KWIC (RIS.~15), BOR TERYAET SVOI PREIMUSHCHESTVA
VSLEDSTVIE HARAKTERA DANNYH. nAPRIMER, BOR TREBUET 12~ITERACIJ, CHTOBY
RAZLICHITX SLOVA |COMPUTATION| I~|COMPUTATIONS|. (v |TOM SLUCHAE BYLO BY
LUCHSHE TAK POSTROITX BOR, CHTOBY SLOVA OBRABATYVALISX SPRAVA NALEVO, A NE
SLEVA NAPRAVO.)

pERVAYA PUBLIKACIYA O BOROVOJ PAMYATI PRINADLEZHIT rENE DE~LA~bRIANDE
[Proc.~Western Joint Computer Conf., {\bf 15} (1959), 295--298]. oN UKAZAL,
 CHTO MOZHNO S|KONOMITX PAMYATX (ZA SCHET UVELICHENIYA VREMENI RABOTY), ESLI
ISPOLXZOVATX SVYAZANNYJ SPISOK DLYA KAZHDOGO UZLA-VEKTORA, TAK KAK
BOLXSHINSTVO |LEMENTOV |TOGO VEKTORA OBYCHNO PUSTO. nA SAMOM DELE
PREDLOZHENNAYA IDEYA VEDET K ZAMENE BORA TABL.~1 NA LES DEREVXEV,
 IZOBRAZHENNYJ NA RIS.~31. pRI POISKE V TAKOM LESU MY NAHODIM KORENX,
SOOTVETSTVUYUSHCHIJ PERVOJ LITERE, ZATEM SYNA |TOGO KORNYA, SOOTVETSTVUYUSHCHEGO
VTOROJ LITERE, I~T.~D.

fAKTICHESKI V SVOEJ STATXE DE LA bRIANDE NE PRERYVAL RAZVETVLENIYA TAK,
KAK POKAZANO V TABL.~1 ILI NA RIS.~31; VMESTO |TOGO ON PREDSTAVLYAL KAZHDYJ
KLYUCH LITERA ZA LITEROJ DO DOSTIZHENIYA PRIZNAKA KONCA SLOVA. tAKIM OBRAZOM,
 V DEJSTVITELXNOSTI DE~LA~bRIANDE VMESTO DERENA "|H|" (RIS.~31)
ISPOLXZOVAL BY
\picture{rIS. STR. 576}
tAKOE PREDSTAVLENIE TREBUET BOLXSHE PAMYATI, NO DELAET OBRABOTKU DANNYH
PEREMENNOJ DLINY OSOBENNO LEGKOJ. eSLI ISPOLXZOVATX NA LITERU DVA POLYA
SSYLOK, MOZHNO LEGKO ORGANIZOVATX DINAMICHESKIE VSTAVKI I UDALENIYA. bOLEE
TOGO, VO MNOGIH PRILOZHENIYAH ARGUMENT POISKA POSTUPAET V "RASPAKOVANNOJ"
FORME, T.~E.~KAZHDAYA LITERA ZANIMAET CELOE SLOVO, I TAKOE DEREVO POZVOLYAET
IZBEZHATX "UPAKOVKI" PERED PROVEDENIEM POISKA.
%%577
%%577

eSLI ISPOLXZOVATX OBYCHNYJ SPOSOB PREDSTAVLENIYA DEREVXEV V BINARNOM VIDE,
TO (1) PREOBRAZUETSYA V BINARNOE DEREVO
(dLYA PREDSTAVLENIYA POLNOGO LESA RIS.~31 NEOBHODIMO DOBAVITX UKAZATELX,
VEDUSHCHIJ IZ~|H| NAPRAVO, K SOSEDNEMU KORNYU~|I|.) pRI POISKE V |TOM BINARNOM
DEREVE LITERY ARGUMENTA SRAVNIVAYUTSYA S LITERAMI DEREVA; MY SLEDUEM PO
SSYLKAM~|RLINK|, POKA NE NAJDEM NUZHNUYU LITERU; ZATEM BEREM SSYLKU~|LLINK|
I SLEDUYUSHCHUYU LITERU ARGUMENTA RASSMATRIVAEM ANALOGICHNYM OBRAZOM.

pOISK V TAKOM BINARNOM DEREVE V BOLXSHEJ ILI MENXSHEJ STEPENI SVODITSYA K
SRAVNENIYAM, PRICHEM RAZVETVLENIE PROISHODIT NE PO PRIZNAKU "MENXSHE-BOLXSHE",
A PO "RAVNO-NERAVNO". eLEMENTARNAYA TEORIYA P.~6.2.1 GLASIT, CHTO V SREDNEM
NA TO, CHTOBY RAZLICHITX $N$~KLYUCHEJ, NUZHNO PO KRAJNEJ MERE $\log_2 N$~SRAVNENIJ;
SREDNEE CHISLO SRAVNENIJ, PROIZVODIMYH PRI POISKE PO
DEREVU, PODOBNOMU IZOBRAZHENNOMU NA RIS.~31, NE MENXSHE CHISLA PROVEROK PRI
ISPOLXZOVANII METODOV BINARNOGO POISKA, IZLOZHENNYH V \S~6.2.

s DRUGOJ STORONY, BOR TABL.~1 POZVOLYAET SRAZU
PROIZVODITX $M\hbox{-PUTEVOE}$ RAZVETVLENIE; MY UVIDIM, CHTO PRI
BOLXSHIH~$N$ POISK V SREDNEM VKLYUCHAET LISHX OKOLO
$\log_M N=\log_2 N/\log_2 M$~ITERACIJ,
ESLI ISHODNYE DANNYE---SLUCHAJNYE CHISLA. mY UVIDIM TAKZHE, CHTO
PRIMENENIE SHEMY BORA V "CHISTOM" VIDE (KAK V ALGORITME~T) TREBUET PORYADKA
$N/\ln M$~UZLOV, ESLI NUZHNO RAZLICHITX $N$~SLUCHAJNYH KLYUCHEJ;
SLEDOVATELXNO, RAZMER ZANIMAEMOJ PAMYATI PROPORCIONALEN $MN/\ln M$.

eTI RASSUZHDENIYA POKAZYVAYUT, CHTO IDEYA BORA HOROSHA LISHX DLYA NEBOLXSHOGO CHISLA
VERHNIH UROVNEJ DEREVA. mOZHNO ULUCHSHITX HARAKTERISTIKI, KOMBINIRUYA DVE
STRATEGII: DLYA NESKOLXKIH PERVYH LITER ISPOLXZOVATX BOR, A ZATEM PEREJTI
NA DRUGUYU METODIKU. nAPRIMER, e.~g.~sASSENGAT, ML.\ [e.~n.~Sassenguth,
 {\sl CACM,\/} {\bf 6} (1963), 272--279] PREDLOZHIL ISPOLXZOVATX
LITERNYJ ANALIZ DO DOSTIZHENIYA TOJ CHASTI DEREVA, GDE OSTAETSYA, SKAZHEM, NE
BOLEE SHESTI KLYUCHEJ, A ZATEM PROIZVESTI V |TOM KOROTKOM SPISKE
POSLEDOVATELXNYJ POISK. dALEE MY UVIDIM, CHTO TAKAYA SMESHANNAYA STRATEGIYA
UMENXSHAET KOLICHESTVO UZLOV BORA PRIMERNO V SHESTX RAZ BEZ SUSHCHESTVENNOGO
IZMENENIYA VREMENI RABOTY.

%%578

\section pRILOZHENIE K ANGLIJSKOMU YAZYKU. nAPRASHIVAETSYA MNOGO IZMENENIJ
OSNOVNYH STRATEGIJ BORA I POLITERNOGO POISKA. chTOBY POLUCHITX PREDSTAVLENIE
O NEKOTORYH IZ IMEYUSHCHIHSYA VOZMOZHNOSTEJ, RASSMOTRIM GIPOTETICHESKOE
KRUPNOMASSHTABNOE PRILOZHENIE: PREDPOLOZHIM, CHTO V PAMYATI evm NUZHNO
ZAPOMNITX DOVOLXNO POLNYJ SLOVARX ANGLIJSKOGO YAZYKA. dLYA |TOGO
TREBUETSYA DOSTATOCHNO BOLXSHAYA VNUTRENNYAYA PAMYATX, SKAZHEM NA 50000~SLOV. nASHA
CELX SOSTOIT V NAHOZHDENII |KONOMNOGO SPOSOBA PREDSTAVLENIYA SLOVARYA,
OBESPECHIVAYUSHCHEGO PRI |TOM DOSTATOCHNO BYSTRYJ POISK.

rEALIZACIYA TAKOGO PROEKTA---ZADACHA NEPROSTAYA. tREBUETSYA KAK HOROSHEE ZNANIE
SODERZHANIYA SLOVARYA, TAK I ZNACHITELXNAYA PROGRAMMISTSKAYA IZOBRETATELXNOSTX.
dAVAJTE NA NEKOTOROE VREMYA POSTAVIM SEBYA V POLOZHENIE CHELOVEKA,
PRISTUPAYUSHCHEGO K TAKOMU KRUPNOMU PROEKTU.

oBYCHNYJ UNIVERSITETSKIJ SLOVARX SODERZHIT SVYSHE 100000~SLOV; NASHI ZAPROSY
NE STOLX VELIKI, NO RASSMOTRENIE PODOBNOGO SLOVARYA POZVOLYAET NAMETITX
PUTI K RESHENIYU. eSLI MY POPYTAEMSYA PRIMENITX BOROVUYU PAMYATX, TO VSKORE
ZAMETIM VOZMOZHNOSTX VAZHNYH UPROSHCHENIJ. pREDPOLOZHIM, CHTO SOBSTVENNYE IMENA
I SOKRASHCHENIYA V RASCHET NE PRINIMAYUTSYA. tOGDA, ESLI SLOVO NACHINAETSYA NA
BUKVU~b, EGO VTORAYA BUKVA OBYAZATELXNO OTLICHNA OT b, c, d, f, g, j, k, m, n,
 p, q, s, t, v, w, x, z. [sLOVO "bdellium" ("BDELLIJ"--- ROD AROMATICHESKOJ
SMOLY) MOZHNO I NE VKLYUCHATX V SLOVARX!] nA SAMOM DELE, TE ZHE 17~BUKV
NE MOGUT STOYATX NA VTOROM MESTE V SLOVAH, NACHINAYUSHCHIHSYA S c, d, f, g, h, j,
k, 1, m, n, p, r, t, v, w, x, z. iSKLYUCHENIE SOSTAVLYAYUT NESKOLXKO SLOV,
NACHINAYUSHCHIHSYA S ct, cz, dw, fj, gn, mn, nt, pf, pn, pt, tc, tm, ts, tz, zw,
I ZAMETNOE KOLICHESTVO SLOV, NACHINAYUSHCHIHSYA S kn, ps, tw. oDIN IZ SPOSOBOV
ISPOLXZOVATX |TOT FAKT SOSTOIT V KODIROVANII BUKV (NAPRIMER, MOZHNO IMETX
TABLICU IZ 26~SLOV I VYPOLNYATX KOMANDU VRODE "|LD1 TABLE,1|") TAKIM
OBRAZOM, CHTOBY SOGLASNYE b, c, d,~\dots, z PEREVODILISX V SPECIALXNOE
PREDSTAVLENIE, BOLXSHEE, CHEM CHISLOVOJ KOD OSTAVSHIHSYA BUKV a, e, h, i, l,
o, r, u, y. tEPERX MNOGIE UZLY BORA MOGUT BYTX UKOROCHENY DO 9-PUTEVOGO
RAZVETVLENIYA; SPECIALXNAYA YACHEJKA VYHODA ISPOLXZUETSYA DLYA REDKO
VSTRECHAYUSHCHIHSYA BUKV. tAKOJ PODHOD POZVOLYAET S|KONOMITX PAMYATX VO MNOGIH
CHASTYAH BORA, PREDNAZNACHENNOGO DLYA ANGLIJSKOGO YAZYKA, A NE TOLXKO PRI
OBRABOTKE VTOROJ BUKVY.

v OBYCHNOM UNIVERSITETSKOM SLOVARE SLOVA NACHINAYUTSYA LISHX S~309 IZ
$26^2=676$~VOZMOZHNYH KOMBINACIJ DVUH BUKV, A IZ |TIH 309~PAR 88~SLUZHAT
NACHALOM 15 ILI MENEE SLOV. (tIPICHNYE PRIMERY TAKIH PAR: aa, ah, aj, ak,
ao, aq, ay, az, bd, bh,~\dots, xr, yc, yi, yp, yt, yu, yw, za, zu, zw;
BOLXSHINSTVO LYUDEJ MOZHET NAZVATX MAKSIMUM PO ODNOMU SLOVU IZ BOLXSHINSTVA
|TIH KATEGORIJ.)
%%579
eSLI VSTRECHAETSYA ODNA IZ UKAZANNYH REDKIH KATEGORIJ, MOZHNO OT
BOROVOJ PAMYATI PEREJTI K NEKOTOROJ DRUGOJ SHEME, NAPRIMER K
POSLEDOVATELXNOMU POISKU.

dRUGIM SPOSOBOM UMENXSHENIYA TREBUEMOGO DLYA SLOVARYA OB®EMA  PAMYATI YAVLYAETSYA
ISPOLXZOVANIE PRISTAVOK. nAPRIMER, ESLI ISHCHETSYA SLOVO, NACHINAYUSHCHEESYA S re-,
pre-, anti-, trans-, dis-, un- I~T.~D., MOZHNO OTDELITX PRISTAVKU I ISKATX
OSTATOK SLOVA. tAKIM PUTEM MOZHNO UDALITX MNOGO SLOV TIPA reapply
(POVTORNO PRIMENYATX), recompute (SNOVA VYCHISLITX), redecorate
(ZANOVO DEKORIROVATX), redesign (PEREPROEKTIROVATX), redeposit
(PEREKLADYVATX) I~T.~D.; ODNAKO NUZHNO OSTAVITX SLOVA VRODE
remainder (OSTATOK), requirement (TREBOVANIE), retain (SOHRANYATX),
remove (UDALYATX), readily (OHOTNO) I T.~D., TAK KAK IH ZNACHENIYA
BEZ PRISTAVKI "re-" POKRYTY TAJNOJ. iTAK, SNACHALA SLEDUET ISKATX SLOVO I
LISHX ZATEM PYTATXSYA UDALITX PRISTAVKU, ESLI PERVYJ POISK OKAZALSYA NEUDACHNYM.

eSHCHE VAZHNEE ISPOLXZOVATX SUFFIKSY. nE VYZYVAET SOMNENIJ, CHTO DVUKRATNOE
VKLYUCHENIE KAZHDOGO SUSHCHESTVITELXNOGO I GLAGOLA V EDINSTVENNOM I
MNOZHESTVENNOM CHISLE BYLO BY SLISHKOM RASTOCHITELXNYM; IMEYUTSYA I DRUGIE
TIPY SUFFIKSOV. nAPRIMER, SLEDUYUSHCHIE OKONCHANIYA MOZHNO DOBAVLYATX KO MNOGIM
GLAGOLXNYM OSNOVAM, POLUCHAYA NABOR RODSTVENNYH SLOV:
\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
}
(mNOGIE IZ |TIH SUFFIKSOV SAMI SOSTAVLENY IZ SUFFIKSOV.) eSLI POPYTATXSYA
DOBAVITX |TI SUFFIKSY K OSNOVAM
\ctable{
#-\hfill\cr
comput\cr
calculat\cr
search\cr
suffix\cr
translat\cr
interpret\cr
confus\cr
}
MY UVIDIM, KAK MNOGO SLOV POLUCHAETSYA; |TO CHREZVYCHAJNO UVELICHIVAET
VMESTIMOSTX NASHEGO SLOVARYA. bEZUSLOVNO, PRI TAKOJ
%% 580
PROCEDURE POLUCHAETSYA I MNOGO NESUSHCHESTVUYUSHCHIH SLOV, NAPRIMER "compution";
OSNOVA computat- OKAZYVAETSYA STOLX ZHE NEOBHODIMOJ, KAK I comput-. oDNAKO
VREDA V |TOM NET, POSKOLXKU TAKIE KOMBINACII I NE BUDUT SLUZHITX
ARGUMENTAMI POISKA, A ESLI BY NEKIJ AVTOR PRIDUMAL BY SLOVO "computedly",
MY IMELI BY DLYA NEGO GOTOVYJ PEREVOD. zAMETIM, CHTO BOLXSHINSTVU
LYUDEJ PONYATNO SLOVO "confusability" (SMUSHCHAEMOSTX), HOTYA ONO VSTRECHAETSYA
V NEMNOGIH SLOVARYAH; NASH SLOVARX BUDET DAVATX PODHODYASHCHEE TOLKOVANIE. pRI
PRAVILXNOJ OBRABOTKE PRISTAVOK I SUFFIKSOV NASH SLOVARX SMOZHET IZ ODNOJ
LISHX GLAGOLXNOJ OSNOVY "establish" VYVESTI ZNACHENIE SLOVA
"antidisestablishmentarianism".

rAZUMEETSYA, NUZHNO ZABOTITXSYA O TOM, CHTOBY ZNACHENIE SLOVA POLNOSTXYU
OPREDELYALOSX OSNOVOJ I SUFFIKSOM; ISKLYUCHENIYA DOLZHNY BYTX VNESENY V SLOVARX
TAKIM OBRAZOM, CHTOBY IH MOZHNO BYLO NAJTI DO OBRASHCHENIYA K POISKU SUFFIKSA.
nAPRIMER, SHODSTVO MEZHDU SLOVAMI "socialism" (SOCIALIZM) I "socialist"
(SOCIALIST) SPOSOBNO TOLXKO SBITX S TOLKU PRI ANALIZE SLOV
"organism" (ORGANIZM) I "organist" (ORGANIST)!

mOZHNO ISPOLXZOVATX CELYJ RYAD PRIEMOV DLYA UMENXSHENIYA OB®EMA PAMYATI. nO KAK
V EDINOJ SISTEME KOMPAKTNO PREDSTAVITX RAZNOOBRAZIE METODOV? oTVET
SOSTOIT V TOM, CHTOBY TRAKTOVATX SLOVARX KAK \emph{PROGRAMMU}, NAPISANNUYU
NA SPECIALXNOM MASHINNOM YAZYKE DLYA SPECIALXNOJ \emph{INTERPRETIRUYUSHCHEJ
SISTEMY} (SR.~S~P.~1.43); ZAPISI V UZLE BORA MOZHNO TRAKTOVATX
KAK \emph{INSTRUKCII}. nAPRIMER, V TABL.~1 MY IMEEM DVA VIDA
"INSTRUKCIJ", A PROGRAMMA~T ISPOLXZUET ZNAKOVYJ BIT KAK KOD OPERACII;
ZNAK MINUS OZNACHAET OTVETVLENIE K DRUGOMU UZLU I PEREHOD K SLEDUYUSHCHEJ
LITERE ZA SLEDUYUSHCHEJ INSTRUKCIEJ, V TO VREMYA KAK ZNAK PLYUS VYZYVAET
SRAVNENIE ARGUMENTA S OPREDELENNYM KLYUCHOM.

v INTERPRETIRUYUSHCHEJ SISTEME DLYA NASHEGO SLOVARYA MY MOGLI BY IMETX OPERACII
SLEDUYUSHCHIH TIPOV:
\medskip
\item{$\bullet$}~pROVERKA $n$, $\alpha$, $\beta$. "eSLI SLEDUYUSHCHAYA LITERA
ARGUMENTA KODIRUETSYA CHISLOM~$k\le n$, PEREJTI V YACHEJKU~$\alpha+k$ ZA
SLEDUYUSHCHEJ INSTRUKCIEJ; V PROTIVNOM SLUCHAE PEREJTI V YACHEJKU~$\beta$".

\item{$\bullet$}~sRAVNENIE $n$, $\alpha$, $\beta$. "sRAVNITX OSTAVSHIESYA
LITERY ARGUMENTA S $n$~SLOVAMI, RASPOLOZHENNYMI V YACHEJKAH~$\alpha$,
$\alpha+1$,~\dots, $\alpha+n-1$. eSLI PODHODYASHCHEE SLOVO IMEET
ADRES~$\alpha+k$, POISK KONCHAETSYA UDACHNO I "ZNACHENIE" LEZHIT V
YACHEJKE~$\beta+k$,
NO ESLI PODHODYASHCHEGO SLOVA NET, POISK KONCHAETSYA NEUDACHNO".

\item{$\bullet$}~rASSHCHEPLENIE $\alpha$, $\beta$. "sLOVO, OBRABOTANNOE DO
DANNOGO MESTA, VOZMOZHNO, YAVLYAETSYA PRISTAVKOJ ILI OSNOVOJ. v PRODOLZHENIE
POISKA NUZHNO NAPRAVITXSYA V YACHEJKU A ZA SLEDUYUSHCHEJ INSTRUKCIEJ. eSLI |TOT
POISK NEUDACHEN, NEOBHODIMO PRODOLZHITX
%%681
POISK, RASSMATRIVAYA OSTAVSHIESYA LITERY ARGUMENTA KAK NOVYJ ARGUMENT.
 eSLI |TOT POISK UDACHEN, SKOMBINIROVATX NAJDENNOE "ZNACHENIE" SO
"ZNACHENIEM"~$\beta$".

\noindent oPERACIYA PROVERKI REALIZUET KONCEPCIYU POISKA PO BORU, A OPERACIYA
SRAVNENIYA OBOZNACHAET PEREHOD K POSLEDOVATELXNOMU POISKU. oPERACIYA
RASSHCHEPLENIYA SLUZHIT DLYA OBRABOTKI PRISTAVOK I SUFFIKSOV. mOZHNO,
OSNOVYVAYASX NA BOLEE DETALXNOM IZUCHENII SPECIFICHESKIH CHERT ANGLIJSKOGO
YAZYKA, PREDLOZHITX NEKOTORYE DRUGIE OPERACII. dALXNEJSHAYA |KONOMIYA PAMYATI
DOSTIGAETSYA ZA SCHET ISKLYUCHENIYA PARAMETRA~$\beta$ IZ KAZHDOJ INSTRUKCII,
TAK KAK PAMYATX MOZHET BYTX ORGANIZOVANA TAK, CHTOBY $\beta$~VYCHISLYALOSX S
POMOSHCHXYU~$\alpha$, $n$ ILI ADRESA INSTRUKCII.

bOLEE POLNAYA INFORMACIYA OB ORGANIZACII SLOVARYA IMEETSYA V INTERESNYH
STATXYAH sIDNEYA l|MBA I uILXYAMA yaKOBSENA,~ML.\
[{\sl Mechanical Translation,\/} {\bf 6} (1961), 76--107]; yu.~s.~shVARCA
[{\sl JACM,\/} {\bf 10} (1963), 413--439]; gALLI I~yaMADY
[{\sl IBM Systems J.,\/} {\bf 6} (1967), 192--207].

\section bINARNYJ SLUCHAJ. rASSMOTRIM TEPERX CHASTNYJ SLUCHAJ~$M=2$, KOGDA V
KAZHDYJ MOMENT VREMENI OBRABATYVAETSYA ODIN BIT ARGUMENTA POISKA.
rAZRABOTANY DVA INTERESNYH METODA, OSOBENNO PODHODYASHCHIE DLYA DANNOGO SLUCHAYA.

pERVYJ METOD, KOTORYJ MY BUDEM NAZYVATX \emph{CIFROVYM POISKOM  PO DEREVU},
 PREDLOZHEN kOFFMANOM I~iVOM
[{\sl CACM,\/} {\bf 13} (1970), 427--432, 436].
 tAK ZHE KAK I V ALGORITMAH POISKA PO DEREVU IZ P.~6.2.2, V UZLAH DEREVA
HRANYATSYA POLNYE KLYUCHI, NO DLYA VYBORA LEVOJ ILI PRAVOJ VETVI ISPOLXZUYUTSYA
NE REZULXTAT SRAVNENIYA KLYUCHEJ, A BITY ARGUMENTA. nA RIS.~32
IZOBRAZHENO DEREVO, POSTROENNOE |TIM METODOM; ONO SOSTAVLENO IZ
31~NAIBOLEE UPOTREBITELXNOGO ANGLIJSKOGO SLOVA, PRICHEM SLOVA
VSTAVLYALISX V PORYADKE UMENXSHENIYA CHASTOT. chTOBY POLUCHITX BINARNYE DANNYE
DLYA |TOJ ILLYUSTRACII, SLOVA ZAPISYVALISX V LITERNOM KODE MASHINY~\MIX\ S
POSLEDUYUSHCHIM PREOBRAZOVANIEM V DVOICHNYE CHISLA, SODERZHASHCHIE PO 5~BITOV V
BAJTE. tAKIM OBRAZOM, SLOVO |WHICH| PREVRATITSYA V "11010\ 01000\ 01001\
00011\ 01000".

chTOBY NAJTI |WHICH| NA RIS.~32, MY SNACHALA SRAVNIVAEM EGO SO SLOVOM~|THE|
V KORNE DEREVA. tAK KAK ONI NE SOVPADAYUT I PERVYJ BIT SLOVA~|WHICH|
RAVEN~1, NUZHNO IDTI VPRAVO I PROIZVESTI SRAVNENIE SO SLOVOM~|OF|. tAK KAK
SOVPADENIYA NE PROIZOSHLO I VTOROJ BIT |WHICH| RAVEN~1, MY IDEM VPRAVO
I SRAVNIVAEM NASH ARGUMENT SO SLOVOM |WITH| I T.~D.

dEREVO RIS.~32 POSTROENO SPOSOBOM, POHOZHIM NA SPOSOB POSTROENIYA DEREVA
RIS.~12 IZ P.~6.2.2, LISHX DLYA RAZVETVLENIYA VMESTO SRAVNENIJ ISPOLXZOVALISX
BITY KLYUCHEJ, PO|TOMU INTERESNO OTMETITX RAZNICU MEZHDU NIMI. eSLI
RASSMOTRETX ZADANNYE CHASTOTY, CIFROVOJ POISK PO DEREVU RIS.~32 TREBUET
%%582
V SREDNEM $3.42$~SRAVNENIYA NA UDACHNYJ POISK; |TO NESKOLXKO LUCHSHE, CHEM
$4.04$~SRAVNENIYA, TREBUYUSHCHEGOSYA DLYA RIS.~12, HOTYA, RAZUMEETSYA, VREMYA SAMOGO
SRAVNENIYA BUDET RAZLICHNYM V DVUH |TIH SLUCHAYAH.

\picture{rIS. 32. dEREVO CIFROVOGO POISKA DLYA 31 NAIBOLEE UPOTREBITELXNOGO
ANGLIJSKOGO SLOVA, SLOVA VSTAVLENY V PORYADKE UMENXSHENIYA CHASTOT.}
\alg D.(cIFROVOJ POISK PO DEREVU.) eTOT ALGORITM POZVOLYAET NAJTI DANNYJ
ARGUMENT~$K$ V TABLICE ZAPISEJ, OBRAZUYUSHCHIH OPISANNYM VYSHE SPOSOBOM
BINARNOE DEREVO. eSLI $K$ NET V TABLICE, V DEREVO V PODHODYASHCHEM MESTE
VSTAVLYAETSYA NOVYJ UZEL, SODERZHASHCHIJ~$K$.

kAK I V ALGORITME~6.2.2t, ZDESX PREDPOLAGAETSYA, CHTO DEREVO NEPUSTO, A EGO
UZLY SODERZHAT POLYA~|KEY|, |LLINK| I~|RLINK|. chITATELX UVIDIT, CHTO |TI
ALGORITMY POCHTI IDENTICHNY.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $|P|\asg|ROOT|$, $K1\asg K$.

\st[sRAVNENIE.] eSLI $K=|KEY| (|P|)$, POISK OKANCHIVAETSYA UDACHNO;
V PROTIVNOM SLUCHAE ZANESTI V~$b$ SAMYJ LEVYJ BIT~$K1$ I SDVINUTX~$K1$ NA
EDINICU VLEVO (T.~E.\ UDALITX |TOT BIT I DOBAVITX SPRAVA~0). eSLI $b=0$,
PEREJTI NA~\stp{3}; V PROTIVNOM SLUCHAE PEREJTI NA~\stp{4}.

\st[shAG VLEVO.] eSLI $|LLINK|(|P|)\ne\NULL$, USTANOVITX
$|P|\asg|LLINK|(|P|)$ I VERNUTXSYA NA~\stp{2}; V PROTIVNOM SLUCHAE PEREJTI NA~\stp{5}.

\st[shAG VPRAVO.] eSLI $|RLINK|(|P|)\ne\NULL$, USTANOVITX
$|P|\asg|RLINK|(|P|)$ I VERNUTXSYA NA~\stp{2}.
%%583
\st[vSTAVKA V DEREVO.] vYPOLNITX $|Q|\Asg|AVAIL|$, $|KEY|(|Q|)\asg K$,
 $|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$. eSLI~$b=0$,
USTANOVITX $|LLINK|(|P|)\asg |Q|$; V PROTIVNOM SLUCHAE $|RLINK| (|P|)\asg|Q|$.
\algend

aLGORITM~6.2.2T PO SUTI SVOEJ BINARNYJ, ODNAKO PRIVEDENNYJ ALGORITM, KAK
NETRUDNO ZAMETITX, MOZHNO LEGKO RASPROSTRANITX NA $M\hbox{-ARNYJ}$
CIFROVOJ POISK DLYA LYUBOGO $M\ge2$ (SM.~UPR.~13).

\picture{rIS. 33.         pRIMER TEKSTA I DEREVA pATRICII.}

dONALXD mORRISON [{\sl JACM,\/} {\bf 15} (1968), 514--534] PRIDUMAL OCHENX
PRIVLEKATELXNYJ SPOSOB FORMIROVANIYA $N\hbox{-UZLOVYH}$ DEREVXEV POISKA,
OSNOVANNYJ NA BINARNOM PREDSTAVLENII KLYUCHEJ, BEZ ZAPOMINANIYA KLYUCHEJ V
UZLAH. eGO METOD, NAZVANNYJ "pATRICIYA" (pRAKTICHESKIJ ALGORITM DLYA VYBORKI
INFORMACII, ZAKODIROVANNOJ BUKVAMI I CIFRAMI)\note{1}%
{v ORIGINALE "Patricia"---Practical Algorithm To Retrieve Information Coded
In Alphanumeric.---{\sl pRIM. PEREV.\/}},
OSOBENNO PODHODIT DLYA RABOTY S OCHENX DLINNYMI KLYUCHAMI PEREMENNOJ DLINY,
TAKIMI, KAK ZAGOLOVKI ILI FRAZY, HRANYASHCHIESYA V FAJLE BOLXSHOGO OB®EMA.

oSNOVNAYA IDEYA pATRICII SOSTOIT V TOM, CHTOBY STROITX BINARNOE DEREVO,
IZBEGAYA ODNOPUTEVYH RAZVETVLENIJ, DLYA CHEGO V KAZHDYJ UZEL VKLYUCHAETSYA CHISLO,
POKAZYVAYUSHCHEE, SKOLXKO BITOV
%%584
NUZHNO PROPUSTITX, PERED TEM KAK DELATX SLEDUYUSHCHUYU PROVERKU. sUSHCHESTVUET
NESKOLXKO SPOSOBOV REALIZACII |TOJ IDEI; VOZMOZHNO, PROSTEJSHIJ S TOCHKI
ZRENIYA OB®YASNENIYA IZOBRAZHEN NA RIS.~33. iMEETSYA MASSIV BITOV |TEXT|
(OBYCHNO DOVOLXNO DLINNYJ); ON MOZHET HRANITXSYA VO VNESHNEM FAJLE S PRYAMYM
DOSTUPOM, TAK KAK PRI KAZHDOM POISKE OBRASHCHENIE K NEMU PROISHODIT LISHX
RAZ. kAZHDYJ KLYUCH, KOTORYJ DOLZHEN HRANITXSYA V NASHEJ TABLICE, OPREDELYAETSYA
MESTOM NACHALA V TEKSTE; MOZHNO SCHITATX, CHTO ON IDET OT MESTA NACHALA DO
KONCA TEKSTA. (pATRICIYA NE ISHCHET TOCHNOGO RAVENSTVA MEZHDU KLYUCHOM I
ARGUMENTOM, A OPREDELYAET, SUSHCHESTVUET LI KLYUCH, \emph{NACHINAYUSHCHIJSYA} S ARGUMENTA.)

v PRIMERE, IZOBRAZHENNOM NA RIS.~33, IMEETSYA SEMX KLYUCHEJ, NACHINAYUSHCHIHSYA S
KAZHDOGO VHODYASHCHEGO V TEKST SLOVA, A IMENNO "|THIS| |IS| |THE| |HOUSE|
|THAT| |JACK| |BUILT|.", "|IS| |THE| |HOUSE| |THAT| |JACK| |BUILT|.",
~\dots, "|BUILT|.". nALAGAETSYA VAZHNOE OGRANICHENIE, SOSTOYASHCHEE V TOM, CHTO
\emph{ODIN KLYUCH NE MOZHET SLUZHITX NACHALOM DRUGOGO;} |TO USLOVIE VYPOLNYAETSYA,
 ESLI MY OKANCHIVAEM TEKST SPECIALXNYM KODOM KONCA TEKSTA (V DANNOM SLUCHAE
"|.|"), KOTORYJ NIGDE BOLXSHE NE POYAVLYAETSYA. tO ZHE OGRANICHENIE
PODRAZUMEVAETSYA V SHEME BORA ALGORITMA~T, GDE PRIZNAKOM KONCA SLUZHIL "\] ".

dEREVO, ISPOLXZUEMOE pATRICIEJ DLYA POISKA, DOLZHNO CELIKOM POMESHCHATXSYA V
OPERATIVNOJ PAMYATI, ILI EGO NUZHNO ORGANIZOVATX PO STRANICHNOJ SHEME,
OPISANNOJ V P.~6.2.4. oNO SOSTOIT IZ GOLOVY I $N-1$~UZLOV, PRICHEM UZLY
SODERZHAT NESKOLXKO POLEJ:
\medskip
{\narrower
\noindent|KEY|---UKAZATELX NA TEKST. eTO POLE DOLZHNO IMETX DLINU NE MENEE
$\log_2 C$~BITOV, GDE $C$---CHISLO LITER V TEKSTE. sLOVA, IZOBRAZHENNYE NA
RIS.~33 VNUTRI UZLOV, NA SAMOM DELE DOLZHNY BYTX PREDSTAVLENY UKAZATELYAMI
NA TEKST; NAPRIMER, VMESTO "|(JACK)|" UZEL SODERZHIT CHISLO~24
(NACHALXNUYU TOCHKU KLYUCHA "|JACK BUILT|.").

\noindent|LLINK| I~|RLINK|---SSYLKI VNUTRI DEREVA. oNI DOLZHNY IMETX DLINU NE
MENEE $\log_2 N$~BITOV.

\noindent|LTAG| I~|RTAG|---ODNOBITOVYE POLYA, PO KOTORYM MY MOZHEM SUDITX,
YAVLYAYUTSYA LI |LLINK| I~|RLINK| SOOTVETSTVENNO SSYLKAMI NA SYNOVEJ ILI NA
PREDKOV. pUNKTIRNYE LINII NA RIS.~33 SOOTVETSTVUYUT SSYLKAM, DLYA KOTORYH $|TAG|=1$.

\noindent|SKIP|---CHISLO BITOV, KOTORYE NUZHNO PROPUSTITX PRI POISKE, KAK
OB®YASNYALOSX VYSHE. eTO POLE DOLZHNO BYTX DOSTATOCHNO BOLXSHIM DLYA TOGO, CHTOBY
VMESTITX NAIBOLXSHEE CHISLO~$k$, DLYA KOTOROGO V DVUH RAZLICHNYH KLYUCHAH
NAJDUTSYA SOVPADAYUSHCHIE PODCEPOCHKI IZ $k$~BITOV; OBYCHNO DLYA
PRAKTICHESKIH CELEJ DOSTATOCHNO SCHITATX, CHTO $k$ NE SLISHKOM VELIKO, I
PRI PREVYSHENII RAZMEROV POLYA |SKIP| VYDAVATX SOOBSHCHENIE OB
%%585
OSHIBKE. nA RIS.~33 POLYA |SKIP| IZOBRAZHENY VNUTRI KAZHDOGO UZLA CHISLAMI.
\par}

gOLOVA SODERZHIT LISHX POLYA KEY, LLINK I LTAG.\medskip

pOISK V DEREVE pATRICII VYPOLNYAETSYA SLEDUYUSHCHIM OBRAZOM:
PREDPOLOZHIM, MY ISHCHEM SLOVO~|THAT| (BINARNOE PREDSTAVLENIE $10111\ 01000\
00001\ 10111$). pO SODERZHIMOMU POLYA |SKIP| V KORNEVOM UZLE~$\alpha$ MY
ZAKLYUCHAEM, CHTO SNACHALA NUZHNO PROVERITX PERVYJ BIT ARGUMENTA. oN RAVEN~1,
PO|TOMU NADO DVIGATXSYA VPRAVO. pOLE |SKIP| SLEDUYUSHCHEGO UZLA POBUZHDAET NAS
PROVERITX $1+11=12\hbox{-J}$~BIT ARGUMENTA. oN RAVEN~0, I MY IDEM VLEVO.
iZUCHIV POLE |SKIP| SLEDUYUSHCHEGO UZLA, VIDIM, CHTO NUZHNO PROVERITX
$12+1=13\hbox{-J}$~BIT, KOTORYJ RAVEN~0. tAK KAK $|LTAG|=1$, MY IDEM NA
UZEL~$\gamma$, KOTORYJ OTSYLAET NAS K MASSIVU |TEXT|. pO TOMU ZHE PUTI
POJDET POISK DLYA LYUBOGO ARGUMENTA, IMEYUSHCHEGO BINARNOE PREDSTAVLENIE $1xxxx\
xxxxx\ x00~\ldots$, PO|TOMU NUZHNO SRAVNITX ARGUMENT S NAJDENNYM KLYUCHOM.

pREDPOLOZHIM, S DRUGOJ STORONY, CHTO MY ISHCHEM NEKOTORYJ KLYUCH, NACHINAYUSHCHIJSYA
S~|TH|, ILI VSE TAKIE KLYUCHI. pOISK NACHINAETSYA, KAK I RANXSHE, NO V KONCE
KONCOV MY OBRATIMSYA K (NESUSHCHESTVUYUSHCHEMU) 12-MU~BITU DESYATIBITOVOGO
ARGUMENTA. tEPERX NUZHNO SRAVNITX ARGUMENT S FRAGMENTOM MASSIVA |TEXT|,
 KOTORYJ SPECIFICIRUETSYA V TEKUSHCHEM UZLE (V DANNOM SLUCHAE~$\gamma$);
ESLI SOVPADENIYA NE PROIZOSHLO, TO NE SUSHCHESTVUET KLYUCHA, NACHALOM KOTOROGO
SLUZHIT ARGUMENT POISKA; ESLI SOVPADENIE IMELO MESTO, ARGUMENT YAVLYAETSYA
NACHALOM LYUBOGO KLYUCHA, NA KOTORYJ UKAZYVAYUT PUNKTIRNYE LINII, VYHODYASHCHIE
IZ UZLA~$\gamma$ I EGO POTOMKOV.

bOLEE TOCHNO |TOT PROCESS OPISYVAETSYA SLEDUYUSHCHIM OBRAZOM.

\alg P.(pATRICIYA.) aLGORITM, ISPOLXZUYA MASSIV |TEXT| I DEREVO S OPISANNYMI
VYSHE POLYAMI |KEY|, |LLINK|, |RLINK|, |LTAG|, |RTAG| I~|SKIP| V UZLAH,
POZVOLYAET OPREDELITX, SUSHCHESTVUET LI V MASSIVE |TEXT| KLYUCH, NACHINAYUSHCHIJSYA
S ARGUMENTA~$K$. (eSLI IMEETSYA $r\ge1$ TAKIH KLYUCHEJ, MOZHNO ZA $O(r)$~SHAGOV
OPREDELITX RASPOLOZHENIE KAZHDOGO IZ NIH; SM.~UPR.~14.) pREDPOLAGAETSYA,
CHTO ESTX PO KRAJNEJ MERE ODIN KLYUCH.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $|P|\asg|HEAD|$
I~$j\asg0$ (pEREMENNAYA~|P| YAVLYAETSYA UKAZATELEM, KOTORYJ BUDET DVIGATXSYA
VNIZ PO DEREVU, A $j$---|TO SCHETCHIK, OPREDELYAYUSHCHIJ POZICII BITOV ARGUMENTA.)
zANESTI V $n$ KOLICHESTVO BITOV ARGUMENTA~$K$.

\st[shAG VLEVO.] uSTANOVITX $|Q|\asg|P|$ I~$|P|\asg|LLINK| (|Q|)$. eSLI
$|LTAG|(|Q|)=1$, PEREJTI NA~\stp{6}.

\st[pROPUSK BITOV.] (v |TOT MOMENT MY ZNAEM, CHTO, ESLI PERVYE $j$~BITOV
ARGUMENTA SOOTVETSTVUYUT NEKOTOROMU KLYUCHU, ONI SOOTVETSTVUYUT KLYUCHU,
NACHINAYUSHCHEMUSYA V~$|KEY|(|P|)$.) uSTANOVITX $j\asg j+|SKIP|(|P|)$.
eSLI~$j>n$, PEREJTI NA~\stp{6}.

%%586
\st[pROVERKA BITA.] v |TOT MOMENT MY ZNAEM, CHTO, ESLI PERVYE $(j-1)$~BITOV
SOOTVETSTVUYUT NEKOTOROMU KLYUCHU, ONI SOOTVETSTVUYUT KLYUCHU, NACHINAYUSHCHEMUSYA
V~$|KEY|(|P|)$. eSLI $j\hbox{-J}$~BIT~$K$ RAVEN~0, PEREJTI NA~\stp{2}; V
PROTIVNOM SLUCHAE PEREJTI NA~\stp{5}.

\st[shAG VPRAVO.] uSTANOVITX $|Q|\asg|P|$ I~$|P|\asg|RLINK|(|Q|)$.
eSLI~$|RTAG|(|Q|)=0$, PEREJTI NA~\stp{3}.

\st[sRAVNENIE.] (v |TOT MOMENT MY ZNAEM, CHTO, ESLI~$K$ SOOTVETSTVUET
NEKOTOROMU KLYUCHU, ON SOOTVETSTVUET KLYUCHU, NACHINAYUSHCHEMUSYA V~$|KEY|(|P|)$.)
sRAVNITX~$K$ S KLYUCHOM, NACHINAYUSHCHIMSYA V POZICII~$|KEY|(|P|)$
MASSIVA~|TEXT|. eSLI PROIZOSHLO SOVPADENIE $n$~PERVYH BITOV, ALGORITM
ZAKANCHIVAETSYA UDACHNO;
V SLUCHAE NESOVPADENIYA ON ZAKANCHIVAETSYA NEUDACHNO.
\algend

v UPR.~15 PREZHDE VSEGO POKAZANO, KAK MOZHNO OSUSHCHESTVITX POSTROENIE DEREVA
pATRICII. iMEETSYA TAKZHE VOZMOZHNOSTX DOBAVLYATX K TEKSTU I VSTAVLYATX NOVYE
KLYUCHI PRI USLOVII, CHTO NOVYJ TEKSTOVOJ MATERIAL OKANCHIVAETSYA OPREDELENNYM
RAZDELITELEM (NAPRIMER, SIMVOLOM KONCA TEKSTA, ZA KOTORYM
SLEDUET PORYADKOVYJ NOMER).

hARAKTER pATRICII SLEGKA PRICHUDLIV, I VSE EE DOSTOINSTVA ZAMETNY LISHX
VNIMATELXNOMU NABLYUDATELYU.

\section aNALIZ ALGORITMOV. zAVERSHIM |TOT RAZDEL MATEMATICHESKIM
IZUCHENIEM BOROV, DEREVXEV CIFROVOGO POISKA I pATRICII. vAZHNEJSHIE
VYVODY IZ |TOGO ANALIZA PRIVEDENY V SAMOM KONCE.
\picture{rIS. 34.             pRIMER SLUCHAJNOGO BINARNOGO BORA.}

rASSMOTRIM SNACHALA BINARNYE BORY, T.~E.~BORY S~$M=2$. nA RIS.~34 IZOBRAZHEN
BINARNYJ BOR, OBRAZUYUSHCHIJSYA, ESLI 16~KLYUCHEJ IZ PRIMEROV SORTIROVKI GL.~5
RASSMATRIVATX KAK DESYATIBITOVYE DVOICHNYE CHISLA. (kLYUCHI PRIVEDENY V
VOSXMERICHNOJ
%%587
ZAPISI, TAK CHTO, NAPRIMER, $1144$ PREDSTAVLYAET DESYATIBITOVOE CHISLO
$(1001100100)_2$.) kAK I V ALGORITME~T, MY ISPOLXZUEM BOR DLYA HRANENIYA
INFORMACII O LEVYH BITAH KLYUCHEJ DO TEH POR, POKA VPERVYE DOSTIGAETSYA TOCHKA,
 GDE KLYUCH OPREDELYAETSYA ODNOZNACHNO; TAM ON ZAPISYVAETSYA POLNOSTXYU.

eSLI SRAVNITX RIS.~34 S TABL.~5.2.2-3, OBNARUZHITSYA UDIVITELXNAYA
VZAIMOSVYAZX MEZHDU BOROVOJ PAMYATXYU I OBMENNOJ PORAZRYADNOJ SORTIROVKOJ.
(vOZMOZHNO, |TA VZAIMOSVYAZX YAVLYAETSYA OCHEVIDNOJ.) 22~UZLA RIS.~34 V TOCHNOSTI
SOOTVETSTVUYUT 22~STADIYAM RASCHLENENIYA V TABL.~5.2.2-3 (UZLY SLEDUET
NUMEROVATX V PRYAMOM PORYADKE). chISLO PROVERYAEMYH BITOV V STADII
RASCHLENENIYA RAVNO CHISLU KLYUCHEJ V SOOTVETSTVUYUSHCHEM UZLE-I EGO PODBORAH;
TAKIM OBRAZOM, MOZHNO SFORMULIROVATX SLEDUYUSHCHIJ REZULXTAT.

\proclaim tEOREMA T.  eSLI $N$ RAZLICHNYH DVOICHNYH CHISEL POMESHCHENY V
BINARNYJ BOR, KAK OPISANO VYSHE, TO (i)~CHISLO UZLOV BORA RAVNO CHISLU STADIJ
RASCHLENENIYA, NUZHNYH PRI OBMENNOJ PORAZRYADNOJ SORTIROVKE |TIH CHISEL;
(ii)~SREDNEE CHISLO PROVEROK BITOV, TREBUEMYH DLYA VYBORKI KLYUCHA S POMOSHCHXYU
ALGORITMA~T, RAVNO~$1/N$, UMNOZHENNOMU NA CHISLO PROVEROK BITOV PRI.
OBMENNOJ PORAZRYADNOJ SORTIROVKE.\endmark

bLAGODARYA TEOREME MY MOZHEM ISPOLXZOVATX VESX MATEMATICHESKIJ APPARAT,
RAZVITYJ V P.~5.2.2 DLYA OBMENNOJ PORAZRYADNOJ SORTIROVKI. pREDPOLOZHIM,
NAPRIMER, CHTO KLYUCHAMI YAVLYAYUTSYA SLUCHAJNYE, RAVNOMERNO RASPREDELENNYE
MEZHDU~0 I~1 VESHCHESTVENNYE CHISLA, PREDSTAVLENNYE S BESKONECHNOJ TOCHNOSTXYU.
tOGDA KOLICHESTVO PROVEROK BITOV, NEOBHODIMYH DLYA VYBORKI INFORMACII,
BUDET RAVNO~$\log_2 N+\gamma/(\ln2)+1/2+f(N)+O(N^{-1})$, A CHISLO UZLOV
BORA SOSTAVIT~$N/(\ln2)+Ng(N)+O(1)$. zDESX~$f(N)$ I~$g(N)$---SLOZHNYE FUNKCII,
 KOTORYMI MOZHNO PRENEBRECHX, TAK KAK IH ZNACHENIYA VSEGDA MENXSHE~$10^{-6}$
(SM.~UPR.~5.2.2-38,48).

rAZUMEETSYA, PERED NAMI STOIT BOLEE TRUDNAYA ZADACHA: OBOBSHCHITX POLUCHENNYE
REZULXTATY NA SLUCHAJ $M\hbox{-ARNYH}$ BOROV. mY OPISHEM LISHX OTPRAVNUYU
TOCHKU ISSLEDOVANIJ, OSTAVLYAYA POUCHITELXNYE DETALI V KACHESTVE UPRAZHNENIJ.

pUSTX $A_N$---SREDNEE CHISLO UZLOV V SLUCHAJNOM $M\hbox{-ARNOM}$ BORU POISKA,
SODERZHASHCHEM $N$~KLYUCHEJ. tOGDA $A_0=A_1=0$, A DLYA $N\ge2$ MY IMEEM
$$
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)
$$
TAK KAK $N!M^{-N}/k_1!\ldots k_M!$~ESTX VEROYATNOSTX TOGO, CHTO $k_1$~KLYUCHEJ
SODERZHITSYA V PERVOM PODBORU,~\dots, $k_M$---V~$M\hbox{-M}$. vOSPOLXZOVAVSHISX
SOOBRAZHENIYAMI SIMMETRII I PROVEDYA SUMMIROVANIE PO
%%588
$k_2$,~\dots, $k_M$,  PEREPISHEM |TO SOOTNOSHENIE TAK:
$$
\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
}
$$
aNALOGICHNO, ESLI CHEREZ $C_N$~OBOZNACHITX SREDNEE SUMMARNOE KOLICHESTVO
PROVEROK BITOV, NUZHNYH DLYA POISKA V BORU VSEH $N$~KLYUCHEJ,  TO
$C_0=C_1=0$, A
$$
C_N=N+M^{1-N}\sum_k\perm{N}{k}(M-1)^{N-k} C_k,\qquad N\ge 2.
\eqno (5)
$$
v UPR.~17 POKAZANO, KAK RABOTATX S REKURRENTNYMI SOOTNOSHENIYAMI TAKOGO
VIDA, A V UPR.~18--25 RAZRABATYVAETSYA SOOTVETSTVUYUSHCHAYA TEORIYA SLUCHAJNYH
BOROV. [s DRUGOJ TOCHKI ZRENIYA K ANALIZU~$A_N$ VPERVYE PODOSHLI
l.~r.~dZHONSON I m.~mAK-eNDRYU [{\sl IBM J.~Res.~and~Devel.,\/} {\bf 8}
(1964), 189--193] V SVYAZI S |KVIVALENTNYM APPARATNO-ORIENTIROVANNYM
ALGORITMOM SORTIROVKI.]

pEREHODYA TEPERX K IZUCHENIYU DEREVXEV CIFROVOGO POISKA, MY OBNARUZHIVAEM, CHTO,
 S ODNOJ STORONY, FORMULY POHOZHI, A S DRUGOJ---DOSTATOCHNO RAZLICHNY, I SRAZU
NE YASNO, KAK ISSLEDOVATX ASIMPTOTICHESKOE POVEDENIE. nAPRIMER, ESLI $\bar
C_N$~OBOZNACHAET SREDNEE SUMMARNOE KOLICHESTVO PROVEROK BITOV,
PROIZVODIMYH PRI POISKE VSEH $N$~KLYUCHEJ V BINARNOM DEREVE CIFROVOGO POISKA,
 NETRUDNO VYVESTI, KAK I RANXSHE, CHTO $\bar C_0=\bar C_1=0$ I
$$
\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)
$$
eTO POCHTI IDENTICHNO VYRAZHENIYU~(5), NO POYAVLENIYA $N+1$ VMESTO~$N$ V LEVOJ,
CHASTI URAVNENIYA DOSTATOCHNO DLYA TOGO, CHTOBY IZMENITX OBSHCHIJ HARAKTER
REKURRENTNOSTI, TAK CHTO METODY, ISPOLXZUEMYE DLYA IZUCHENIYA~(5), V DANNOM
SLUCHAE NEPRIGODNY.

rASSMOTRIM SNACHALA BINARNYJ SLUCHAJ. nA RIS.~35 IZOBRAZHENO DEREVO CIFROVOGO
POISKA, SOOTVETSTVUYUSHCHEE 16~KLYUCHAM RIS.~34, VSTAVLENNYM V PORYADKE,
ISPOLXZOVANNOM V PRIMERAH IZ GL.~5. sREDNEE CHISLO PROVEROK BITOV PRI
SLUCHAJNOM UDACHNOM POISKE NAJTI LEGKO---ONO RAVNO DLINE VNUTRENNEGO PUTI
DEREVA, DELENNOJ NA~$N$, TAK KAK NUZHNO $l$~PROVEROK, CHTOBY NAJTI UZEL,
RASPOLOZHENNYJ NA UROVNE~$l$. zAMETIM, ODNAKO, CHTO SREDNEE CHISLO PROVEROK
BITOV PRI SLUCHAJNOM \emph{NEUDACHNOM} POISKE \emph{NE TAK} PROSTO SVYAZANO S
DLINOJ VNESHNEGO PUTI DEREVA, IBO NEUDACHNYJ POISK S BOLXSHEJ VEROYATNOSTXYU
OKANCHIVAETSYA VBLIZI KORNYA; NAPRIMER, VEROYATNOSTX DOSTIZHENIYA LEVOJ VETVI
UZLA~$0075$ (RIS.~35) RAVNA~$1/8$ (RASSMATRIVAYUTSYA BESKONECHNO TOCHNYE
KLYUCHI), A V LEVUYU VETVX
%%589
UZLA~$0232$ MY POPADAEM S VEROYATNOSTXYU, RAVNOJ LISHX~$1/32$. (pO |TOJ
PRICHINE PRI RAVNOMERNOM RASPREDELENII KLYUCHEJ DEREVXYA CIFROVOGO POISKA,
KAK PRAVILO, LUCHSHE SBALANSIROVANY, CHEM BINARNYE DEREVXYA POISKA,
ISPOLXZOVAVSHIESYA V ALGORITME~6.2.2T.)

dLYA OPISANIYA SOOTVETSTVUYUSHCHIH HARAKTERISTIK DEREVXEV CIFROVOGO POISKA
MOZHNO ISPOLXZOVATX PROIZVODYASHCHUYU FUNKCIYU. pUSTX NA UROVNE~$l$ RASPOLOZHENO
$a_l$~UZLOV; RASSMOTRIM PROIZVODYASHCHUYU FUNKCIYU~$a(z)=\sum a_l z^l$.
nAPRIMER, RIS.~35 SOOTVETSTVUET
\picture{rIS. 35 sLUCHAJNOE DEREVO CIFROVOGO POISKA, POSTROENNOE S POMOSHCHXYU
ALGORITMA D.}
FUNKCIYA~$a(z)=1+2z+4z^2+5z^3+4z^4$. eSLI $b_l$~UZLOV UROVNYA~$l$ YAVLYAYUTSYA
VNESHNIMI I~$b(z)=\sum b_l z^l$, TO V SILU UPR.~6.2.1-25 IMEEM
$$
b(z)=1+(2z-1)a(z).
\eqno(7)
$$
nAPRIMER, $1+(2z-1)(1+2z+4z^2+5z^3+4z^4)=3z^3+6z^4+8z^5$. sREDNEE CHISLO
PROVEROK BITOV PRI SLUCHAJNOM UDACHNOM POISKE RAVNO~$a'(1)/a(l)$, TAK KAK
$a'(1)$~ESTX DLINA VNUTRENNEGO PUTI DEREVA, A $a(1)$---KOLICHESTVO VNUTRENNIH
UZLOV. sREDNEE CHISLO PROVEROK BITOV DLYA SLUCHAJNOGO \emph{NEUDACHNOGO}
POISKA
RAVNO~$\sum l b_l 2^{-l}={1\over2}b'\left({1\over2}\right)=
a\left({1\over2}\right)$,  TAK KAK MY DOSTIGAEM DANNOGO
VNESHNEGO UZLA UROVNYA~$l$ S VEROYATNOSTXYU~$2^{-l}$. pRI NEUDACHNOM POISKE
CHISLO SRAVNENIJ SOVPADAET S CHISLOM PROVEROK BITOV, A PRI "UDACHNOM"---NA
EDINICU BOLXSHE |TOGO CHISLA. dLYA DEREVA
RIS.~35 UDACHNYJ POISK V SREDNEM TREBUET $2{9\over16}$~PROVEROK BITOV
I~$3{9\over16}$~SRAVNENIJ; V PROCESSE NEUDACHNOGO POISKA
PROIZVODITSYA $3{7\over8}$~SRAVNENIJ I PROVEROK (V SREDNEM).
%%590

vVEDEM TEPERX "USREDNENNUYU" PO VSEM DEREVXYAM S $N$~UZLAMI FUNKCIYU~$a(z)$ I
OBOZNACHIM EE CHEREZ~$g_N(z)$. iNYMI SLOVAMI, $g_N(z)=\sum p_T a_T(z)$, GDE
SUMMA BERETSYA PO VSEM BINARNYM DEREVXYAM CIFROVOGO POISKA~$T$ S
$N$~VNUTRENNIMI UZLAMI; $a_T(z)$ ESTX PROIZVODYASHCHAYA FUNKCIYA DLYA
VNUTRENNIH UZLOV~$T$, A $p_T$~ESTX VEROYATNOSTX TOGO, CHTO PRI VSTAVKE
$N$~SLUCHAJNYH CHISEL S POMOSHCHXYU ALGORITMA~D POLUCHAETSYA DEREVO~$T$. tAKIM
OBRAZOM, DLYA UDACHNOGO POISKA SREDNEE CHISLO PROVEROK BITOV
RAVNO~$g'_N(1)/N$, A DLYA
NEUDACHNOGO---$g_N\left({1\over2}\right)$.

iMITIRUYA PROCESS POSTROENIYA DEREVA, $g_N(z)$ MOZHNO VYCHISLITX SLEDUYUSHCHIM
OBRAZOM. eSLI $a(z)$ ESTX PROIZVODYASHCHAYA FUNKCIYA DLYA DEREVA S $N$~UZLAMI,
MOZHNO OBRAZOVATX $N+1$~DEREVXEV, DELAYA VSTAVKU V POZICIYU LYUBOGO VNESHNEGO
UZLA. eTA VSTAVKA PROIZVODITSYA V DANNYJ VNESHNIJ UZEL UROVNYA~$l$ S
VEROYATNOSTXYU~$2^{-l}$; SLEDOVATELXNO, SUMMA PROIZVODYASHCHIH FUNKCIJ DLYA
$N+1$~NOVYH DEREVXEV, UMNOZHENNYH NA VEROYATNOSTX IH POYAVLENIYA, RAVNA
$a(z)+b\left({1\over2}z\right)=a(z)+1 +(z-1)a\left({1\over2}z\right)$.
uSREDNYAYA PO VSEM DEREVXYAM S $N$~UZLAMI, POLUCHAEM
$$
g_{N+1}(z)=g_N(z)+1+(z-1)g_N\left({1\over2}z\right);\qquad
g_0(z)=0.
\eqno(8)
$$
s SOOTVETSTVUYUSHCHEJ PROIZVODYASHCHEJ FUNKCIEJ DLYA VNESHNIH
UZLOV $h_N(z)=1+(2z-1)g_N(z)$ RABOTATX NESKOLXKO LEGCHE, TAK KAK
(8)~|KVIVALENTNO FORMULE
$$
h_{N+1}(z)=h_N(z)+(2z-1)h_N\left({1\over2}z\right);
h_0(z)=1.
\eqno(9)
$$
mNOGOKRATNO PRIMENYAYA |TO PRAVILO, NAHODIM, CHTO
$$
\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
}
$$
I T.~D.; OKONCHATELXNO IMEEM
$$
\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
}
$$
nAPRIMER, $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)$. eTI FORMULY POZVOLYAYUT
VYRAZITX ISKOMYE VELICHINY V VIDE SUMM PROIZVEDENIJ:
$$
\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
}
$$
sOVSEM NE OCHEVIDNO, CHTO |TI FORMULY DLYA $\overline{C}_N$ UDOVLETVORYAYUT~(B)!

k SOZHALENIYU, NAJDENNYE VYRAZHENIYA NEPRIGODNY DLYA VYCHISLENIJ ILI POLUCHENIYA
ASIMPTOTICHESKIH OCENOK, TAK KAK $2^{-j}-1<0$; POLUCHITSYA BOLXSHOE KOLICHESTVO
CHLENOV, MNOGIE IZ KOTORYH SOKRATYATSYA. bOLEE POLEZNYE FORMULY DLYA
$\overline{C}_N$ MOZHNO VYVESTI, PRIMENYAYA TOZHDESTVA UPR.~5.1.1-16. iMEEM
$$
\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)
$$
sRAZU NE YASNO, CHEM |TO LUCHSHE VYRAZHENIYA~(12), NO VYVEDENNAYA FORMULA IMEET
TO VAZHNOE PREIMUSHCHESTVO, CHTO ONA BYSTRO SHODITSYA DLYA LYUBOGO
FIKSIROVANNOGO~$n$. v TOCHNOSTI ANALOGICHNAYA SITUACIYA VOZNIKAET I V SLUCHAE
BORA [FORMULA (5.2.2-38)]; V SAMOM DELE, ESLI RASSMOTRETX V~(14) LISHX
CHLENY S~$n=0$, POLUCHAETSYA ROVNO $N-1$~PLYUS CHISLO PROVEROK V BINARNOM
BORU. dALXNEJSHIJ VYVOD ASIMPTOTICHESKOJ OCENKI MOZHNO PROVESTI UZHE IZVESTNYM
NAM SPOSOBOM; SM.~UPR.~27. pRIVEDENNYJ VYVOD V BOLXSHOJ STEPENI OSNOVAN
NA PODHODE, PREDLOZHENNOM e.~g.~kONHEJMOM I~d.~dZH.~nXYUM|NOM [{\sl Discrete
Mathematics,\/} {\bf 4} (1973), 56--63].

i NAKONEC, VZGLYANEM NA pATRICIYU S TOCHKI ZRENIYA MATEMATIKA. eE BINARNOE
DEREVO POHOZHE NA SOOTVETSTVUYUSHCHIJ BINARNYJ BOR S TEMI ZHE KLYUCHAMI, NO
SZHATYMI VMESTE (IBO POLYA~|SKIP| USTRANYAYUT ODNOPUTEVYE RAZVETVLENIYA), TAK
CHTO IMEETSYA $N-1$~VNUTRENNIH
%%592
I $N$~VNESHNIH UZLOV. nA RIS.~36 IZOBRAZHENO DEREVO pATRICII,
SOOTVETSTVUYUSHCHEE SHESTNADCATI KLYUCHAM V BORU RIS.~34. chISLA, ZAKLYUCHENNYE VO
VNUTRENNIH UZLAH, OBOZNACHAYUT SODERZHIMOE POLEJ |SKIP|; KLYUCHI UKAZANY
VMESTE S VNESHNIMI UZLAMI, HOTYA POSLEDNIE NE PRISUTSTVUYUT YAVNO (V
DEJSTVITELXNOSTI VMESTO VNESHNIH UZLOV SUSHCHESTVUYUT POMECHENNYE SSYLKI NA
VNUTRENNIE UZLY, KOTORYE V SVOYU OCHEREDX SSYLAYUTSYA NA MASSIV
|TEXT|). oDNAKO DLYA CELEJ ANALIZA MOZHNO SCHITATX, CHTO VNESHNIE
UZLY SUSHCHESTVUYUT V TOM VIDE, KAK ONI IZOBRAZHENY NA RIS.~36.

tAK KAK UDACHNYJ POISK S ISPOLXZOVANIEM pATRICII OKANCHIVAETSYA VO VNESHNIH
UZLAH, SREDNEE CHISLO PROVEROK BITOV, PROIZVODIMYH PRI SLUCHAJNOM UDACHNOM
POISKE, RAVNO DLINE
\picture{rIS. 36.            pATRICIYA STROIT |TO DEREVO VMESTO RIS. 34.}
VNESHNEGO PUTI, DELENNOJ NA~$N$. eSLI, KAK I VYSHE, VVESTI PROIZVODYASHCHUYU
FUNKCIYU~$b(z)$ DLYA VNESHNIH UZLOV, |TO CHISLO BUDET RAVNO~$b'(1)/b(1)$.
\emph{nEUDACHNYJ} POISK TAKZHE KONCHAETSYA VO VNESHNEM UZLE, NO S
VEROYATNOSTXYU~$2^{-l}$ ($l$---NOMER UROVNYA, NA KOTOROM RASPOLOZHEN UZEL),
TAK CHTO SREDNEE CHISLO PROVEROK BITOV
SOSTAVLYAET~${1\over2}b'\left({1\over2}\right)$. nAPRIMER, DLYA RIS.~36
$b(z)=3z^3+8z^4-3z^5+2z^6$; V SREDNEM UDACHNYJ POISK TREBUET
$4{1\over4}$~PROVEROK BITOV, A NEUDACHNYJ---$3{25\over32}$.

pROIZVODYASHCHUYU FUNKCIYU~$b(z)$, USREDNENNUYU PO VSEM DEREVXYAM pATRICII,
POSTROENNYM S $N$~VNESHNIMI UZLAMI S ISPOLXZOVANIEM RAVNOMERNO
RASPREDELENNYH KLYUCHEJ, OBOZNACHIM CHEREZ~$h_N(z)$.
%%593
rEKURRENTNOE SOOTNOSHENIE
$$
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)
$$
PO-VIDIMOMU, NE IMEET PROSTOGO RESHENIYA. nO, K SCHASTXYU, SUSHCHESTVUET
PROSTOE REKURRENTNOE SOOTNOSHENIE DLYA SREDNEJ DLINY VNESHNEGO PUTI~$h'_n(1)$,
 POSKOLXKU
$$
\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
}
$$
tAK KAK ONO IMEET VID~(6), DLYA NAHOZHDENIYA~$h'_n(1)$ MOZHNO ISPOLXZOVATX UZHE
RAZVITYE METODY; OKAZYVAETSYA, CHTO $h'_n(1)$ ROVNO NA~$n$ MENXSHE
SOOTVETSTVUYUSHCHEGO CHISLA PROVEROK BITOV V SLUCHAJNOM BINARNOM BORU. tAKIM
OBRAZOM, POLE |SKIP| POZVOLYAET S|KONOMITX PRIMERNO ODNU PROVERKU BITA DLYA
UDACHNOGO POISKA PRI SLUCHAJNYH DANNYH. (sM.~UPR.~31.) nA SAMOM ZHE DELE
IZBYTOCHNOSTX TIPICHNYH DANNYH PRIVEDET K BOLXSHEJ |KONOMII.

eSLI MY POPYTAEMSYA NAJTI SREDNEE CHISLO PROVEROK BITOV DLYA SLUCHAJNOGO
NEUDACHNOGO POISKA, PROIZVODIMOGO pATRICIEJ, TO POLUCHIM SOOTNOSHENIE
$$
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)
$$
(zDESX $a_n={1\over2}h'_n\left({1\over2}\right)$.) oNO \emph{NE} POHOZHE NI
NA ODNO IZ IZUCHENNYH SOOTNOSHENIJ, I SVESTI EGO K NIM NE PROSTO. nA SAMOM
DELE OKAZYVAETSYA, CHTO RESHENIE SODERZHIT CHISLA bERNULLI:
$$
{na_{n-1}\over2}-n+2=\sum_{2\le k<n}\perm{n}{k}{B_k\over 2^{k-1}-1}.
\eqno(18)
$$
eTA FORMULA YAVLYAETSYA, VEROYATNO, NAIBOLEE SLOZHNOJ ASIMPTOTICHESKOJ OCENKOJ
IZ VSEH, KOTORYE NAM NUZHNO BYLO POLUCHITX;
RESHENIE V UPR.~34 DAET POUCHITELXNYJ OBZOR MNOGIH RANEE IZUCHENNYH VESHCHEJ S
NEKOTORYMI NYUANSAMI.

\section vYVODY IZ ANALIZA. sLEDUYUSHCHIE REZULXTATY ZASLUZHIVAYUT NAIBOLXSHEGO
VNIMANIYA:

\item{(a)}~chISLO UZLOV, NEOBHODIMYH DLYA HRANENIYA $N$~SLUCHAJNYH KLYUCHEJ V
$M\hbox{-ARNOM}$ BORU, RAZVETVLENIYA V KOTOROM PROISHODYAT DO TEH.POR, POKA
NE OSTANETSYA PODFAJL IZ $\le s$~KLYUCHEJ, PRIMERNO RAVNO~$N/(s\ln M)$. (eTO
PRIBLIZHENIE SPRAVEDLIVO DLYA BOLXSHIH~$N$
%%594
I MALYH~$s$ I~$M$.) tAK KAK UZEL BORA SODERZHIT $M$~POLEJ SSYLOK, TO, ESLI
VYBRATX $s=M$, VSEGO POTREBUETSYA LISHX OKOLO $N/(\ln M)$~POLEJ SSYLOK.

\item{(b)}~dLYA VSEH RASSMOTRENNYH METODOV KOLICHESTVO CIFR ILI LITER,
PROVERYAEMYH V PROCESSE SLUCHAJNOGO POISKA, PRIMERNO RAVNO~$\log_M N$. pRI
$M=2$ RAZLICHNYMI METODAMI MOZHNO POLUCHITX SLEDUYUSHCHIE BOLEE TOCHNYE
PRIBLIZHENIYA DLYA CHISLA PROVEROK BITOV:
\ctable{
#\hfill\bskip &&\bskip \hfill$#$\hfill \cr
                         & \hbox{uDACHNYJ} &\hbox{nEUDACHNYJ} \cr
pOISK PO BORU            &\log_2N+1.33275 &\log_2N-0.10995\cr
cIFROVOJ POISK PO DEREVU &\log_2N-1.71665 &\log_2N-0.27395\cr
pATRICIYA                 &\log_2N+0.33275 &\log_2N-0.31875\cr
}
[vSE |TI PRIBLIZHENNYE ZNACHENIYA MOZHNO VYRAZITX CHEREZ FUNDAMENTALXNYE
MATEMATICHESKIE POSTOYANNYE; NAPRIMER, CHISLO~$0.31875$ POLUCHILOSX IZ~$(\ln \pi-\gamma)/(\ln2)-1/2$.]

\item{(c)}~"sLUCHAJNOSTX" DANNYH ZDESX OZNACHAET TO, CHTO $M\hbox{-ICHNYE}$
CIFRY YAVLYAYUTSYA RAVNOMERNO RASPREDELENNYMI, KAK ESLI BY KLYUCHAMI BYLI
DEJSTVITELXNYE CHISLA MEZHDU~0 I~1, ZAPISANNYE V $M\hbox{-ICHNOJ}$ SISTEME
SCHISLENIYA. mETODY CIFROVOGO POISKA NE CHUVSTVITELXNY K PORYADKU, V KOTOROM
KLYUCHI POMESHCHENY V FAJL (ISKLYUCHENIEM YAVLYAETSYA ALGORITM~D, LISHX V MALOJ
STEPENI CHUVSTVITELXNYJ K PORYADKU); NO ONI OCHENX CHUVSTVITELXNY K
RASPREDELENIYU CIFR. nAPRIMER, ESLI NULEVYE BITY VSTRECHAYUTSYA GORAZDO CHASHCHE
EDINICHNYH, DEREVXYA BUDUT GORAZDO BOLEE ASIMMETRICHNYMI PO SRAVNENIYU S
DEREVXYAMI, POLUCHENNYMI DLYA SLUCHAJNYH DANNYH. (v UPR.~5.2.2-53 RAZOBRAN
PRIMER TOGO, CHTO PROISHODIT PRI TAKOM VOZDEJSTVII NA DANNYE.)

\excercises
\ex[00] eSLI DEREVO IMEET LISTXYA, TO CHTO IMEET BOR?

\ex[20] pOSTROJTE ALGORITM VSTAVKI NOVOGO KLYUCHA V $M\hbox{-ARNYJ}$ BOR,
PRIDERZHIVAYASX SOGLASHENIJ ALGORITMA~T.

\ex[21] pOSTROJTE ALGORITM UDALENIYA KLYUCHA IZ $M\hbox{-ARNOGO}$ BORA,
PRIDERZHIVAYASX SOGLASHENIJ ALGORITMA~T.

\rex[21] bOLXSHINSTVO IZ 360~|LEMENTOV TABL.~1---PROBELY (PUSTYE
SSYLKI). oDNAKO MOZHNO SZHATX TABLICU DO 49~|LEMENTOV, DOPUSKAYA PEREKRYTIE
NEPUSTYE I PUSTYH |LEMENTOV:
\picture{rIS. NA STR. 594}
%% 595
[uZLY (1), (2),~\dots, (12) TABL.~1 NACHINAYUTSYA SOOTVETSTVENNO S POZICIJ 20,
 19, 3, 14, 1, 17, 1, 7, 3, 20, 18, 4 SZHATOJ TABLICY.]

pOKAZHITE, CHTO, ESLI ZAMENITX TAKOJ SZHATOJ TABLICEJ TABL.~1,
PROGRAMMA~T BUDET RABOTATX I V |TOM SLUCHAE, PRAVDA, NE STOLX BYSTRO.

\rex[m26] (j.~n.~p|TT.) v DEREVXYAH RIS.~31 BUKVY UPORYADOCHENY PO ALFAVITU
VNUTRI KAZHDOGO SEMEJSTVA. eTO NE YAVLYAETSYA NEOBHODIMYM, I ESLI MY, PREZHDE
CHEM STROITX BINARNOE DEREVO TIPA~(2), IZMENIM PORYADOK UZLOV VNUTRI KAZHDOGO
SEMEJSTVA, POISK MOZHET USKORITXSYA. kAKOE PEREUPORYADOCHENIE RIS.~31 BUDET
OPTIMALXNYM S |TOJ TOCHKI ZRENIYA? (iSPOLXZUJTE CHASTOTY, DANNYE NA RIS.~32,
I NAJDITE LES, KOTORYJ, BUDUCHI PREDSTAVLEN V VIDE BINARNOGO DEREVA,
MINIMIZIRUET VREMYA UDACHNOGO POISKA.)

\ex[15] kAKOE DEREVO CIFROVOGO POISKA POLUCHITSYA, ESLI PYATNADCATX
CHETYREHBITOVYH BINARNYH KLYUCHEJ 0001, 0010, 0011,~\dots, 1111 VSTAVITX V
VOZRASTAYUSHCHEM PORYADKE S POMOSHCHXYU ALGORITMA~D? (nACHNITE S KLYUCHA~0001 V
KORNEVOM UZLE I ZATEM PROIZVEDITE CHETYRNADCATX VSTAVOK.)

\rex[M26] eSLI PYATNADCATX KLYUCHEJ IZ UPR.~6 VSTAVLYAYUTSYA V DRUGOM PORYADKE,
MOZHET POLUCHITXSYA DRUGOE DEREVO. kAKOVA NAIHUDSHAYA SREDI VSEH
$15!$~VOZMOZHNYH PERESTANOVOK |TIH KLYUCHEJ V TOM SMYSLE, CHTO ONA POROZHDAET
DEREVO S NAIBOLXSHEJ DLINOJ VNUTRENNEGO PUTI?

\ex[20] rASSMOTRIM SLEDUYUSHCHIE IZMENENIYA ALGORITMA~D, VEDUSHCHIE K ISKLYUCHENIYU
PEREMENNOJ~$K1$: ZAMENITX "$K1$" NA "$K$" V SHAGE~D2 I USTRANITX
OPERACIYU~"$K1\asg K$" IZ SHAGA~D1. gODITSYA LI POLUCHENNYJ ALGORITM DLYA
POISKA I VSTAVKI?

\ex[21] nAPISHITE \MIX-PROGRAMMU DLYA ALGORITMA~D I SRAVNITE EE S
PROGRAMMOJ~6.2.2T. vY MOZHETE ISPOLXZOVATX BINARNYE OPERACII VRODE
|SLB| (BINARNYJ SDVIG VLEVO |AX|), |JAE| (PEREHOD, ESLI |A|~CHETNO) I T.~D.,
 ESLI SOCHTETE NUZHNYM. vY MOZHETE TAKZHE ISPOLXZOVATX IDEYU UPR.~8.

\ex[23] iMEETSYA FAJL, VSE KLYUCHI KOTOROGO SUTX $n\hbox{-BITOVYE}$
DVOICHNYE CHISLA, I ARGUMENT POISKA $K=b_1\ b_2\ \ldots\ b_n$. pREDPOLOZHIM,
CHTO MY HOTIM NAJTI MAKSIMALXNOE CHISLO~$k$, TAKOE, CHTO V FAJLE SUSHCHESTVUET
KLYUCH, NACHINAYUSHCHIJSYA S $b_1b_2\ldots b_k$. kAK SDELATX |TI |FFEKTIVNO, ESLI
FAJL PREDSTAVLEN V VIDE: (a)~BINARNOGO DEREVA POISKA
(SR.~S~ALGORITMOM 6.2.2T); (b)~BINARNOGO BORA (SR.~S ALGORITMOM~T);
(c)~BINARNOGO DEREVA CIFROVOGO POISKA (SR. S ALGORITMOM~D)?

\ex[21] mOZHNO LI ISPOLXZOVATX ALGORITM~6.2.2D BEZ IZMENENIJ DLYA UDALENIYA
UZLA IZ DEREVA CIFROVOGO POISKA?

\ex[25]  bUDET LI SLUCHAJNYM DEREVO, POLUCHENNOE V REZULXTATE
UDALENIYA SLUCHAJNOGO |LEMENTA IZ SLUCHAJNOGO DEREVA CIFROVOGO POISKA,
POSTROENNOGO S POMOSHCHXYU ALGORITMA~D? (sR.~S~UPR.~11 I S TEOREMOJ~6.2.2H.)

\ex[20] ($M\hbox{-ARNYJ}$ CIFROVOJ POISK). oB®YASNITE, KAK IZ ALGORITMOV~T
I~D SOSTAVITX SOOBSHCHENNYJ ALGORITM, SVODYASHCHIJSYA K ALGORITMU~D PRI~$M=2$.
kAK SLEDUET IZMENITX TABL.~1, ESLI ISPOLXZOVATX VASH ALGORITM PRI~$M=30?$

\rex[25] pOSTROJTE |FFEKTIVNYJ ALGORITM, S POMOSHCHXYU KOTOROGO SRAZU POSLE
UDACHNOGO ZAVERSHENIYA ALGORITMA~P MOZHNO BYLO BY NAJTI VSE MESTA V MASSIVE
|TEXT|, GDE VSTRECHAETSYA~$K$.

\ex[28] pRIDUMAJTE, |FFEKTIVNYJ ALGORITM, KOTORYJ MOZHNO ISPOLXZOVATX DLYA
POSTROENIYA DEREVA pATRICII ILI DLYA VSTAVKI NOVOJ SSYLKI NA |TEXT| V UZHE
SUSHCHESTVUYUSHCHEE DEREVO. vASH ALGORITM VSTAVKI DOLZHEN OBRASHCHATXSYA K MASSIVU
|TEXT| NE BOLEE DVUH RAZ.

\ex[22] pOCHEMU DLYA pATRICII HOTELOSX BY IMETX TAKOE OGRANICHENIE, CHTO NI
ODIN KLYUCH NE DOLZHEN SLUZHITX NACHALOM DRUGOGO?

\ex[m25] nAJDITE SPOSOB VYRAZITX RESHENIE REKURRENTNOGO SOOTNOSHENIYA
$$
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,
$$
S POMOSHCHXYU BINOMIALXNYH PREOBRAZOVANIJ, OBOBSHCHAYA METOD UPR.~5.2.2-36.

\ex[M21] iSPOLXZUYA REZULXTAT UPR.~17, VYRAZITE RESHENIYA URAVNENIJ~(4) I~(5)
CHEREZ FUNKCII~$U_n$ I~$V_n$, ANALOGICHNYE VVEDENNYM V UPR.~5.2.2-38.

%%596

\ex[vm23] nAJDITE ASIMPTOTICHESKOE ZNACHENIE FUNKCII
$$
K(n,s,m)=\sum_{k\ge2}\perm{n}{k}\perm{k}{s}{(-1)^k\over m^{k-1}-1}
$$
S TOCHNOSTXYU DO~$O(1)$ PRI~$n\to\infty$ DLYA FIKSIROVANNYH ZNACHENIJ~$s\ge0$
I~$m>1$. [sLUCHAJ~$s=0$ RASSMOTREN V UPR.~5.2.2-50,
A SLUCHAJ~$s=l$, $m=2$---V UPR.~5.2.2-48.]

\rex[M30] rASSMOTRIM $M\hbox{-ARNUYU}$ BOROVUYU PAMYATX, V KOTOROJ,
DOSTIGNUV PODFAJLA, SODERZHASHCHEGO NE BOLEE $s$~KLYUCHEJ, MY ISPOLXZUEM
POSLEDOVATELXNYJ POISK. (sLUCHAYU~$s=1$ SOOTVETSTVUET ALGORITM~T.) pRIMENITE
REZULXTATY PREDYDUSHCHIH UPRAZHNENIJ, CHTOBY PROANALIZIROVATX: (a)~SREDNEE
CHISLO UZLOV BORA;
(b)~SREDNEE CHISLO PROVERYAEMYH CIFR ILI LITER PRI UDACHNOM POISKE;
(c)~SREDNEE CHISLO SRAVNENIJ, PROIZVODIMYH PRI UDACHNOM POISKE.
sFORMULIRUJTE OTVETY V VIDE ASIMPTOTICHESKIH FORMUL~($N\to\infty$) DLYA
FIKSIROVANNYH~$M$ I~$s$,
OTVET DLYA~(a) DOLZHEN BYTX DAN S TOCHNOSTXYU DO~$O(1)$, OTVETY DLYA~(b)
I~(c)---S TOCHNOSTXYU DO~$O(N^{-1})$. [eSLI~$M=2$, |TOT ANALIZ PRIMENIM TAKZHE
K MODIFICIROVANNOJ OBMENNOJ PORAZRYADNOJ SORTIROVKE, KOGDA PODFAJLY
RAZMERA~$<s$ SORTIRUYUTSYA POSREDSTVOM VSTAVOK].

\ex[m25] sKOLXKO UZLOV V SLUCHAJNOM $M\hbox{-ARNOM}$ BORU, SODERZHASHCHEM $N$~KLYUCHEJ,
IMEYUT PUSTUYU SSYLKU V KACHESTVE NULEVOJ KOMPONENTY? (nAPRIMER, 9 IZ 12~UZLOV
TABL.~1 V POZICII "\]" IMEYUT PUSTUYU SSYLKU. "sLUCHAJNYJ" V
|TOM UPRAZHNENII, KAK I OBYCHNO, OZNACHAET, CHTO LITERY KLYUCHEJ RAVNOMERNO
RASPREDELENY MEZHDU~$0$ I~$M-1$.)

\ex[m25] sKOLXKO UZLOV RASPOLOZHENO NA 1-M UROVNE SLUCHAJNOGO
$M\hbox{-apNoro}$ BORA, SODERZHASHCHEGO $N$~KLYUCHEJ, PRI $l=0$, 1, 2,~\dots?

\ex[m26] sKOLXKO PROVEROK CIFR PROIZVODITSYA V SREDNEM PRI
NEUDACHNOM POISKE V $M\hbox{-ARNOM}$ BORU, SODERZHASHCHEM $N$~SLUCHAJNYH KLYUCHEJ?

\ex[M30] rASSMOTRIM $M\hbox{-ARNYJ}$ BOR, PREDSTAVLENNYJ V VIDE LESA
(SR.~S~RIS.~31). nAJDITE TOCHNYE I ASIMPTOTICHESKIE VYRAZHENIYA DLYA:
(a)~SREDNEGO CHISLA UZLOV V LESU; (b)~SREDNEGO KOLICHESTVA VYPOLNENII
PRISVAIVANIYA~$|P|\asg|RLINK|(|P|)$ V PROCESSE SLUCHAJNOGO UDACHNOGO POISKA.

\rex[m24] mATEMATICHESKIJ VYVOD ASIMPTOTICHESKIH ZNACHENIJ, SDELANNYJ V DANNOM
PUNKTE, VESXMA TRUDEN; ISPOLXZOVALASX DAZHE TEORIYA KOMPLEKSNOGO PEREMENNOGO.
dELO V TOM, CHTO MY NE HOTELI OGRANICHIVATXSYA GLAVNYM CHLENOM ASIMPTOTIKI, A
VTOROJ CHLEN DEJSTVITELXNO SLOZHEN. cELX |TOGO UPRAZHNENIYA SOSTOIT V TOM, CHTOBY
|LEMENTARNYMI METODAMI POLUCHITX NEKOTORYE REZULXTATY V OSLABLENNOJ FORME,
(a)~dOKAZHITE PO INDUKCII, CHTO RESHENIE URAVNENIYA~(4) PRI~$N\ge1$
UDOVLETVORYAET NERAVENSTVU~$A_N\le M(N-1)/(M-1)$.
(b)~pUSTX~$D_N=C_N-NH_{N-1}/(\ln M)$, GDE $C_N$~NAHODITSYA IZ~(5).
dOKAZHITE, CHTO~$D_N=O(N)$, SLEDOVATELXNO, $C_N=N\log_MN+O(N)$.
[\emph{uKAZANIE:} ISPOLXZUJTE~(a) I TEOREMU~1.2.7A.]

\ex[23] oPREDELITE VRUCHNUYU ZNACHENIE BESKONECHNOGO PROIZVEDENIYA
$$
\left(1-{1\over2}\right)\left(1-{1\over4}\right)
\left(1-{1\over8}\right)\left(1-{1\over16}\right)\cdots
$$
S TOCHNOSTXYU DO~$10^{-5}$. [\emph{uKAZANIE:} SR.~S~UPR.~5.1.1-16.]

\ex[vm31] s POMOSHCHXYU SOOTNOSHENIYA~(14) NAJDITE ASIMPTOTICHESKOE
ZNACHENIE~$\overline{C}_N$ S TOCHNOSTXYU DO~$O(1)$.

\ex[vm26] nAJDITE ASIMPTOTICHESKOE POVEDENIE SREDNEGO CHISLA PROVEROK CIFR
PRI POISKE V SLUCHAJNOM DEREVE CIFROVOGO POISKA, $M\ge2$. rASSMOTRITE KAK
UDACHNYJ, TAK I NEUDACHNYJ POISK. dAJTE OTVET S TOCHNOSTXYU DO~$O(N^{-1})$.

\ex[m46] nAJDITE ASIMPTOTIKU SREDNEGO CHISLA UZLOV V $M\hbox{-ARNOM}$
DEREVE CIFROVOGO POISKA, VSE $M$~SSYLOK KOTORYH PUSTY. (iSKLYUCHIV TAKIE UZLY,
MY MOGLI BY S|KONOMITX PAMYATX; SR.~S~UPR.~13.)

%% 597

\ex[M24] pOKAZHITE, CHTO PROIZVODYASHCHUYU FUNKCIYU pATRICII~$h_n(z)$,
OPREDELENNUYU V~(15), MOZHNO VYRAZITX V TAKOM DOSTATOCHNO "UZHASNOM" VIDE:
$$
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).
$$
[tAKIM OBRAZOM, ESLI BY SUSHCHESTVOVALA PROSTAYA FORMULA DLYA~$h_n(z)$, MY
MOGLI BY UPROSTITX |TO DOVOLXNO GROMOZDKOE VYRAZHENIE.]

\ex[M21] nAJDITE~$h'_n(1)$ IZ SOOTNOSHENIYA~(16).

\ex[M21] chEMU RAVNO SREDNEE ZNACHENIE SUMMY VSEH POLEJ |SKIP| V SLUCHAJNOM
DEREVE pATRICII S $N-1$ VNUTRENNIMI UZLAMI?

\ex[M30] dOKAZHITE, CHTO~[18] UDOVLETVORYAET REKURRENTNOMU SOOTNOSHENIYU~(17).
[\emph{uKAZANIE:}  RASSMOTRITE  PROIZVODYASHCHUYU
FUNKCIYU~$A(z)=\sum_{n\ge0} a_nz^n/n!$.]

\ex[vm40] cELXYU |TOGO UPRAZHNENIYA YAVLYAETSYA NAHOZHDENIE ASIMPTOTICHESKOGO
POVEDENIYA FUNKCII~(18).

\item{(a)}~dOKAZHITE, CHTO PRI $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)}~pOKAZHITE, CHTO SLAGAEMYE V PRAVOJ CHASTI~(a) MOZHNO PRIBLIZITX
FUNKCIYAMI~$1/(e^x-1)-1/x+1/2$, GDE~$x=n/2^j$; POLUCHAYUSHCHAYASYA PRI |TOM
SUMMA OTLICHAETSYA OT PERVONACHALXNOJ NA~$O(n^{-1})$.

\item{(c)}~pOKAZHITE, CHTO DLYA DEJSTVITELXNOGO~$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)}~sLEDOVATELXNO, RASSMATRIVAEMAYA SUMMA RAVNA
$$
{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});
$$
OCENITE |TOT INTEGRAL.

\rex[m20] kAKOVA VEROYATNOSTX TOGO, CHTO DEREVO pATRICII, SODERZHASHCHEE PYATX
KLYUCHEJ, IMEET VID
\picture{rIS. STR. 597}
%%598
PRICHEM POLYA |SKIP| SODERZHAT $a$, $b$, $c$, $d$, KAK POKAZANO NA RISUNKE?
(pREDPOLAGAETSYA, CHTO KLYUCHI IMEYUT NEZAVISIMYE SLUCHAJNYE BITY; OTVET NUZHNO
PREDSTAVITX V VIDE FUNKCII OT $a$, $b$, $c$ I~$d$.)

\ex[M25] iMEETSYA PYATX BINARNYH DEREVXEV S TREMYA VNUTRENNIMI UZLAMI. eSLI
MY RASSMOTRIM, KAK CHASTO KAZHDOE IZ NIH SLUZHIT DEREVOM, POISKA V
RAZLICHNYH ALGORITMAH (DANNYE PREDPOLAGAYUTSYA SLUCHAJNYMI), TO POLUCHIM
SLEDUYUSHCHIE RAZLICHNYE VEROYATNOSTI:
\picture{rIS. STR. 598 --- V TABLICU PO CHASTYAM:}
\ctable{
# &$#$&$#$&$#$&$#$&$#$\cr
   &&&&&\cr
pOISK PO DEREVU (ALGORITM 6.2.2.T) & 1\over 6 & 1\over6 & 1\over3 &
1\over6 & 1\over6\cr
cIFROVOJ POISK PO DEREVU (ALGORITM D)&1\over8 & 1\over8 & 1\over2 &
1\over8 & 1\over8\cr
pATRICIYA (ALGORITM r) & 1\over7 & 1\over7 & 3\over7 & 1\over7 & 1\over7\cr
}
(zAMETIM, CHTO DEREVO CIFROVOGO POISKA IMEET NAIBOLXSHUYU TENDENCIYU K
SBALANSIROVANNOSTI.) v UPR.~6.2.2-5 MY NASHLI FORMULU DLYA VEROYATNOSTI V
SLUCHAE POISKA PO DEREVU: $\prod(1/s(x))$, GDE PROIZVEDENIE BERETSYA PO
VSEM VNUTRENNIM UZLAM~$x$, a~$s(x)$---CHISLO VNUTRENNIH UZLOV V PODDEREVE,
KORNEM KOTOROGO SLUZHIT~$x$. nAJDITE ANALOGICHNYE FORMULY DLYA VEROYATNOSTI
V SLUCHAE: (a)~ALGORITMA~D;  (b)~ALGORITMA~r.

\rex[m22] rASSMOTRIM BINARNOE DEREVO, NA $l\hbox{-M}$ UROVNE KOTOROGO
RASPOLOZHENO $b_l$~VNESHNIH UZLOV. v TEKSTE UKAZYVALOSX, CHTO VREMYA
NEUDACHNOGO POISKA V DEREVXYAH CIFROVOGO POISKA NE SVYAZANO NEPOSREDSTVENNO S
DLINOJ VNESHNEGO PUTI~$\sum lb_l$, A, PO SUSHCHESTVU, PROPORCIONALXNO
\emph{MODIFICIROVANNOJ DLINE VNESHNEGO PUTI}~$\sum l b_l 2^{-l}$.
dOKAZHITE ILI OPROVERGNITE SLEDUYUSHCHEE UTVERZHDENIE:
SREDI VSEH DEREVXEV S $N$~VNESHNIMI UZLAMI NAIMENXSHUYU
MODIFICIROVANNUYU DLINU VNESHNEGO PUTI IMEET TO DEREVO, VSE VNESHNIE UZLY
KOTOROGO RASPOLOZHENY NE BOLEE CHEM NA DVUH SMEZHNYH UROVNYAH (SR.~S UPR.~5.3.1-20).

\ex[m40] rAZRABOTAJTE ALGORITM DLYA NAHOZHDENIYA $n\hbox{-UZLOVOGO}$ DEREVA,
 IMEYUSHCHEGO MINIMALXNOE ZNACHENIE VELICHINY
$\alpha\times\hbox{(DLINA VNUTRENNEGO PUTI)}+
\beta\times\hbox{(MODIFICIROVANNAYA DLINA VNESHNEGO PUTI)}$, $\alpha$
I~$\beta$---DANNYE CHISLA (SR.~S~UPR.~37).

\ex[m43] pRIDUMAJTE ALGORITM NAHOZHDENIYA OPTIMALXNYH DEREVXEV CIFROVOGO
POISKA, ANALOGICHNYH OPTIMALXNYM BINARNYM DEREVXYAM POISKA, RASSMOTRENNYM
V P.~6.2.2.

\ex[25] pUSTX $a_0a_1a_2\ldots$---PERIODICHESKAYA BINARNAYA POSLEDOVATELXNOSTX;
$a_{N+k}=a_k$ PRI VSEH~$k\ge0$. pOKAZHITE, CHTO LYUBUYU FIKSIROVANNUYU
CEPOCHKU |TOGO TIPA MOZHNO PREDSTAVITX V $O(N)$~YACHEJKAH PAMYATI TAKIM OBRAZOM,
 CHTO SLEDUYUSHCHAYA OPERACIYA TREBUET LISHX $O(n)$~SHAGOV: IMEYA BINARNUYU
CEPOCHKU $b_0b_1\ldots b_{n-1}$, NUZHNO OPREDELITX, SKOLXKO RAZ ONA
VSTRECHAETSYA V PERIODE (T.~E.~NAJTI KOLICHESTVO ZNACHENIJ~$p$, $0\le p<N$,
TAKIH, CHTO~$b_k=a_{p+k}$ PRI~$0\le k<n$). (dLINA CEPOCHKI~$n$, KAK I SAMA
CEPOCHKA, YAVLYAETSYA PEREMENNOJ. pREDPOLAGAETSYA, CHTO KAZHDAYA YACHEJKA PAMYATI
DOSTATOCHNO VELIKA, CHTOBY VMESTITX PROIZVOLXNOE CELOE CHISLO OT~$0$ DO~$N$.)

%%599

\ex[vm28] \exhead(pRILOZHENIE K TEORII GRUPP.) pUSTX $G$---SVOBODNAYA
GRUPPA NAD SIMVOLAMI~$\set{a_1,~\ldots, a_n}$, T.~E.~MNOZHESTVO VSEH
CEPOCHEK $\alpha=b_1\ldots{}b_r$, GDE $b_i$~ESTX LIBO~$a_j$,
LIBO~$a_j^{-1}$, I NET SMEZHNYH PAR~$a_ja_j^{-1}$ ILI~$a_j^{-1}a_j$.
oBRATNYM K~$\alpha$ |LEMENTOM YAVLYAETSYA~$b_r^{-1}\ldots{}b_1^{-1}$; MY
PEREMNOZHAEM DVE TAKIE CEPOCHKI PUTEM KONKATENACII I SOKRASHCHENIYA SMEZHNYH
VZAIMNOOBRATNYH |LEMENTOV. pUSTX $H$---PODGRUPPA GRUPPY~$G$, POROZHDENNAYA
CEPOCHKAMI~$\set{\beta_1,~\ldots, \beta_p}$, T.~E.~MNOZHESTVO VSEH |LEMENTOV
IZ~$G$, KOTORYE MOZHNO ZAPISATX V VIDE PROIZVEDENIJ~$\beta_i$
I~$\beta_j^{-1}$. mOZHNO POKAZATX (SM.~a.~g.~kUROSH, tEORIYA GRUPP (m.,
"nAUKA", 1967), GL.~9], CHTO VSEGDA SUSHCHESTVUET SISTEMA
OBRAZUYUSHCHIH~$\theta_1$,~\dots,$\theta_m$ DLYA~$H$, $m\le p$, UDOVLETVORYAYUSHCHAYA
"SVOJSTVU nILXSENA", KOTOROE GLASIT, CHTO SREDNIJ SIMVOL V~$\theta_i$ (ILI
NE MENEE CHEM ODIN IZ DVUH CENTRALXNYH SIMVOLOV, ESLI $\theta_i$~IMEET
CHETNUYU DLINU) NIKOGDA NE SOKRASHCHAETSYA V VYRAZHENIYAH~$\theta_i\theta^e_j$
ILI~$\theta^e_j\theta_i$, $e=\pm1$ (KROME OCHEVIDNOGO ISKLYUCHENIYA~$i=j$,
$e=-1$). iZ |TOGO SVOJSTVA, VYTEKAET, CHTO SUSHCHESTVUET PROSTOJ ALGORITM
PROVERKI PRINADLEZHNOSTI PROIZVOLXNOGO |LEMENTA~$G$ PODGRUPPE~$H$:
ISPOLXZUYA $2n$~SIMVOLOV $a_1$,~\dots, $a_n$, $a^{-1}_1$,~\dots, $a^{-1}_n$,
 ZAPISHEM $2m$~KLYUCHEJ $\theta_1$,~\dots, $\theta_m$, $\theta^{-1}_1$,~\dots,
 $\theta^{-1}_m$ V DEREVO, ORIENTIROVANNOE NA POISK PO SIMVOLAM. pUSTX
$\alpha=b_1\ldots{}b_r$---DANNYJ |LEMENT IZ~$G$; ESLI~$r=0$, TO
|LEMENT~$\alpha$, RAZUMEETSYA, PRINADLEZHIT~$H$. v PROTIVNOM SLUCHAE
ISHCHEM~$\alpha$, NAHODYA SAMUYU DLINNUYU PRISTAVKU~$b_1\ldots{}b_k$,
SOOTVETSTVUYUSHCHUYU KLYUCHU. eSLI BOLEE CHEM ODIN KLYUCH NACHINAETSYA
S~$b_1\ldots{}b_k$, TO |LEMENT~$\alpha$ NE PRINADLEZHIT~$H$; V PROTIVNOM
SLUCHAE OBOZNACHIM |TOT EDINSTVENNYJ KLYUCH
CHEREZ~$b_1\ldots{}b_kc_1\ldots{}c_l=\theta^e_l$ I ZAMENIM~$\alpha$
NA~$\theta^{-e}_l\alpha=c^{-1}_l\ldots{}c^{-1}_1b_{k+1}\ldots{}b_r$. eSLI
|TO NOVOE ZNACHENIE~$\alpha$ DLINNEE STAROGO (T.~E.\ ESLI~$l>k$),
$\alpha$~NE PRINADLEZHIT~$H$; V PROTIVNOM SLUCHAE POVTORYAEM PROCESS S NOVYM
ZNACHENIEM~$\alpha$. sVOJSTVO nILXSENA GARANTIRUET KONECHNOSTX |TOGO
ALGORITMA. eSLI UDALOSX SVESTI~$\alpha$ K PUSTOJ CEPOCHKE, MY MOZHEM
VOSSTANOVITX ISHODNOE PREDSTAVLENIE~$\alpha$ V VIDE PROIZVEDENIJ~$\theta_i$.

nAPRIMER, PUSTX $\set{\theta_1, \theta_2, \theta_3}=\set{bbb,
b^{-1}a^{-1}b^{-1}, ba^{-1}b}$ I~$\alpha=bbabaab$. lES
\picture{rIS. STR. 599}
VMESTE S OPISANNYM ALGORITMOM POZVOLYAET
POLUCHITX~$\alpha=\theta_1\theta_3^{-1}\theta_1\theta_3^{-1}\theta_2^{-1}$.
rEALIZUJTE |TOT ALGORITM, ISPOLXZUYA V KACHESTVE VHODNYH DANNYH DLYA VASHEJ
PROGRAMMY~$\theta_i$.

\ex[23] \exhead(sZHATIE SPEREDI I SZADI.) eSLI NABOR BINARNYH KLYUCHEJ
ISPOLXZUETSYA V KACHESTVE UKAZATELYA DLYA RASCHLENENIYA BOLEE KRUPNOGO FAJLA,
TO NET NUZHDY HRANITX POLNYE KLYUCHI. nAPRIMER, SHESTNADCATX KLYUCHEJ RIS.~34
MOZHNO UREZATX SPRAVA TAK, CHTOBY OSTAVALOSX DOSTATOCHNO CIFR DLYA IH
ODNOZNACHNOGO OPREDELENIYA: $0000$, $0001$, $00100$, $00101$, $010$,~\dots,
$1110001$. tAKIE UREZANNYE KLYUCHI MOZHNO ISPOLXZOVATX DLYA RASCHLENENIYA FAJLA
NA SEMNADCATX CHASTEJ; NAPRIMER, PYATAYA CHASTX SOSTOIT IZ VSEH KLYUCHEJ,
NACHINAYUSHCHIHSYA S~$0011$ ILI~$010$, A POSLEDNYAYA CHASTX SODERZHIT VSE KLYUCHI,
NACHINAYUSHCHIESYA S~$111001$, $11101$ ILI~$1111$. uREZANNYE KLYUCHI MOZHNO
PREDSTAVITX BOLEE KOMPAKTNO, ESLI OPUSTITX LEVYE CIFRY, OBSHCHIE S PREDYDUSHCHIM
KLYUCHOM: $0000$, $***1$, $**100$, $****1$, $*10$,~\dots, $******1$. zA
ZVEZDOCHKAMI VSEGDA SLEDUET EDINICA, PO|TOMU EE MOZHNO OPUSTITX v BOLXSHOM
FAJLE BUDET MNOGO ZVEZDOCHEK, I MY DOLZHNY HRANITX LISHX IH CHISLO I
ZNACHENIYA SLEDUYUSHCHIH BITOV. (nA |TOT SPOSOB SZHATIYA AVTORU UKAZALI
r.~e.~gELLER I~r.~l.~jONSEN.)
%%600
pOKAZHITE, CHTO SUMMARNOE CHISLO BITOV V SZHATOM FAJLE, ISKLYUCHAYA ZVEZDOCHKI I
SLEDUYUSHCHUYU ZA NIMI EDINICU, RAVNO CHISLU UZLOV V BINARNOM BORU, SODERZHASHCHEM
|TI KLYUCHI.

(sLEDOVATELXNO, SREDNEE SUMMARNOE CHISLO TAKIH BITOV VO VSEM
UKAZATELE PRIMERNO RAVNO~$N/(\ln 2)$, CHTO SOSTAVLYAET LISHX OKOLO
$1.44$~BITA NA KLYUCH. vOZMOZHNO I ESHCHE BOLXSHEE SZHATIE, TAK KAK NAM NUZHNO
PREDSTAVITX LISHX STRUKTURU BORA, SR.~S~TEOREMOJ 2.3.1A).
\bye