\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