\input style
\chapno=6\subchno=4\chapnotrue

\subchap{vyborka po vtorichnym klyucham} %%6.5
mY ZAVERSHILI IZUCHENIE POISKA PO "PERVICHNYM KLYUCHAM", T.~E.
PO KLYUCHAM, ODNOZNACHNO OPREDELYAYUSHCHIM ZAPISX V FAJLE. nO INOGDA
NEOBHODIMO VESTI POISK, OSNOVYVAYASX NE NA PERVICHNYH KLYUCHAH, A NA ZNACHENIYAH
DRUGIH POLEJ ZAPISI, KOTORYE CHASTO NAZYVAYUTSYA "VTORICHNYMI KLYUCHAMI" ILI
"ATRIBUTAMI" ZAPISI. nAPRIMER, V REGISTRACIONNOM FAJLE, SODERZHASHCHEM
INFORMACIYU O STUDENTAH UNIVERSITETA, MOZHET PONADOBITXSYA NAJTI VSEH
STUDENTOV-VTOROKURSNIKOV IZ oGAJO, NE SPECIALIZIRUYUSHCHIHSYA PO
MATEMATIKE ILI STATISTIKE, ILI MOZHET PONADOBITXSYA NAJTI VSEH NEZAMUZHNIH
ASPIRANTOK, GOVORYASHCHIH PO-FRANCUZSKI, I T.~D.

vOOBSHCHE PREDPOLOZHIM, CHTO KAZHDAYA ZAPISX IMEET NESKOLXKO ATRIBUTOV I MY HOTIM
NAJTI VSE ZAPISI S OPREDELENNYMI ZNACHENIYAMI OPREDELENNYH ATRIBUTOV.
sPECIFIKACIYA ISKOMYH ZAPISEJ NAZYVAETSYA \dfn{ZAPROSOM}. oBYCHNO DOPUSKAETSYA
NE BOLEE TREH SLEDUYUSHCHIH TIPOV ZAPROSOV.
\medskip
\item{a)}~\dfn{pROSTOJ ZAPROS}, KOGDA OPREDELENNOMU ATRIBUTU
ZADAETSYA KONKRETNOE ZNACHENIE, NAPRIMER $|special'nost'|=|matematika|$ ILI
$|mestozhitel'stvo|.|shtat| = |ogajo|$.

\item{b)}~\dfn{zAPROS PO OBLASTI ZNACHENIJ}, KOGDA DLYA
OPREDELENNOGO ATRIBUTA ZADAETSYA KONKRETNAYA OBLASTX ZNACHENIJ, NAPRIMER
$|cena|<18.00\$$; ILI $21 \le |vozrast| \le 23$.

\item{c)}~\dfn{bULEV ZAPROS} SOSTOIT IZ ZAPROSOV DVUH PERVYH TIPOV,
 SOEDINENNYH OPERACIYAMI |i|, |ili|, |ne|; NAPRIMER,
