Mis on ümberpööratud indeks? On üldtuntud fakt, et tõhusate otsingute tegemiseks peate looma indeksid. Mis vahe on indeksi ja ümberpööratud indeksi vahel ja kuidas saab üles ehitada ümberpööratud indeksi?


Vastus 1:

Inverteeritud indeks

Elastses otsingus kasutatakse ümberpööratud indeksiks kutsutavat struktuuri, mis on loodud väga kiireteks täistekstiotsingute võimaldamiseks. Ümberpööratud register koosneb loendist kõigist unikaalsetest sõnadest, mis esinevad suvalises dokumendis, ja iga sõna kohta, loendist dokumentidest, milles see ilmub.

Oletame näiteks, et meil on kaks dokumenti, millest igaühel on sisuväli, mis sisaldab järgmist:

  1. Kiire pruun rebane hüppas üle laisast koerast. Kiired pruunid rebased hüppavad suvel laisast koerast üle

Ümberpööratud indeksi loomiseks jaotame kõigepealt iga dokumendi sisu välja eraldi sõnadeks (mida me nimetame terminiteks või tähisteks), loome kõigi ainulaadsete terminite sorteeritud loendi ja seejärel loetleme, millises dokumendis iga termin ilmub. Tulemus näeb välja umbes selline:

Mõiste Doc_1 Doc_2
-------------------------
Kiire | | X
| X |
pruun | X | X
koer | X |
koerad | | X
rebane | X |
rebased | | X
sisse | | X
hüppas | X |
laisk | X | X
hüpe | | X
üle | X | X
kiire | X |
suvi | | X
| X |
------------------------

Kui tahame otsida kiiret pruuni, peame lihtsalt leidma dokumendid, milles kõik mõisted esinevad:

Mõiste Doc_1 Doc_2
-------------------------
pruun | X | X
kiire | X |
------------------------
Kokku | 2 | 1

Mõlemad dokumendid vastavad, kuid esimesel dokumendil on rohkem vasteid kui teisel. Kui rakendame naiivset sarnasuse algoritmi, mis lihtsalt loeb sobivate terminite arvu, siis võime öelda, et esimene dokument sobib paremini - on meie päringule asjakohasem kui teine ​​dokument.

Kuid meie praeguse ümberpööratud indeksiga on mõned probleemid:

  • Kiire ja kiire ilmuvad eraldi terminitena, samas kui kasutaja arvab neid arvatavasti olevat sama sõna. Fox ja rebased on üsna sarnased, nagu ka koer; Neil on sama juursõna.jumpe ja hüpe, ehkki mitte samast juursõnast, on tähenduses sarnased. Need on sünonüümid.

Eelmise registri korral ei vasta + Kiire + rebane otsing ühelegi dokumendile. (Pidage meeles, et eelnev + tähendab, et sõna peab olema olemas.) Päringu rahuldamiseks peavad nii termin Kiire kui ka rebane olema ühes ja samas dokumendis, kuid esimene dokument sisaldab kiiret rebane ja teine ​​dokument kiiret rebased.

Meie kasutaja võis mõistlikult eeldada, et mõlemad dokumendid vastavad päringule. Saame paremini hakkama.

Kui normaliseerime tingimused standardvormingusse, võime leida dokumente, mis sisaldavad termineid, mis pole küll täpselt samad, mida kasutaja nõudis, kuid on piisavalt sarnased, et endiselt asjakohased. Näiteks:

  • Kiiret saab väiketäheliseks muuta, et kiireks muutuda. Rebased võivad olla varrega - taandatud juurekujuliseks - rebaseks. Samamoodi võiksid koerad saada dog.jumped ja hüpe on sünonüümid ja neid saab indekseerida lihtsalt ühe mõiste hüppena.

Nüüd näeb register välja selline:

Mõiste Doc_1 Doc_2
-------------------------
pruun | X | X
koer | X | X
rebane | X | X
sisse | | X
hüpata | X | X
laisk | X | X
üle | X | X
kiire | X | X
suvi | | X
| X | X
------------------------

Kuid meid pole veel seal. Meie otsing + Quick + rebane ikkagi nurjuks, sest meil pole enam täpset terminit Quick meie indeksis. Kui aga rakendaksime oma päringustringi suhtes samu normaliseerimisreegleid, mida kasutasime sisukorral, muutuks see + quick + fox päringuks, mis vastaks mõlemale dokumendile!

Märkus: - see on väga oluline. Leiate ainult termineid, mis teie indeksis olemas on, nii et nii indekseeritud tekst kui ka päringustring tuleb normaliseerida samasse vormi.

Viide: lõplik juhend [2.x] | Elastne


Vastus 2:

Lihtsamalt öeldes on see hashmapi taoline andmestruktuur, mis suunab teid sõnalt dokumendile või veebilehele.

Vaatame probleemi teisest suunast. Teil on miljoneid dokumente või veebilehti või pilte, mida peame võib-olla hiljem uuesti hankima. Indekseerimise ja selle abil teabe hankimise kohta oma intuitsiooni abistamiseks lisan teile meelde, et olete varem näinud tagurpidi indeksit.

