Index inversat

Un index inversat este o structură de date în care, pentru fiecare cuvânt dintr-o colecție de documente, lista corespunzătoare listează toate documentele din colecția în care apare. Indexul inversat este folosit pentru a căuta prin texte.

Există două variante ale indexului inversat:

un index care conține doar o listă de documente pentru fiecare cuvânt,
un index care include opțional poziția cuvântului în fiecare document [1] .

Aplicație

Să descriem cum rezolvăm problema găsirii documentelor care conțin toate cuvintele din interogarea de căutare . Când procesați o interogare de căutare cu un singur cuvânt, răspunsul este deja în indexul inversat - trebuie doar să luați lista corespunzătoare cuvântului din interogare. La procesarea unei interogări cu mai multe cuvinte, este luată intersecția listelor corespunzătoare fiecăruia dintre cuvintele de interogare.

De obicei, în motoarele de căutare , după construirea unei liste de documente care conțin cuvinte dintr-o interogare folosind un index inversat, documentele din listă sunt clasate . Indicele inversat este cea mai populară structură de date utilizată în regăsirea informațiilor [2] .

Exemplu

Să avem un corpus de trei texte și apoi indexul inversat va arăta astfel: $T_{0}=$ "it is what it is" $T_{1}=$ "what is it" $T_{2}=$ "it is a banana"

„a”: {2} „banana”: {2} „este”: {0, 1, 2} „it”: {0, 1, 2} „ce”: {0, 1}

Aici numerele indică numerele textelor în care apare cuvântul corespunzător. Apoi, procesarea "what is it"interogării de căutare va da următorul rezultat . $\{0,1\}\cap \{0,1,2\}\cap \{0,1,2\}=\{0,1\}$

Caracteristicile aplicației în motoarele de căutare reale

În lista de apariții ale unui cuvânt în documente, pe lângă id-ul documentelor, sunt de obicei indicați și factori ( TF-IDF , factor binar: „dacă cuvântul atinge titlul sau nu”, alți factori), care sunt folosit în clasament. Indexul poate fi construit nu după toate formele de cuvinte , ci după leme (după formele canonice ale cuvintelor). Cuvintele stop pot fi excluse și nu se construiește un index pentru ele, presupunând că fiecare dintre ele apare în aproape toate documentele din corpus. Pentru a accelera calculul intersecțiilor, se utilizează euristicile indicatoarelor de salt . La procesarea cererilor care conțin multe cuvinte se folosește funcția de cvorum, care trece la următoarea etapă de clasare a părții de documente în care nu au fost găsite toate cuvintele din cerere.

Vezi și

Index de cautare

Literatură

Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Găsirea modernă a informațiilor . - Reading, Massachusetts : Addison-Wesley Longman, 1999. - 192 p. — ISBN 0-201-39829-X .
Justin Zobel, Alistair Moffat, Kotagiri Ramamohanarao. Fișiere inversate versus fișiere de semnătură pentru indexarea textului // Tranzacții ACM pe sisteme de baze de date ( TODS) : Journal. - 1998. - Nr. 23 . - P. 453 - 490 . - doi : 10.1145/296854.277632 .