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

Перш за все про те, що таке індекс з точки зору пошуку інформації. Індекс (лат. Index - список, покажчик) - в загальному випадку упорядкований список зв'язків. Різні види індексів з давніх часів вживалися для полегшення пошуку інформації. Наприклад, зміст книги, де назва глави зв'язується з номером сторінки, де ця глава розташована.

Докладніший індекс - алфавітний покажчик, де вже реалізована зв'язок «один до багатьох»: кожному значимому терміну зіставлений список сторінок, де цей термін згадується. Наступна сходинка - конкорданс. Це словник, де кожному слову зіставлені «координати» входжень цього слова в текст. У загальному вигляді це і є те, що називається «інвертованим індексом», який використовують найбільш відомі пошукові системи.

Це два різновиди індексу, які реалізують зв'язку в різних напрямках. Уявімо собі колекцію текстових документів і повний список слів, знайдених в цих документах. Кожному документу в колекції присвоєно унікальний ідентифікатор DocID, кожному слову - унікальний ідентифікатор WordID.

Прямий індекс - таблиця зв'язків, де кожному DocID зіставлений повний список WordID входять в цей документ слів.

Інвертований індекс - таблиця зв'язків, де кожному WordID зіставлений список DocID, де це слово зустрічається.

Інвертований індекс ідеально пристосований для пошуку. З нього дуже просто береться список DocID документів, в які входить шукане слово. Якщо в запиті два слова, вибираємо два списки документів (по WordID обох слів). Потім вибираємо ті DocID, які входять в обидва ці списку і отримуємо підсумковий список DocID всіх документів, де зустрічаються обидва слова.

Спробуємо трохи ускладнити структуру індексів. У інвертований індекс додамо для кожного DocID число входжень слова в цей документ. І отримаємо самий грубий і примітивний інструмент визначення важливості слова в документі (чим частіше повторюється, тим важливіше). А в прямий індекс додамо для кожного WordID позицію всередині документа, з якої починається найкраща для цього слова цитата. Тепер у нас готове засіб вилучення сниппета для видачі документа по даному слову.

Природно, перш ніж користуватися цими інструментами, потрібно обробити (проіндексувати) всю колекцію документів. Для цього потрібно кожен документ розібрати на слова, попутно підрахувати число входжень кожного слова, зібрати словник і індекси. Якщо не підходити до важливості слова в тексті так грубо, а підрахувати важливість слів в тексті за законами Зіпфа. то ми отримаємо вже цілком придатний інструмент ранжирування знайдених текстів.

З опису індексу відразу зрозуміло, що це ідеальний інструмент для пошуку по окремо взятому слову. Завдання тривіальна: за ідентифікатором WordID вибрати з бази всі DocId документів, де це слово зустрічається. Ранжування теж не важко, якщо для кожного DocID в базі зберігається інформація про те, чи є це слово ключовим в тексті, або ж воно другорядне і не має прямого відношення до теми. Тобто, для кожної зв'язку «WordID - DocID» повинна бути підготовлена ​​інформація про релевантності документа цьому слову.

У разі запиту з двох і більше слів завдання різко ускладнюється. Процедура вибірки залишається досить простий, це стандартна задача в теорії баз даних: вибрати документи, в які входять всі слова запиту. Але з ранжируванням отриманого списку нас чекають труднощі. В цьому випадку потрібно враховувати релевантність документа вже не кожному зі слів, а саме даному поєднанню слів, інакше ранжування в багатьох випадках буде невдалим. Для з'ясування релевантності поєднанню слів як мінімум потрібно врахувати, як розподілені ці слова в тексті:

не підряд, але в одному пасажі,

в суміжних пасажах,

зустрічаються в різних частинах тексту.

Це самий грубий спосіб визначення релевантності. У першому випадку релевантність документа найбільша, у другому більш слабка, в третьому - вже сумнівна, в четвертому - мінімальна. Для більш точної оцінки в перших двох випадках необхідно враховувати, чи відповідає запиту порядок проходження слів, у другому і третьому варіанті врахувати відстань між словами (скільки сторонніх слів «вклинилося»).

Для забезпечення повноти пошуку потрібно врахувати форми слів запиту - отже, в індексі потрібно приводити слова до вихідної форми (наприклад, для іменників - однина, називний відмінок) і пов'язувати з усіма можливими словоформами. У той же час для пошуку по точним входженням потрібна можливість пошуку кожної словоформи. Це ускладнює структури даних пошукової системи, приводячи до безлічі індексів (зі зрозумілих причин тупий стемінг тут слабо допомагає).