Indexarea în motoarele de căutare reprezintă procesul de colectare, analizare și stocare a datelor pentru a facilita recuperarea rapidă și precisă a informațiilor. Designul indexării încorporează concepte interdisciplinare din lingvistică, psihologie cognitivă, matematică, știința calculatoarelor și informatică. Un nume alternativ pentru proces, în contextul motoarelor de căutare concepute pentru a găsi pagini web pe Internet, este indexarea web.
Motoarele de căutare populare se concentrează pe indexarea integrală a documentelor online, în limbaj natural. Tipuri de media, cum ar fi imagini, înregistrări video sau audio, și grafice Verificat în decembrie 2006 pot fi, de asemenea, căutate.
Meta-motoarele de căutare reutilizează indexurile altor servicii fără a stoca un index propriu, spre deosebire de motoarele de căutare bazate pe cache, care păstrează permanent indexul împreună cu corpusul. Spre deosebire de indexurile pe text complet, serviciile pe text parțial limitează profunzimea indexării pentru a reduce dimensiunea indexului. Serviciile mai mari efectuează, de obicei, indexarea la intervale prestabilite, din cauza costurilor de timp și procesare, în timp ce motoarele de căutare bazate pe agenți indexează în timp real.
Indexarea Scopul stocării unui index este de a optimiza viteza și performanța în găsirea documentelor relevante pentru o interogare de căutare. Fără un index, motorul de căutare ar scana fiecare document din corpus, ceea ce ar necesita timp și putere de calcul considerabile. De exemplu, în timp ce un index de 10.000 de documente poate fi interogat în milisecunde, o scanare secvențială a fiecărui cuvânt din 10.000 de documente mari poate dura ore. Spațiul de stocare suplimentar pe calculator necesar pentru stocarea indexului, precum și creșterea considerabilă a timpului necesar pentru ca o actualizare să aibă loc, sunt compensate cu timpul economisit în timpul regăsirii informațiilor. Factorii de proiectare a indicelui Cei mai importanți factorii în proiectarea arhitecturii unui motor de căutare includ:
Factorii de unire Modul în care datele sunt adăugate în index, cum sunt incluse cuvintele sau caracteristicile subiectului în timpul parcurgerii corpusului de text și dacă mai mulți indexatori pot opera asincron. Indexatorul trebuie mai întâi să determine dacă va actualiza conținutul existent sau va adăuga unul nou. Parcurgerea se corelează de obicei cu politica de colectare a datelor. Unirea indexului motorului de căutare este similară ca concept cu comanda SQL Merge și cu alți algoritmi de unire. Tehnici de stocare Cum se stochează datele de index, adică dacă informațiile ar trebui să fie date comprimate sau filtrate. Dimensiunea indexului Cât de mult spațiu de stocare este necesar pentru a suporta indexul. Viteza de căutare Cât de repede poate fi găsit un cuvânt în indexul inversat. Viteza de găsire a unei intrări într-o structură de date, comparată cu viteza de actualizare sau eliminare, este un punct central al științei calculatoarelor. Întreținere Cum este întreținut indicele în timp. Toleranță la erori Cât de important este ca serviciul să fie fiabil (de încredere). Problemele includ tratarea corupției indexului, determinarea dacă datele proaste pot fi tratate izolat, tratarea hardware-ului defectuos, partiționarea și scheme precum partiționarea bazată pe hash sau compusă, precum și replicarea.
Structuri de date indexate Arhitecturile motoarelor de căutare diferă în funcție de metodele de indexare și de strategiile de stocare a indexului, adaptându-se la diverși factori de design.
Arborele de sufixe Structurat figurativ ca un arbore, acceptă căutarea liniară în timp. Construit prin stocarea sufixelor cuvintelor. Arborele sufixului este un tip de . Trie-urile acceptă , care este important pentru indexarea motoarelor de căutare. Folosit pentru căutarea modelelor în secvențele de ADN și în grupare. Un dezavantaj major este că stocarea unui cuvânt în arbore poate necesita spațiu dincolo de cel necesar pentru stocarea cuvântului în sine.. O reprezentare alternativă este o , care se consideră că necesită mai puțină memorie virtuală și acceptă compresia datelor, cum ar fi algoritmul . Index inversat Stochează o listă de apariții ale fiecărui criteriu de căutare atomică, de obicei sub forma unui tabel hash sau a unui arbore binar. Index de citare Stochează citări sau hyperlinkuri între documente pentru a sprijini analiza citațiilor, un subiect de bibliometrie. Index -gram Stochează secvențe de lungime a datelor pentru a sprijini alte tipuri de extragere sau extragere de text.Google Ngram Datasets for sale at LDC Catalog Matrice document-termen Folosită în analiza semantică latentă, stochează aparițiile cuvintelor din documente într-o bidimensională.
Provocări în paralelism O provocare majoră în proiectarea motoarelor de căutare este gestionarea proceselor de calcul în serie. Există multe oportunități pentru și greșeli coerente. De exemplu, un document nou este adăugat în corpus și indexul trebuie actualizat dar, în același timp, indexul trebuie să continue să răspundă la interogările de căutare. Aceasta este o coliziune între două sarcini concurente. Considerând că autorii sunt producători de informații, iar un crawler web este consumatorul acestor informații, preluând textul și stochându-l într-un cache (sau corpus). Indicele direct (indexul forward) este consumatorul de informații produse de corpus, iar indicele inversat este consumatorul de informații produse de indicele direcr. Acesta este denumit în mod obișnuit modelul producător-consumator. Indexatorul este producătorul de informații care pot fi căutate, iar utilizatorii sunt consumatorii care trebuie să caute. Provocarea este amplificată atunci când se lucrează cu stocare distribuită și procesare distribuită. Într-un efort de a scala cu cantități mai mari de informații indexate, arhitectura motorului de căutare poate implica calcul distribuit, în care motorul de căutare este format din mai multe mașini care funcționează în acord unele cu altele. Acest lucru crește posibilitățile de incoerență și face mai dificilă menținerea unei arhitecturi paralele, distribuite și sincronizate complet.
Indexuri inverse Multe motoare de căutare încorporează un index inversat atunci când evaluează o interogare de căutare pentru a localiza rapid documentele care conțin cuvintele dintr-o interogare și apoi să claseze aceste documente în funcție de relevanță. Deoarece indexul inversat stochează o listă a documentelor care conțin fiecare cuvânt, motorul de căutare poate folosi accesul direct pentru a găsi documentele asociate fiecărui cuvânt din interogare pentru a regăsi rapid documentele care se potrivesc.
Aceasta este o ilustrare simplificată a unui index inversat: +Index inversat Cuvânt Documente cel Documentul 1, Documentul 3, Documentul 4, Documentul 5, Documentul 7 vacă Documentul 2, Documentul 3, Documentul 4 spune Documentul 5 moo Documentul 7 Acest index poate determina doar dacă un cuvânt există într-un anumit document, deoarece nu stochează informații cu privire la frecvența și poziția cuvântului; de aceea este considerat a fi un index boolean. Un astfel de index determină ce documente corespund unei interogări, dar nu clasifică documentele potrivite. În unele modele, indexul include informații suplimentare, cum ar fi frecvența fiecărui cuvânt din fiecare document sau pozițiile unui cuvânt în fiecare document. Informațiile de poziție permit algoritmului de căutare să identifice proximitatea cuvântului pentru a sprijini căutarea expresiilor; frecvența poate fi folosită pentru a ajuta la clasificarea relevanței documentelor pentru interogare. Astfel de subiecte reprezintă centrul de cercetare al regăsării informațiilor.
Indicele inversat este o matrice dispersată, deoarece nu toate cuvintele sunt prezente în fiecare document. Pentru a reduce cerințele de memorie de stocare a computerului, aceasta este stocată diferit de o matrice bidimensională. Indicele este similar cu termenul de matrice de document folosit de analiza semantică latentă. Indicele inversat poate fi considerat o formă de tabel hash. În unele cazuri, indexul este o formă de arbore binar, care necesită stocare suplimentară, dar poate reduce timpul de căutare. În indici (indexuri) mai mari, arhitectura este de obicei un tabel hash distribuit.
Implementarea căutării cu expresii utilizând un index inversat Pentru căutarea expresiilor, se folosește o formă specializată a unui index inversat numit index pozițional. Un index de poziție nu stochează doar ID-ul documentului care conține indicativul, ci și poziția exactă (pozițiile) jetonului în document în lista de posturi. Aparițiile expresiei specificate în interogare sunt preluate prin navigarea în aceste liste de postări și identificarea indecșilor la care termenii doriți apar în ordinea așteptată (la fel ca și ordinea în frază). Deci, dacă căutăm apariția expresiei „Prima vrăjitoare”, am:
Se preia lista de posturi (ul) pentru „prima” și „vrăjitoare” Se identifică prima dată când „vrăjitoare” apare după „prima” Se verifică dacă această apariție este imediat după apariția lui „prima”. Dacă nu, se continuă cu următoarea apariție a lui „prima”.
(posting list-urile) pot fi navigate utilizând o căutare binară pentru a minimiza complexitatea de timp a acestei proceduri. Fuziunea indexului Indexul inversat este actualizat fie prin îmbinare, fie prin reconstrucție. Spre deosebire de îmbinare, reconstrucția presupune ștergerea prealabilă a conținutului existent. Arhitectura poate fi concepută pentru a permite indexarea incrementală,Tomasic, A., et al.: Incremental Updates of Inverted Lists for Text Document Retrieval. Short Version of Stanford University Computer Science Technical Note STAN-CS-TN-93-1, decembrie, 1993. unde o îmbinare identifică documentul sau documentele care urmează să fie adăugate sau actualizate și apoi analizează fiecare document în cuvinte. Pentru o acuratețe tehnică, îmbinarea combină documentele recent indexate, care sunt de obicei stocate în memoria virtuală, cu cache-ul de index aflat pe unul sau mai multe hard disk-uri ale computerului.
După analizare, indexatorul adaugă documentul referențiat la lista de documente pentru cuvintele corespunzătoare. În cazul unui motor de căutare mai mare, procesul de căutare al fiecărui cuvânt în indexul inversat (pentru a raporta apariția acestuia într-un document) poate consuma prea mult timp. Prin urmare, acest proces este de obicei împărțit în două etape: dezvoltarea unui index direct și un proces care sortează conținutul indexului direct în indexul inversat. Indexul inversat poartă acest nume deoarece reprezintă o inversare a indexului direct.
Indicele direct (forward index) Indicele direct stochează o listă de cuvinte pentru fiecare document. Următoarea este o formă simplificată a indicelui direct: +Indice direct Document Cuvinte Documentul 1 vaca, face, moo Documentul 2 pisica, și, pălăria Documentul 3 farfuria, a, fugit, cu, lingura Motivul din spatele dezvoltării unui indice direct este că, pe măsură ce documentele sunt analizate, este mai bine să stocați intermediar cuvintele per document. Delimitarea permite procesarea asincronă a sistemului, care ocolește parțial blocajul de actualizare a indicelui inversat. Indicele direct este sortat pentru a-l transforma într-un index inversat. Indicele direct este, în esență, o listă de perechi formată dintr-un document și un cuvânt, colazionate de document. Convertirea indicelui direct într-un index inversat este doar o chestiune de sortare a perechilor după cuvinte. În acest sens, indexul inversat este un indice direct sortat după cuvinte.
Comprimare