Алгоритми роботи пошукових систем

Алгоритм прямого пошуку

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

Алгоритм зворотного пошуку (інвертованих індексів)

Для ефективного пошуку у великих обсягах даних всі потужні пошукові системи використовують алгоритм зворотних (інвертованих) індексів.

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

Це подібно до алфавітного покажчика слів в технічних або наукових книгах, де наводиться список використаних слів із зазначенням номерів сторінок, де вони зустрічаються.

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

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

Основним завданням математичної моделі будь-якої пошукової системи є пошук документів (сторінок) у своїй базі зворотних індексів відповідних до даного пошукового запиту і сортування цих знайдених документів у порядку зменшення їх релевантності до пошукового запиту. Використання простої логічної математичної моделі, яка знаходить документ, якщо в ньому зустрічається шукана фраза, не підходить, в силу величезної кількості таких документів.

Математична модель, яку використовується пошукові системи, відноситься до класу векторних математичних моделей. В ній використовується поняття ваги документа по відношенню до заданого користувачем запиту.

В базовій векторної математичної моделі вага документа за заданим пошуковим запитом обчислюється за двома основними параметрами: частотою, з якою зустрічається дане слово в аналізованому документі (TF - term frequency) і частотою, наскільки рідко це слово зустрічається у всіх інших документах колекції пошукової системи (IDF - inverse document frequency). Під колекцією пошукової системи розуміють всю сукупність документів, які відомі пошуковій системі. Перемноживши ці два параметри, отримується вага документа за заданим пошуковим запитом.

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


Comments