LAB1 Захаров А.Е. (544680), страница 2

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

Текст из файла (страница 2)

Интерфейс поисковой системы от компании Google google.ru

Выделяют три поколения поисковых машин [8, стр. 7].

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

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

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

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

Поисковые машины состоят из трёх основных элементов: индексатора, индекса и программного обеспечения поисковой машины [7, стр. 29].

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

Индекс (каталог) хранит все, найденные индексатором данные о страницах. При изменении web-страницы, со временем меняется и информация о ней в индексе. Пока данные о web-странице не попали в каталог, страница недоступна для поисковой машины.

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

Каталог поисковой системы Яндекс yaca.yandex.ru

1. Способы оценки степени релевантности запросу пользователя информации, найденной поисковой машиной.

Определение

Релевантность в информационном поиске – семантическое соответствие поискового запроса и поискового образа документа. В более общем смысле, одно из наиболее близких понятию качества «релевантности» — «адекватность», то есть не только оценка степени соответствия, но и степени практической применимости результата, а также степени социальной применимости варианта решения задачи [9].

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

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

Затем обратили внимание не только на количество, но и на качество ссылок. По этой причине 90% каталогов стали абсолютно бесполезны. Компания Google первой модернизировала свою поисковую машину. Поисковый робот не просто бродил по сети и собирал ссылки, но и смотрел, на каких сайтах они находятся, оценивал важность каждой ссылки. Новый алгоритм поиска получил название PageRank, и сводился к попытке оценивать каждый документ с учётом его веса в среде всех других проиндексированных документов сети, ссылающихся на оцениваемый.

Несомненно, такая система оценки релевантности выглядит гораздо более полезной для пользователей. В целом же идея подобного алгоритма оказалась весьма удачной, и её переняли другие поисковые системы, но под своим именем. Например, у Яндекса это называется ТИЦ.

Тематический индекс цитирования (тИЦ) определяет «авторитетность» Интернет-ресурсов с учётом качественной характеристики ссылок на них с других сайтов. Эту качественную характеристику называют «весом» ссылки. Рассчитывается она по специально разработанному алгоритму. Большую роль играет тематическая близость ресурса и ссылающихся на него сайтов. Само по себе количество ссылок на ресурс также влияет на значение его тИЦ, но тИЦ определяется не количеством ссылок, а суммой их весов.

тИЦ как средство определения авторитетности ресурсов призван обеспечить релевантность расположения ресурсов в рубриках каталога Яндекса. тИЦ не является чисто количественной характеристикой, поэтому представляет собой некоторые округлённые значения, которые помогают ориентироваться в «значимости» («авторитетности») ресурсов в каждой области [10].

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

• Количество исходящих ссылок на странице с обратной ссылкой. Каждая исходящая ссылка с сайта делит передаваемый «вес» с другими внешними. То есть получается, чем меньше исходящих ссылок со страницы, тем больший тИЦ будет передаваться.

• Количество исходящих ссылок с сайт в целом. Здесь похожая методика с первым пунктом, только не в масштабе страницы, а целого сайта. Сайт с огромным числом внешних ссылок передаст меньше тематического индекса цитирования, нежели сайт с меньшим количеством обратных ссылок.

• тИЦ исходящих ссылок. Чем больше тематический индекс цитирования, тем больше его сайт сможет передать по ссылкам.

• Фильтры, наложенные на сайт. Если на сайт наложены какие-то негативные фильтры, то «веса» ссылок с него упадут.

• Возраст домена.

Уровень вложенности страниц. Например, главная страница у «Яндекса» имеет больший авторитет, чем внутренние.

1. Функции оценки релевантности TF/IDF, PageRank, LexRank.

TF/IDF (Term frequency/Inverse document frequency) – статистическая мера, используемая для оценки важности слова в контексте документа, являющегося частью коллекции документов или корпуса. Вес некоторого слова пропорционален количеству употребления этого слова в документе, и обратно пропорционален частоте употребления слова в других документах коллекции [11].

TF (частота слова) – отношение числа вхождения некоторого слова к общему количеству слов документа. Таким образом, оценивается важность слова в пределах отдельного документа.