See on näide mõnest juhuslikust õpikust. Kui teil on vaja mõne teema kohta teavet, näiteks aktiveerimisenergiaid, avatakse register ja saate teada, kas see sõna on. Ümberpööratud register näitab teile leheküljenumbreid, kus seda sõna seletatakse suures osas tuhande lehena.

Sa näed! Kui peaksite tegema tavalist lineaarset otsingut, kulub sellele lehele jõudmiseks mitu tundi. Kuid nüüd oli see vaevalt sekundite küsimus.

Kuidas näeb välja tavaline register?

Muidugi, just selle vastas. See kaardistab teemakohase lehe numbri. Ja võite hõlpsalt öelda, et need pole otsingu ja teabe hankimise valdkonnas nii kasulikud. (Võib-olla on neil kuskil mujal õnne). Facebooki otsingu korral kasutatakse neid järjestamise (punktiarvestuse) eesmärkidel, nii et saate kõige asjakohasemad tulemused kõrgemale.

Kuidas luua ümberpööratud indeks? Ümberpööratud indeksi loomine mis tahes otsimissüsteemi säilitamiseks eeldab lehtede või dokumentide sõelumisel seeriatoimingute tegemist. Vaatame läbi oma otsingumootori konstrueerimise.

Tahan luua otsimootori kõigi oma arvutis olevate dokumentide jaoks. Ma tean, mida ma otsin. Nii et ma käivitan programmi, mis läbib kõvakettad kogu puu ja kogub soovitud lehed. Ma tean, et mp3-failidest ja JPEG-ist pole mulle midagi kasu. Ma palun oma programmil txt-, doc- ja pdf-failid alla laadida. Niisiis, kui olen dokumendi kätte saanud, asun järgmise sammu juurde.

1. Dokumendi toomineTöö on tõesti lihtne, kui saan tekstifaili (.txt). Aga kui see oli doc või pdf, siis pean nad nende teksti hankimiseks sõeluma, kasutades mõnda raamatukogu. Ütleme, et mul on teksti lugemine õnnestunud. Mis edasi?

2. Stop Words eemaldamineMõtke viimast lõiku. Millised olid olulised sõnad, mida me võib-olla otsime? "tekst", "teegid", "doc", "pdf", "tooma", "edukas". Kuid enamik teisi sõnu on lihtsalt raiskamine. Me tähistame kõige sagedamini esinevaid sõnu kui "peatussõnu" ja eemaldame need nii, et ma ei saaks indekseerida sõnu nagu "mina", "", "me", "on", "an". Regulaarsel kasutamisel on meil 500–1000 sõna. Kuid see võib olenevalt kasutamisest erineda.

3. Juur tüve juurdeSee tuleb tüvi. Nüüd, kui tahan otsida otsingut, on vaja näha dokumenti, millel on selle kohta teavet. Kuid dokumendis esinevat sõna nimetatakse "retrieve" asemel "retrieve". Mõlema sõna seostamiseks tükeldan igast loetud sõnast mingi osa, et saaksin "juursõna". Toode võib muutuda "retrieviks". Nii ka "väljavõtmine". Peame olema kindlad reeglites, mida kasutame sõnade tükeldamisel. Selle teostamiseks on olemas standardsed tööriistad, näiteks "Porteri tütar". Portreevarrega saate mängida siin: Porter Stemmer Online

4. Salvestage dokumentide ID-dKinnitage nüüd põhiülesanne - indekseerimine - valmis. Igal dokumendil on mul ainulaadne ID. Kuna puutun kokku peatumata sõnaga, mis on nüüd sirgunud, salvestan selle oma mällu kujul: retriev ==> docID104007

Kui ma saan sama sõna mõnes muus dokumendis, võin kirjutadatrreviev ==> docID104007retriev ==> docID154033

Kuid üsna varsti olen ma need ühendanud ühte nimekirjaretriev ==> docID104007 ja docID154033

Saan veelgi paremaks muuta, kirjutades mitu ajaliselt sõna ilmnes dokumendis, et saaksime tähtsamad dokumendid reastamisel reastada. retriev ==> docID104007 | 5 | & docID154033 | 2 |

5. Tingimused ühendage ja säilitageLõpuks salvestame need kettafailidesse. Tore, kui sorteerime indeksi sõnade põhjal kiireks ja lihtsaks hankimiseks.

See kõik vajab ilmselgelt konkreetseid andmestruktuure, mis teie tööd lihtsustavad.

Väljavõtete parandamiseks saame ehitada täiendavaid sekundaarseid indekseid. Edetabelimisega on seotud ka palju küsimusi.

Loodetavasti selgitas see teile, kuidas tagurpidi indekseid luuakse. Kui soovite rohkem lugeda, võite viidata Chris Manningu kirjutatud vingele raamatule Sissejuhatus teabeotsimisse, mis on veebis tasuta saadaval.