$$
\displaylines{
(|kurs|=|vtorokursnik|) \mathbin{|i|} (|mestozhitel'stvo.shtat|=|ogajo|) \cr
\mathbin{|i|} \mathop{|ne|}\nolimits
((|special'nost'|=|matematika|)\mathbin{|ili|} (|special'nost'|=|statistika|)).\cr
}
$$

zADACHA RAZRABOTKI |FFEKTIVNYH METODOV POISKA DOSTATOCHNO TRUDNA UZHE DLYA
|TIH TREH TIPOV ZAPROSOV, PO|TOMU ZAPROSY BOLEE SLOZHNYH TIPOV OBYCHNO NE
RASSMATRIVAYUTSYA. nAPRIMER, ZHELEZNODOROZHNAYA KOMPANIYA MOGLA BY IMETX FAJL,
OPISYVAYUSHCHIJ TEKUSHCHEE SOSTOYANIE VSEH PRINADLEZHASHCHIH EJ TOVARNYH
VAGONOV. zAPROS TIPA "NAJDI VSE SVOBODNYE VAGONY-HOLODILXNIKI V PREDELAH
500~MILX OT sI|TLA" V YAVNOM VIDE BYL BY NEDOPUSTIM, ESLI BY "RASSTOYANIE OT
sI|TLA" BYLO NE ATRIBUTOM KAZHDOJ ZAPISI, A SLOZHNOJ FUNKCIEJ NESKOLXKIH
ATRIBUTOV. iSPOLXZOVANIE ZHE LOGICHESKIH KVANTOROV V DOPOLNENIE K |i|,
|ili| I~|ne| VEDET K DALXNEJSHIM USLOZHNENIYAM, STEPENX KOTORYH OGRANICHENA
%% 652
LISHX FANTAZIEJ AVTORA ZAPROSA. nAPRIMER, IMEYA FAJL BEJSBOLXNOJ
STATISTIKI, MY MOGLI BY ZAPROSITX DANNYE O SAMOJ DLINNOJ SERII UDACHNYH
UDAROV V VECHERNIH IGRAH. eTI ZAPROSY SLOZHNY, NO NA NIH VSE ZHE MOZHNO
OTVETITX, VYPOLNIV ODIN PROHOD PO DOLZHNYM OBRAZOM ORGANIZOVANNOMU FAJLU.
eSTX I ESHCHE BOLEE TRUDNYE ZAPROSY; NAPRIMER, NAJTI VSE PARY ZAPISEJ,
IMEYUSHCHIH ODINAKOVYE ZNACHENIYA PYATI ILI BOLEE ATRIBUTOV (BEZ OPREDELENIYA
TOGO, KAKIE IMENNO ATRIBUTY DOLZHNY SOVPADATX). pODOBNYE ZAPROSY MOZHNO
RASSMATRIVATX KAK OBSHCHIE ZADACHI PROGRAMMIROVANIYA, VYHODYASHCHIE ZA RAMKI
DANNOJ RABOTY, HOTYA CHASTO IH MOZHNO RAZBITX NA PODZADACHI RASSMATRIVAEMYH
NAMI TIPOV.

pREZHDE CHEM PEREHODITX K IZUCHENIYU RAZLICHNYH METODOV VYBORKI PO VTORICHNYM
KLYUCHAM, UMESTNO RASSMOTRETX |KONOMICHESKUYU STORONU VOPROSA. hOTYA DOVOLXNO
OBSHIRNAYA OBLASTX PRILOZHENIJ POPADAET V ZHESTKIE RAMKI TREH TIPOV ZAPROSOV,
SLOZHNYE METODY, KOTORYE MY BUDEM IZUCHATX, DALEKO NE VSEGDA
YAVLYAYUTSYA UDOVLETVORITELXNYMI; INUYU RABOTU MOZHNO BYSTREE SDELATX VRUCHNUYU!
evm UVELICHILI SKOROSTX NAUCHNYH VYCHISLENIJ PRIBLIZITELXNO V
$10^7$--$10^8$~RAZ; POVYSHENIE ZHE |FFEKTIVNOSTI V DELE UPRAVLENIYA
INFORMACIEJ NEIZMERIMO MENXSHE. pRI OPERACIYAH S BOLXSHIM KOLICHESTVOM DANNYH
SOVREMENNYE evm RABOTAYUT VSE ESHCHE S MEHANICHESKIMI (A NE |LEKTRONNYMI)
SKOROSTYAMI, PO|TOMU, ZAMENYAYA RUCHNUYU SISTEMU NA evm, MY NE POLUCHAEM REZKOGO
ULUCHSHENIYA HARAKTERISTIK NA EDINICU ZATRAT. nE SLEDUET OZHIDATX OT evm
SLISHKOM MNOGOGO TOLXKO POTOMU, CHTO ONI ZDOROVO RESHAYUT NEKOTORYE ZADACHI\dots

lYUDI POKORILI eVEREST "POTOMU, CHTO ON SUSHCHESTVUET", I POTOMU, CHTO BYLO
SOZDANO OBORUDOVANIE, SDELAVSHEE VOSHOZHDENIE VOZMOZHNYM; TOCHNO TAK ZHE,
VSTRETIVSHISX S GOROJ INFORMACII, LYUDI POPYTALISX ISPOLXZOVATX evm DLYA
OTVETOV NA SAMYE TRUDNYE MYSLIMYE I NEMYSLIMYE VOPROSY V OPERATIVNOM
REZHIME I REALXNOM MASSHTABE VREMENI, NE UCHITYVAYA DOLZHNYM OBRAZOM STOIMOSTI
RABOTY. tREBUEMYE VYCHISLENIYA VOZMOZHNY, NO SLISHKOM DOROGI DLYA KAZHDODNEVNOGO
ISPOLXZOVANIYA.

rASSMOTRIM, NAPRIMER, SLEDUYUSHCHIJ PROSTOJ SPOSOB VYBORKI PO VTORICHNYM
KLYUCHAM: POSLE "\emph{BUFERIZACII}" RYADA ZAPROSOV MOZHNO PROIZVESTI
POSLEDOVATELXNYJ POISK VO VSEM FAJLE, VYBIRAYA VSE NUZHNYE ZAPISI.
("bUFERIZACIYA" OZNACHAET, CHTO MY NAKAPLIVAEM ZAPROSY, PREZHDE CHEM NACHATX
IH OBRABOTKU.) eTOT METOD VPOLNE UDOVLETVORITELEN, ESLI FAJL NE SLISHKOM
VELIK, A NA ZAPROSY NE NADO OTVECHATX NEMEDLENNO. oN GODITSYA DAZHE
DLYA FAJLOV NA LENTAH I LISHX VREMYA OT VREMENI TREBUET VNIMANIYA evm, CHTO
DELAET EGO OCHENX |KONOMICHNYM V SMYSLE STOIMOSTI OBORUDOVANIYA. bOLEE TOGO,
PREDLAGAEMYJ PODHOD PRIMENIM DAZHE DLYA OBRABOTKI VYCHISLITELXNYH ZAPROSOV
TIPA "RASSTOYANIYA OT sI|TLA".

%%653

dRUGOJ SPOSOB OBLEGCHITX VYBORKU PO VTORICHNYM KLYUCHAM---PORUCHITX
\emph{CHELOVEKU} CHASTX RABOTY, OBESPECHIV EGO DOLZHNYM OBRAZOM OFORMLENNYMI
UKAZATELYAMI INFORMACII. chASTO TAKOJ PODHOD OKAZYVAETSYA NAIBOLEE RAZUMNYM
I |KONOMICHNYM (RAZUMEETSYA, PRI TOM USLOVII, CHTO POSLE VYHODA V SVET NOVOGO
UKAZATELYA STARAYA BUMAGA PERERABATYVAETSYA).

oDNAKO OPISANNYE PROSTYE SHEMY NE YAVLYAYUTSYA UDOVLETVORITELXNYMI, ESLI
VAZHNY BYSTRYE OTVETY NA ZAPROSY, A FAJLY OCHENX VELIKI. tAKAYA SITUACIYA
IMEET MESTO, NAPRIMER, ESLI FAJL PREDSTAVLYAET SOBOJ OB�EKT NEPRERYVNYH
ZAPROSOV OT RYADA ODNOVREMENNYH, POLXZOVATELEJ ILI ESLI ZAPROSY
POROZHDAYUTSYA NE CHELOVEKOM, A MASHINOJ. cELX NASTOYASHCHEGO PARAGRAFA---PONYATX,
NASKOLXKO HOROSHO MOZHNO PROIZVODITX VYBORKU PO VTORICHNYM KLYUCHAM, ISPOLXZUYA
OBYCHNYE evm, PRI RAZLICHNYH PREDPOLOZHENIYAH O STRUKTURE FAJLA.

bYLO VYDVINUTO NEMALO HOROSHIH IDEJ DLYA RESHENIYA |TOJ ZADACHI, NO (KAK
CHITATELX NAVERNYAKA UZHE DOGADALSYA) |TI ALGORITMY OKAZALISX NEIZMERIMO
HUZHE IMEYUSHCHIHSYA ALGORITMOV VYBORKI PO PERVICHNYM KLYUCHAM. vSLEDSTVIE
BOLXSHOGO RAZNOOBRAZIYA FAJLOV I PRILOZHENIJ MY NE SMOZHEM DATX
ISCHERPYVAYUSHCHEGO OBSUZHDENIYA VSEH IMEYUSHCHIHSYA VOZMOZHNOSTEJ, KAK I NE
SMOZHEM PROANALIZIROVATX POVEDENIE KAZHDOGO ALGORITMA V TIPICHNYH USLOVIYAH. v
NASTOYASHCHEM PARAGRAFE SODERZHATSYA LISHX OSNOVNYE IZ PREDLAGAVSHIHSYA PODHODOV;
DELO CHITATELYA RESHATX, KAKAYA KOMBINACIYA METODOV BOLXSHE VSEGO PODHODYAT V
KAZHDOM KONKRETNOM SLUCHAE.

\section iNVERTIROVANNYE FAJLY. pERVYJ VAZHNYJ KLASS METODOV VYBORKI PO
VTORICHNYM KLYUCHAM OSNOVAN NA IDEE "INVERTIROVANNOGO FAJLA". eTOT TERMIN NE
OZNACHAET, CHTO FAJL PEREVERNUT VVERH DNOM, ON OZNACHAET, CHTO ZAPISI I
ATRIBUTY POMENYALISX ROLYAMI. vMESTO PERECHISLENIYA ATRIBUTOV DANNOJ ZAPISI
PERECHISLYAYUTSYA ZAPISI, IMEYUSHCHIE DANNOE ZNACHENIE ATRIBUTA.

v POVSEDNEVNOJ ZHIZNI MY DOVOLXNO CHASTO (PRAVDA, POD DRUGIMI IMENAMI)
STALKIVAEMSYA S INVERTIROVANNYMI FAJLAMI. nAPRIMER, INVERTIROVANNYM FAJLOM,
SOOTVETSTVUYUSHCHIM RUSSKO-ANGLIJSKOMU SLOVARYU, YAVLYAETSYA ANGLO-RUSSKIJ
SLOVARX. iNVERTIROVANNYM FAJLOM, SOOTVETSTVUYUSHCHIM |TOJ KNIGE,
YAVLYAYUTSYA UKAZATELI, POMESHCHENNYE NA POSLEDNIH STRANICAH.
bUHGALTERY TRADICIONNO ISPOLXZUYUT "DVOJNUYU BUHGALTERIYU", KOGDA VSE
DELOVYE SOGLASHENIYA REGISTRIRUYUTSYA KAK V SCHETE KASSY, TAK I V SCHETE
KLIENTA, CHTO POZVOLYAET LEGKO KONTROLIROVATX NALICHNUYU SUMMU DENEG I DOLG
KLIENTA.

vOOBSHCHE INVERTIROVANNYJ FAJL OBYCHNO NE SUSHCHESTVUET SAM PO SEBE, EGO NUZHNO
ISPOLXZOVATX VMESTE S PERVONACHALXNYM, NEINVERTIROVANNYM FAJLOM DLYA
USKORENIYA POISKA S POMOSHCHXYU SODERZHASHCHEJSYA
%%654
V NEM IZBYTOCHNOJ INFORMACII. kOMPONENTY INVERTIROVANNOGO FAJLA,
T.~E.~SPISKI VSEH ZAPISEJ, IMEYUSHCHIH DANNOE ZNACHENIE NEKOTOROGO ATRIBUTA,
NAZYVAYUTSYA \dfn{INVERTIROVANNYMI SPISKAMI}.

kAK I VSE SPISKI VOOBSHCHE, INVERTIROVANNYE SPISKI MOZHNO PREDSTAVLYATX V
PAMYATI evm RAZLICHNYMI SPOSOBAMI, I DLYA RAZNYH PRILOZHENIJ PODHODYAT RAZNYE
PREDSTAVLENIYA. nEKOTORYE POLYA VTORICHNYH KLYUCHEJ MOGUT IMETX LISHX DVA
ZNACHENIYA (NAPRIMER, ATRIBUT "POL"), A SOOTVETSTVUYUSHCHIE
INVERTIROVANNYE SPISKI OCHENX DLINNY, NO DRUGIE POLYA OBYCHNO IMEYUT OCHENX
MNOGO ZNACHENIJ S REDKIMI POVTORENIYAMI (NAPRIMER, ATRIBUT "NOMER TELEFONA").

pREDSTAVIM SEBE, CHTO MY HOTIM HRANITX INFORMACIYU V TELEFONNOJ KNIGE
TAKIM OBRAZOM, CHTOBY VSE |LEMENTY MOZHNO BYLO VYBIRATX LIBO PO IMENI, LIBO
PO NOMERU TELEFONA, LIBO PO MESTU ZHITELXSTVA. oDNO IZ RESHENIJ SOSTOIT V
TOM, CHTOBY PROSTO IMETX TRI OTDELXNYH FAJLA, ORIENTIROVANNYH NA KAZHDYJ
TIP KLYUCHEJ. dRUGAYA IDEYA ZAKLYUCHAETSYA V OB�EDINENII |TIH FAJLOV, NAPRIMER, S
POMOSHCHXYU POSTROENIYA TREH RASSEYANNYH TABLIC, SLUZHASHCHIH V METODE CEPOCHEK
GOLOVNYMI UZLAMI SPISKOV. v |TOJ POSLEDNEJ SHEME KAZHDAYA ZAPISX DOLZHNA BYTX
|LEMENTOM TREH SPISKOV I DOLZHNA PO|TOMU SODERZHATX TRI POLYA SSYLKI; TAKOJ
METOD NAZYVAETSYA \dfn{mNOGOSPISOCHNYM} I OBSUZHDAETSYA NIZHE. eSHCHE ODNA
VOZMOZHNOSTX---OB�EDINITX TRI FAJLA V ODIN SUPERFAJL PO ANALOGII S
BIBLIOTECHNYM KATALOGOM, V KOTOROM KARTOCHKI S FAMILIYAMI AVTOROV, KARTOCHKI S
NAZVANIYAMI KNIG I KARTOCHKI S TEMAMI KNIG VSE VMESTE UPORYADOCHENY PO ALFAVITU.

iZUCHENIE FORMATA, ISPOLXZOVANNOGO V UKAZATELYAH K DANNOJ KNIGE, NATALKIVAET
NA DRUGIE IDEI O PREDSTAVLENII INVERTIROVANNYH SPISKOV. eSLI
OPREDELENNOMU ZNACHENIYU ATRIBUTA SOOTVETSTVUET OKOLO PYATI |LEMENTOV,
MOZHNO ORGANIZOVATX OBYCHNYJ POSLEDOVATELXNYJ SPISOK ADRESOV ZAPISEJ
(ANALOGICHNO NOMERAM STRANIC V UKAZATELE K KNIGE), IMEYUSHCHIH DANNOE ZNACHENIE
VTORICHNOGO KLYUCHA. eSLI SOOTVETSTVUYUSHCHIE ZAPISI
RASPOLAGAYUTSYA POSLEDOVATELXNO, MOZHET BYTX POLEZNYM UKAZANIE
DIAPAZONA (NAPRIMER, SO STRANICY~200 PO~214). eSLI IZVESTNO, CHTO
ZAPISI FAJLA DOVOLXNO CHASTO PEREMESHCHAYUTSYA, VMESTO ADRESOV ZAPISEJ V
INVERTIROVANNOM FAJLE, POZHALUJ, LUCHSHE ISPOLXZOVATX PERVICHNYE KLYUCHI;
TOGDA PRI SMENE ADRESOV ZAPISEJ NE NUZHNO BUDET PROIZVODITX NIKAKIH
IZMENENIJ. nAPRIMER, PRI SSYLKAH NA bIBLIYU VSEGDA UKAZYVAETSYA GLAVA I STIH,
 A UKAZATELI V NEKOTORYH KNIGAH OSNOVANY NE NA NUMERACII STRANIC, A NA NOMERAH PARAGRAFOV.

oDNAKO PREDLOZHENNYE IDEI NE OCHENX PODHODYAT DLYA SLUCHAYA ATRIBUTA S DVUMYA
VOZMOZHNYMI ZNACHENIYAMI, TIPA ATRIBUTA "|pol|". v TAKOJ SITUACII NUZHEN LISHX
ODIN INVERTIROVANNYJ SPISOK,
%%655
IBO NE MUZHCHINA ESTX ZHENSHCHINA I OBRATNO. eSLI KAZHDOE ZNACHENIE SOOTVETSTVUET
PRIMERNO POLOVINE |LEMENTOV FAJLA, INVERTIROVANNYE SPISKI BUDUT UZHASNO
DLINNYMI, ODNAKO NA DVOICHNOJ evm |TU TRUDNOSTX MOZHNO RAZRESHITX VESXMA
IZYASHCHNO, ISPOLXZUYA PREDSTAVLENIE V VIDE CEPOCHKI BITOV, GDE KAZHDYJ
BIT OPREDELYAET ZNACHENIE ATRIBUTA OPREDELENNOJ ZAPISI. tAK, CEPOCHKA
BITOV~$01001011101\ldots$ MOGLA BY OZNACHATX, CHTO PERVAYA ZAPISX
FAJLA OPISYVAET MUZHCHINU, VTORAYA---ZHENSHCHINU, SLEDUYUSHCHIE DVE---MUZHCHIN I T.~D.
(sR.~TAKZHE S OBSUZHDENIEM PREDSTAVLENIYA PROSTYH CHISEL V KONCE~\S~6.1.)

pRIVEDENNYE METODY UDOVLETVORITELXNY DLYA OBRABOTKI ZAPROSOV PO
KONKRETNYM ZNACHENIYAM ATRIBUTOV. nEKOTOROE OBOBSHCHENIE |TIH METODOV
POZVOLIT OBRABATYVATX ZAPROSY PO OBLASTI ZNACHENIJ. pRI |TOM VMESTO
HESHIROVANIYA NUZHNO ISPOLXZOVATX SHEMU POISKA, OSNOVANNUYU NA SRAVNENIYAH (\S~6.2).

dLYA BULEVYH ZAPROSOV TIPA
"$(|special'nost'| = |matematika|) \mathbin{|i|}
(|mestozhitel'stvo|.|shtat|= |ogajo|)$"
 NUZHNO PERESECHX DVA INVERTIROVANNYH SPISKA. eTO MOZHNO SDELATX
NESKOLXKIMI SPOSOBAMI; NAPRIMER, ESLI OBA SPISKA UPORYADOCHENY, ODIN
PROHOD PO KAZHDOMU IZ NIH POZVOLYAET VYYAVITX VSE OBSHCHIE |LEMENTY. iLI ZHE
MOZHNO VZYATX \emph{KRATCHAJSHIJ} SPISOK I PROSMATRIVATX EGO |LEMENTY,
PROVERYAYA ZNACHENIYA DRUGIH ATRIBUTOV;
ODNAKO TAKOJ METOD PRIMENIM K OPERACII~|i| I NE PRIMENIM K OPERACII~|ili|.
kROME TOGO, ON NE GODITSYA DLYA VNESHNIH FAJLOV, IBO VEDET K BOLXSHOMU CHISLU
OBRASHCHENIJ K ZAPISYAM, NE UDOVLETVORYAYUSHCHIM ZAPROSU.

aNALOGICHNYE RASSUZHDENIYA POKAZYVAYUT, CHTO UPOMYANUTAYA VYSHE mNOGOSPISOCHNAYA
ORGANIZACIYA NE|FFEKTIVNA DLYA BULEVYH ZAPROSOV, ESLI FAJL VNESHNIJ,
POSKOLXKU ONA TREBUET MNOGO NENUZHNYH OBRASHCHENIJ. pREDSTAVIM SEBE, NAPRIMER,
CHTO PROIZOJDET, ESLI UKAZATELX K |TOJ KNIGE ORGANIZOVATX mNOGOSPISOCHNYM
OBRAZOM. kAZHDYJ |LEMENT UKAZATELYA BUDET SSYLATXSYA LISHX NA POSLEDNYUYU IZ TEH
STRANIC, GDE RASPOLAGAETSYA OPISYVAEMYJ OB�EKT; NA KAZHDOJ STRANICE DLYA
KAZHDOGO OB�EKTA DOLZHNA IMETXSYA SSYLKA NA MESTO EGO PREDYDUSHCHEGO POYAVLENIYA.
v TAKOM SLUCHAE PRIDETSYA PERELISTATX MNOGO STRANIC, CHTOBY NAJTI VESX
MATERIAL, OTNOSYASHCHIJSYA K TEME "[aNALIZ ALGORITMOV] I [(vNESHNYAYA SORTIROVKA)
ILI (vNUTRENNYAYA SORTIROVKA)]". s DRUGOJ STORONY, TOT ZHE ZAPROS
MOZHNO OBRABOTATX, VZGLYANUV VSEGO NA DVE STRANICY OBYCHNOGO UKAZATELYA I
PROIZVEDYA NESLOZHNYE OPERACII NAD INVERTIROVANNYMI SPISKAMI DLYA
NAHOZHDENIYA NEBOLXSHOGO PODMNOZHESTVA STRANIC, UDOVLETVORYAYUSHCHIH ZAPROSU.

eSLI INVERTIROVANNYJ SPISOK PREDSTAVLEN V VIDE CEPOCHKI BITOV, NE
SOSTAVLYAET BOLXSHOGO TRUDA VYPOLNITX BULEVY KOMBINACII ZAPROSOV,
POSKOLXKU evm MOGUT MANIPULIROVATX CEPOCHKAMI BITOV SO SRAVNITELXNO
VYSOKOJ SKOROSTXYU. v SLUCHAE SMESHANNYH
%%656
ZAPROSOV, KOGDA NEKOTORYE ATRIBUTY PREDSTAVLENY POSREDSTVOM
POSLEDOVATELXNYH SPISKOV NOMEROV ZAPISEJ, A DRUGIE POSREDSTVOM CEPOCHEK
BITOV, NETRUDNO PREOBRAZOVATX POSLEDOVATELXNYE SPISKI V CEPOCHKI BITOV I
PROIZVESTI NAD NIMI BULEVY OPERACII.

v |TOM MESTE POLEZNO PRIVESTI KOLICHESTVENNYJ PRIMER GIPOTETICHESKOGO
PRILOZHENIYA. pREDPOLOZHIM, IMEETSYA 1000000~ZAPISEJ PO 40~LITER V KAZHDOJ, I
PUSTX FAJL HRANITSYA NA DISKAH \MIXTEC (SM.~P.~5.4.9). sAM FAJL ZANIMAET
DVA DISKOVYH PAKETA;
INVERTIROVANNYE SPISKI ZAJMUT, VEROYATNO, NESKOLXKO BOLXSHE MESTA. kAZHDAYA
DOROZHKA SODERZHIT
$5000\hbox{~LITER}=30\ 000\hbox{~BITOV}$, PO|TOMU INVERTIROVANNYJ SPISOK
DLYA NEKOTOROGO ATRIBUTA ZAJMET NE BOLEE 34~DOROZHEK. (mAKSIMALXNOE CHISLO
DOROZHEK SOOTVETSTVUET SLUCHAYU, KOGDA PREDSTAVLENIE V VIDE CEPOCHEK BITOV
NAIBOLEE KOROTKOE.) pREDPOLOZHIM, IMEETSYA DOVOLXNO SLOZHNYJ ZAPROS,
SOSTOYASHCHIJ IZ BULEVOJ KOMBINACII 10~INVERTIROVANNYH SPISKOV; V
HUDSHEM SLUCHAE NAM PRIDETSYA PERESECHX 340~DOROZHEK INFORMACII IZ
INVERTIROVANNOGO FAJLA. pOLNOE VREMYA CHTENIYA SOSTAVIT
$340\times 25\hbox{~MS} =8.5\hbox{~S.}$
sREDNEE VREMYA ZADERZHKI RAVNO PRIBLIZITELXNO POLOVINE |TOGO KOLICHESTVA, NO
ESLI ISKUSNO SOSTAVITX PROGRAMMU, ZADERZHKU MOZHNO ISKLYUCHITX. eSLI HRANITX
PERVYE DOROZHKI CEPOCHEK NA ODNOM CILINDRE, VTORYE NA SLEDUYUSHCHEM I T.~P., TO
VREMYA POISKA MOZHNO OCENITX
VELICHINOJ~$34\times26\hbox{~MS}\approx0.9\hbox{~S}$ (ILI 1.8~S, ESLI
CHTENIE PROIZVODITSYA S DVUH DISKOV). nAKONEC, ESLI ZAPROSU UDOVLETVORYAET
$k$~ZAPISEJ, TO POTREBUETSYA
$k\times (60\hbox{~MS (POISK)}+12.5\hbox{~MS(ZADERZHKA)}+0.2\hbox{~MS (CHTENIE)})$
DOPOLNITELXNOGO VREMENI, CHTOBY DOSTATX IH DLYA POSLEDUYUSHCHEJ
OBRABOTKI. tAKIM OBRAZOM, OPTIMISTICHESKAYA OCENKA POLNOGO VREMENI OBRABOTKI
|TOGO DOVOLXNO SLOZHNOGO ZAPROSA DAET CHISLO~$(10+0.073kt)\hbox{~S}$.
pOLUCHENNYJ REZULXTAT MOZHNO SOPOSTAVITX S 210~S, NUZHNYMI NA CHTENIE
VSEGO FAJLA S MAKSIMALXNOJ SKOROSTXYU.

rASSMOTRENNYJ PRIMER POKAZYVAET, CHTO DLYA DISKOVOJ PAMYATI OPTIMIZACIYA PO
PROSTRANSTVU TESNO SVYAZANA S OPTIMIZACIEJ PO VREMENI; VREMYA OBRABOTKI
INVERTIROVANNYH SPISKOV PRIBLIZITELXNO RAVNO VREMENI, ZATRACHIVAEMOMU NA
IH POISK I CHTENIE.

dO SIH POR V BOLXSHEJ ILI MENXSHEJ STEPENI PREDPOLAGALOSX, CHTO V PROCESSE
OBRABOTKI ZAPROSA FAJL NE RASTET I NE SOKRASHCHAETSYA; NO CHTO DELATX, ESLI
NEOBHODIMY CHASTYE IZMENENIYA? vO MNOGIH PRILOZHENIYAH DOSTATOCHNO BUFERIZOVATX
RYAD TREBUEMYH IZMENENIJ I POZABOTITXSYA O NIH V SVOBODNUYU MINUTU, KOGDA
NE NUZHNO OTVECHATX NA ZAPROSY. eSLI ZHE IZMENENIYA FAJLA IMEYUT VYSOKIJ
PRIORITET, NAPRASHIVAETSYA ISPOLXZOVANIE $B\hbox{-DEREVXEV}$ (P.~6.2.4). vSE
MNOZHESTVO INVERTIROVANNYH SPISKOV MOZHNO BYLO BY POMESTITX V ODNO
GIGANTSKOE $B\hbox{-DEREVO}$, PRICHEM NETERMINALXNYE UZLY DOLZHNY
SODERZHATX ZNACHENIYA KLYUCHEJ, A LISTXYA---I KLYUCHI, I SPISKI UKAZATELEJ NA ZAPISI.

%%657
%% 657

v PREDYDUSHCHEM OBSUZHDENII MY UMOLCHALI ESHCHE OB ODNOM TRUDNOM VOPROSE---O ZADACHE
BULEVYH KOMBINACIJ ZAPROSOV PO OBLASTI ZNACHENIJ. pREDPOLOZHIM, NAPRIMER,
CHTO ZAPISI FAJLA OPISYVAYUT GORODA sEVERNOJ aMERIKI I CHTO ZAPRASHIVAYUTSYA
NAZVANIYA VSEH GORODOV S KOORDINATAMI
$$
(21.49^\circ<|shirota|\le 37.41^\circ)\mathbin{|i|} (70.34^\circ\le
|dolgota| \le  75.72^\circ).
$$
sKOREE VSEGO, NI ODNA STRUKTURA DANNYH PO-NASTOYASHCHEMU NE GODITSYA DLYA
PODOBNYH "ZAPROSOV PO PRYAMOUGOLXNOJ OBLASTI ZNACHENIJ". (vZGLYANUV NA
KARTU, MY VIDIM, CHTO MNOGIE GORODA UDOVLETVORYAYUT OGRANICHENIYU NA SHIROTU,
MNOGIE---NA DOLGOTU, NO EDVA LI NAJDETSYA GOROD, UDOVLETVORYAYUSHCHIJ OBOIM
OGRANICHENIYAM.) pOZHALUJ, NAILUCHSHIJ PODHOD SOSTOIT V DOVOLXNO
GRUBOM RASCHLENENII MNOZHESTVA VSEH VOZMOZHNYH ZNACHENIJ |shiroty| I |dolgoty|,
CHTOBY NA KAZHDYJ ATRIBUT PRIHODILOSX LISHX NESKOLXKO KLASSOV (NAPRIMER,
MOZHNO OKRUGLYATX S NEDOSTATKOM DO CHISLA, KRATNOGO~$5^\circ$), I V
POSLEDUYUSHCHEM POSTROENII INVERTIROVANNOGO SPISKA DLYA KAZHDOGO
KOMBINIROVANNOGO $(|shirota|, |dolgota|)$~KLASSA. eTO VSE RAVNO, CHTO IMETX
KARTY, GDE DLYA KAZHDOGO NEBOLXSHOGO RAJONA OTVEDENA OTDELXNAYA STRANICA.
pRI ISPOLXZOVANII INTERVALOV V~$5^\circ$ K ZAPROSU IMEYUT OTNOSHENIE VOSEMX
STRANIC, A IMENNO $(20^\circ, 70^\circ)$, $(25^\circ, 70^\circ)$,~\dots,
$(35^\circ, 75^\circ)$. zAPROS NEOBHODIMO OBRABOTATX DLYA KAZHDOJ IZ NIH,
LIBO PROIZVODYA BOLEE TONKOE RASCHLENENIE VNUTRI STRANICY, LIBO
NEPOSREDSTVENNO OBRASHCHAYASX K ZAPISYAM V ZAVISIMOSTI OT CHISLA ZAPISEJ,
SOOTVETSTVUYUSHCHIH |TOJ STRANICE. pO SUSHCHESTVU, POLUCHAETSYA STRUKTURA DEREVA S
DVUMERNYMI RAZVETVLENIYAMI VO VNUTRENNIH UZLAH.

dRUGOJ PODHOD K ZAPROSAM PO PRYAMOUGOLXNOJ OBLASTI, TAKZHE OSNOVANNYJ NA
STRUKTURE DEREVA, PREDLOZHIL bRYUS mAK-nATT. pUSTX, NAPRIMER, NUZHNO
OBRABOTATX ZAPROS TIPA "kAKOJ GOROD BLIZHE VSEGO K TOCHKE~$x$?", ESLI DANO
ZNACHENIE~$x$. kAZHDYJ UZEL PREDLAGAEMOGO mAK-nATTOM BINARNOGO DEREVA POISKA
SOOTVETSTVUET GORODU~$y$ I "KONTROLXNOMU RADIUSU"~$r$; LEVOE
PODDEREVO |TOGO UZLA SOOTVETSTVUET VSEM GORODAM~$z$, POZDNEE VSTAVLENNYM V
DEREVO, PRICHEM RASSTOYANIE OT~$y$ DO~$z$ DOLZHNO BYTX $\le r+\delta$;
ANALOGICHNO PRAVOE PODDEREVO PREDNAZNACHENO DLYA RASSTOYANIJ $\ge r-\delta$.
zDESX $\delta$---DANNYJ DOPUSK; GORODA, OTSTOYASHCHIE OT~$y$ MENXSHE, CHEM
NA~$r+\delta$, I BOLXSHE, CHEM NA~$r-\delta$, DOLZHNY VHODITX V OBA PODDEREVA.
 pOISK V TAKOM "POCHTOVOM DEREVE" POZVOLYAET VYYAVITX VSE GORODA, OTSTOYASHCHIE
OT DANNOJ TOCHKI MENEE, CHEM NA~$\delta$. (sM.~RIS.~45.)

v 1972~G. mAK-nATT I eDVARD pRING, OSNOVYVAYASX NA |TOJ IDEE, PROVELI
NESKOLXKO |KSPERIMENTOV. v KACHESTVE BAZY DANNYH ONI ISPOLXZOVALI
231~NAIBOLEE NASELENNYJ GOROD KONTINENTALXNYH
%% 658
\picture{rIS 45. vERHNIE UROVNI "POCHTOVOGO DEREVA". chTOBY NAJTI VSE GORODA,
 RASPOLOZHENNYE VBLIZI DANNOJ TOCHKI~$x$, NACHNEM S KORNYA: ESLI $x$ NE DALEE
1800 MILX OT lAS-vEGASA, IDEM VLEVO, V PROTIVNOM SLUCHAE--- VPRAVO; ZATEM
POVTORYAEM |TOM PROCESS, POKA NE DOSTIGNEM KONCEVOGO UZLA. mETOD POSTROENIYA
DEREVA GARANTIRUET, CHTO V PROCESSE POISKA MY DOSTIGNEM VSEH GORODOV,
OTSTOYASHCHIH OT~$x$ NE BOLEE CHEM NA 20~MILX.
}
%%659
sOEDINENNYH shTATOV, VZYATYJ V SLUCHAJNOM PORYADKE. kONTROLXNYJ
RADIUS~$r$ UMENXSHALSYA REGULYARNYM OBRAZOM: PRI SHAGE VLEVO $r$~ZAMENYALI
NA~$0.67r$, A PRI SHAGE VPRAVO---NA~$0.57r$. eSLI ZHE VYBIRALASX VTORAYA IZ
DVUH POSLEDOVATELXNYH PRAVYH VETVEJ, RADIUS OSTAVALSYA NEIZMENNYM. v
REZULXTATE POLUCHILOSX, CHTO PRI $\delta = 20\hbox{~MILX}$ V DEREVE BYLO
610~UZLOV, A PRI $\delta=35\hbox{~MILX}$---1600~UZLOV. nA RIS.~45 IZOBRAZHENY
VERHNIE UROVNI MENXSHEGO DEREVA. (v OSTAVSHIHSYA UROVNYAH oRLANDO (SHTAT
fLORIDA) POYAVLYAETSYA I NIZHE dZHEKSONVILA, I NIZHE mAJAMI. nEKOTORYE GORODA
VSTRECHAYUTSYA DOVOLXNO CHASTO; TAK, 17~UZLOV PREDNAZNACHENY DLYA bROKTONA
(SHTAT mASSACHUSETS)!)

\section sOSTAVNYE ATRIBUTY. mOZHNO SKOMBINIROVATX DVA ILI BOLEE ATRIBUTOV
V ODIN SUPERATRIBUT. nAPRIMER, ATRIBUT
"$(|kurs|, |special'nost'|)$" V UNIVERSITETSKOM REGISTRACIONNOM FAJLE
MOZHNO SOZDATX, KOMBINIRUYA POLYA |kurs| I~|special'nost'|. pRI TAKOM PODHODE
NA ZAPROS CHASTO MOZHNO OTVETITX S POMOSHCHXYU OB�EDINENIYA NESKOLXKIH KOROTKIH
SPISKOV, A NE S POMOSHCHXYU PERESECHENIYA BOLEE DLINNYH SPISKOV.

iDEYU KOMBINACII ATRIBUTOV RAZVIL v.~lUM [{\sl CACM,\/} {\bf 13} (1970),
660--665]. oN PREDLOZHIL UPORYADOCHIVATX INVERTIROVANNYE SPISKI,
 SOOTVETSTVUYUSHCHIE SOSTAVNYM ATRIBUTAM, LEKSIKOGRAFICHESKI SLEVA NAPRAVO I
IZGOTOVLYATX NESKOLXKO KOPIJ, V KOTORYH OTDELXNYE ATRIBUTY PERESTAVLENY
NADLEZHASHCHIM OBRAZOM. pREDPOLOZHIM, NAPRIMER, CHTO IMEYUTSYA TRI ATRIBUTA |A|,
|B|, |C|; MOZHNO OBRAZOVATX TRI KOMBINIROVANNYH ATRIBUTA
$$
(|A|, |B|, |C|),   (|B|, |C|, |A|),   (|C|, |A|, |B|)
\eqno (1)
$$
I DLYA KAZHDOGO IZ NIH POSTROITX UPORYADOCHENNYJ INVERTIROVANNYJ SPISOK.
(tAK, V PERVOM SPISKE ZAPISI UPORYADOCHENY PO ZNACHENIYU POLYA~|A|; VSE
ZAPISI S ODNIM I TEM ZHE ZNACHENIEM~|A| UPORYADOCHENY PO~|B|, A ZATEM I
PO~|C|.) pODOBNAYA ORGANIZACIYA POZVOLYAET OTVECHATX NA ZAPROSY, SOSTOYASHCHIE IZ
LYUBOJ KOMBINACII |TIH TREH ATRIBUTOV; NAPRIMER, VSE ZAPISI, IMEYUSHCHIE
OPREDELENNYE ZNACHENIYA~|A| I~|C|, RASPOLOZHENY V TRETXEM SPISKE DRUG ZA DRUGOM.

aNALOGICHNO IZ CHETYREH ATRIBUTOV |A|, |B|, |C|, |D| MOZHNO OBRAZOVATX
SHESTX KOMBINIROVANNYH ATRIBUTOV
$$
\matrix{
(|A|,  |B|, |C|, |D|), &  (|B|, |C|, |D|, |A|), & (|B|, |D|, |A|, |C|), \cr
(|C|, |A|, |D|, |B|), &(|C|, |D|, |A|, |B|), &(|D|, |A|, |B|, |C|),\cr
}
\eqno(2)
$$
CHTO POZVOLYAET OTVECHATX NA VSE KOMBINACIJ PROSTYH ZAPROSOV, V KOTORYH
FIKSIROVANY, ZNACHENIYA ODNOGO, DVUH, TREH ILI CHETYREH ATRIBUTOV.
sUSHCHESTVUET OBSHCHAYA PROCEDURA POSTROENIYA $\perm{n}{k}$~KOMBINIROVANNYH
ATRIBUTOV IZ $n$~ATRIBUTOV, GDE $k\le{1\over2}n$; PRI |TOM VSE ZAPISI,
IMEYUSHCHIE OPREDELENNYE KOMBINACII $\le k$ ILI
%% 660
$\ge n-k$~ZNACHENIJ ATRIBUTOV, RASPOLOZHATSYA POSLEDOVATELXNO V ODNOM IZ
INVERTIROVANNYH SPISKOV (SM.~UPR.~1). iLI ZHE MOZHNO  OBOJTISX MENXSHIM
CHISLOM KOMBINACIJ, ESLI NEKOTORYE ATRIBUTY IMEYUT OGRANICHENNOE KOLICHESTVO
ZNACHENIJ. nAPRIMER, ESLI  ATRIBUT~$|D|$ MOZHET PRINIMATX LISHX DVA ZNACHENIYA,
TO TRI KOMBINACII
$$
\matrix{
(|D|, |A|, |B|, |C|),& (|D|, |B|, |C|, |A|),& (|D|, |C|, |A|, |B|),\cr
}
\eqno(3)
$$
POLUCHENNYE IZ~(1) VNESENIEM~$|D|$ V SKOBKI, BUDUT POCHTI STOLX ZHE HOROSHI,
KAK I~(2), IBO DLYA OTVETOV NA ZAPROSY, NE ZAVISYASHCHIE OT~|D|, ODIN IZ
SPISKOV DOSTATOCHNO PROSMOTRETX VSEGO V DVUH MESTAH. iZBYTOCHNOSTX ZHE
INFORMACII UMENXSHILASX VDVOE.

\section bINARNYE ATRIBUTY. pOLEZNO RASSMOTRETX CHASTNYJ SLUCHAJ, KOGDA VSE
ATRIBUTY MOGUT PRINIMATX LISHX DVA ZNACHENIYA. pO SUSHCHESTVU, MY IMEEM
\emph{POLNUYU PROTIVOPOLOZHNOSTX} KOMBINIROVANIYU ATRIBUTOV, TAK KAK MOZHEM
PREDSTAVITX LYUBOE ZNACHENIE V VIDE DVOICHNOGO CHISLA I RASSMATRIVATX BITY
|TOGO CHISLA KAK OTDELXNYE ATRIBUTY. v TABL.~1 (SM.~McCall, Cook Book (New
York: Random House (1963), Ch.~9) PRIVEDEN TIPICHNYJ FAJL, SODERZHASHCHIJ
ATRIBUTY "DA-NET"; V DANNOM SLUCHAE ZAPISI OPISYVAYUT IZBRANNYE RECEPTY
PECHENXYA, A ATRIBUTY OPREDELYAYUT, KAKIE INGREDIENTY ISPOLXZUYUTSYA. nAPRIMER,
DLYA PRIGOTOVLENIYA MINDALXNYH  VAFELX S ROMOM NUZHNY MASLO, MUKA, MOLOKO,
OREHI I SAHARNYJ
PESOK. eSLI TRAKTOVATX TABL.~1 KAK MATRICU IZ NULEJ I EDINIC, TO
TRANSPONIROVANNAYA MATRICA DAET INVERTIROVANNYJ FAJL V VIDE CEPOCHEK BITOV.

v PRAVOM STOLBCE TABL.~1 UKAZANY OSOBYE, REDKO UPOTREBLYAEMYE PRODUKTY iH
MOZHNO BYLO BY ZAKODIROVATX BOLEE |FFEKTIVNO, NE OTVODYA KAZHDOMU PO STOLBCU;
TO ZHE SPRAVEDLIVO  I DLYA STOLBCA "MAISOVYJ KRAHMAL". mOZHNO BYLO BY
|FFEKTIVNEE ZAKODIROVATX STOLBEC "MUKA", IBO MUKA VHODIT VO VSE BLYUDA,
 KROME MERENGI. sEJCHAS, ODNAKO, DAVAJTE OSTAVIM V STORONE |TI SOOBRAZHENIYA
I PROSTO PROIGNORIRUEM STOLBEC "OSOBYE INGREDIENTY".

oPREDELIM \emph{BAZOVYJ ZAPROS} V FAJLE S BINARNYMI ATRIBUTAMI, KAK ZAPROS
NA VSE ZAPISI, IMEYUSHCHIE NULI V OPREDELENNYH STOLBCAH, EDINICY---V NEKOTORYH
DRUGIH I PROIZVOLXNYE ZNACHENIYA---V OSTAVSHIHSYA STOLBCAH. iSPOLXZUYA "$*$" DLYA
OBOZNACHENIYA PROIZVOLXNOGO ZNACHENIYA, LYUBOJ BAZOVYJ ZAPROS MOZHNO
PREDSTAVITE V VIDE POSLEDOVATELXNOSTI NULEJ, EDINIC I ZVEZDOCHEK.
pREDSTAVIM SEBE CHELOVEKA, KOTOROMU VDRUG OCHENX ZAHOTELOSX PECHENXYA S
KOKOSOVYMI OREHAMI, TOGDA KAK SHOKOLAD VYZYVAET U NEGO ALLERGIYU, ANIS ON NE
TERPIT, A VANILINA V DOME NET. oN MOZHET SFORMULIROVATX TAKOJ ZAPROS:
$$
0 * * 0 * * * 1 * * * * * * * * * * * * * * * * * * * 0 * *
\eqno(4)
$$
%% 661
\picture{tABLICA 1 fAJL S BINARNYMN ATRIBUTAMI}
%% 662
tABLICA~1 POKAZHET, CHTO NA SAMOM DELE EMU HOCHETSYA PALOCHEK AROMATNYH S
CHERNOSLIVOM.

pREZHDE CHEM RASSMOTRETX OBSHCHUYU ZADACHU ORGANIZACII FAJLA  DLYA OBRABOTKI
BAZOVYH ZAPROSOV, VAZHNO IZUCHITX CHASTNYJ SLUCHAJ, KOGDA ZAPROS SOSTOIT
TOLXKO IZ EDINIC I ZVEZDOCHEK. tAKOJ
ZAPROS MOZHNO NAZVATX \emph{VKLYUCHAYUSHCHIM}, IBO ON ZAPRASHIVAET VSE;
ZAPISI, VKLYUCHAYUSHCHIE V SEBYA NEKOTOROE MNOZHESTVO ATRIBUTOV (ESTESTVENNO
SCHITATX, CHTO EDINICA OBOZNACHAET IMEYUSHCHIJSYA ATRIBUT, A NULX---OTSUTSTVUYUSHCHIJ).
 nAPRIMER, IZ RECEPTOV TABL.~1
\picture{rIS. 46.  kARTA S KRAEVOJ PERFORACIEJ.}
TOLXKO GLAZIROVANNYE IMBIRNYE PRYANIKI I STARINNOE SAHARNOE PECHENXE
SODERZHAT I PEKARNYJ POROSHOK, I PISHCHEVUYU SODU.

dLYA NEKOTORYH PRILOZHENIJ DOSTATOCHNO OBESPECHITX LISHX OTVETY NA VKLYUCHAYUSHCHIE
ZAPROSY. eTO SPRAVEDLIVO, NAPRIMER, DLYA RUCHNYH FAJLOVYH SISTEM "NA KARTAH
S KRAEVOJ PERFORACIEJ" ILI "KARTOTEK PRIZNAKOV". sISTEMA NA KARTAH S
KRAEVOJ PERFORACIEJ, SOOTVETSTVUYUSHCHAYA TABL.~1, SODERZHALA BY PO KARTE NA
KAZHDYJ RECEPT, GDE KAZHDOMU INGREDIENTU SOOTVETSTVUET VYREZ. (sM.~RIS.~46.)
dLYA OBRABOTKI VKLYUCHAYUSHCHEGO ZAPROSA KARTY SKLADYVAYUT V AKKURATNUYU STOPKU I
VVODYAT SPICY V POZICII, SOOTVETSTVUYUSHCHIE TREBUEMYM ATRIBUTAM. zATEM SPICY
PODNIMAYUT I KARTY, IMEYUSHCHIE NUZHNYE ATRIBUTY, VYPADAYUT.

"kARTOTEKA PRIZNAKOV" ANALOGICHNO RABOTAET S INVERTIROVANNYM FAJLOM. v
|TOM SLUCHAE IMEETSYA PO KARTE NA KAZHDYJ ATRIBUT. dLYA KAZHDOJ ZAPISI NA
KARTAH OTVODITSYA OPREDELENNAYA POZICIYA, I ESLI ZAPISX OBLADAET NEKOTORYM
ATRIBUTOM, TO V SOOTVETSTVUYUSHCHEM MESTE DELAETSYA PROBIVKA. sLEDOVATELXNO,
OBYCHNAYA $80\hbox{-KOLONNAYA}$ PERFOKARTA MOZHET SODERZHATX INFORMACIYU O
$12\times80=960\hbox{~ZAPISYAH}$. dLYA OBRABOTKI VKLYUCHAYUSHCHEGO
ZAPROSA OTBIRAYUT KARTY NUZHNYH ATRIBUTOV, KLADUT IH VMESTE I PROSVECHIVAYUT;
%%663
\htable{tABLICA 2}%
{pRIMER KODIROVANIYA NALOZHENIEM}%
{
#\bskip\hfill&\bskip$#$\bskip&#\bskip\hfill&\bskip$#$\bskip\cr
\noalign{\hbox{kODY OTDELXNYH SPECIJ}}
aBRIKOSY           & 1000010000 & lIMONNYJ SOK      & 1000100000\cr
aPELXSINY          & 0100000100 & mED               & 0000000011\cr
aRAHISOVOE MASLO   & 0000000101 & mELASSA           & 1001000000\cr
bANANY             & 0000100010 & mUSKATNYJ OREH    & 0000010010\cr
vANILIN            & 0000001001 & mUSKATNYJ "CVET"  & 0000010100\cr
dUSHISTYJ PEREC     & 0000100001 & oREHI             & 0000100100\cr
zASAHARENNAYA VISHNYA & 0000101000 & pEREC             & 0010000100\cr
zERNA ANISA        & 0000011000 & sMORODINOVOE ZHELE & 0010000001\cr
iZYUM               & 0101000000 & fINIKI            & 1000000100\cr
iMBIRX             & 0000110000 & cITRON            & 0100000010\cr
kARDAMON           & 1000000001 & chERNOSLIV         & 0010000010\cr
kOKOSOVYE OREHI    & 0001010000 & chESNOK            & 0001100000\cr
kORICA             & 1000000010 & shOKOLAD           & 0010001000\cr
kOFE               & 0001000100 & eKSTRAKT MINDALYA  & 0100000001\cr
lIMONNAYA CEDRA     & 0011000000 & yaBLOCHNYJ SOUS     & 0010010000\cr
\noalign{\hbox{nALOZHENNYE KODY}}
bANANOVO-OVSYANOE PECHENXE       &\span\span 1000111111\cr
vANILXNO-OREHOVOE MOROZHENOE    &\span\span 0000101101\cr
vOZDUSHNOE PECHENXE              &\span\span 0000001001\cr
gLAZIROVANNYE IMBIRNYE PRYANIKI &\span\span 1001110010\cr
dRAGOCENNOE PECHENXE            &\span\span 0010101101\cr
dRAZHE V SHOKOLADE               &\span\span 0010101100\cr
iRISKI                         &\span\span 0010111101\cr
mALAJSKIJ KRENDELX             &\span\span 1011100101\cr
mEDOVYE PRYANIKI                &\span\span 1011110111\cr
mERENGI                        &\span\span 1000101100\cr
mINDALXNOE PECHENXE S KOKOSAMI  &\span\span 0001111101\cr
mINDALXNYE VAFLI S ROMOM       &\span\span 0000100100\cr
mORAVSKOE PECHENXE SO SPECIYAMI  &\span\span 1001110011\cr
oVSYANYE PALOCHKI S FINIKAMI     &\span\span 1000100100\cr
pALOCHKI AROMATNYE S CHERNOSLIVOM&\span\span 0111110110\cr
pECHENXE S ARAHISOVYM MASLOM    &\span\span 0010001101\cr
pECHENXE S OREHAMI              &\span\span 1101010110\cr
pECHENXE S PERCEM               &\span\span 1111111111\cr
pECHENXE S YABLOCHNYM SOUSOM      &\span\span 1111111111\cr
pECHENXE SO SLIVOCHNYM SYROM     &\span\span 0010001001\cr
pOLUKRUGLYJ PIROG S NACHINKOJ   &\span\span 1011101101\cr
pUTANICA                       &\span\span 1000001011\cr
rAJSKIE PALOCHKI                &\span\span 0001111101\cr
rOZHDESTVENSKOE ANISOVOE PECHENXE&\span\span 0011011000\cr
sTARINNOE SAHARNOE PECHENXE     &\span\span 0000011011\cr
fIGURNYE PESOCHNYE KORZHIKI      &\span\span 0000000000\cr
fINSKIJ KAKOR                  &\span\span 0100100101\cr
%% 664
shVEDSKIJ KRENDELX                       &\span\span 0000000000\cr
shVEJCARSKOE RASSYPNOE PECHENXE S KORICEJ &\span\span 1000000010\cr
shOKOLADNYJ HVOROST                      &\span\span 0010101101\cr
shOTLANDSKIE OVSYANYE KORZHIKI             &\span\span 0000001001\cr
yuBOCHKI                                  &\span\span 0000001001\cr
}%
LUCHI SVETA PROJDUT CHEREZ VSE POZICII, SOOTVETSTVUYUSHCHIE ISKOMYM
ZAPISYAM eTA OPERACIYA ANALOGICHNA OBRABOTKE BULEVYH ZAPROSOV PUTEM
PERESECHENIYA INVERTIROVANNYH CEPOCHEK BITOV.

\section kODIROVANIE NALOZHENIEM. pRICHINA NASHEGO OSOBOGO INTERESA K RUCHNYM
KARTOTEKAM KROETSYA V TOM, CHTO BYLO PRIDUMANO MNOGO OSTROUMNYH SPOSOBOV
|KONOMII MESTA NA KARTAH S KRAEVOJ PERFORACIEJ; TOT ZHE PODHOD PRIMENIM K
PREDSTAVLENIYU FAJLOV V PAMYATI evm. kODIROVANIE NALOZHENIEM NAPOMINAET
HESHIROVANIE; V DEJSTVITELXNOSTI EGO IZOBRELI ZA NESKOLXKO LET
DO OTKRYTIYA HESHIROVANIYA. iDEYA SOSTOIT V TOM, CHTOBY OTOBRAZITX ATRIBUTY V
SLUCHAJNYE $k\hbox{-BITOVYE}$ KODY V $n\hbox{-BITOVYH}$ POLYAH I NALOZHITX
KODY IMEYUSHCHIHSYA V ZAPISI ATRIBUTOV. vKLYUCHAYUSHCHIJ ZAPROS O NEKOTOROM MNOZHESTVE
ATRIBUTOV MOZHNO PREOBRAZOVATX VO VKLYUCHAYUSHCHIJ ZAPROS O SOOTVETSTVUYUSHCHIH
NALOZHENNYH DVOICHNYH KODAH. eTOMU ZAPROSU MOGUT UDOVLETVORYATX NESKOLXKO
LISHNIH ZAPISEJ, NO KOLICHESTVO TAKIH "LOZHNYH VYPADENIJ"
MOZHNO STATISTICHESKI UCHESTX. [sR. S Calvin N.~Mooers,
{\sl Amer.~Chem.~Soc.~Meeting\/}, {\bf 112} (September, 1947), 14E--15E;
{\sl American Documentation,\/} {\bf 2} (1951), 20--32.]
v KACHESTVE PRIMERA KODIROVANIYA NALOZHENIEM VNOVX RASSMOTRIM TABL.~1, NO
NE VSYU, A TOLXKO CHASTX, KASAYUSHCHUYUSYA SPECIJ. v TABL.~2 POKAZANO, CHTO
POLUCHITSYA, ESLI PRISVOITX ATRIBUTAM SPECIJ SLUCHAJNYE DVUHBITOVYE KODY V
DESYATIBITOVOM POLE I NALOZHITX IH. nAPRIMER, |LEMENT "SHOKOLADNYJ
HVOROST" POLUCHAETSYA NALOZHENIEM KODOV DLYA SHOKOLADA, OREHOV I VANILINA:
$$
0010001000 \vee 0000100100 \vee 0000001001 = 0010101101.
$$
nALOZHENIE KODOV PRIVNOSIT TAKZHE NESKOLXKO LISHNIH ATRIBUTOV, V DANNOM
SLUCHAE |TO DUSHISTYJ PEREC, ZASAHARENNAYA VISHNYA, SMORODINOVOE ZHELE,
KOKOSOVOE MASLO I PEREC, CHTO PRIVEDET K "LOZHNYM VYPADENIYAM" PRI OTVETAH NA
NEKOTORYE ZAPROSY (KROME TOGO, U NAS POYAVILSYA NOVYJ RECEPT---LOZHNOGO PECHENXYA!)
nA SAMOM DELE KODIROVANIE NALOZHENIEM NE OCHENX HOROSHO RABOTAET DLYA TABL.~2,
YAVLYAYUSHCHEJSYA MALENXKIM PRIMEROM SO MNO-
%%665
GIMI ATRIBUTAMI. dEJSTVITELXNO, PECHENXE S YABLOCHNYM SOUSOM BUDET VYPADATX
PRI \emph{KAZHDOM} ZAPROSE, IBO |TA ZAPISX POLUCHENA NALOZHENIEM SEMI KODOV,
POKRYVAYUSHCHIH VSE DESYATX POZICIJ; ESHCHE HUZHE OBSTOIT DELO S PECHENXEM S PERCEM,
POLUCHENNYM NALOZHENIEM" DVENADCATI KODOV! s DRUGOJ STORONY, V NEKOTORYH
SLUCHAYAH TABL.~2 RABOTAET UDIVITELXNO HOROSHO; NAPRIMER, V OTVET NA ZAPROS
O VANILINE ZRYA VYPADET LISHX PECHENXE S PERCEM.

bOLEE PODHODYASHCHIM YAVLYAETSYA PRIMER, KOGDA U NAS ESTX, SKAZHEM, 32-BITOVOE
POLE I MNOZHESTVO IZ $\perm{32}{3}=4960$ RAZLICHNYH ATRIBUTOV. kAZHDAYA ZAPISX
MOZHET IMETX DO SHESTI ATRIBUTOV, I KAZHDYJ ATRIBUT KODIRUETSYA SPECIFIKACIEJ
3-H IZ 32-H BITOV. eSLI MY PREDPOLOZHIM, CHTO KAZHDAYA ZAPISX IMEET SHESTX
SLUCHAJNO VYBRANNYH ATRIBUTOV, TO VEROYATNOSTI LOZHNOGO VYPADENIYA PRI
VKLYUCHAYUSHCHEM ZAPROSE TAKOVY:
$$
\matrix{
\hbox{PO ODNOMU ATRIBUTU:}\hfill   & 0.07948358; \cr
\hbox{PO DVUM ATRIBUTAM:} \hfill   & 0.00708659;\cr
\hbox{PO TREM ATRIBUTAM:} \hfill   & 0.00067094;\cr
\hbox{PO CHETYREM ATRIBUTAM:}\hfill & 0.00006786;\cr
\hbox{PO PYATI ATRIBUTAM:} \hfill   & 0.00000728;\cr
\hbox{PO SHESTI ATRIBUTAM:}\hfill   & 0.00000082.\cr
}
\eqno(5)
$$
tAKIM OBRAZOM, ESLI ESTX $M$~ZAPISEJ, NE UDOVLETVORYAYUSHCHIH ZAPROSU PO DVUM
ATRIBUTAM, TO PRIBLIZITELXNO $0.007M$ IMEYUT NALOZHENNYE KODY, POKRYVAYUSHCHIE
VSE BITY |TIH DVUH ATRIBUTOV. (vEROYATNOSTI PODSCHITANY V UPR.~4.) dLYA
PREDSTAVLENIYA INVERTIROVANNOGO FAJLA POTREBUETSYA $32\times
\hbox{(KOLICHESTVO ZAPISEJ)}$~BITOV, CHTO SOSTAVLYAET MENEE POLOVINY OT CHISLA
BITOV, NEOBHODIMYH DLYA OPISANIYA SOBSTVENNO ATRIBUTOV V ISHODNOM FAJLE.

mALXKOLXM~ch.~hARRISON [{\sl CACM,\/} {\bf 14} (1971), 777--779] ZAMETIL,
CHTO KODIROVANIE NALOZHENIEM MOZHNO ISPOLXZOVATX DLYA USKORENIYA POISKA TEKSTA.
pREDPOLOZHIM, CHTO NAM NUZHNO OPREDELITX VSE VHOZHDENIYA NEKOTOROJ CEPOCHKI
LITER V BOLXSHOJ TEKST BEZ POSTROENIYA GROMOZDKOGO DEREVA pATRICII.
pREDPOLOZHIM, KROME TOGO, CHTO TEKST PODELEN NA STROKI $c_1$ $c_2$~\dots
$c_{50}$  PO 50~LITER V KAZHDOJ. hARRISON PREDLAGAET KODIROVATX KAZHDUYU IZ
49~PAR $c_1$~$c_2$, $c_2$~$c_3$,~\dots, $c_{49}~c_{50}$ PUTEM OTOBRAZHENIYA
EE V CHISLO OT~0 DO, SKAZHEM,~127. zATEM PODSCHITATX "SIGNATURU" STROKI $c_1$
$c_2$~\dots $c_{50}$---CEPOCHKU IZ 128 BITOV $b_0$ $b_1$~\dots $b_{127}$, GDE
$b_i=1$ TOGDA I TOLXKO TOGDA, KOGDA $h(c_j, c_{j+1})=i$ PRI NEKOTOROM~$j$.


eSLI NAM NUZHNO NAJTI VSE VHOZHDENIYA SLOVA |igolka| V BOLXSHOJ TEKSTOVOJ FAJL
|stogsena|, MY PROSTO OTYSKIVAEM VSE STROKI, SIGNATURY KOTORYH SODERZHAT~1
V POZICIYAH $h(|ig|)$, $h(|go|)$, $h(|ol|)$, $h(|lk|)$, $h(|KA|)$. pRI
SLUCHAJNOJ HESH-FUNKCII VEROYATNOSTX TOGO, CHTO NEKOTORAYA SLUCHAJNAYA STROKA
SODERZHIT V
%%666
SIGNATURE VSE |TI EDINICY, RAVNA VSEGO LISHX 0.00341 (SR.~S~UPR.~4);
SLEDOVATELXNO, PERESECHENIE PYATI INVERTIROVANNYH SPISKOV CEPOCHEK BITOV
POZVOLIT BYSTRO NAJTI VSE STROKI, SODERZHASHCHIE SLOVO |igolka| (HOTYA,
VEROYATNO, BUDET I NESKOLXKO LOZHNYH VYPADENIJ).

v DANNOM PRILOZHENII GIPOTEZA O SLUCHAJNOSTI NA SAMOM DELE NESPRAVEDLIVA,
POSKOLXKU OBYCHNYE TEKSTY NESUT V SEBE BOLXSHOE KOLICHESTVO IZBYTOCHNOJ
INFORMACII; RASPREDELENIE DVUHBUKVENNYH KOMBINACIJ V SLOVAH VESXMA
NERAVNOMERNO. nAPRIMER, POLEZNO OTBROSITX VSE PARY~$c_j$~$c_{j+1}$,
SODERZHASHCHIE LITERU "PROBEL", TAK KAK OBYCHNO PROBELY VSTRECHAYUTSYA GORAZDO
CHASHCHE DRUGIH LITER.

dRUGOE INTERESNOE PRIMENENIE KODIROVANIYA NALOZHENIEM K ZADACHAM POISKA NASHEL
bARTON bLUM [{\sl CACM,\/} {\bf 13} (1970), 422--426]; NA SAMOM DELE EGO
METOD PREDNAZNACHEN DLYA VYBORKI PO \emph{PERVICHNYM} KLYUCHAM, NO NAM UDOBNO
OBSUDITX EGO V |TOM PARAGRAFE. pREDSTAVIM SEBE, CHTO PROIZVODITSYA POISK V
BOLXSHOJ SOVOKUPNOSTI DANNYH, PRICHEM, ESLI ON OKAZALSYA NEUDACHNYM, NIKAKIH
DEJSTVIJ VYPOLNYATX NE NUZHNO. nAPRIMER, MY HOTIM PROVERITX CHEJ-LIBO NOMER
PASPORTA ILI SUMMU VYPLACHENNYH NALOGOV I T.~P.; I ESLI V FAJLE NET
SOOTVETSTVUYUSHCHEJ |TOMU LICU ZAPISI, TO DALXNEJSHEGO ISSLEDOVANIYA NE
TREBUETSYA. aNALOGICHNO PRI PRIMENENII evm DLYA TIPOGRAFSKOGO NABORA TEKSTOV
MOZHNO PRIDUMATX PROSTOJ ALGORITM, KOTORYJ POZVOLIT PRAVILXNO DELATX
PERENOSY DLYA BOLXSHINSTVA SLOV, NO BUDET NEPRIMENIM K
50000~SLOVAM-ISKLYUCHENIYAM. eSLI KAKOE-LIBO SLOVO NE UDASTSYA NAJTI V FAJLE
ISKLYUCHENIJ, MOZHNO ISPOLXZOVATX |TOT PROSTOJ ALGORITM.

v PODOBNOJ SITUACII MOZHNO HRANITX VO VNUTRENNEJ PAMYATI TABLICU BITOV, TAK
CHTO V BOLXSHINSTVE SLUCHAEV OTSUTSTVIE KLYUCHA BUDET OPOZNALO BEZ OBRASHCHENIJ
K VNESHNEJ PAMYATI. vOT KAK |TO DELAETSYA. oBOZNACHIM VNUTRENNYUYU TABLICU BITOV
CHEREZ $b_0$~$b_1$~\dots~$b_{M-1}$, GDE $M$ VESXMA VELIKO. dLYA KAZHDOGO
KLYUCHA~$K_j$ FAJLA VYCHISLIM $k$ NEZAVISIMYH HESH-FUNKCIJ $h_1(K_j)$,~\dots,
$h_k(K_j)$ I USTANOVIM SOOTVETSTVUYUSHCHIE $k$~BITOV RAVNYMI~1. (eTI
$k$~ZNACHENIJ NE OBYAZANY BYTX RAZLICHNYMI.) tAKIM OBRAZOM, $b_i=1$ TOGDA I
TOLXKO TOGDA, KOGDA $h_l(K_j)=i$ PRI NEKOTORYH~$j$ I~$l$. tEPERX DLYA TOGO,
CHTOBY OPREDELITX, SODERZHITSYA LI ARGUMENT POISKA~$K$ VO VNESHNEM FAJLE,
NUZHNO SNACHALA PROVERITX, VYPOLNYAETSYA LI SOOTNOSHENIE $b_{h_l(K)}=1$ PRI
$1\le l\le k$: ESLI NET, TO NEZACHEM OBRASHCHATXSYA K VNESHNEJ PAMYATI, ESLI ZHE
DA, TO PRI PODHODYASHCHEM VYBORE~$K$ I~$M$ OBYCHNYMI METODAMI POISKA NAM
SKOREE VSEGO UDASTSYA NAJTI~$K$. vEROYATNOSTX LOZHNOGO VYPADENIYA DLYA FAJLA IZ
$N$~ZAPISEJ PRIBLIZHENNO RAVNA~$(1-e^{-kN/M})^k$. pO SUSHCHESTVU, V
METODE bLUMA VESX FAJL RASSMATRIVAETSYA KAK ODNA ZAPISX, PERVICHNYE
%%667
KLYUCHI TRAKTUYUTSYA KAK IMEYUSHCHIESYA ATRIBUTY, A KODIROVANIE NALOZHENIEM
PROIZVODITSYA V OGROMNOM $M\hbox{-BITOVOM}$ POLE.

eSHCHE ODIN VARIANT KODIROVANIYA NALOZHENIEM V SVOEJ DOKTORSKOJ DISSERTACII
RAZRABOTAL rICHARD gUSTAFSON (Univ. South Carolina, 1969). pREDPOLOZHIM,
IMEETSYA $N$~ZAPISEJ I KAZHDAYA IZ NIH SODERZHIT~6 IZ 10000~VOZMOZHNYH
ATRIBUTOV. nAPRIMER, ZAPISI MOGLI BY OPISYVATX TEHNICHESKIE STATXI, A
ATRIBUTY---IMEYUSHCHIESYA V NIH KLYUCHEVYE SLOVA. pUSTX $h$---HESH-FUNKCIYA,
OTOBRAZHAYUSHCHAYA KAZHDYJ ATRIBUT V CHISLO MEZHDU~0 I~15. eSLI ZAPISX
OBLADAET ATRIBUTAMI $a_1$, $a_2$,~\dots, $a_6$, TO PO METODU gUSTAFSONA
ONA OTOBRAZHAETSYA V 16-BITOVOE CHISLO $b_0$~$b_1$\dots$b_{15}$, GDE $b_i=1$
TOGDA I TOLXKO TOGDA, KOGDA $h(a_j)=i$ PRI NEKOTOROM~$j$; DALEE, ESLI LISHX
$k$~BITOV STALI EDINICHNYMI, $k<6$, TO DRUGIE $6-k$~EDINIC DOBAVLYAYUTSYA
NEKIM SLUCHAJNYM OBRAZOM (NE OBYAZATELXNO ZAVISYASHCHIM OT
SAMIH ZAPISEJ). iMEETSYA $\perm{16}{9}=8008$ 16-BITOVYH KODOV, SODERZHASHCHIH
ROVNO SHESTX EDINIC; PRI IZVESTNOJ DOLE VEZENIYA PRIBLIZITELXNO
$N/8008$~ZAPISEJ OTOBRAZYATSYA V KAZHDOE ZNACHENIE. mOZHNO HRANITX
8008~SPISKOV ZAPISEJ, S POMOSHCHXYU PODHODYASHCHEJ FUNKCII VYCHISLYAYA ADRES,
SOOTVETSTVUYUSHCHIJ KODU $b_0$~$b_1$\dots$b_{15}$. v SAMOM DELE, ESLI EDINICY
RASPOLOZHENY V POZICIYAH $0\le p_1<p_2<\ldots<p_6$, FUNKCIYA
$$
\perm{p_1}{1}+\perm{p_2}{2}+\cdots+\perm{p_6}{6}
$$
PREOBRAZUET KAZHDUYU CEPOCHKU $b_0$~$b_1$\dots$b_{15}$ V CHISLO MEZHDU~0 I~8007,
PRICHEM RAZNYE CEPOCHKI POROZHDAYUT RAZNYE ADRESA. (sM.~UPR.~1.2.6-56 I~2.2.6-7.)

eSLI TEPERX MY HOTIM NAJTI VSE ZAPISI, IMEYUSHCHIE TRI OPREDELENNYH ATRIBUTA
$A_1$, $A_2$, $A_3$, TO SLEDUET VYCHISLITX $h(A_1)$, $h(A_2)$ I~$h(A_3)$;
ESLI |TI ZNACHENIYA RAZLICHNY, NAM PRIDETSYA PROSMOTRETX ZAPISI, HRANYASHCHIESYA V
$\perm{13}{3}=286$~SPISKAH, KODY KOTORYH $b_0$~$b_1$\dots$b_{15}$ SODERZHAT
EDINICY V POZICIYAH $h(A_1)$, $h(A_2)$ I~$h(A_3)$. iNYMI SLOVAMI,
ISSLEDOVANIYU PODVERGNUTSYA LISHX $286\times100/8008\approx 3.5$\%~ZAPISEJ.

\section kOMBINATORNOE HESHIROVANIE. oSNOVNAYA IDEYA TOLXKO CHTO OPISANNOGO
METODA gUSTAFSONA SOSTOIT V TOM, CHTOBY NAJTI TAKOJ SPOSOB OTOBRAZHENIYA
ZAPISEJ V ADRESA PAMYATI, CHTOBY LISHX NEBOLXSHOE KOLICHESTVO ADRESOV BYLO
SVYAZANO S OPREDELENNYM ZAPROSOM. oDNAKO |TOT METOD PRIMENIM LISHX K
VKLYUCHAYUSHCHIM ZAPROSAM, KOGDA OTDELXNYE ZAPISI OBLADAYUT MALYM CHISLOM
ATRIBUTOV. dRUGOJ TIP OTOBRAZHENIJ, PREDNAZNACHENNYH DLYA OBRABOTKI
PROIZVOLXNYH BAZOVYH ZAPROSOV TIPA~(4), SOSTOYASHCHIH IZ NULEJ, EDINIC I
ZVEZDOCHEK, OTKRYL V 1971~G. rONALXD rAJVEST.

pREDPOLOZHIM SNACHALA, CHTO IMEETSYA 1000000~ZAPISEJ I KAZHDAYA IZ NIH
SODERZHIT 10 VTORICHNYH KLYUCHEJ, PRICHEM KAZHDYJ VTORICHNYJ
%%668
KLYUCH MOZHET PRINIMATX DOVOLXNO MNOGO RAZLICHNYH ZNACHENIJ. zAPISX SO
VTORICHNYMI KLYUCHAMI ($K_1$, $K_2$,~\dots, $K_{10}$) MOZHNO OTOBRAZITX V
20-BITOVOE CHISLO
$$
h(K_1) h(K_2) \ldots h(K_{10}),
\eqno(6)
$$
GDE $h$---HESH-FUNKCIYA, PREOBRAZUYUSHCHAYA VTORICHNYJ KLYUCH V 2-BITOVOE CHISLO, A
(6) OBRAZOVANO POSLEDOVATELXNYM VYPISYVANIEM |TIH DESYATI PAR BITOV. pRI
TAKOJ SHEME 1000000~ZAPISEJ OTOBRAZHAYUTSYA V MNOZHESTVO IZ
$2^{20}=1048576$~ZNACHENIJ; VSE OTOBRAZHENIE MOZHNO RASSMATRIVATX KAK
HESH-FUNKCIYU S~$M=2^{20}$. dLYA RAZRESHENIYA KOLLIZIJ VOSPOLXZUEMSYA METODOM
CEPOCHEK. eSLI MY HOTIM VYBRATX VSE ZAPISI, IMEYUSHCHIE OPREDELENNYE
ZNACHENIYA PYATI VTORICHNYH KLYUCHEJ, NAM PRIDETSYA PROSMOTRETX LISHX
$2^{10}$~SPISKOV [SOOTVETSTVUYUSHCHIH PYATI NESPECIFICIROVANNYM PARAM V (6)],
T.~E.~V SREDNEM NUZHNO PROVERITX OKOLO $1000=\sqrt{N}$~ZAPISEJ.
[aNALOGICHNYJ PODHOD PREDLOZHIL aRISAVA, {\sl J.~Inf.~Proc.~Soc.~Japan,\/}
{\bf 12} (1971), 163--167.]

rAJVEST RAZVIL |TU IDEYU DALXSHE, TAK CHTO VO MNOGIH SLUCHAYAH MY IMEEM
SLEDUYUSHCHUYU SITUACIYU. pREDPOLOZHIM, SUSHCHESTVUET $N\approx2^n$~ZAPISEJ I KAZHDAYA
IZ NIH SODERZHIT $m$~VTORICHNYH KLYUCHEJ. zAPISI OTOBRAZHAYUTSYA V
$n\hbox{-BITOVYE}$ HESH-ADRESA TAKIM OBRAZOM, CHTO ZAPROS, NE
SPECIFICIRUYUSHCHIJ ZNACHENIYA $k$~KLYUCHEJ, ZATRAGIVAET PRIMERNO
$N^{k/m}$~ADRESOV. vSE OSTALXNYE OBSUZHDAVSHIESYA V |TOM PARAGRAFE METODY
(KROME METODA gUSTAFSONA) TREBUYUT DLYA VYBORKI INFORMACII PORYADKA $N$~SHAGOV
(PRAVDA, KO|FFICIENT PROPORCIONALXNOSTI NEVELIK); PRI DOSTATOCHNO
BOLXSHOM~$N$ METOD rAJVESTA OKAZHETSYA BOLEE BYSTRYM, K TOMU ZHE ON NE
TREBUET INVERTIROVANIYA FAJLOV.

nO, PREZHDE CHEM PRIMENITX TAKOJ PODHOD, NUZHNO OPREDELITX PODHODYASHCHEE
OTOBRAZHENIE. rASSMOTRIM PRIMER S NEBOLXSHIMI ZNACHENIYAMI PARAMETROV, KOGDA
$m=4$ I~$n=3$, A VSE VTORICHNYE KLYUCHI MOGUT PRINIMATX LISHX DVA ZNACHENIYA;
OTOBRAZIM 4-BITOVYE ZAPISI V VOSEMX ADRESOV SLEDUYUSHCHIM OBRAZOM:
$$
\matrix{
*&0&0&0&\to& 1\cr
*&1&1&1&\to& 2\cr
0&*&0&1&\to& 3\cr
1&*&1&0&\to& 4\cr
}
\qquad
\matrix{
0&1&*&0&\to& 5\cr
1&0&*&1&\to& 6\cr
0&0&1&*&\to& 7\cr
1&1&0&*&\to& 8\cr
}
\eqno(7)
$$
iSSLEDOVANIE |TOJ TABLICY POKAZYVAET, CHTO VSE ZAPISI, SOOTVETSTVUYUSHCHIE
ZAPROSU~$0***$, OTOBRAZHAYUTSYA V PYATX ADRESOV 1, 2, 3, 5 I~7; I VOOBSHCHE
\emph{LYUBOJ} BAZOVYJ ZAPROS S TREMYA ZVEZDOCHKAMI ZATRAGIVAET ROVNO PYATX
ADRESOV. bAZOVYJ ZAPROS S DVUMYA ZVEZDOCHKAMI ZATRAGIVAET TRI ADRESA, I,
NAKONEC, BAZOVYJ ZAPROS S ODNOJ ZVEZDOCHKOJ ZATRAGIVAET LIBO ODIN, LIBO
DVA, A V SREDNEM $(8\times1+24\times2)/32=1.75$~ADRESA. tAKIM OBRAZOM, IMEEM
%%669
{\def\hdr#1{\vbox{\dimen255=\hsize\divide\dimen255 by 3\hsize=\dimen255\leftskip=0pt plus 1fill\rightskip=0pt plus 1fill\noindent #1\par}}
$$
\matrix{
\hdr{kOLICHESTVO NESPECIFICIROVANNYH \goodbreak BITOV V ZAPROSE} & \hdr{kOLICHESTVO ZATRAGIVAEMYH \goodbreak ADRESOV}\cr
4 & 8 = 8^{4/4}\cr
3& 5\approx 8^{3/4}\cr
2& 3\approx 8^{2/4}\cr
1& 1.75\approx 8^{1/4}\cr
0& 1= 8^{0/4}\cr
}
\eqno(8)
$$
}

rAZUMEETSYA, |TO LISHX MALENXKIJ PRIMER; TABLICY PODOBNOGO RAZMERA PROSHCHE
OBRABATYVATX BEZ VSYAKIH UHISHCHRENIJ. nO ON POLEZEN I DLYA NETRIVIALXNYH
PRILOZHENIJ, KOGDA $m=4r$ I~$n=3r$, VEDX $4r\hbox{-BITOVYE}$ ZAPISI MOZHNO
OTOBRAZITX V
$2^{3r}\approx N$~ADRESOV, RAZDELIV VTORICHNYE KLYUCHI NA $r$~GRUPP PO CHETYRE
BITA V KAZHDOJ I PRIMENIV~(7) K KAZHDOJ GRUPPE. pOLUCHAYUSHCHEESYA OTOBRAZHENIE
OBLADAET TREBUEMYM SVOJSTVOM: \dfn{ZAPROS, OSTAVLYAYUSHCHIJ $k$ IZ $m$~BITOV
NESPECIFICIROVANNYMI, ZATRONET PRIMERNO $N^{k/m}$~ADRESOV}. (sM.~UPR.~6.)

nEKOTORYE DRUGIE OTOBRAZHENIYA, NAJDENNYE rAJVESTOM, PRIVODYATSYA V UPR.~7;
IH MOZHNO ISPOLXZOVATX VMESTE S~(7) DLYA POLUCHENIYA FUNKCIJ KOMBINATORNOGO
HESHIROVANIYA V SLUCHAE $1\le m/n \le 2$. nA SAMOM DELE MOZHNO BYLO BY
ISPOLXZOVATX BLOKI RAZMERA~$b$ I POLOZHITX~$N \approx 2^n b$; MY VZYALI
$b=1$ DLYA PROSTOTY IZLOZHENIYA.

\section *sBALANSIROVANNYE FAJLOVYE SISTEMY. dRUGOJ KOMBINATORNYJ PODHOD K
ZADACHE VYBORKI INFORMACII, OSNOVANNYJ NA "SISTEMAH SBALANSIROVANNYH
NEPOLNYH GRUPP", YAVILSYA PREDMETOM MNOGOCHISLENNYH ISSLEDOVANIJ. hOTYA ON
OCHENX INTERESEN S MATEMATICHESKOJ TOCHKI ZRENIYA, SVOEJ PRAKTICHESKOJ
CENNOSTI |TOT METOD, K SOZHALENIYU, ESHCHE NE PROYAVIL. chTOBY DATX CHITATELYU
VOZMOZHNOSTX POCHUVSTVOVATX IZYASHCHESTVO REZULXTATOV, MY VSE ZHE IZLOZHIM
ZDESX KRATKOE VVEDENIE V TEORIYU, NE TERYAYA NADEZHDY, CHTO KTO-NIBUDX NAJDET
EJ PRAKTICHESKOE PRIMENENIE.

\emph{shTEJNEROVSKOJ SISTEMOJ TROEK} NAZYVAETSYA TAKOE RASPREDELENIE
$v$~OB�EKTOV V NEUPORYADOCHENNYE TROJKI, KOGDA KAZHDAYA PARA OB�EKTOV
VSTRECHAETSYA ROVNO V ODNOJ TROJKE. nAPRIMER, ESLI $v=7$, IMEETSYA, PO
SUSHCHESTVU, ODNA SHTEJNEROVSKAYA SISTEMA TROEK, A IMENNO
$$
\matrix{
\hbox{tROJKA} & \hbox{sODERZHASHCHIESYA V NEJ PARY}\span \span \span\cr
\set{1,2,4} & \set{1,2}, & \set{1,4}, & \set{2,4}\cr
\set{2,3,5} & \set{2,3}, & \set{2,5}, & \set{3,6}\cr
\set{3,4,6} & \set{3,4}, & \set{3,6}, & \set{4,6}\cr
\set{4,5,0} & \set{0,4}, & \set{0,5}, & \set{4,5}\cr
\set{5,6,1} & \set{1,5}, & \set{1,6}, & \set{5,6}\cr
\set{6,0,2} & \set{0,2}, & \set{0,6}, & \set{2,6}\cr
\set{0,1,3}  & \set{0,1}, & \set{0,3}, & \set{1,8}\cr
}
$$
%%670
pOSKOLXKU SUSHCHESTVUET ${1\over2}v(v-1)$~PAR OB�EKTOV, A V TROJKE---TRI
PARY, OBSHCHEE CHISLO TROEK RAVNO~${1\over6}v(v-1)$; POSKOLXKU KAZHDYJ OB�EKT
MOZHET SOSTAVLYATX PARU ROVNO S $v-1$ DRUGIMI OB�EKTAMI, ON DOLZHEN
PRISUTSTVOVATX ROVNO V ${1\over2}(v-1)$~TROJKAH. iZ |TIH SOOBRAZHENIJ
SLEDUET, CHTO SISTEMA shTEJNERA SUSHCHESTVUET LISHX TOGDA, KOGDA CHISLA
${1\over6}v(v-1)$ I~${1\over2}(v-1)$ CELYE. zNACHIT,
$v$ DOLZHNO BYTX NECHETNYM I PRI DELENII NA~3 NE DAVATX V OSTATKE 2, T.~E.
$$
v \bmod 6 =1\hbox{ ILI } 3.
\eqno(10)
$$
oBRATNO, V 1847~G.~kIRKMAN DOKAZAL, CHTO, ESLI $v\ge1$ I VYPOLNENO
USLOVIE~(10), SHTEJNEROVSKAYA SISTEMA TROEK DEJSTVITELXNO SUSHCHESTVUET. eGO
INTERESNAYA KONSTRUKCIYA PRIVEDENA V UPR.~10.

shTEJNEROVSKIE SISTEMY TROEK MOZHNO ISPOLXZOVATX DLYA UMENXSHENIYA IZBYTOCHNOSTI
V KOMBINIROVANNYH INVERTIROVANNYH FAJLAH. rASSMOTRIM VNOVX FAJL RECEPTOV
PECHENIJ (TABL.~1) I PREOBRAZUEM PRAVYJ STOLBEC V 31-J~ATRIBUT, KOTORYJ
RAVEN~1, ESLI TREBUETSYA SPECIALXNYJ INGREDIENT, I~0 V PROTIVNOM
SLUCHAE. pREDPOLOZHIM, MY HOTIM OTVECHATX NA VSE VKLYUCHAYUSHCHIE ZAPROSY O PARAH
ATRIBUTOV, NAPRIMER NA ZAPROS "v KAKIH RECEPTAH ISPOLXZUYUTSYA I KOKOSOVYE
OREHI, I IZYUM?" mOZHNO BYLO BY POSTROITX INVERTIROVANNYJ SPISOK DLYA KAZHDOGO
IZ $\perm{31}{2}=465$~VOZMOZHNYH ZAPROSOV. oDNAKO |TI SPISKI ZAJMUT MNOGO
MESTA, POSKOLXKU, NAPRIMER, PECHENXE S PERCEM BUDET SODERZHATXSYA V
$\perm{17}{2}=136$ IZ NIH, A ZAPISX, OBLADAYUSHCHAYA VSEMI ATRIBUTAMI,
VOJDET V KAZHDYJ SPISOK! iSPOLXZOVANIE SISTEMY TROEK shTEJNERA NESKOLXKO
ULUCHSHAET SITUACIYU. dLYA 31~OB�EKTA SUSHCHESTVUET SISTEMA shTEJNERA IZ
155~TROEK, PRICHEM KAZHDAYA PARA OB�EKTOV VHODIT ROVNO V ODNU TROJKU. kAZHDOJ
TROJKE~$\set{a, b, c}$ MOZHNO SOPOSTAVITX CHETYRE SPISKA: ODIN SPISOK---DLYA
ZAPISEJ, OBLADAYUSHCHIH ATRIBUTAMI $a$, $b$, $\bar c$ (T.~E.~NE~$c$);
DRUGOJ---DLYA $a$, $\bar b$, $c$; TRETIJ---DLYA $\bar a$, $b$, $c$;
CHETVERTYJ---DLYA $a$, $b$, $c$. tAKAYA KONSTRUKCIYA GARANTIRUET, CHTO NIKAKAYA
ZAPISX NE POPADET BOLEE CHEM V 155~INVERTIROVANNYH SPISKOV, I |KONOMIT
PROSTRANSTVO, ESLI ZAPISX IMEET TRI ATRIBUTA, SOOTVETSTVUYUSHCHIH TROJKE SISTEMY.

sISTEMA TROEK YAVLYAETSYA CHASTNYM SLUCHAEM SISTEM GRUPP, SOSTOYASHCHIH IZ TREH
ILI BOLEE OB�EKTOV. nAPRIMER, 31~OB�EKT MOZHNO TAK RASPREDELITX PO
NEUPORYADOCHENNYM SHESTERKAM, CHTO KAZHDAYA PARA OB�EKTOV POPADET ROVNO V ODNU SHESTERKU:
%%671
{\def\sset#1{\scriptstyle\set{#1}\hfill}
$$\matrix{
\sset{1,  5, 17, 22, 23, 25} &\sset{ 7, 11, 23, 28, 29, 0} &\sset{13, 17, 26, 3,  4,  6} &\sset{20, 24,  5, 10, 11, 13} &\sset{26, 30, 11, 16, 17, 19}\cr
\sset{2,  6, 18, 23, 24, 26} &\sset{ 8, 12, 24, 29, 30, 1} &\sset{14, 18, 30, 4,  5,  7} &\sset{21, 25,  6, 11, 12, 14} &\sset{27,  0, 12, 17, 18, 20}\cr
\sset{3,  7, 19, 24, 25, 27} &\sset{ 9, 13, 25, 30,  0, 2} &\sset{15, 19,  0, 5,  6,  8} &\sset{22, 26,  7, 12, 13, 15} &\sset{28,  1, 13, 18, 19, 21}\cr
\sset{4,  8, 20, 25, 26, 28} &\sset{10, 14, 26,  0,  1, 3} &\sset{16, 20,  1, 6,  7,  9} &\sset{23, 27,  8, 13, 14, 16} &\sset{29,  2, 14, 19, 20, 22}\cr
\sset{5,  9, 21, 26, 27, 29} &\sset{11, 15, 27,  1,  2, 4} &\sset{17, 21,  2, 7,  8, 10} &\sset{24, 28,  9, 14, 15, 17} &\sset{30,  3, 15, 20, 21, 23}\cr
\sset{6, 10, 22, 27, 28, 30} &\sset{12, 16, 28,  2,  3, 5} &\sset{18, 22,  3, 8,  9, 11} &\sset{25, 29, 10, 15, 16, 18} &\sset{ 0,  4, 16, 21, 22, 24}\cr
                             &                             &\sset{19, 23,  4, 9, 10, 12} \cr
}
$$
}
[eTA SISTEMA POLUCHAETSYA IZ PERVOJ GRUPPY PUTEM SLOZHENIYA PO MODULYU~31. dLYA
PROVERKI TOGO, CHTO ONA OBLADAET TREBUEMYM SVOJSTVOM, ZAMETIM, CHTO
30~ZNACHENIJ~$(a_i-a_j)\bmod 31$, $i\ne j$, RAZLICHNY, ESLI
$(a_1, a_2, ~\ldots, a_6)=(1, 5, 17, 22, 23, 25)$. chTOBY NAJTI SHESTERKU,
SODERZHASHCHUYU DANNUYU PARU~$(x, y)$, VYBEREM $i$ I~$j$ TAK, CHTO
$a_i-a_j\equiv x-y \pmod{31}$; ESLI $k=(x-a_i) \bmod 31$, TO
$(a_i+k) \bmod31=x$ I~$(a_j+k)\bmod31=y$.]

sISTEMU~(11) MOZHNO ISPOLXZOVATX DLYA HRANENIYA INVERTIROVANNYH SPISKOV,
PRICHEM NI ODNA ZAPISX NE POYAVITSYA BOLEE 31~RAZA. kAZHDOJ
SHESTERKE~$\set{a, b, c, d, e, f}$ SOPOSTAVLENO 57~SPISKOV,
PREDNAZNACHENNYH DLYA ZAPISEJ,
IMEYUSHCHIH DVA ILI BOLEE ATRIBUTA $a$, $b$, $c$, $d$, $e$ ILI~$f$,
T.~E.~IMEYUSHCHIH ATRIBUTY $(a, b, \bar c, \bar d, \bar e, \bar f)$,
$(a, \bar b, c, \bar d, \bar e, f)$,~\dots,
$(a, b, c, d, e, f)$; OTVETOM NA LYUBOJ VKLYUCHAYUSHCHIJ ZAPROS PO DVUM ATRIBUTAM
YAVLYAETSYA OB�EDINENIE BEZ PERESECHENIJ 16~PODHODYASHCHIH SPISKOV PODHODYASHCHEJ
SHESTERKI. pECHENXE S PERCEM VOJDET V~29 IZ 31~GRUPPY |TOJ SISTEMY,
POSKOLXKU NAZVANNOE BLYUDO IMEET DVA IZ SHESTI ATRIBUTOV VO VSEH SHESTERKAH,
 KROME $\set{19, 23, 4, 9, 10, 12}$
I~$\set{13, 17, 29, 3, 4, 6}$ (ESLI MY ZANUMERUEM STOLBCY CHISLAMI OT~0 DO~30).

aNALOGICHNAYA IDEYA PRIMENIMA DLYA UMENXSHENIYA IZBYTOCHNOSTI V SOSTAVNYH
INVERTIROVANNYH SPISKAH, KOGDA MY HOTIM OTVECHATX NA BAZOVYE, A NE NA
VKLYUCHAYUSHCHIE ZAPROSY. pREDPOLOZHIM, NAPRIMER, CHTO ZAPISI SODERZHAT PYATX
VTORICHNYH KLYUCHEJ $K_1$, $K_2$, $K_3$, $K_4$, $K_5$, KAZHDYJ IZ KOTORYH
MOZHET PRINIMATX ODNO IZ CHETYREH ZNACHENIJ~0, 1, 2 ILI~3. chTOBY OTVETITX
NA ZAPROS O ZAPISYAH, DLYA KOTORYH $K_i=a$ I~$K_j=b$ PRI DANNYH $a$, $b$
I~$i\ne j$, MY MOGLI BY OBRAZOVATX INVERTIROVANNYE SPISKI DLYA VSEH
160~PODOBNYH ZAPROSOV; V TAKOM SLUCHAE KAZHDAYA ZAPISX PRISUTSTVOVALA BY
V DESYATI INVERTIROVANNYH SPISKAH. aLXTERNATIVOJ YAVLYAETSYA ISPOLXZOVANIE
SLEDUYUSHCHEJ SISTEMY UPORYADOCHENNYH PYATEROK, OSNOVANNOJ NA KOMBINATORNOJ
SHEME, KOTORAYA NAZYVAETSYA "VZAIMNO ORTOGONALXNYE LATINSKIE KVADRATY":
$$
\matrix{
(0, 0, 0, 0, 0) & (1, 0, 1, 2, 3) & (2, 0, 2, 3, 1) & (3, 0, 3, 1, 2) \cr
(0,1,1,1,1) & (1,1,0,3,2) & (2,1,3,2,0) & (3,1,2,0,3)\cr
(0,2,2,2,2) & (1,2,3,0,1) & (2,2,0,1,3) & (3,2,1,3,0)\cr
(0,3,3,3,3) & (1,3,2,1,0) & (2, 3,1,0,2) & (3,3,0,2,1)\cr
}
$$
eSLI MY TEPERX POSMOTRIM NA LYUBYE DVE IZ PYATI KOMPONENT, TO UVIDIM, CHTO
VSE 16~VOZMOZHNYH UPORYADOCHENNYH PAR ZNACHENIJ
%%672
VSTRECHAYUTSYA V |TIH POZICIYAH ROVNO ODIN RAZ. gRUPPE ($a$, $b$, $c$, $d$,
$e$) |TOJ SISTEMY MOZHNO SOPOSTAVITX ZAPISI, UDOVLETVORYAYUSHCHIE PO KRAJNEJ
MERE DVUM IZ USLOVIJ $K_1=a$, $K_2=b$,~\dots, $K_5=e$. tAKIM OBRAZOM,
KAZHDOJ IZ 16~GRUPP BUDUT SOPOSTAVLENY 376 IZ~1024 VOZMOZHNYH ZAPISEJ,
PO|TOMU SREDNYAYA IZBYTOCHNOSTX
UMENXSHILASX S~ 0 DO~$16\times 376/1024 =5{7\over8}$.

tEORIYA SISTEM TAKIH GRUPP I LATINSKIH KVADRATOV DETALXNO RAZRABOTANA V
"KNIGE Marshall Hall, Jr., Combinatorial Theory (Waltham; Mass.: Blaisdell,
 1967). nESMOTRYA NA VSYU KRASOTU |TOGO KRUGA IDEJ, V ZADACHAH VYBORKI
INFORMACII IH UDALOSX ISPOLXZOVATX LISHX DLYA UMENXSHENIYA IZBYTOCHNOSTI PRI
POSTROENII SOSTAVNYH INVERTIROVANNYH SPISKOV; d|VID chZHOU [{\sl
Information and Control,\/} {\bf 15} (1969), 377--396] ZAMETIL, CHTO TOGO
ZHE REZULXTATA MOZHNO DOSTICHX I BEZ KOMBINATORNYH SISTEM.

\section kRATKAYA ISTORIYA I BIBLIOGRAFIYA. pERVAYA OPUBLIKOVANNAYA STATXYA O
METODAH VYBORKI PO VTORICHNYM KLYUCHAM NAPISANA l. dZHONSONOM [{\sl CACM,\/}
{\bf 4} (1961), 218--222]. mNOGOSPISOCHNUYU SISTEMU PRIMERNO V ODNO I TO ZHE
VREMYA NEZAVISIMO RAZRABOTALI nOJ pRAJVZ, X.~gR|J, u.~lANDAU|R, d.~lEFKOVICH
I s.~lITVIN; SR.~S [{\sl IEEE Trans.~on Communication and Electronics,\/}
{\bf 68} (1963), 488--492]. dRUGAYA DOVOLXNO RANNYAYA PUBLIKACIYA,
OKAZAVSHAYA VLIYANIE NA POSLEDUYUSHCHIE RABOTY, PRINADLEZHIT d.~r.~d|VISU I
e.~d.~lINU [{\sl CACM,\/} {\bf 8} (1965), 243--246].

v OBSHIRNOJ LITERATURE, POYAVIVSHEJSYA S TEH POR PO |TOMU VOPROSU, OSNOVNOE
VNIMANIE UDELYALOSX VZAIMODEJSTVIYU S POLXZOVATELYAMI I YAZYKAM
PROGRAMMIROVANIYA, NO |TIH TEM MYV NASHEJ KNIGE NE KASAEMSYA. v DOPOLNENIE
K UZHE PERECHISLENNYM STATXYAM MOZHNO POREKOMENDOVATX SLEDUYUSHCHIE
OPUBLIKOVANNYE RABOTY, OKAZAVSHIE AVTORU NAIBOLXSHUYU POMOSHCHX
PRI-NAPISANII |TOGO PARAGRAFA: Jack Minker, Jerome Sable, {\sl
Ann.~Rev.~of Information Science and Technology,\/} {\sl 2} (1967),
123--160; Robert E.~Bleier, Proc.~ACM~Nat.~Conf., {\bf 22} (1967), 41--49;
Jerome A.~Feldman, Paul D.~Rovner, {\sl CACM,\/} {\bf 12} (1969),
439--449; Burton H.~Bloom, Proc.~ACM~Nat.~Conf., {\bf 24} (1969), 83--95;
H.~S.~Heaps, L.~H.~Thiel, {\sl Information Storage and Retrieval,\/} {\bf
6} (1970), 137--153;
Vincent Y.~Lum, Huei Ling, Proc.~ACM~Nat.~Conf., {\bf 26} (1971), 349--356.
 hOROSHIJ OBZOR RUCHNYH KARTOCHEK SDELAN V GL.~5 KNIGI bURNA Methods of
Information Handling (New York: Wiley, 1963). "sBALANSIROVANNYE FAJLOVYE
SISTEMY" VPERVYE RAZRABOTALI aBRAHAM, s.~gHOSH I d.~rOJ-chOUDHURI V 1965~G.;
POZHALUJ, LUCHSHEE REZYUME |TOJ RABOTY I POSLEDUYUSHCHEGO RAZVITIYA METODA
DALI r.~bOZE I g|RI kOCH [{\sl SIAM, J.~Appl.~Math.,\/} {\bf 17} (1969), 1203--1214].

v NASTOYASHCHEM PARAGRAFE MY OBSUDILI DOVOLXNO MNOGO INTERESNYH IDEJ,
POLEZNYH V OCHENX RAZNYH SITUACIYAH. pOSKOLXKU
%% 673
MNOGIE IZ |TIH METODOV POYAVILISX NEZADOLGO DO NAPISANIYA DANNOGO
PARAGRAFA, TO NOVYE USPEHI, VEROYATNO, NE ZASTAVYAT SEBYA ZHDATX.

iNTERESNO OTMETITX, CHTO CHELOVECHESKIJ MOZG VYPOLNYAET VYBORKU PO VTORICHNYM
KLYUCHAM GORAZDO LUCHSHE, CHEM evm; V SAMOM DELE, MY DOVOLXNO LEGKO RASPOZNAEM
LICA ILI MELODII I~T.~P.\ PO OTRYVOCHNOJ INFORMACII, V TO VREMYA KAK MASHINY,
POZHALUJ, VOOBSHCHE NE V SOSTOYANII SDELATX |TO. i NET NICHEGO NEVOZMOZHNOGO V
TOM, CHTO ODNAZHDY BUDET OTKRYT PRINCIPIALXNO NOVYJ PODHOD K KONSTRUIROVANIYU
MASHIN, KOTORYJ RAZ I NAVSEGDA RESHIT ZADACHU VYBORKI PO VTORICHNYM KLYUCHAM,
SDELAV TEM SAMYM VESX |TOT PARAGRAF NENUZHNYM.

\excercises
\rex[m27] pUSTX $0\le k \le {1\over2}n$. dOKAZHITE, CHTO SLEDUYUSHCHEE
POSTROENIE DAET
$\perm{n}{k}$~PERESTANOVOK CHISEL~$\set{1, 2,~\ldots, n}$, TAKIH, CHTO
KAZHDOE $t\hbox{-|LEMENTNOE}$ PODMNOZHESTVO MNOZHESTVA~$\set{1, 2,~\dots, n}$
PRI $t\le k$ ILI~$t\ge n-k$ VSTRECHAETSYA PO KRAJNEJ MERE ODIN RAZ V
KACHESTVE PERVYH $t$~|LEMENTOV PERESTANOVKI. rASSMOTRIM PUTX NA PLOSKOSTI
IZ TOCHKI~$(0, 0)$ V~$(n, r)$, GDE $r\ge n-2k$, V KOTOROM $i\hbox{-J}$~SHAG
PROIZVODITSYA IZ TOCHKI~$(i-1, j$) V~$(i, j+1)$ ILI V~$(i, j-1)$;
POSLEDNYAYA VOZMOZHNOSTX IMEETSYA LISHX DLYA~$j\ge 1$, PO|TOMU PUTX NIKOGDA NE OPUSKAETSYA
NIZHE OSI~$x$. sUSHCHESTVUET ROVNO $\perm{n}{k}$ TAKIH PUTEJ. pERESTANOVKA,
SOOTVETSTVUYUSHCHAYA PODOBNOMU PUTI, STROITSYA S ISPOLXZOVANIEM TREH
PERVONACHALXNO PUSTYH SPISKOV SLEDUYUSHCHIM OBRAZOM: ESLI $i\hbox{-J}$~SHAG
DELAETSYA VVERH, $i=1$, 2,~\dots, $n$, TO CHISLO~$i$ POMESHCHAETSYA V
SPISOK~$B$; ESLI ZHE VNIZ, TO $i$~POMESHCHAETSYA V SPISOK~$A$, A MAKSIMALXNYJ
NA DANNYJ MOMENT |LEMENT SPISKA~$B$ IZYMAETSYA IZ NEGO I PERENOSITSYA V
SPISOK~$C$. zATEM NUZHNO VYPISATX DRUG ZA DRUGOM |LEMENTY SPISKOV~$A$, $B$
(V VOZRASTAYUSHCHEM PORYADKE) I~$C$ (TAKZHE V VOZRASTAYUSHCHEM PORYADKE). pOSTROENIE
PERESTANOVKI ZAVERSHENO.

nAPRIMER, PRI $n=4$ I~$k=2$ POLUCHAETSYA SHESTX PUTEJ I SOOTVETSTVUYUSHCHIH IM
PERESTANOVOK
\picture{rIS. STR. 673}
(vERTIKALXNYE LINII RAZDELYAYUT SPISKI~$A$, $B$ I~$C$. eTI SHESTX
PERESTANOVOK SOOTVETSTVUYUT SOSTAVNYM ATRIBUTAM V~(2).)

[\emph{uKAZANIE.} pREDSTAVXTE KAZHDOE $t\hbox{-|LEMENTNOE}$
PODMNOZHESTVO~$S$ S POMOSHCHXYU PUTI IZ~$(0, 0)$ V~$ (n, n-2t)$,
$i\hbox{-J}$~SHAG KOTOROGO VYPOLNYAETSYA IZ~$(i-1, j)$ V
$(i, j+1)$, ESLI $i\notin S$, I V~$(i, j-1)$, ESLI $i\in S$. pREOBRAZUJTE
KAZHDYJ TAKOJ PUTX V PUTX OPISANNOGO VYSHE VIDA.]

\ex[m25] (sAKTI gHOSH.) nAJDITE MINIMALXNO VOZMOZHNUYU DLINU~$l$ SPISKA $r_1$
$r_2$~\dots $r_l$ SSYLOK NA ZAPISI, OBLADAYUSHCHEGO TEM SVOJSTVOM, CHTO VSE
OTVETY NA LYUBOJ IZ VKLYUCHAYUSHCHIH ZAPROSOV $* * 1$, $* 1 *$, $1* *$, $* 1 1$,
$1*1$, $11*$, $1 1 1$ PO TREM KLYUCHAM S DVUMYA VOZMOZHNYMI ZNACHENIYAMI
OKAZHUTSYA V POSLEDOVATELXNYH
|LEMENTAH~$r_i~\ldots r_j$.
%%674

\ex[19] rASSMOTRIM TABL.~2. kAKIE VKLYUCHAYUSHCHIE ZAPROSY VYZOVUT
LOZHNOE VYPADENIE: (a)~STARINNOGO SAHARNOGO PECHENXYA; (b)~OVSYANYH PALOCHEK
S FINIKAMI?

\ex[M30] nAJDITE TOCHNYE FORMULY DLYA VEROYATNOSTEJ~(5), PREDPOLAGAYA, CHTO
KAZHDAYA ZAPISX IMEET G RAZLICHNYH ATRIBUTOV, SLUCHAJNO VYBIRAEMYH
IZ~$\perm{n}{k}$ $k\hbox{-BITOVYH}$ KODOV V $n\hbox{-BITOVOM}$ POLE, I CHTO
ZAPROS VKLYUCHAET $q$~RAZLICHNYH, A V OSTALXNOM SLUCHAJNYH ATRIBUTOV. (nE
PUGAJTESX, ESLI FORMULY NE BUDUT UPROSHCHATXSYA!)

\ex[40] pO|KSPERIMENTIRUJTE S RAZLICHNYMI SPOSOBAMI UMENXSHENIYA
IZBYTOCHNOSTI V TEKSTAH, ESLI DLYA POISKA PODCEPOCHEK ISPOLXZUETSYA METOD
hARRISONA.

\rex[m20] oBSHCHEE CHISLO $m\hbox{-BITOVYH}$ ZAPROSOV S $k$~SPECIFICIROVANNYMI
BITAMI RAVNO $s=\perm{m}{k}2^k$. eSLI KOMBINATORNAYA HESH-FUNKCIYA,
PODOBNAYA~(7), PREOBRAZUET |TI ZAPROSY V ADRESA $l_1$, $l_2$,~\dots, $l_s$
SOOTVETSTVENNO, TO $L(k)=(l_1+l_2+\cdots+l_s)/s$ DAET SREDNEE CHISLO
ADRESOV, PRIHODYASHCHIHSYA NA ZAPROS. [nAPRIMER, V~(7) IMEEM $L(3)=1.75$.]

rASSMOTRIM TEPERX SOSTAVNUYU HESH-FUNKCIYU NAD $(m_1+m_2)\hbox{-BITOVYM}$
POLEM, OBRAZOVANNUYU OTOBRAZHENIEM PERVYH $m_1$~BITOV S POMOSHCHXYU ODNOJ
HESH-FUNKCII, A OSTAVSHIHSYA $m_2$~BITOV---S POMOSHCHXYU DRUGOJ. pUSTX $L_1(k)$
I~$L_2(k)$---SOOTVETSTVUYUSHCHIE SREDNIE KOLICHESTVA ADRESOV, PRIHODYASHCHIHSYA NA
ZAPROS. nAJDITE FORMULU, VYRAZHAYUSHCHUYU~$L(k)$ (SREDNEE DLYA SOSTAVNOJ FUNKCII)
CHEREZ~$L_1$ I~$L_2$.

\ex[M24] (r.~rAJVEST.) nAJDITE ZNACHENIYA FUNKCII~$L(k)$, OPREDELENNOJ V
PREDYDUSHCHEM UPRAZHNENII, DLYA SLEDUYUSHCHIH FUNKCIJ KOMBINATORNOGO HESHIROVANIYA:
$$
{\hbox{(a) $m=3$, $n=2$}
\atop
\matrix{
0&0&*&\to&1\cr
1&*&0&\to&2\cr
*&1&1&\to&3\cr
1&0&1&\to&4\cr
0&1&0&\to&4\cr
}
}
\qquad
{\hbox{(a) $m=4$, $n=2$}
\atop
\matrix{
0&0&*&*\to&1\cr
*&1&*&0\to&2\cr
*&1&1&1\to&3\cr
1&0&1&*\to&3\cr
*&1&0&1\to&4\cr
1&0&0&*\to&4\cr
}
}
$$

\ex[m47] pRIDUMAJTE NOVYE POLEZNYE KLASSY FUNKCIJ
KOMBINATORNOGO HESHIROVANIYA, ANALOGICHNYE~(7).

\ex[m20] dOKAZHITE, CHTO PRI $v=3^n$ MNOZHESTVO VSEH TROEK VIDA
$$
\set{ (a_1\ldots a_{k-1} 0 b_1\ldots b_{n-k})_3, (a_1\ldots
a_{k-1}1c_1\ldots c_{n-k})_3,
(a_1\ldots a_{k-1} 2 d_1\ldots d_{n-k})_3}, 1\le k\le n,
$$
OBRAZUET SHTEJNEROVSKUYU SISTEMU TROEK. pREDPOLAGAETSYA, CHTO $a_i$, $b_i$,
$c_i$ I~$d_i$ RAVNY 0, 1 ILI~2 I~$b_i+c_i+d_i\equiv 0 \pmod{3}$.

\ex[m32] (tOMAS kIRKMAN [{\sl Cambridge and Dublin Math~ Journal,\/}
{\bf 2} (1847), 191--204].) nAZOVEM SISTEMOJ TROEK kIRKMANA PORYADKA~$v$ TAKUYU
ORGANIZACIYU $v+1$~OB�EKTOV $\set{x_0, x_1,~\ldots, x_v}$ V TROJKI, CHTO
KAZHDAYA PARA~$\set{x_i, x_j}$, $i\ne j$, VSTRECHAETSYA ROVNO V ODNOJ TROJKE;
ISKLYUCHENIE SOSTAVLYAYUT $v$~PAR $\set{ x_i, x_{(i+1)\bmod v}}$, $0\le i<v$,
NE VSTRECHAYUSHCHIHSYA NI V ODNOJ TROJKE. nAPRIMER,
$$
\set{x_0, x_2, x_4}, \set{x_1, x_3, x_4}
$$
YAVLYAETSYA SISTEMOJ TROEK kIRKMANA PORYADKA~4.

\item{a)}~dOKAZHITE, CHTO SISTEMA TROEK kIRKMANA MOZHET SUSHCHESTVOVATX
TOLXKO PRI~$v\bmod 6= 0$ ILI~4.
%%675
\item{b)}~dANA SHTEJNEROVSKAYA SISTEMA TROEK~$S$ NAD $v$~OB�EKTAMI
$\set{x_1,~\ldots, x_v}$.
dOKAZHITE, CHTO SLEDUYUSHCHEE POSTROENIE PRIVODIT K SHTEJNEROVSKOJ
SISTEME TROEK~$S'$ NAD $2v+1$~OB�EKTAMI I KIRKMANOVSKOJ SISTEME TROEK~$K'$
PORYADKA $2v-2$: V $S'$ VHODYAT VSE TROJKI IZ $S$ PLYUS
\itemitem{i)} $\set{x_i, y_j, y_k}$, GDE $j+k\equiv i \pmod{v}$ I~$j<k$,
$1\le i, j, k\le v$;
\itemitem{ii)} $\set{x_i, y_j, z}$, GDE $2j\equiv i \pmod{v}$, $1\le i,
j\le v$.
v SISTEMU~$K'$ VHODYAT VSE TROJKI~$S'$, NE SODERZHASHCHIE $y_1$ I/ILI~$y_v$.

