LAB1 Кобец С.Ю (Лабораторная работа 1)

Национальный Исследовательский Университет

Московский Энергетический Институт (Технический Университет)

Кафедра прикладной математики

Лабораторная работа №1 по дисциплине ВМСС

Поиск информации в Internet

Выполнил: Кобец С. Ю.

А-13-08

Преподаватель: Куриленко И. Е.

Москва

2012г.

Адресация в сети Интернет

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

IP-адреса

Уникальный код компьютера в сети Интернет (IP-номер) состоит из четырех чисел со значениями от 0 до 255, разделенных точками (ххх.ххх.ххх.ххх.). Такая схема нумерации позволяет иметь в сети более четырех миллиардов компьютеров.

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

DNS-адреса

Для удобства компьютерам в Интернете кроме цифровых адресов присваиваются собственные имена. При этом также, как и в случае с IP-адресами, необходима уникальность этого имени. С этой целью была создана специальная система адресации - доменная система имен (Domain Name System) или сокращенно DNS. DNS-адрес вместо цифр содержит буквы, разделяемые точками на отдельные информационные блоки (домены). 
Первым в DNS-адресе стоит имя реального компьютера с IP-адресом. Далее последовательно идут адреса доменов, в которые входит компьютер, вплоть до домена страны (для них принята двухбуквенная кодировка). Например, duma.ru: duma - имя домена Государственной думы, ru - страна Россия, аналогично mvd.ru. Здесь имеет место ситуация, сходная с присвоением географических названий и организацией почтовых адресов. 
Когда используется DNS-адрес, компьютер посылает запрос на DNS-сервер, обладающий соответствующей базой данных, DNS-сервер начинает обработку имени с правого конца влево, постепенно сужая поиск, определяя IP-адрес. Таким образом, по DNS-имени можно определить эквивалентный IP-адрес.

Три поколения поиска

Поиск 1.0

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

Поиск 2.0

С запуском Google, поиск стал больше опираться на данные сети – анализировалась не только одна страница, но и ссылки, ведущие на нее. Таким образом устанавливалась система авторитетности страниц, подобная системе оценки цитируемости работ, принятой в научном мире. Ссылки становились как бы «голосами» в пользу какой-либо страницы.

Поиск 3.0

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

Общие принципы и модели работы современных ИПС

Общие принципы текстового поиска

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

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

При поступлении в систему пользовательского запроса для него также строится соответствующее представление. Метод его построения аналогичен используемому для построения представлений документов.

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

Простейшие модели поиска

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

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

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

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

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

Булевские модели поиска. Пользователь может формулировать запрос в виде булевского выражения с использованием операторов И, ИЛИ, НЕТ. Термы булевского выражения могут быть различными в разных вариациях булевских моделей поиска. Это может быть, например, условие вхождения данного слова или словосочетания (с точностью до грамматических форм) в текст документа в булевском расширении контекстной модели поиска. В булевском расширении модели поиска по классификаторам термами выражения могут быть условия принадлежности документа данному классу классификатора.

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

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

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

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

Принцип работы ИПС Яндекс

Логическую структуру поисковой системы можно представить в виде трех модулей:

• Робот (краулер)

• База данных

• Клиентская часть

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

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

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

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

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

Что примечательно, в Яндексе используются отдельные формулы релевантности для полутора десятков крупных городов России, отдельные формулы для стран СНГ (Белоруссия, Казахстан и Украна) и Турции. Т.о. алгоритм, используемый в Яндексе для ранжирования сайтов, работает в автоматическом режиме, однако иногда используются и полуавтоматические и ручные действия, направленные на корректировку поисковой выдачи в сторону повышения ее релевантности.

Итак, представим упрощенно, что происходит в Яндексе, когда пользователь задает запрос, например, «пластиковые окна».

Запрос обрабатывается синтаксическим анализатором, приводится к начальной форме. Далее по базе ищутся все документы, содержащие слова «пластиковый» и «окно». Естественно, Яндекс не производит прямой поиск информации по всем документам в базе. Вся информация содержится в виде т.н. «обратного индекса», т.е. для каждого слова указаны порядковые номера документов, где содержится это слово и позиции данного слова в документе. Аналогом обратного индекса является, например, алфавитный указатель в книге, где указано, на какой странице встречается тот или иной термин и вы можете с легкостью найти информацию, не пролистывая всю книгу.

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

Принцип работы ИПС Google

Каких-либо особенных отличий в логике работы поисковой системы Google от поисковой системы Яндекс нет. 

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