Как работает поисковая машина

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

Аналогично, поисковая машина состоит из двух частей: так называемого робота (или паука), который обходит серверы Сети и формирует базу данных поискового механизма.

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

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

Следует отметить, что, отрабатывая конкретный запрос пользователя, поисковая система оперирует именно внутренними ресурсами (а не пускается в путешествие по Сети, как часто полагают неискушенные пользователи), а внутренние ресурсы, естественно, ограниченны. Несмотря на то что база данных поисковой машины постоянно обновляется, поисковая машина не может проиндексировать все Web-документы: их число слишком велико. Поэтому всегда существует вероятность, что искомый ресурс просто неизвестен конкретной поисковой системе.

Эту мысль наглядно иллюстрирует рис. 25. Эллипс 1 ограничивает множество всех Web-документов, существующих на некоторый момент времени, эллипс 2 - все документы, которые проиндексированы данной поисковой машиной, а эллипс 3 - искомые документы. Таким образом, найти с помощью данной поисковой машины можно лишь ту часть искомых документов, которые ею проиндексированы.

Рис. 29Схема, поясняющая возможности поиска

Проблема недостаточности полноты поиска состоит не только в ограниченности внутренних ресурсов поисковика, но и в том, что скорость робота ограниченна, а количество новых Web-документов постоянно растет. Увеличение внутренних ресурсов поисковой машины не может полностью решить проблему, поскольку скорость обхода ресурсов роботом конечна.

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

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

Очевидно, что конкорданс (словарь) гораздо компактнее исходных текстов произведений и найти в нем нужное слово намного проще, нежели перелистывать книгу в надежде наткнуться на нужное слово.

Построение индекса

Схема построения индекса показана на рис. 30. Сетевые агенты, или роботы-пауки, "ползают" по Сети, анализируют содержимое Web-страниц и собирают информацию о том, что и на какой странице было обнаружено.

Рис. 30 Роботы-пауки просматривают информационное наполнение Web-страниц и создают базу, на основе которой производится поиск

При нахождении очередной HTML-страницы большинство поисковых систем фиксируют слова, картинки, ссылки и другие элементы (в разных поисковых системах по-разному), содержащиеся на ней. Причем при отслеживании слов на странице фиксируется не только их наличие, но и местоположение, т.е. где эти слова находятся: в заголовке (title), подзаголовках (subtitles), в метатэгах (meta tags)или в других местах. При этом обычно фиксируются значимые слова, а союзы и междометия типа "а", "но" и "или" игнорируются. Метатэги позволяют владельцам страниц определить ключевые слова и тематику, по которым индексируется страница. Это может быть актуально в случае, когда ключевые слова имеют несколько значений. Метатэги могут сориентировать поисковую систему при выборе из нескольких значений слова на единственно правильное. Однако метатэги работают надежно только в том случае, когда заполняются честными владельцами сайта. Недобросовестные владельцы Web-сайтов помещают в свои метатэги наиболее популярные в Сети слова, не имеющие ничего общего с темой сайта. В результате посетители попадают на незапрашиваемые сайты, повышая тем самым их рейтинг. Именно поэтому многие современные поисковики либо игнорируют метатэги, либо считают их дополнительными по отношению к тексту страницы. Каждый робот поддерживает свой список ресурсов, наказанных за недобросовестную рекламу.

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

Слова в любом тексте в информационном отношении весьма неравнозначны. И дело не только в том, что текст содержит много вспомогательных элементов предлогов или артиклей (напр., в англоязычных текстах). Часто для сокращения объема индексных регистров и ускорения самого процесса индексации вводятся так называемые стоп-листы. В эти стоп-листывносятся слова, которые не несут смысловой нагрузки (например, предлоги или некоторые вводные слова). Но при использовании стоп-листов необходима определенная осторожность. Например, занеся в стоп-лист, неопределенный артикль английского языка "а", можно заблокировать нахождение ссылки на "витамин А".

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

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

Современная поисковая система содержит в себе несколько подсистем.

§ web-агенты. Осуществляют поиск серверов, извлекают оттуда документы и передают их системе обработки.

§ Система обработки. Индексирует полученные документы, используя синтаксический разбор и стоп-листы (где, помимо прочего, содержатся все стандартные операторы и атрибуты HTML).

§ Система поиска. Воспринимает запрос от системы обслуживания, осуществляет поиск в индексных файлах, формирует список найденных ссылок на документы.

§ Система обслуживания. Принимает запросы поиска от клиентов, преобразует их, направляет системе поиска, работающей с индексными файлами, возвращает результат поиска клиенту. Система в некоторых случаях может осуществлять поиск в пределах списка найденных ссылок на основе уточняющего запроса клиента (например, recall в системе altavista). Задание системе обслуживания передается WEB-клиентом в виде строки, присоединенной к URL, наример, http://altavista.com/cgi-bin/query?pg=q&what=web&fmt=/&q=plug+%26+play, где в поле поиска было записано plug & play)