\item{c)} dANA KIRKMANOVSKAYA SISTEMA TROEK~$K$ NAD OB�EKTAMI
$\set{x_0, x_1,~\ldots, x_v}$, GDE~$v=2u$. dOKAZHITE, CHTO SLEDUYUSHCHEE
POSTROENIE PRIVODIT K SHTEJNEROVSKOJ SISTEME TROEK~$S'$ NAD
$2v+1$~OB�EKTAMI I KIRKMANOVSKOJ SISTEME TROEK~$K'$ PORYADKA~$2v-2$: V $S'$
VHODYAT VSE TROJKI IZ $K$ PLYUS
\itemitem{i)}~$\set{x_i, x_{(i+1)\bmod v}, y_{i+1}}$, $ 0\le i <v$;
\itemitem{ii)}~$\set{x_i, y_j, y_k}$,.$j+k\equiv 2i+1 \pmod{v-1}$, $1\le j <k-1 \le v-2$, $1\le i \le v-2$;
\itemitem{iii)}~$\set{x_i, y_j, y_v}$, $2j\equiv 2i+1 \pmod{v-1}$, $1\le j \le v-1$, $1\le i \le v-2$;
\itemitem{iv)}~$\set{x_0, y_{2j}, y_{2j+1}}$, $\set{x_{v-1}, y_{2j-1}, y_{2j}}$, $\set{x_v, y_j, y_{v-j}}$, $1\le j <u$;
\itemitem{v)}~$\set{x_v, y_u, y_v}$.
v $K'$ VHODYAT VSE TROJKI IZ $S'$, NE SODERZHASHCHIE $y_1$ I/ILI $y_{v-1}$.

