Invertovaný index

Invertovaný index je datová struktura , ve které pro každé slovo ve sbírce dokumentů obsahuje odpovídající seznam všechny dokumenty ve sbírce, ve které se vyskytuje. K vyhledávání v textech se používá obrácený index.

Existují dvě varianty obráceného indexu:

rejstřík obsahující pouze seznam dokumentů pro každé slovo,
index, který volitelně zahrnuje pozici slova v každém dokumentu [1] .

Aplikace

Pojďme si popsat, jak řešíme problém hledání dokumentů, které obsahují všechna slova z vyhledávacího dotazu . Při zpracování jednoslovného vyhledávacího dotazu je odpověď již v obráceném indexu – stačí vzít seznam odpovídající danému slovu z dotazu. Při zpracování víceslovného dotazu se bere průsečík seznamů odpovídajících každému dotazovacímu slovu.

Ve vyhledávačích se obvykle po vytvoření seznamu dokumentů obsahujících slova z dotazu pomocí obráceného indexu dokumenty ze seznamu seřadí . Invertovaný index je nejoblíbenější datovou strukturou používanou při vyhledávání informací [2] .

Příklad

Mějme korpus tří textů a pak bude obrácený index vypadat takto: $T_{0}=$ "it is what it is" $T_{1}=$ "what is it" $T_{2}=$ "it is a banana"

"a": {2} "banán": {2} "je": {0, 1, 2} "it": {0, 1, 2} "co": {0, 1}

Čísla zde označují čísla textů, ve kterých se příslušné slovo vyskytuje. Poté zpracování vyhledávacího "what is it"dotazu poskytne následující výsledek . $\{0,1\}\cap \{0,1,2\}\cap \{0,1,2\}=\{0,1\}$

Funkce aplikace ve skutečných vyhledávačích

V seznamu výskytů slova v dokumentech jsou kromě id dokumentů obvykle uvedeny také faktory ( TF-IDF , binární faktor: „zda slovo trefilo nebo ne“, další faktory), které jsou použité v žebříčku. Index lze sestavit ne podle všech tvarů slov , ale podle lemmat (podle kanonických tvarů slov). Zastavovací slova lze vyloučit a nelze pro ně vytvořit index za předpokladu, že se každé z nich vyskytuje téměř ve všech dokumentech korpusu. Pro urychlení výpočtu průsečíků se používá heuristika skip-pointerů . Při zpracování požadavků obsahujících mnoho slov se využívá funkce quorum, která přeskočí do další fáze řazení části dokumentů, ve kterých nebyla nalezena všechna slova z požadavku.

Viz také

Hledat index

Literatura

Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Moderní vyhledávání informací . - Reading, Massachusetts : Addison-Wesley Longman, 1999. - 192 s. — ISBN 0-201-39829-X .
Justin Zobel, Alistair Moffat, Kotagiri Ramamohanarao. Invertované soubory versus soubory podpisů pro textové indexování // ACM Transactions on Database Systems ( TODS) : Journal. - 1998. - Ne. 23 . - S. 453 - 490 . - doi : 10.1145/296854.277632 .