Інвертований індекс (англ. inverted index) — структура даних, в якій для кожного слова колекції документів у відповідному списку перераховані всі документи в колекції — в яких воно зустрілося. Інвертований індекс використовується для пошуку за текстами.
Є два варіанти інвертованого індексу:
- індекс, який містить лише список документів для кожного слова,
- індекс, додатково включає позицію слова в кожному документу
Застосування
Опишемо, як вирішується завдання знаходження документів, в яких зустрічаються всі слова з пошукового запиту. При обробці однослівного пошукового запиту відповідь вже є в інвертованому індексі — достатньо взяти список, відповідний слову із запиту. При обробці багатослівної запиту беруться списки, відповідні кожному зі слів запиту і пересічні.
Зазвичай в пошукових системах після побудови за допомогою інвертованого індексу списку документів, що містять слова із запиту, йде ранжування документів зі списку. Інвертований індекс — це найпопулярніша структура даних, яка використовується в інформаційному пошуку.
Приклад
Нехай у нас є корпус з трьох текстів "it is what it is"
, "what is it"
та "it is a banana"
, тоді інвертований індекс буде виглядати наступним чином:
"a": {2} "banana": {2} "is": {0, 1, 2} "it": {0, 1, 2} "what": {0, 1}
Тут цифри позначають номери текстів, у яких зустрілося відповідне слово. Тоді відпрацювання пошукового "what is it"
запиту дасть наступний результат .
Особливості застосування в реальних пошукових системах
У списку входжень слова в документи крім id документів зазвичай також зазначаються фактори (TF-IDF, бінарний фактор: «потрапило слово в заголовок або не потрапило», інші фактори), які використовуються при ранжируванні. Індекс може будуватися не за всіма (словоформам), а по лемам (по канонічних форм слів).
(Стоп-слова) можна виключити і не будувати для них індекс, вважаючи що кожне з них зустрічається майже у всіх документах корпусу. Для прискорення обчислення перетинань використовують евристику skip-pointer-ів. При обробці запитів, що містять багато слів, використовують функцію кворуму, яка пропускає на наступну стадію ранжирування частина документів, в яких зустрілися не всі слова із запиту.
Див. Також
Посилання
- Baeza-Yates, Ricardo; Ribeiro-Neto, Berthier (1999). Modern information retrieval (PDF). Редінг (Массачусетс): Addison-Wesley Longman. ISBN .
- Inverted files versus signature files for text indexing // ACM Transactions on Database Systems (TODS) : journal. — 1998. — P. 453—490. — DOI: .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет