Старое доброе индексирование

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

В наши дни словом «индекс» (по-русски «указатель») обычно называют раздел в конце книги. В нем в определенном порядке (обычно по алфавиту) перечислены все понятия, которые могли бы заинтересовать читателя, и против каждого понятия указаны места (обычно номера страниц), где это понятие встречается. Так, индекс в книге о животных мог бы содержать запись «гепард 124, 156», которая означает, что слово «гепард» встречается на страницах 124 и 156 (забавы ради можете поискать в индексе к этой книге слово «индекс» - попадете как раз на эту страницу).

В поисковой системе индекс выполняет те же функции, что в книге. «Страницами» теперь являются веб-страницы во Всемирной паутине, и поисковая система присваивает каждой веб-странице уникальный номер. (Да, страниц уйма - на момент последнего подсчета их количество исчислялось многими миллиардами - но компьютеры отлично справляются с большими числами.) Пример на рисунке проясняет ситуацию. Представьте, что во Всемирной паутине всего-то и есть что три таких коротких страницы, и им присвоены номера 1, 2 и 3.

Чтобы построить индекс для этих трех веб-страниц, компьютер мог бы сначала составить список всех встречающихся на них слов, а затем отсортировать его по алфавиту. Назовем результат списком слов - в данном случае он будет выглядеть так: «а, cat, dog, mat, on, sat, stood, the, while». Затем компьютер перебрал бы все страницы и просмотрел бы все слова на каждой из них. Для каждого слова он записал бы номер текущей страницы против соответствующей позиции в списке слов. Окончательный результат показан на рисунке. Сразу видно, что слово «cat» встречается на страницах 1 и 3, но не на странице 2. А слово «while» есть только на странице 3.

Уже при таком элементарном подходе поисковая система может дать ответы на многие простые запросы. Пусть, например, вы вводите запрос cat. Поисковая система быстро найдет слово cat в списке слов. (Поскольку слова в списке расположены по алфавиту, компьютер может очень быстро найти нужное - точно так же, как человек находит слово в словаре.) Л найдя слово cat, система может вернуть связанный с ним список страниц - в данном случае 1 и 3. Современные поисковые системы красиво форматируют результаты, включая в каждый небольшой фрагмент найденной страницы, но мы на такие детали не будем обращать внимания, а сосредоточимся на том, как система узнает, какие номера страниц соответствуют введенному запросу.

Рассмотрим еще один простой пример - порядок обработки запроса dog. В данном случае система быстро находит в списке слово dog и возвращает номера страниц 2 и 3. А что, если запрос содержит несколько слов, например: cat dog? Это означает, что мы хотим найти все страницы, содержащие оба слова «cat» и «dog». При наличии уже имеющегося индекса поисковая система легко справится и с этой задачей. Сначала она найдет каждое слово порознь и определит, какие им соответствуют страницы. Получится 1,3 для «cat» и 2,3 для «dog». Затем компьютер может просмотреть оба списка результатов и найти номера страниц, встречающиеся как в одном, так и в другом. В данном случае страницы 1 и 2 отбрасываются, но страница 3 присутствует в обоих списках, поэтому окончательный список результатов содержит только страницу 3. Аналогичная стратегия работает для запросов, в которых больше двух слов. Например, в ответ на запрос cat the sat будут возвращены страницы 1 и 3, поскольку они встречаются в каждом из трех списков для слов «cat» (1, 3), «the» (1, 2, 3) и «sat» (1,3).

Пока что складывается впечатление, что построить поисковую систему довольно легко. Простейшая техника индексирования вроде бы отлично работает, даже для запросов с несколькими словами. Увы, как выясняется, такой примитивный подход для современных поисковых систем совершенно не годится. Причин несколько, но мы рассмотрим только одну проблему: фразовые запросы. Фразовым называется запрос, в котором мы ищем точную фразу, не довольствуясь тем, что слова встречаются в разных местах страницы. В большинстве поисковых систем фразовые запросы заключаются в кавычки. Например, запрос "cat sat" по смыслу сильно отличается от запроса cat sat.no запросу cat sat ищутся страницы, на которых где-то встречаются оба слова «cat» и «sat» в любом порядке. Напротив, по запросу "cat sat" ищутся страницы, на которых сразу после слова «cat» идет слово «sat». В нашем случае в ответ на запрос cat sat возвращаются страницы 1 и 3, а на запрос "cat sat" - только страница 1.

Как поисковая система могла бы эффективно обработать фразовый запрос? Вернемся к примеру "cat sat". Вроде бы на первом шаге можно было бы поступить так же, как при обработке запроса из двух слов cat sat: по списку слов построить список страниц, на которых встречается каждое слов; в данном случае мы получим 1,3 для «cat» и точно такой же список - 1,3 - для «sat». Но на этом поисковая система упирается в тупик. Она точно знает, что оба слова встречаются на страницах 1 и 3, но не может сказать, стоят ли они рядом и в нужном порядке. Можно было бы предположить, что в этот момент система просматривает исходные веб-страницы, чтобы понять, есть там нужная фраза или нет. Да, так поступить можно, но это было бы крайне неэффективно. Системе пришлось бы читать все содержимое каждой страницы, которая могла бы содержать фразу, а таких страниц может быть очень-очень много. Напомним, что в нашем примере всего-то три странички, а настоящая поисковая система должна правильно работать, когда страниц десятки миллиардов.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >