![]() Интернет, компьютеры, софт и прочий Hi-Tech | ||||||
Избранные докиМетки (все метки)hi tech, internet, it, software, интернет, информационные технологии, ит, по, программное обеспечение, софт
Подписаться через RSS2Email.ru
|
Алгоритмы поисковых систем![]() Д.С. — Прочел статью Ильи Сегаловича «Как работают поисковые системы» («Мир Интернет», №10, 2002). Хоть и старая, но очень интересная. Выписал из нее самые интересные для себя моменты. Чтобы не потерять этот конспект, публикую его на своем сайте. Может и еще кому-нибудь пригодится. Итак, на сегодняшний день существует четыре класса поисковых алгоритмов:
Прямой поиск осуществляется при помощи последовательного просмотра документов. В документах ищутся подстроки, совпадающие с запросом. Остальные три класса алгоритмов требуют построения поискового индекса. Инвертированный файл представляет собой упорядоченный по алфавиту список слов, для каждого из которых перечислены все документы, в которых это слово встречается. Алгоритмы инвертированных файлов заключаются в отыскании слов запроса и выдаче списка соответствующих им документов. Инвертированный файл может содержать дополнительные сведения о словах. Например, число его вхождений в документы, позиции, с которыми оно входит в документы, соответствующие сниппеты и т.п. все это требует дополнительного дискового пространства. В классической теории информационного поиска основной схемой считается следующая: в индексе хранятся
Методы суффиксных деревьев и сигнатур не получили широкого распространения. В известных поисковых системах они не применяются. Математические модели классической теории информационного поиска принято делить на три семейства:
Классическая булевская модель проста — документ считается найденным, если в нем найдено искомое слов. Недостаток этой модели — ее непригодность для ранжирования найденных документов. Недостатки булевской модели были учтены в векторной модели. Векторная модель (TF*IDF) сопоставляет каждому документу определенный «вес» по отношению к искомому термину. Вес вычисляется как частота термина в данном документе (TF) умноженный на «редкость» этого термина в коллекции документов (IDF). Документы выдачи ранжируются согласно их весам по отношению к запросам. В вероятностных моделях для каждого найденного документа вычисляется вероятность, с которой он может заинтересовать пользователя. Ранжирование осуществляется соответственно этим вероятностям. Вероятностная модель предполагает наличие первоначального набора документов, чья релевантность запросу уже известна. Для каждого следующего документа вероятность оказаться релевантным вычисляется по соотношению входящих в него терминов и терминов в релевантном наборе документов. Вероятностные модели не получили широкого распространения на практике несмотря на свою теоретическую привлекательность. Продвинутые (т.н. «альтернативные») модели каждого из семейств моделей поиска позволяют находить документы «по смыслу» даже когда они не содержат слов запроса. Пожалуй самой популярной из таких моделей является так называемое латентно-семантическое индексирование, относящееся к семейству алгебраических моделей. Однако эта модель не получила большого распространения для поиска. Чаще применяется для классификации документов, разделения их коллекций и т.п. Для оценки качества поиска применяются два параметра:
Оценка обоих параметров производится экспертами. Поскольку их мнения могут сильно различаться, оценка качества поиска не отличается особой точностью. Помимо задачи собственно поиска поисковым системам приходится также решать смежные задачи:
Кроме того, перед поисковиками стоит класс задач, решаемых лингвистическими методами. Это:
Поиск в Вебе имеет дополнительную специфику по сравнению с поиском по другим коллекциям документов. Помимо анализа собственно текстов при ранжировании приходится учитывать «внетекстовые» (off-page) факторы, такие как
Некоторые специфические проблемы поиска в Вебе:
Последнее часто подменяется приемом под названием «иллюзия свежести», который заключается в более частом обходе поисковым роботом тех документов, которые чаще находятся пользователями. Одним из основных внетекстовых факторов ранжирования при поиске в Вебе является ссылочная популярность. К алгоритмам подсчета этой популярности относятся, среди прочих, PageRank и HITS. Первый применяется очень широко. Второй не используется на практике из-за вычислительной дороговизны. PageRank вместе с поиском по лексике ссылок, ведущих на страницы, позволил резко повысить качество поиска Google. Ссылочная популярность используется также в следующих задачах:
Используемые в поисковых системах формулы расчета ссылочной популярности учитывают также тематическую близость ссылающихся документов, их структуру и др. Поисковики заинтересованы в росте поисковой базы. Дело в том что около 30% всех поисков приходится на «редкие» запросы, т.е. на такие, по которым находится менее 100 документов. Поэтому, чем больше документов находятся в индексе, тем выше становится качество поиска. Вместе с тем огромные базы создают определенные технические проблемы. Поисковики становятся многокомпьютерными системами и применяют специальные техники по ускорению работы с поисковой базой. Вот эти техники:
Эшелонирование заключается в разделении поисковой базы на более и менее релевантные части. Поиск осуществляется сначала в первой части базы, а затем, если найдено недостаточно, по второй части базы. Прюнинг (pruning) заключается в отсечении (нерассмотрении) документов, которые на основании каких-то допущений считаются заведомо нерелевантными запросу. «Статический» прюнинг заключается в том, что на основании каких-то допущений из индекса исключаются документы, которые никогда не будут найдены. 16.03.2011 Предыдущие публикации: Последнее редактирование: 2011-03-16 14:14:54 Метки материала: алгоритмы, алгоритмы поисковых систем, it, информационные технологии, поисковики 2 комментария
Браво! Все в тему и разложено по полочкам. |
© 2007-2019, Дмитрий Скоробогатов.
Разрешается воспроизводить, распространять и/или изменять материалы сайта
в соответствии с условиями GNU Free Documentation License,
версии 1.2 или любой более поздней версии, опубликованной FSF,
если только иное не указано в самих материалах.