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

11. 09. 2016

Obsah článku

На цьому уроці, присвяченому принципам роботи пошукової системи в Інтернеті, ми розберемося, як пошукова система сортує, описує та оцінює результати.

Результати сортування

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

Нехай маємо наступний приклад вхідного запиту:

[O (and) pejskovi (and) a (and) kočičce]

Так, саме в такому вигляді пошуковий сервер отримує оброблений запит від користувача і тепер чекає на повернення результату. Загалом у нас на це є менше "300 мс", так що швидко :)

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

Бочки, документи.
o
собака 5,19,23,42,46,58.
a
кицька 9,19,42,57,58,62,68,83

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

Спільними ідентифікаторами у всіх бочках є "19, 42, 58", тому майбутня сторінка результатів містить 3 позиції у певному, поки що невідомому порядку. Ми все ще дивимося на документи як на посвідчення особи, тому що це економить величезну кількість даних. Однак у результатах пошуку ми, як правило, хочемо показувати користувачеві не номери документів, а назву (заголовок), опис, URL-адресу та іншу інформацію про документ. Це забезпечується компонентом "дескриптор".

Дескриптор

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

Наприклад, зріз бази даних може мати такий вигляд:

Ідентифікатор	Назва	Етикетка	URL	Ранг
19	Йозеф Чапек: Казка про пса і кота ¦ Це було тоді, коли пес і кіт ще господарювали разом; вони мали свій будиночок біля лісу, жили там разом і хотіли робити все так, як роблять великі люди ¦ www.troglodytarium.cz/webz/axf/.../Capek_J_Pejsek_a_kocicka.htm	72
Про собаку і кота	42	Розповідь про собаку і кота	"Добре, - сказав собака, а кіт взяв мило і горщик з водою, і став на коліна на підлогу, і взяв собаку за щітку, і вимив собакою всю підлогу". Підлога була вся мокра	www.capek.narod.ru/povidani.htm
58	Як пес і кіт готували торт на свято	Завтра було свято у песика і день народження у кота. Діти знали про це і захотіли зробити собаці та коту сюрприз на день народження. Вони думали, що можна зробити для собаки і ¦ a.da.mek.sweb.cz/capek.j/dort.htm ¦ 34 ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦зробити для нього.

Розрахунок релевантності

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

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

Повернення результатів користувачеві

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

Висновок і розуміння семантики

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

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

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

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

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

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: