Fordított index

A fordított index olyan adatstruktúra , amelyben a dokumentumgyűjtemény minden egyes szavához a megfelelő lista felsorolja a gyűjteményben található összes dokumentumot, amelyben előfordul. A fordított index a szövegek közötti keresésre szolgál.

A fordított indexnek két változata van:

egy index, amely minden szóhoz csak egy dokumentumlistát tartalmaz,
egy index, amely opcionálisan tartalmazza a szó pozícióját az egyes dokumentumokban [1] .

Alkalmazás

Leírjuk, hogyan oldjuk meg a keresési lekérdezésből származó összes szót tartalmazó dokumentumok megtalálásának problémáját . Egyszavas keresési lekérdezés feldolgozásakor a válasz már az invertált indexben van - csak vegye ki a szónak megfelelő listát a lekérdezésből. Többszavas lekérdezés feldolgozása során az egyes lekérdezési szavaknak megfelelő listák metszéspontját veszik fel.

Általában a keresőmotorokban , miután egy fordított indexet használó lekérdezésből származó szavakat tartalmazó dokumentumlistát állítanak össze, a listában szereplő dokumentumokat rangsorolják . Az invertált index az információkeresésben használt legnépszerűbb adatstruktúra [2] .

Példa

Legyen három szövegből álló korpuszunk és , akkor a fordított index így fog kinézni: $T_{0}=$ "it is what it is" $T_{1}=$ "what is it" $T_{2}=$ "it is a banana"

"a": {2} "banán": {2} "van": {0, 1, 2} "it": {0, 1, 2} "mi": {0, 1}

Itt a számok azoknak a szövegeknek a számait jelzik, amelyekben a megfelelő szó előfordul. Ezután a keresési "what is it"lekérdezés feldolgozása a következő eredményt adja . $\{0,1\}\cap \{0,1,2\}\cap \{0,1,2\}=\{0,1\}$

Alkalmazási funkciók valódi keresőmotorokban

A dokumentumokban előforduló szók listájában a dokumentumok azonosítója mellett általában olyan tényezőket is feltüntetnek ( TF-IDF , bináris faktor: „eltalálta-e a szó a címet vagy sem”, egyéb tényezők), amelyek használt a rangsorban. Az index nem minden szóalak szerint, hanem lemmák szerint (a szavak kanonikus alakjai szerint) felépíthető. A stopszavak kizárhatók és index nem építhető rájuk, feltételezve, hogy mindegyik előfordul a korpusz szinte minden dokumentumában. A metszéspontok kiszámításának felgyorsítása érdekében az átugrási mutatók heurisztikáját használják . A sok szót tartalmazó kérelmek feldolgozásakor a határozatképesség függvényt használjuk, amely a dokumentum azon részének rangsorolásának következő szakaszába ugrik, amelyben nem található meg a kérés összes szava.

Lásd még

Index keresése

Irodalom

Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Modern információkeresés . - Reading, Massachusetts : Addison-Wesley Longman, 1999. - 192 p. — ISBN 0-201-39829-X .
Justin Zobel, Alistair Moffat, Kotagiri Ramamohanarao. Invertált fájlok versus aláírási fájlok szöveges indexeléshez // ACM Tranzakciók adatbázis-rendszereken ( TODS) : Napló. - 1998. - Nem. 23 . - 453-490 o . - doi : 10.1145/296854.277632 .