\item{d)}~iSPOLXZUJTE PREDYDUSHCHIE REZULXTATY DLYA DOKAZATELXSTVA TOGO,
CHTO KIRKMANOVSKAYA SISTEMA TROEK PORYADKA~$v$ SUSHCHESTVUET PRI LYUBOM $v\ge0$,
IMEYUSHCHEM VID $6k$ ILI~$6k+4$, A SHTEJNEROVSKAYA SISTEMA TROEK NAD
$v$~OB�EKTAMI SUSHCHESTVUET PRI LYUBOM $v\ge1$, IMEYUSHCHEM VID~$6k+1$ ILI~$6k+3$.

\ex[m25] v TEKSTE OPISANO ISPOLXZOVANIE SHTEJNEROVSKOJ SISTEMY TROEK V
SVYAZI S VKLYUCHAYUSHCHIMI ZAPROSAMI; CHTOBY ISPOLXZOVATX IH I DLYA
BAZOVYH ZAPROSOV, ESTESTVENNO VVESTI SLEDUYUSHCHEE PONYATIE. \dfn{pOPOLNENNOJ
SISTEMOJ TROEK} PORYADKA~$v$ NAZYVAETSYA TAKAYA ORGANIZACIYA $2v$~OB�EKTOV
$\set{x_1,~\ldots, x_v, \bar x_1,~\ldots., \bar x_v}$ V TROJKI, CHTO KAZHDAYA
PARA OB�EKTOV VSTRECHAETSYA ROVNO V ODNOJ TROJKE; ISKLYUCHENIE SOSTAVLYAYUT PARY
DOPOLNITELXNYH |LEMENTOV~$\set{x_i, \bar x_i}$, NE VHODYASHCHIE NI V ODNU
TROJKU. nAPRIMER,
$$
\set{x_1, x_2, x_3},\quad, \set{x_1, \bar x_2, \bar x_3},\quad
\set{\bar x_1, x_2, \bar x_3}, \quad \set{\bar x_1, \bar x_2, x_3}
$$
ESTX POPOLNENNAYA SISTEMA TROEK PORYADKA~3.

dOKAZHITE, CHTO POPOLNENNAYA SISTEMA TROEK PORYADKA~$v$ SUSHCHESTVUET DLYA
LYUBOGO~$v\ge0$, NE IMEYUSHCHEGO VIDA~$3k+2$.

\ex[m23] v PRODOLZHENIE UPR.~11 POSTROJTE POPOLNENNUYU SISTEMU
\emph{CHETVEROK} PORYADKA~7.

\ex[m25] pOSTROJTE SISTEMU CHETVEROK, SODERZHASHCHUYU $v=4^n$~|LEMENTOV,
 ANALOGICHNUYU SISTEME TROEK IZ UPR.~9.

\ex[25] oBSUDITE ZADACHU UDALENIYA UZLOV IZ POCHTOVYH DEREVXEV, PODOBNYH
IZOBRAZHENNOMU NA RIS.~45.

%%676

\bye