Следует иметь в виду, что работа web-агентов и системы поиска напрямую независимы. WEB-агенты (роботы) работают постоянно, вне зависимости от поступающих запросов. Их задача - выявление новых информационных серверов, новых документов или новых версий уже существующих документов. Под документом здесь подразумевается HTML-, текстовый или nntp-документ. WEB-агенты имеют некоторый базовый список зарегистрированных серверов, с которых начинается просмотр. Этот список постоянно расширяется. При просмотре документов очередного сервера выявляются URL и по ним производится дополнительный поиск. Таким образом, WEB-агенты осуществляют обход дерева ссылок. Каждый новый или обновленный документ передается системе обработки. Роботы могут в качестве побочного продукта выявлять разорванные гиперсвязи, способствовать построению зеркальных серверов.

Поиск по индексу

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

Текст, в пределах которого проверяется действие логических операторов, называется единицей поиска. Это может быть предложение, абзац или весь документ. В разных поисковых системах могут использоваться различные единицы поиска. Например, можно искать документы, в которых два слова - "электрический" и "счетчик" - находятся одновременно в пределах предложения или в пределах всего документа. Соответственно поиск в пределах предложения возможен для тех систем, которые имеют в индексе подробный адрес.

Поисковые машины- это роботизированные системы (Search Engines). Специальная программа-робот, которую называют паук (spider) или ползун (crawler), постоянно обходит Сеть в поисках новой информации, которую она вносит в базу данных. База данных содержит URL-адреса и проиндексированную информацию, связанную с этими адресами. Важными показателями качества поисковой машины являются объем базы данных (количество документов), скорость обхода Сети (с этим связана скорость обновления информации в базе данных), алгоритм индексации (только по ключевым словам Web-страницы или по всему тексту, с учетом морфологии или без него, с поиском по тэгам HTML - заголовкам, ссылкам, подписям к изображениям и др.), а также дополнительные возможности (расширенный поиск, поиск похожих документов, ограничение области поиска), удобный пользовательский интерфейс и справочная система.

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

Таблица 4

	Яндекс	Rambler	Апорт!	AltaVista	Google
Зона поиска,объем базы данных	Русская часть Интернета. Поиск по страницам сайтов из раздела каталога, по регионам. Специальный поиск по новостям, товарам, картинкам.	Русская часть Интернета.	Русская часть Интернета. Специализи-рованный поиск по новостям, товарам, картинкам, MP3	Специализи-рованный поиск по новостям, товарам, развлечениям, аудио (MP3) и видео.	Специализи-рованный поиск по университе-там США, Apple, Linux, BSD
Объем базы на начало 2001 года	Более 31 миллионов документов	Более 12 миллионов документов	Более 14 миллионов документов	Более 250 миллионов документов	1,25 миллиарда страниц
Тип индексации	полнотекстовая индексация	полнотекстовая индексация	полнотекстовая индексация и индексация по ссылкам	полнотекстовая индексация	полнотекстовая индексация и индексация по ссылкам
Наличие дополнительных сервисов	Система объединяет поисковую машину и каталог, а также ряд дополнительных проектов (Закладки.Ру, Народ.Ру, система интеллектуального выбора товаров, CY и пр.).	Система объединяет поисковую машину и рейтинг-классификатор Top100	Система объединяет поисковую машину, каталог и дополнительные сервисы (интернет-покупки и др.)	Система объединяет поисковую машину, каталог и ряд дополнительных сервисов (хостинг, регистрация доменного имени, перевод и др.)	Система объединяет поисковую машину и каталог, содержащий 15 разделов и 1,5 миллиона Web-страниц.
Синтаксис языка поиска
логическое И	пробел или & (в пределах предложения)&&(в пределах документа)	AND, &, пробел между словамипо умолчанию	И, AND, &,+, пробел между словами по умолчанию	AND, & (только при сложном поиске)	по умолчанию для всех слов поиска
логическое ИЛИ	|	OR, |	ИЛИ, OR, |	OR (по умолчанию при простом поиске), | (только при сложном поиске)	OR
бинарный оператор И-НЕ	~ (в пределах предложения) ~ ~ (в пределах документа)	не используется	заменяется префиксным оператором "-" (AND - пробел по умолчанию); НЕ, NOT	AND NOT, ! (только при сложном поиске)	заменяется префиксным оператором "-"
префиксы обязательных (+) и запрещенных (-) слов	+, -	не используются	+, -	+, - (только при простом поиске)	+, -
группирование слов	( )	( )	( )	( )	не используется
расстояние между ключевыми словами при поиске	/(n m) - в словах, &&/(n m) - в предложениях (- назад, + вперед)	при расширенном поиске - выдача документов только с минимальным расстоянием между словами	сл2(...), с2(...), w2(...), [2,...] (- назад, + вперед)	NEAR (в пределах10 слов, только при сложном поиске)	не используется
поиск фразы	" "	нет	" ", ' '	" "	" ", ' ', -..-
символы замены части слова	нет	*, ? (замена любого символа)	* (только в конце слова)	*	нет
ограничение по языку документа	выбор: любой, кириллица, латиница	выбор: любой, русский, английский	выбор: русский, английский	выбор из 25 языков	выбор из 25 языков
морфология	все склонения и спряжения по умолчанию, ! (поиск точной словоформы)	# (все формы слов), @ (однокоренные слова)	! (указание нормальной формы)	нет	нет
поиск по датам	есть	есть	есть	есть	нет
ограничение поиска по полям	Поиск в заголовках, ссылках, мета-тэгах, файлах и подписях картинок, в текстах ссылок, в названиях скриптов, объектов и апплетов. Поиск похожих документов. Сужение поиска на выбранные сайты.	Поиск в заголовках, адресах, названиях документов (только при расширенном поиске). Поиск похожих документов.	Поиск в заголовках, ссылках, мета-тэгах, файлах и подписях картинок, в адресах, в текстах ссылок. Сужение поиска на выбранные сайты.	Поиск в заголовках, ссылках, мета-тэгах, файлах и подписях картинок, в адресах, в текстах ссылок, в названиях скриптов, объектов и апплетов	Поиск в ссылках и Поиск похожих документов. Сужение поиска на выбранные сайты.
Возможности расширенной формы, качество помощи
настройка расширенной формы	настройка словарного фильтра, настройки по дате, по сайту, ссылке, изображению, специальному объекту	по документу, дате, режимам AND, OR, расстоянию между словами, усечению слова	по документу, заголовку, изображению,дате, 5 разделам (сайты, МР3, картинки, товары, новости)	по булевскому вопроснику, дате, по сайту, ссылке, изображению, тексту и пр.	ограничения по сайту, языку, ссылкам
настройка вывода результатов	задание числа результатов на странице, всех элементов формы вывода	задание числа результатов на странице, формы вывода	задание формы выдачи	задание числа результатов на странице, всех элементов формы вывода	задание числа результатов на странице, всех элементов формы вывода
ранжирование результатов поиска	сортировка по релевантности или дате	сортировка по релевантности или дате	по популярности сайта	по терминам, указанным в SORT	по цитируемости (ссылок на страницу с других страниц)
итеративный поиск (в результатах поиска)	Да. Выполняется с помощью установки флажка	Да. Выполняется с помощью переключателя области поиска	Да. Выполняется с помощью установки флажка	Да. Выполняется с помощью SORT BY	нет
качество раздела помощи	имеется детальное описание языка запросов, таблица синтаксиса и раздел по поиску в категориях	краткий раздел HELP	подробный справочник по языку запросов, есть много русских синонимов для основных операторов	самый большой из рассмотренных в этой таблице учебник on-line по языку запросов	очень ограниченный раздел HELP
семейный фильтр	есть	нет	нет	есть	нет

