Интернет, компьютеры, софт и прочий Hi-Tech

Алгоритмы поисковых систем

Д.С. — Прочел статью Ильи Сегаловича «Как работают поисковые системы» («Мир Интернет», №10, 2002). Хоть и старая, но очень интересная. Выписал из нее самые интересные для себя моменты. Чтобы не потерять этот конспект, публикую его на своем сайте. Может и еще кому-нибудь пригодится.

Итак, на сегодняшний день существует четыре класса поисковых алгоритмов:

1. прямой поиск;
2. алгоритм инвертированных файлов;
3. алгоритм суффиксных деревьев;
4. алгоритм сигнатур.

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

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

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

1. слова;
2. номера документов, в которые входят эти слова;
3. число употреблений данных слов в данных документах.

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

Математические модели классической теории информационного поиска принято делить на три семейства:

1. теоретико-множественные модели. К ним относятся булевская модель, расширенная булевская модель и модель нечетких множеств;
2. алгебраические модели. К ним относятся векторная модель, обобщенная векторная модель, латентно-семантическая и нейросетевая модели;
3. вероятностные модели.

Классическая булевская модель проста — документ считается найденным, если в нем найдено искомое слов. Недостаток этой модели — ее непригодность для ранжирования найденных документов. Недостатки булевской модели были учтены в векторной модели.

Векторная модель (TF*IDF) сопоставляет каждому документу определенный «вес» по отношению к искомому термину. Вес вычисляется как частота термина в данном документе (TF) умноженный на «редкость» этого термина в коллекции документов (IDF). Документы выдачи ранжируются согласно их весам по отношению к запросам.

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

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

Вероятностные модели не получили широкого распространения на практике несмотря на свою теоретическую привлекательность.

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

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

Для оценки качества поиска применяются два параметра:

• точность — доля релевантных документов в выдаче поисковой системы;
• полнота — доля найденных релевантных документов в общем числе релевантных документов.

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

Помимо задачи собственно поиска поисковым системам приходится также решать смежные задачи:

• классификация;
• маршрутизация;
• фильтрация;
• аннотирование найденных документов;
• кластеризация результатов;
• расширение и сужение запросов;
• обратная связь (отклик пользователей на полученный результат поиска);
• «запросо-зависимое» аннотирование;
• поисковый интерфейс;
• языки запросов.

Кроме того, перед поисковиками стоит класс задач, решаемых лингвистическими методами. Это:

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

Поиск в Вебе имеет дополнительную специфику по сравнению с поиском по другим коллекциям документов. Помимо анализа собственно текстов при ранжировании приходится учитывать «внетекстовые» (off-page) факторы, такие как

• положение документа на сайте;
• посещаемость сайтов;
• авторитетность источников;
• частота обновления сайтов;
• цитируемость страниц и авторов.

Некоторые специфические проблемы поиска в Вебе:

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

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

Одним из основных внетекстовых факторов ранжирования при поиске в Вебе является ссылочная популярность. К алгоритмам подсчета этой популярности относятся, среди прочих, PageRank и HITS. Первый применяется очень широко. Второй не используется на практике из-за вычислительной дороговизны.

PageRank вместе с поиском по лексике ссылок, ведущих на страницы, позволил резко повысить качество поиска Google.

Ссылочная популярность используется также в следующих задачах:

• определение порядка обхода документов;
• ранжирование поиска по текстам ссылок
• и др.

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

Поисковики заинтересованы в росте поисковой базы. Дело в том что около 30% всех поисков приходится на «редкие» запросы, т.е. на такие, по которым находится менее 100 документов. Поэтому, чем больше документов находятся в индексе, тем выше становится качество поиска.

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

• эшелонирование;
• прюнинг.

Эшелонирование заключается в разделении поисковой базы на более и менее релевантные части. Поиск осуществляется сначала в первой части базы, а затем, если найдено недостаточно, по второй части базы.

Прюнинг (pruning) заключается в отсечении (нерассмотрении) документов, которые на основании каких-то допущений считаются заведомо нерелевантными запросу. «Статический» прюнинг заключается в том, что на основании каких-то допущений из индекса исключаются документы, которые никогда не будут найдены.

16.03.2011

Предыдущие публикации:

Последнее редактирование: 2011-03-16 14:14:54

Метки материала: алгоритмы, алгоритмы поисковых систем, it, информационные технологии, поисковики

2 комментария

16.03.2011 16:29:13

#

 dima

Илье Сегаловичу браво Я всего лишь кратко пересказал его труд.

Оставьте, пожалуйста, свой комментарий к публикации

Представиться как

Антибот:

Просьба не постить мусор. Если вы хотите потестить xBB, воспользуйтесь кнопкой предварительного просмотра на панели инструментов xBBEditor-а.