IDF (обратная частота документа) – инверсия частоты, с которой некоторое слово встречается в документах коллекции. Учёт IDF уменьшает вес широкоупотребительных слов.

– количество документов в корпусе;

– количество документов, в которых встречается слово (когда ).

В некоторых вариантах формулы не учитывается логарифмирование.

Таким образом, мера TF-IDF является произведением двух сомножителей: TF и IDF.

TF-IDF

Большой вес в TF-IDF получат слова с высокой частотой в пределах конкретного документа и с низкой частотой употреблений в других документах.

Пример

Вычислим TF-IDF для слова в контексте некоторого документа, если в этом документе оно встречается 25 раз, общее количество слов в документе равно 870, общее количество документов 60, и слово встречается в половине этих документов.

TF-IDF

PageRank – это числовая величина, характеризующая «важность» веб-страницы. Чем больше ссылок на страницу, тем она становится «важнее». Кроме того, «вес» страницы определяется весом множества страниц , ссылающихся на , и нормированным количеством исходящих ссылок . Таким образом, PageRank – это метод вычисления веса страницы путём подсчёта важности ссылок на неё.

Пример

Если страницы B, C, D ссылаются на страницу А, каждая из них вносит по 0.25 в PageRank страницы А.

Предположим, что на странице B имеются ссылки на страницы A и C, а страница D содержит ссылки на все три страницы. Значение PageRank распределяются между всеми исходящими ссылками на странице. Таким образом, страница B «даёт» по 0.125 страницам A и C. Только треть PageRank страницы D учитывается в PageRank А.

LexRank – лексический аналог функции ранжирования PageRank, используемой в поисковике Google [12].

Выполнение работы.

1. Изучить принципы и модель работы поисковой машины Yandex.

Сканирование.

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

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

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

У Яндекса два поисковых робота ­– основной и быстрый (он называется Orange). Основной робот индексирует интернет в целом, а Orange отвечает за то, чтобы в поиске можно было найти самые свежие документы, которые появились минуты или даже секунды назад. У каждого робота есть список адресов документов, которые нужно проиндексировать.

Индексирование.

Когда при обходе робот видит на уже известных сайтах новые ссылки, он добавляет их в свой список, увеличивая количество индексируемых страниц. Впрочем, владелец сайта сам может помочь основному роботу Яндекса найти свой ресурс и подсказать, например, как часто обновляются его страницы – через сервис Яндекс.Вебмастер.

После создания маршрута планировщик отдаёт его другой части поискового робота – «пауку». Паук регулярно обходит документы по заданному маршруту. Если сайт на месте, то есть работает и доступен, паук выкачивает запланированные в маршруте документы. Он определяет тип скачанного документа (html, pdf, swf и т.п.), кодировку и язык, а затем отправляет данные в хранилище.

Там программа разбирает документ: очищает от картинок и html-разметки, оставляет чистый текст, выделяет данные о местоположении каждого слова и добавляет их в индекс. Сам документ в исходном виде также остается в хранилище до следующего обхода.

Поисковый индекс, данные о типе документов, кодировке, языке и сохраненные копии документов вместе составляют поисковую базу. Она обновляется постоянно, но, чтобы это обновление стало доступно пользователям, её нужно перенести на «базовый поиск». Базовый поиск — сервера, которые отвечают пользователям на запросы. Туда переносится не вся поисковая база, а только её полезная часть – без спама, дубликатов сайтов (зеркал) и других ненужных документов.

Обновление поисковой базы из хранилища основного робота попадает в поиск «пакетами» – раз в несколько дней. Этот процесс создаёт дополнительную нагрузку на сервера, поэтому производится ночью, когда к Яндексу обращаются на порядок меньше пользователей. Сначала новые части базы помещаются рядом с такими же частями из прошлого обхода. Затем они проверяются по целому ряду факторов, чтобы обновление не ухудшило качество поиска. Если проверка прошла успешно, новая часть базы заменяет собой старую.

Характеристики

Список файлов лабораторной работы