Інвертований індекс

Інвертований індекс (англ. inverted index) — структура даних, в якій для кожного слова колекції документів у відповідному списку перераховані всі документи в колекції — в яких воно зустрілося. Інвертований індекс використовується для пошуку за текстами.

Є два варіанти інвертованого індексу:

• індекс, який містить лише список документів для кожного слова,
• індекс, додатково включає позицію слова в кожному документу[1]

Застосування

Опишемо, як вирішується завдання знаходження документів, в яких зустрічаються всі слова з пошукового запиту. При обробці однослівного пошукового запиту відповідь вже є в інвертованому індексі — достатньо взяти список, відповідний слову із запиту. При обробці багатослівної запиту беруться списки, відповідні кожному зі слів запиту і пересічні.

Зазвичай в пошукових системах після побудови за допомогою інвертованого індексу списку документів, що містять слова із запиту, йде ранжування документів зі списку. Інвертований індекс — це найпопулярніша структура даних, яка використовується в інформаційному пошуку.[2]

Приклад

Нехай у нас є корпус з трьох текстів ${\displaystyle T_{0}=}$"it is what it is", ${\displaystyle T_{1}=}$"what is it" та ${\displaystyle T_{2}=}$"it is a banana", тоді інвертований індекс буде виглядати наступним чином:

"a":      {2}
"banana": {2}
"is":     {0, 1, 2}
"it":     {0, 1, 2}
"what":   {0, 1}

Тут цифри позначають номери текстів, у яких зустрілося відповідне слово. Тоді відпрацювання пошукового "what is it" запиту дасть наступний результат ${\displaystyle \{0,1\}\cap \{0,1,2\}\cap \{0,1,2\}=\{0,1\}}$.

Особливості застосування в реальних пошукових системах

У списку входжень слова в документи крім id документів зазвичай також зазначаються фактори (TF-IDF, бінарний фактор: «потрапило слово в заголовок або не потрапило», інші фактори), які використовуються при ранжируванні. Індекс може будуватися не за всіма словоформам, а по лемам (по канонічних форм слів).

Стоп-слова можна виключити і не будувати для них індекс, вважаючи що кожне з них зустрічається майже у всіх документах корпусу. Для прискорення обчислення перетинань використовують евристику skip-pointer-ів. При обробці запитів, що містять багато слів, використовують функцію кворуму, яка пропускає на наступну стадію ранжирування частина документів, в яких зустрілися не всі слова із запиту.

Див. Також

• Пошуковий індекс

Посилання

1. Baeza-Yates, Ricardo; Ribeiro-Neto, Berthier (1999). Modern information retrieval (PDF). Редінг (Массачусетс): Addison-Wesley Longman. ISBN 0-201-39829-X.
2. Inverted files versus signature files for text indexing // ACM Transactions on Database Systems (TODS) : journal. — 1998. — P. 453—490. — DOI:10.1145/296854.277632.