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

На сьогоднішньому уроці ми обговоримо бочки даних, їх структуру, StopSlovas і наостанок опишемо кроулери.

Data Barrels

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

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

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

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

Будова ствола

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

Приклад дуже маленької бочки на три сторінки:

[1:5,8,12,27,30;5:1,3,6;12:4,8,10]

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

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

StopLead

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

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

Прикладом пошуку за допомогою StopSlovy є запит "Прага 1".

Пошукова система видає лише "3 020 000 результатів" за цим запитом. Однак в реальності таких об'єктів набагато більше. Однак, з міркувань ефективності, обшуки проводяться не у всіх з них.

Шукайте варіанти доступу за допомогою StopSlovy:

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

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

Гусеничний (робот, також павук)

Краулер - це програма, яка систематично сканує Інтернет і відстежує, які слова з'являються на яких сторінках, а також збирає допоміжну інформацію (також звану метаінформацією). Сканер зазвичай працює на багатьох серверах, оскільки сканування Інтернету є вимогливим до пропускної здатності мережі, і тому багато сторінок повинні скануватися одночасно. За оцінками Google, одночасно сканується до 30 000 сторінок у будь-який час.

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

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

Наприклад, List таким чином сканує лише кілька рівнів посилань на кожному сайті, в той час як Google намагається сканувати весь сайт, включаючи неважливі документи, що робить його найбільш всеосяжною пошуковою системою в Інтернеті. Робот також намагається оцінити сторінку під час сканування і обчислює її "ранг", який є числовим представленням того, наскільки важлива сторінка в Інтернеті. Раніше Google використовував показник PageRank, який має діапазон від 0 до 10. Google розраховує PageRank 10 тільки для себе і таких сайтів, як microsoft.com або w3c.org. Зараз вона розраховує вартість по-іншому (штучний інтелект та векторна математика).

Seznam.cz має найвищий показник PageRank у Чеської Республіки, який дорівнює 7, і має великий вплив на те, як часто робот відвідує сторінку та як високо вона знаходиться в пошуковій видачі. Ранги розраховуються тільки за зворотними посиланнями, що вказують на потрібну сторінку.

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

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