Илья Сегалович - человек, который придумал слово "Яндекс". В настоящий момент возглавляет в Яндексе отдел разработки поисковых систем.

1. Intro. Про поиск вообще

Основная задача поисковой системы — доставлять людям информацию, то есть соединять пользователей с нужными им документами. Причем общение между пользователем и поисковой системой происходит при помощи слов поискового запроса.

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

Известно несколько классов алгоритмов поиска. Подавляющее большинство из них требуют предварительного индексирования (алгоритмы инвертированных файлов, суффиксных деревьев, сигнатур). В случае прямого поиска индексирование не требуется — поиск производится в лоб, путем последовательного просмотра документов. Поисковая система Яндекса использует индекс, основанный на инвертированных файлах.

Инвертированный файл — концептуально довольно простое понятие, с которым сталкивался в обыденной жизни каждый из нас. Любой индекс базы данных по ключевому полю является формой инвертированного списка. Впрочем, такие списки не обязательно должны быть реализованы на компьютере: существуют бумажные конкордансы текстов российских классиков, то есть словари, в которых в алфавитном порядке перечислены слова, употребляемые писателями, а также указана частота их употребления.

Разумеется, работа с подобным индексом гораздо эффективнее, чем без него. Гораздо проще отыскать нужное слово в конкордансе и посмотреть по ссылкам, где оно употребляется, нежели перелистывать книгу в надежде это слово отыскать.

Конечно, подробный инвертированный индекс может быть довольно большим. Для уменьшения размеров файла обычно прибегают к двум очевидным приемам. Первый заключается в минимизации объема информации, которая хранится в инвертированном файле. Проще говоря, все лишнее удаляется — остается лишь то, что действительно необходимо для подавляющего большинства запросов. Второй прием заключается в указании относительных адресов: для каждой позиции запоминается не ее абсолютный адрес, а разница адресов между текущей и предыдущей позициями. Для пущей эффективности файл упаковывается (коды Голомба и прочие не очень жесткие алгоритмы упаковки), однако эффективные алгоритмы сжатия используются редко — сказывается и отсутствие особого эффекта от сжатия, да и процессорное время, расходуемое на распаковку данных, жалко.
Как правило, размер упакованного инвертированного файла составляет от 7 до 30 процентов от исходного текста.

Итак, чтобы что-то найти, поисковая система выполняет два почти независимых процесса: индексирование (получение документов, переработка, сохранение индекса) и поиск. Индекс устроен так, чтобы поиск работал максимально быстро и качественно. Находил все, что нужно, правильно ранжировал и выдавал максимум полезной информации, необходимой для процесса поиска.
Критичным с точки зрения экономики поисковых систем является, как ни странно, поиск, а не индексирование, так как для ответа на миллионы запросов в сутки, даже прибегая к невероятным ухищрениям, не обойтись без громоздких компьютерных комплексов. Причем, главный фактор, определяющий количество участвующих в поиске серверов, — именно поисковая нагрузка. Это следует иметь в виду при попытке понять всякие странности и неприятные особенности поисковых систем
Итак, что же происходит с документами при индексировании, а с запросами при их выполнении? Какой путь должны проделать друг к друг документы и запросы, чтобы в конечном счете нужный документ оказался в нужном списке, в том, в котором его ищут самым «нужным» запросом?

2. Индексирование. Путь документа
2.1 Скачивание

Индексирующую часть поисковиков принято называть роботом. Альфа и омега любого робота — модуль скачивания. Так как Сеть — это огромная паутина проводов, модули скачивания лучше запускать параллельно, обычно несколько сотен на одной машине, и одновременно скачивать из разных мест Сети разные документы. Скачивать документы по очереди бессмысленно.

Технически модуль скачивания может быть либо мультитредовым (Altavista Merkator), либо использовать асинхронный ввод-вывод (GoogleBot). В любом случае, разработчикам попутно приходится решать задачу многопоточного DNS-сервиса. В Яндексе реализована мультитредовая схема, скачивающие треды называются червями (worms), а их менеджер — погоняльщиком червей (wormboy).
Однако редкий сервер выдержит одновременное «поедание» тремя сотнями червей, поэтому в обязанности диспетчера может входить и слежение за тем, чтобы не перегружать чужой сервер и вообще вести себя вежливо.

Для скачивания робот использует протокол HTTP (иного просто нет, это полный синоним слова «веб»), поэтому многочисленные вопросы вебмастеров: «а что происходит с активными документами», «а индексирует ли ваш робот Server Side Includes?» — просто-напросто не имеют смысла. Почему?
Суть HTTP-протокола в следующем. Робот передает серверу строчку: «GET /path/document» и иные полезные строки, входящие в HTTP-запрос, а в ответ получает текстовый поток, в начале которого — несколько служебных строк HTTP-заголовка, выдаваемых веб-сервером (непосредственно или с помощью вашего скрипта), а затем уже и сам документ. Это все.

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

 

Лучшее - враг хорошего

