Алгоритм пошукової системи в Інтернеті - індексація та канонізація

На сьогоднішньому занятті ми розглянемо індексацію та канонізацію документів в Інтернеті.

Індексація

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

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

Візьмемо, наприклад, сторінку про котів, завантажену з Вікіпедії. Індексатор отримує повний текст сторінки і повинен видалити непотрібні речі (наприклад, меню управління користувачем, рекламу, колонтитули, ...) і проаналізувати сторінку, щоб отримати чистий текст. Наприклад, текст міг би бути таким:

Свійський кіт (Felis silvestris f. catus) - одомашнена форма дикого кота, який був супутником людини протягом тисячоліть. Як і його дикий родич, він належить до підродини малих котячих і є типовим представником цієї групи. Він має легке і м'язисте тіло, чудово пристосоване до полювання, гострі кігті і зуби, а також відмінний зір, слух і нюх.

Витяг з [Вікіпедії] (http://cs.wikipedia.org/wiki/Ko%C4%8Dka_dom%C3%A1c%C3…).

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

Ідентифікатор документа	Слово	Позиція	Тип
1 кіт. 1 нормальний.
1 - внутрішній 2 - звичайний
1 - Феліс, 3 - Нормальний.
1 - це 7 - Стоп-слово.
1 - одомашнений, 8 - нормальний.

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

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

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

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

Канонізація документів

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

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

Кожна пошукова система поділяє дублікати на 2 великі категорії:

Натуральні дублікати

Вони створюються природною поведінкою Інтернету та його характеристиками.

Наприклад, URL-адреса http://mathematicator.cz, швидше за все, матиме той самий вміст, що й URL-адреса http://www.mathematicator.cz або http://mathematicator.cz/index.php, оскільки це стандартна поведінка сервера Apache (та Інтернету в цілому).

У разі виявлення природного дублювання пошукова система створює "канонічний набір", який являє собою групу сторінок, з яких пошукова система вибирає одного представника, що виділяється в пошуку. Якщо посилання веде на будь-яку сторінку з канонічного набору, її рейтинг автоматично передається головному представнику.

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

Дублі, що призводять до плагіату

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

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

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

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