Синтаксис языка запросовв разных поисковых системах может отличаться, обычно в справочных данных на поисковом сервере приводится информация о синтаксисе запросов. В качестве примера в табл. приводится синтаксис языка запросов, принятый в поисковой машине Yandex.

Таблица 5. Синтаксис языка запросов при строгом поиске

Синтаксис	Что означает оператор	Пример запроса
Пробел или &	Логическое И (в пределах предложения)	Лечебная физкультура
&&	Логическое И (в пределах документа)	Рецепты && (плавленый сыр)
I	Логическое ИЛИ	Фото I фотография I снимок I фотоизображение
+	Обязательное наличие слова в найденном документе (работает также в применении к стоп-словам)	+Быть или +не быть
()	Группирование слов	(Технология I изготовление) (сыра I творога)
~	Оператор И НЕ (в пределах документа)	Банки ~ закон
~~или~	Оператор И НЕ (в пределах документа)	Путеводитель по Парижу ~~ (агентство I тур)
/(n m)	Расстояние в словах (~ назад +вперед)	Поставщики /2 кофе музыкальное /(-2 4) образование вакансии ~/+1 студентов
<< <<	Поиск фразы	<<Красная шапочка>> (эквивалентно красная /+1 шапочка)
&&/(n m)	Расстояние в предложениях (-назад +вперед)	Банк && /1 налоги

Многие поисковые системы имеют режим "расширенный поиск". Например, в наиболее популярной на сегодня поисковой системе Google (www.google.com) этот режим дает возможность искать документы на определенном языке, измененные в определенное время или представленные в определенном формате, например Word-документ или презентацию Power Point.

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

Несмотря на то что человек человеку всегда лучше объяснит, что же он ищет, нельзя сказать, что современные поисковые машины - это примитивные системы, которые, кроме как найти некоторую последовательность символов, ничего не могут. Напротив, существуют, например, поисковые системы позволяющие решать проблему различных словоформ. А это далеко не тривиальная задача. Если мы ищем документ по ключевому слову "стол", то, вероятно, документ, содержащий фразу "столы для кухни" - это то, что нам нужно. Однако "стол" и "столы" для системы, осуществляющей формальное сравнение, - это разные слова. Поиск, учитывающий словоизменения, называется морфологическим поиском.