Каждый вебмастер хочет, чтобы его сайт находился в списке результатов поиска по тематическому запросу как можно выше. И знание особенностей работы тех или иных поисковых систем позволяет вебмастеру оптимизировать свой сайт с тем, чтобы увеличить количество приходящих с поисковика пользователей. Однако здесь главное не перестараться. Можно так увлечься процессом оптимизации, что релевантность результатов поиска будет нарушена за счет присутствия в них спаммерских сайтов, «обманывающих» поисковую систему. Грань между «спаммерством» и «честной оптимизацией» провести трудно, и противоположные стороны — представители поисковиков и оптимизаторы — попытаются договориться о «правилах игры» в ноябре этого года на специальной конференции «Стратегия продвижения сайта в поисковых машинах». Одним из организаторов конференции является сайт searchengines.ru — пожалуй, самый полный и профессиональный российский ресурс, посвященный вопросам оптимизации.

Скачивание может быть организовано на разных принципах: «в ширину», по цитируемости, тематической локальности, по PageRank, — но цель одна — свести до минимума сетевой трафик при максимальной полноте. Поэтому эффективное скачивание — целая наука, которой посвящены центральные доклады на лучших международных конференциях (WWW Conference, VLDB и т. п.).
Тем не менее, у всех модулей скачивания всех искалок есть общие черты. Во-первых, они подчиняются правилам для роботов, записанным в файле robots.txt, который должен лежать в корне каждого сервера. Там вебмастер может указать желательные и нежелательные области доступа тем или иным роботам (или всем сразу). Контроль поведения роботов возможен и при помощи строчки <meta name=robots>, помещаемой в документ. Тогда робот будет подчиняться тому, что там написано «по-документно».
Однако кроме фильтров, устанавливаемых вебмастером, у роботов есть и свои собственные фильтры.
Во-первых, многие роботы опасаются индексировать так называемые динамические документы, формально относя к таковым и документы, содержащие вопросительный знак в URL. Понятно, что это всего лишь «эвристика», предположение роботов, не более того. Ведь в руках вебмастера есть способы передавать параметры, скрывая CGI-механизм (то есть без вопросительного знака и пар имя_параметра = значение_параметра), например при помощи PATH_INFO или mod_rewrite. И наоборот, масса серверов, использующих CGI-интерфейс, годами выдают исключительно стабильное и «статичное» содержание. Заметьте, что многие роботы (например, Яндекс) на эту эвристику не обращают внимания и индексируют «динамические страницы» так же, как и «статические».

Во-вторых, каждый робот поддерживает свой собственный список ресурсов: наказанных за спам или отфильтрованных по какой-нибудь технической причине. Об этом мы поговорим чуть позже, а пока лишь подчеркнем, что поисковики, как правило, не берут на себя функцию общественного цензора и не фильтруют «плохое» или «противозаконное» содержание. В лучшем случае они предоставляет подобную фильтрацию как специальный сервис. И здесь мы вплотную подходим к этической проблеме, слишком глубокой для обсуждения в короткой статье. Сформулирую лишь «возможный принцип»: качество поиска информации не связано с качеством самой информации. Поисковик — своего рода зеркало, отвечающее только за качество процесса отражения, но не предметов, которые в нем отражаются.

2.2 Отбрасывание повторов

За передним краем — модулем скачивания — стоят другие модули, которые помогают первым уменьшать трафик, повышать покрытие и обрабатывать такие ресурсы, которые с наибольшей вероятностью «пришла пора скачать», или же те, которые следует чаще обновлять для поддержания высокого качества поиска.

Прежде всего, это модули хранения URL и ссылок. Они позволяют не скачивать повторно один и тот же URL, обмениваться списком новых URL между разными серверами скачивания или считать полезные метрики цитируемости документов.

Далее. Модули отслеживания дубликатов решают задачу неиндексирования дубликатов, то есть позволяют избегать резкого замусоривания базы повторами. Заметьте, что для корректного сравнения нужно сначала определить кодировку документа, ведь 30 процентов серверов ее не сообщают. Этим занимается специальный модуль определения языка и кодировки, после отработки которого документу может быть приписана кодировка и язык, или же он может быть отфильтрован (еще один вид фильтра!), если робот посчитает данную кодировку или язык «чужими» для себя.

Простейшая проверка на повтор содержимого состоит в вычислении контрольной суммы всех слов текста и в тесте базы данных на ее присутствие. Кстати, сразу после получения сигнала о точном повторе червь Яндекса получает команду не ходить по ссылкам от дубликата: логика такой фильтрации проста и очень популярна у всех роботов. Она построена на естественном предположении, что точно повторяющиеся документы содержат набор ссылок на точно такие же документы, какие уже получены по ссылкам оригинала.

Отдельно стоит проблема учета «слегка измененных» документов (обычно это делается по набору характерных слов или контрольных сумм), а также выявления зеркал серверов. Зеркала представляют собой специальный случай: их не надо индексировать, хотя время от времени надо проверять, не «расклеились» ли они.