Indexul de căutare este o structură de date care conține informații despre documente și este utilizată în motoarele de căutare . Indexarea efectuată de un motor de căutare este procesul de colectare, sortare și stocare a datelor pentru a oferi o recuperare rapidă și precisă a informațiilor . Crearea indexului implică concepte interdisciplinare din lingvistică , psihologie cognitivă , matematică , informatică și fizică . Indexarea web se referă la procesul de indexare în contextul motoarelor de căutare concepute pentru a căuta pagini web.în internet.
Motoarele de căutare populare se concentrează pe indexarea integrală a documentelor scrise în limbi naturale [1] . La căutare pot participa și documente multimedia precum video și audio [2] și grafice [3] [4] .
Motoarele de metacăutare folosesc indici de la alte motoare de căutare și nu stochează un index local, în timp ce motoarele de căutare bazate pe pagini stocate în cache stochează atât indexul, cât și corpurile de text pentru o lungă perioadă de timp . Spre deosebire de indexurile full-text, serviciile de text parțial limitează adâncimea de indexare pentru a reduce dimensiunea indexului. Serviciile mai mari tind să se indexeze într-un anumit interval de timp datorită timpului și costului de procesare implicat, în timp ce motoarele de căutare bazate pe agenți construiesc indexul în timp real .
Scopul utilizării unui index este de a crește viteza de căutare a documentelor relevante pentru o interogare de căutare . Fără un index, un motor de căutare ar trebui să acceseze cu crawlere fiecare document din corpus, ceea ce ar necesita mult timp și putere de procesare. De exemplu, în timp ce un index de 10.000 de documente poate fi interogat în milisecunde, scanarea secvenţială a fiecărui cuvânt din 10.000 de documente mari poate dura ore. Memoria suplimentară alocată pentru stocarea indexului și creșterea timpului necesar pentru actualizarea indexului este compensată de reducerea timpului de căutare a informațiilor.
Atunci când proiectați un motor de căutare, trebuie luați în considerare următorii factori:
Factori de confluență Cum sunt incluse datele în index? Cum sunt adăugate cuvintele și sub-funcțiile la index în timpul parcurgerii corpus de text? Și mai multe crawler -uri pot funcționa asincron? Crawler-ul trebuie să verifice mai întâi dacă actualizează conținut vechi sau adaugă conținut nou. Îmbinarea indexului motorului de căutare este similară cu SQL Merge și cu alți algoritmi de îmbinare [5] . Metode de depozitare Cum se stochează datele indexate ? Adică determină tipul de informații stocate: comprimate sau filtrate. Dimensiunea indexului Câtă memorie de calculator este necesară pentru a menține un index. Viteza de căutare Cât de repede poate fi găsit un cuvânt într-un index inversat . Este important ca informatica sa compare viteza de gasire a unei inregistrari intr-o structura de date si viteza de actualizare/stergere a unui index. Depozitare Cum este stocat indexul pentru o perioadă lungă de timp [6] . toleranta la greseli Este important ca un serviciu de căutare să fie de încredere. Problemele de toleranță la erori includ problema corupției indexului, stabilirea dacă datele malformate asociate cu hardware defectuos, partiționarea și schemele bazate pe funcții hash și partiționare compusă [7] și replicarea pot fi tratate separat .Arhitectura motorului de căutare diferă în metodele de indexare și metodele de stocare a indexului, satisfăcând factorii . Indicii sunt de următoarele tipuri:
arbore de sufix Structurat figurativ ca un arbore , acceptă timpul de căutare liniar. Construit pe stocarea sufixelor de cuvinte. Arborele suportă hashing avansat, care este important pentru indexarea motoarelor de căutare [8] . Folosit pentru potrivirea modelelor în secvențele de ADN și grupare . Principalul dezavantaj este că stocarea unui cuvânt într-un arbore poate necesita spațiu dincolo de ceea ce este necesar pentru stocarea cuvântului în sine [9] . O reprezentare alternativă este o matrice de sufixe . Se consideră că necesită mai puțină memorie virtuală și acceptă comprimarea datelor prin sortare bloc . Index inversat Stocați o listă de apariții ale fiecărui termen de căutare [10] , de obicei sub formă de tabele hash sau un arbore binar [11] [12] . Index de citare Un depozit de citări sau hyperlinkuri între documente pentru a sprijini analiza citărilor, subiect de bibliometrie . N-gram Stocarea unor secvențe de lungimi de date pentru a sprijini alte tipuri de căutare sau analiză de text [13] . Matricea termenilor documentului Folosit în analiza semantică latentă (LSA) , stochează aparițiile cuvintelor din documente într- o matrice rară bidimensională .Una dintre sarcinile principale în proiectarea motoarelor de căutare este gestionarea proceselor de calcul secvenţial. Există situații în care este posibil să se creeze condiții de cursă și eșecuri coerente . De exemplu, un document nou este adăugat la un corpus și indexul trebuie actualizat, dar în același timp indexul trebuie să continue să răspundă la căutări. Aceasta este o coliziune între două sarcini concurente. Se crede că autorii sunt producători de informații, iar crawler-ul este consumatorul acestor informații, captând textul și stocându-l în cache (sau corpus). Indicele direct este consumatorul informațiilor produse de corpus, iar indicele inversat este consumatorul informațiilor produse de indicele direct. 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 care le caută sunt consumatorii. Problema este exacerbată de stocarea distribuită și procesarea distribuită. Pentru a scala cantități mari de informații indexate, un motor de căutare se poate baza pe o arhitectură de calcul distribuită , motorul de căutare constând din mai multe mașini care lucrează în comun. Acest lucru crește probabilitatea de ilogic și face mai dificilă menținerea unei arhitecturi paralele complet sincronizate, distribuite [14] .
Indexul înainte stochează o listă de cuvinte pentru fiecare document. Următoarea este o formă simplificată a unui index direct:
| Document | Cuvintele |
|---|---|
| Documentul 1 | a noastră, Tanya, plângând tare |
| Documentul 2 | a căzut, în, râu, minge |
| Documentul 3 | Taci, Tanechka, nu plânge, |
| Documentul 4 | nu, înec, în, râu, minge |
Motivul dezvoltării unui index direct este că este mai bine să stocați imediat cuvintele din spatele documentelor, deoarece acestea sunt analizate ulterior pentru a crea un index de căutare. Generarea de index înainte implică procesarea asincronă a sistemului care ocolește parțial blocajul de actualizare inversă a indexului [15] . Indicele direct este sortat pentru a fi convertit în cel inversat. Un index direct este în esență o listă de perechi de documente și cuvinte, sortate după document. Convertirea unui index direct într-unul inversat este doar o chestiune de sortare a perechilor de cuvinte. În acest sens, un index inversat este un index direct sortat în cuvinte.
Multe motoare de căutare folosesc un index inversat atunci când evaluează o interogare de căutare pentru a localiza rapid documentele care conțin cuvintele din interogare și apoi clasa documentele în funcție de relevanță. Deoarece indexul inversat stochează o listă de documente care conțin fiecare cuvânt, motorul de căutare poate folosi accesul direct pentru a găsi documentele asociate fiecărui cuvânt dintr-o interogare și pentru a le prelua rapid. Mai jos este o reprezentare simplificată a indicelui inversat:
| Cuvânt | Documentele |
|---|---|
| în | Documentul 2, Documentul 4 |
| tare | Documentul 1 |
| minge | Documentul 2, Documentul 4 |
| al nostru | Documentul 1 |
| nu | Documentul 3, Documentul 4 |
| strigăt | Documentul 1, Documentul 3 |
| râu | Documentul 2, Documentul 4 |
| Tanya | Documentul 1, Documentul 3 |
| Liniște | Documentul 3 |
| cădere brusca | Documentul 2 |
| îneca | Documentul 4 |
Un index inversat poate determina doar dacă un cuvânt există într-un anumit document, deoarece nu stochează nicio informație cu privire la frecvența și poziția cuvântului și, prin urmare, este considerat un index logic . Indexul inversat determină ce documente se potrivesc cu interogarea, dar nu evaluează documentele corespunzătoare. În unele cazuri, indexul include informații suplimentare, cum ar fi frecvența fiecărui cuvânt din fiecare document sau poziția unui cuvânt într-un document [16] . Informațiile despre poziția cuvântului permit algoritmului de căutare să identifice proximitatea cuvântului pentru a sprijini căutările de expresii. Frecvența poate fi folosită pentru a ajuta la clasarea documentelor pentru o interogare. Astfel de subiecte sunt în centrul cercetării privind regăsirea informațiilor.
Indicele inversat este reprezentat printr-o matrice rară, deoarece nu toate cuvintele sunt prezente în fiecare document. Indexul este similar cu matricea termenilor de document utilizată în LSA. Un index inversat poate fi considerat ca o formă de tabel hash. În unele cazuri, indexul este sub forma unui arbore binar, care necesită memorie suplimentară, dar poate reduce timpul de căutare. În indicii mari, arhitectura este de obicei reprezentată printr -un tabel hash distribuit [17] .
Indexul inversat este populat prin îmbinare sau restaurare. Arhitectura poate fi proiectată pentru a sprijini indexarea incrementală [18] [19] unde îmbinarea definește documentul sau documentele care urmează să fie adăugate sau actualizate și apoi parsează fiecare document în cuvinte. Pentru acuratețe tehnică, merge combină documentele nou indexate, aflate de obicei în memoria virtuală , cu un cache de index, care se află pe unul sau mai multe hard disk-uri ale computerului .
După parsare, indexatorul adaugă documentul specificat la lista de documente pentru cuvintele care se potrivesc. Într-un motor de căutare mai mare, procesul de găsire a fiecărui cuvânt pentru un index inversat poate consuma prea mult timp, așa că este de obicei împărțit în două părți:
Indicele inversat este numit astfel deoarece este inversul indicelui direct.
Construirea și menținerea unui index de căutare la scară largă necesită sarcini semnificative de memorie și procesare. Multe motoare de căutare folosesc o anumită formă de compresie pentru a reduce dimensiunea indicilor lor de pe disc [6] . Luați în considerare următorul scenariu pentru un motor de căutare pe Internet cu text integral:
Având în vedere acest scenariu, un index necomprimat pentru 2 miliarde de pagini web ar trebui să stocheze 500 de miliarde de intrări de cuvinte. 1 octet pe caracter sau 5 octeți pe cuvânt ar necesita doar 2500 gigaocteți de spațiu de memorie. Acesta este mai mult decât spațiul mediu liber pe disc a 2 computere personale. O arhitectură distribuită tolerantă la erori necesită și mai multă memorie. În funcție de metoda de compresie aleasă, indicele poate fi redus la o fracțiune din această dimensiune. Compensarea timpului și a puterii de procesare necesare pentru a efectua compresia și decompresia.
În special, proiectele de motoare de căutare pe scară largă includ costurile de stocare, precum și costurile cu energia pentru stocare.
Analiza (sau analiza ) a unui document implică analizarea documentului în componente (cuvinte) pentru inserarea în indecși direcți și inversați. Cuvintele găsite se numesc tokens , iar în contextul indexării motoarelor de căutare și al procesării limbajului natural, analizarea este adesea numită tokenizare (adică împărțirea în token-uri). Analiza este uneori numită marcaj parțial de vorbire , analiză morfologică, analiză de conținut, analiză de text, analiză de text, generare de acorduri , segmentare a vorbirii, analiză lexicală . Termenii „indexare”, „parsare” și „tokenizare” sunt folosiți interschimbabil în argou corporativ.
Procesarea limbajului natural este în mod constant cercetată și îmbunătățită. Tokenizarea are probleme la extragerea informațiilor necesare din documente pentru indexare pentru a susține căutări de calitate. Tokenizarea pentru indexare implică mai multe tehnologii, a căror implementare poate fi un secret comercial .
Spre deosebire de majoritatea oamenilor, computerele nu înțeleg structura unui document în limbaj natural și nu pot recunoaște automat cuvintele și propozițiile. Pentru un computer, un document este doar o secvență de octeți. Computerul nu „știe” că caracterul spațiu este separatorul de cuvinte din document. O persoană trebuie să programeze computerul pentru a determina ce este un singur cuvânt numit token. Un astfel de program este de obicei numit tokenizer sau parser (parser), precum și analizor lexical [21] . Unele motoare de căutare și alte programe de procesare a limbajului natural suportă programe specializate de analiză precum YACC sau Lex [22] .
În timpul tokenizării, analizatorul determină o secvență de caractere care reprezintă cuvinte și alte elemente, cum ar fi punctuația , reprezentate prin coduri numerice, dintre care unele sunt caractere de control neimprimabile . Analizatorul poate recunoaște unele obiecte, cum ar fi adrese de e-mail , numere de telefon și adrese URL . La recunoașterea fiecărui simbol, pot fi stocate unele caracteristici, de exemplu, limba sau codificarea, partea de vorbire, poziția, numărul propoziției, poziția în propoziție, lungimea și numărul rândului [21] .
Dacă motorul de căutare acceptă mai multe limbi, atunci primul pas în timpul tokenizării va fi determinarea limbii fiecărui document, deoarece mulți pași următori depind de aceasta (de exemplu, stabilirea și determinarea părții de vorbire). Recunoașterea limbii este procesul prin care un program de calculator încearcă să detecteze sau să clasifice automat limba unui document. Recunoașterea automată a limbajului este subiectul cercetărilor în prelucrarea limbajului natural [23] .
Dacă motorul de căutare acceptă mai multe formate de documente, atunci documentele trebuie pregătite pentru tokenizare. Problema este că unele formate de documente conțin informații de formatare în plus față de conținutul textual. De exemplu, documentele HTML conțin etichete HTML [24] . Dacă motorul de căutare ar ignora distincția dintre conținut și textul de marcare, informațiile străine ar fi incluse în index, rezultând rezultate slabe ale căutării. Analiza formatului - Identificarea și procesarea limbajului de marcare încorporat într-un document. Analiza formatului este denumită și analiză structurală, împărțirea etichetelor , normalizarea textului.
Sarcina de a analiza un format este complicată de complexitatea diferitelor formate de fișiere. Unele formate de fișiere sunt protejate de drepturi de proprietate intelectuală , există puține informații despre acestea, în timp ce altele, dimpotrivă, sunt bine documentate. Formate de fișiere comune, bine documentate, acceptate de motoarele de căutare [25] [26] :
Unele motoare de căutare acceptă fișiere care sunt stocate într-un format comprimat sau criptat [27] [28] [29] . Când lucrați cu un format comprimat, indexatorul decomprimă mai întâi documentul. Acest pas poate avea ca rezultat unul sau mai multe fișiere, fiecare dintre ele trebuie indexat separat. Sunt acceptate următoarele formate de fișiere comprimate:
Analiza formatului poate include tehnici de îmbunătățire a calității pentru a evita includerea informațiilor inutile în index. Conținutul poate gestiona informațiile de formatare pentru a include informații suplimentare. Exemple de abuz de formatare a documentelor în caz de spam web :
Unele motoare de căutare includ recunoașterea secțiunilor, identificând părțile principale ale unui document înainte de tokenizare. Nu toate documentele dintr-un corpus citesc ca o carte bine scrisă, împărțită în capitole și pagini. Unele documente de pe Internet, cum ar fi buletinele informative și rapoartele corporative, conțin conținut eronat și bare laterale cărora le lipsește conținutul principal. De exemplu, acest articol afișează linkuri către alte pagini web în meniul din stânga . Unele formate de fișiere, cum ar fi HTML sau PDF, permit afișarea conținutului în coloane. Deși conținutul documentului este prezentat pe ecran în zone diferite, textul sursă stochează aceste informații secvenţial. Cuvintele care apar secvenţial în textul sursă sunt indexate secvenţial, chiar dacă propoziţiile şi paragrafele apar în diferite părţi ale monitorului. Dacă motoarele de căutare indexează tot conținutul ca și cum ar fi conținutul principal al documentului, atunci calitatea indexului și a căutării poate fi degradată. Se remarcă două probleme principale:
Analizarea unei secțiuni poate solicita ca motorul de căutare să implementeze logica de redare a fiecărui document, adică o reprezentare abstractă a documentului în sine, și apoi să indexeze reprezentarea în locul documentului. De exemplu, uneori JavaScript este folosit pentru a afișa conținut pe o pagină web . Dacă motorul de căutare „nu vede” JavaScript, atunci paginile sunt indexate incorect, deoarece o parte din conținut nu este indexată. Având în vedere că unele motoare de căutare nu se deranjează cu problemele de randare, dezvoltatorii web încearcă să nu redea conținut prin JavaScript sau să folosească eticheta NoScript pentru a se asigura că pagina web este indexată corect [30] . În același timp, acest fapt poate fi folosit pentru a „face” indexatorul motorului de căutare „să vadă” diverse conținuturi ascunse.
Anumite documente conțin adesea metadate încorporate, cum ar fi autorul, cuvintele cheie , descrierea și limba. În paginile HTML, metaetichetele conțin cuvinte cheie care sunt incluse și în index. Tehnologiile anterioare de căutare pe Internet au indexat cuvintele cheie din metaetichetele de index direct și nu au analizat textul integral al documentului. La acel moment nu exista încă o indexare full-text, iar hardware -ul computerului nu putea suporta o astfel de tehnologie. Limbajul de marcare HTML a inclus inițial suport pentru meta-etichete pentru a indexa corect și ușor, fără utilizarea tokenizării [31] .
În timpul dezvoltării Internetului în anii 1990 , multe corporații au creat site-uri web corporative. Cuvintele cheie folosite pentru a descrie paginile web au devenit mai orientate spre marketing și concepute pentru a stimula vânzările prin plasarea unei pagini web în partea de sus a paginii cu rezultatele căutării pentru anumiți termeni de căutare. Faptul că aceste cuvinte cheie au fost determinate subiectiv a dus la spam, care a forțat motoarele de căutare să accepte indexarea full-text. Este posibil ca dezvoltatorii motoarelor de căutare să fi introdus multe „cuvinte cheie de marketing” în conținutul unei pagini web înainte de a o completa cu informații interesante și utile. Cu toate acestea, scopul proiectării site-urilor web a fost de a atrage clienți, astfel încât dezvoltatorii au fost interesați să includă mai mult conținut util pe site pentru a reține vizitatorii . În acest sens, indexarea full-text a fost mai obiectivă și a sporit calitatea rezultatelor motoarelor de căutare, ceea ce a contribuit la cercetarea tehnologiilor de indexare full-text.
În căutarea locală , soluțiile pot include metaetichete pentru a permite căutarea de către autori, deoarece motorul de căutare indexează conținutul din diferite fișiere al căror conținut nu este evident. Căutarea locală este mai mult sub controlul utilizatorului, în timp ce motoarele de căutare pe Internet ar trebui să se concentreze mai mult pe indexul textului integral.
| Căutarea de informații pe Internet | |
|---|---|
| Instrumente | |
| Indexarea | |
| Cerere | |
| rezultatele căutării | |
| Alte | |