Інвертований індекс (англ. Inverted index) - структура даних. в якій для кожного слова колекції документів у відповідному списку перераховані всі документи в колекції, в яких воно зустрілося. Інвертований індекс використовується для пошуку за текстами.
Є два варіанти інвертованого індексу:
- індекс, який містить лише список документів для кожного слова,
- індекс, що додатково включає позицію слова в кожному документі [1].
Опишемо, як вирішується завдання знаходження документів, в яких зустрічаються всі слова з пошукового запиту. При обробці однословного пошукового запиту відповідь вже є в інвертованому індексі - достатньо взяти список, відповідний слову із запиту. При обробці багатослівної запиту беруться списки, що відповідають кожному з слів запиту і пересічні.
Зазвичай в пошукових системах після побудови за допомогою інвертованого індексу списку документів, що містять слова із запиту, йде ранжування документів зі списку. Інвертований індекс - це найпопулярніша структура даних, яка використовується в інформаційному пошуку [2].
Нехай у нас є корпус з трьох текстів T 0 = => "it is what it is". T 1 = => "what is it" і T 2 = => "it is a banana". тоді інвертований індекс буде виглядати наступним чином:
Тут цифри позначають номери текстів, в яких зустрілося відповідне слово. Тоді відпрацювання пошукового "what is it" запиту дасть наступний результат <0. 1> ∩ <0. 1. 2> ∩ <0. 1. 2> = <0. 1>\ Cap \\ cap \ = \>.
Особливості застосування в реальних пошукових системах
У списку входжень слова в документи крім id документів зазвичай також зазначаються фактори (TF-IDF. Бінарний фактор: «потрапило слово в заголовок або не потрапило», інші чинники), які використовуються при ранжируванні. Індекс може будуватися не за всіма словоформам. а по Лемма (по канонічних форм слів). Стоп-слова можна виключити і не будувати для них індекс, вважаючи що кожне з них зустрічається майже у всіх документах корпусу. Для прискорення обчислення перетинів використовують евристику skip-pointer-ів. При обробці запитів, що містять багато слів, використовують функцію кворуму, яка пропускає на наступну стадію ранжирування частина документів, в яких зустрілися не всі слова з запиту.