Алгоритм пошукової системи в інтернеті - Дерева і СтопЛід

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

Знайти і відсортувати мільярди документів - завдання не з легких. Лише Google потребує 300 000 веб-серверів, щоб впоратися з цим завданням за кілька годин. Фактично, пошук вашого запиту відбувається задовго до того, як ви його задасте. Google вже зберігає в своїй пам'яті результати пошуку, які ви будете шукати в найближчі дні.

Архітектура пошукової системи

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

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

Введення запиту

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

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

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

Розглянемо наступний запит:

"O pejskovi a kočičce"

Цей запит буде перетворено у бінарне дерево, яке відображає його смислову суть:

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

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

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

Перезапис у бінарне дерево

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

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

Методи розшифровки запитів

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

Візьмемо наступний запит: "Про собаку і кота", його розшифровка в найпростішому вигляді виглядає наступним чином:

"O (and) pejskovi (and) a (and) kočičce"

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

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

["pejskovi (and) * (and) kočičce"]

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

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

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

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

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

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

За англійським запитом "I love her" погано спроектований інфлектор відмінюватиме слово "games" як, наприклад, "games, gaming, gaming room, ...", тому необхідно також індексувати навколишні слова як словосполучення і виконувати відмінювання лише у знайомих ситуаціях, або використовувати іншу процедуру (тут часто вступають у дію фонетичні алгоритми).

Останнім кроком є відправка готового дерева на пошукові сервери Бази, де і буде відбуватися власне пошук стовбурів - це вже тема наступного розділу.

Jan Barášek   Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu:

Kontakt