Анализ гипертекстовых документов с различных сайтов с целью автоматизированного сбора данных

Министерство образования РФ Владимирский Государственный университет Муромский институт Факультет Радиотехнический Кафедра Информационные системы Научно-исследовательская работа Тема Анализ гипертекстовых документов с различных сайтов с целью автоматизированного сбора данных

.

Муром 2002

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

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

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

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

Более серьезным является необходимость сбора статистики о конкретной поисковой системе. Включаемые в запрос термины должны обладать значительной дискриминационной силой, иными словами, не разумно включать в запрос те термины, которые в данной коллекции являются общеупотребительными, т. е. встречаются почти в каждом документе. Далее, необходимо оценить реальную пользу от использования различных возможностей поиска, предоставляемых данной системой. В отличие от языка запросов к реляционной базе данных, например, SQL, которые позволяют получить именно те данные, которые запрашиваются, в документальных поисковых системах результат поиска зависит от огромного числа факторов. Один из таких факторов — используемый в системе алгоритм поиска, который часто является коммерческим секретом. Только длительная активная работа с конкретной системой позволит выявить сильные и слабые стороны данной системы. В результате анализа статистики запросов большого числа пользователей к известным поисковым системам выяснилось, что средняя длина запроса не превышает двух слов, и, как правило, пользователи используют самую простую форму запроса. Проведенный в данном разделе анализ позволяет сделать следующее заключение. Нельзя надеяться на то, что пользователь поисковой системы будет формулировать достаточно сложные эффективные запросы. Современная поисковая система должна выявлять информационные потребности конкретного пользователя и учитывать их при поиске в интересах данного пользователя. При работе с поисковой системой пользователь выражает свои информационные потребности на языке запросов данной системы и надеется получить в результате поиска ссылки на наиболее релевантные запросу документы. Понятие релевантность используется в мире информационного поиска очень широко. Однако его нельзя строго определить. Можно привести лишь следующий пример, дающий косвенным образом представление о смысле этого понятия. Для оценки качества поисковых систем проводятся различные тестовые испытания. Наиболее известной системой тестирования является TREC — TExt Retrieval Conference. Это система ежегодных конференций (с 1992 года), на которых производится тестирование различных поисковых систем на одном множестве специально подготовленных тестов. Например, для проведения тестирований на пятой конференции (TREC-5), были подготовлены тестовые данные, включающие около 260 тысяч текстовых документов общим объемом более гигабайта текстовой информации.

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

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

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

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

Актуальность задачи, связанной с созданием поисковых систем определяется рядом факторов:

в связи с растущим объёмом информации требуются новые поисковые средства;

необходимо повысить качество (релевантность) находимой информации Цель дипломной работы:

— изучить существующие поисковые системы,

— разработка структуры и реализовать новую поисковую систему в Интернет,

— разработка алгоритмов поиска информации и определения релевантности найденных документов,

— исследование разработанных алгоритмов.

Назначение системы — обеспечение более качественного (релевантного) нахождения информации.

Основными задачами, решаемыми в работе, являются:

анализ и исследование существующих поисковых систем в Интернет;

разработка структуры поисковой системы;

разработка алгоритмов поиска и определения релевантности документов;

исследование разработанных алгоритмов.

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

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

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

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

В программной части приводится реализация системы. Рассмотрена структура системы, описаны основные компоненты системы. Дается руководство программисту и оператору.

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

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

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

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

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

1. Обзор состояния проблемы и постановка задачи

1.1 Обзор поисковых систем Будем представлять Web как совокупность сайтов, каждый из которых содержит множество документов.

(1.1)

(1.2)

Авторы создают документы, а у какой-то определённой группы людей возникает информационная потребность. Эта потребность часто (как правило) даже не может быть точно выражена словами, и выражается только в оценке просматриваемых документов — подходит или не подходит. В теории информационного поиска вместо слова «подходит» используют термин пертинентный (от англ. pertinent — относящийся к делу, подходящий по сути), а вместо «не подходит» — «не пертинентный». Субъективно понимаемая цель информационного поиска — найти все пертинентные и только пертинентные документы (найти «только то, что надо, и ничего больше»).

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

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

Рисунок 1.1 — Информационно-поисковая система.

Запрос редко может точно выразить информационную потребность, если это, конечно, не запрос на естественном языке. Однако многие ИПС по разным причинам не могут определить, соответствует ли тот или иной документ запросу. Степень соответствия документа запросу называется релевантностью. Релевантный документ может оказаться непертинентным и наоборот. [13]

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

В соответствии с ИПС, основанные на каталогах, будем называть классификационными ИПС, а ИПС, использующие поисковые машины, — словарными.

В основе составления тематических каталогов лежит принцип классификации, то есть распределения документов (или целых сайтов) по иерархии тематических рубрик (классификатору). Классификатор разрабатывается и совершенствуется коллективом авторов. Внутри рубрик документы упорядочены по рейтингам популярности. Классификацию в большинстве случаев также производят вручную, так как этот процесс трудно осуществить автоматически. Но уже существуют системы автоматической классификации документов, примером которых является разработка компании МедиаЛингва (http://www.medialingua.ru).

Каталоги могут содержать рефераты документов и краткие описания сайтов. Количество классифицированных документов ничтожно мало по сравнению с их общим количеством в Web, поэтому каталоги не могут дать исчерпывающих сведений по определённой тематике. Системы, основанные на каталогах, лучше подходят в тех случаях, когда надо осуществить быстрый поиск каких-либо общих укрупненных тем или пользователям, которые занимаются «вольным скольжением» по Сети. Небольшие размеры и созданная людьми система упорядочения материала делают их особенно пригодными для быстрого нахождения качественной информации. В данном случае делается ставка именно на качество информации, а не на её количество [6, 7].

Классификационные ИПС обладают рядом специфических недостатков. Разработка классификатора связана с оценкой относительной важности различных областей человеческой деятельности. Например, сравнивая классификаторы многих ИПС Интернет (таких, как Yahoo, Excite, Look Smart), замечаем, что во многих из них нет раздела «Наука». Кроме того, в создании таких ИПС участвуют также и коллективы систематизаторов, которые выносят свои субъективные оценки о соответствии документов рубрикам классификатора. Любая оценка является социальным действием; она связана с обществом, культурой, социальной группой, к которым принадлежит человек, выносящий оценку. Поэтому тематические каталоги, созданные разными коллективами в разных странах, могут иметь весьма различную степень полезности при поиске информации — всё зависит от того, кто и что ищет. Таким образом, при поиске информации с помощью ИПС, основанной на каталоге, возникает необходимость взаимодействия с другими культурами — культурами авторов, создателей классификаторов и систематизаторов.

Недостатки:

— не могут дать исчерпывающих сведений по определённой тематике;

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

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

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

Рассмотрим принцип действия словарных ИПС. Все словарные ИПС имеют общую структуру, которая приведена на рис. 1.2.

Рисунок 1.2 — Общая структура словарной ИПС С точки зрения внутренней организации словарная ИПС состоит из двух частей, как правило, работающих параллельно. Первая часть (индексирующий агент (agent), паук (spider), робот (robot)) ответственна за индексирование Webдокументов, а вторая (поисковая машина) осуществляет поиск документов по индексу в соответствии с запросами пользователей.

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

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

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

С философской точки зрения каждый документ можно представить состоящим из двух частей: «важной» и «неважной».

{Документ} = {Важная часть} U {Неважная часть} (1.3)

{Неважная{Важная часть} часть} = O

В идеале в индекс должна попадать только «важная» часть документа, а «неважная» часть теряться. Однако алгоритмы индексирования, применяемые разными ИПС отличаются.

Для хранения индекса часто используются системы управления базами данных (СУБД). В таких случаях поиск по индексу осуществляется с использованием встроенных средств СУБД.

Каждая ИПС имеет свой собственный ИПЯ, на котором необходимо формулировать поисковые запросы к ней. Поэтому для того, чтобы осуществлять полнофункциональный поиск с использованием нескольких ИПС пользователю придётся изучить несколько ИПЯ. ИПЯ разных ИПС хотя и различаются, но в большинстве своём несильно и уже предпринимаются попытки создания стандарта на ИПЯ. При участии 15 крупнейших поисковых систем Интернета в феврале 1999 года стартовал проект SESP (Search Engine Standards Project), призванный стандартизировать работу поисковых служб. Материалы о нём можно найти по адресу http://www.searchenginewatch.com/standards/990 204.html. Задачей стандарта является максимально сблизить синтаксис и возможности ИПЯ различных ИПС. В частности, одним из обязательных требований становится поддержка любой поисковой системой единых команд запросов, локализующих узел по его доменному имени, а документ — по URL.

Самая популярная в мире поисковая машина AltaVista (http://www.altavista.com/) содержит 11 миллиардов слов, извлеченных из 30 миллионов Web-страниц. Несмотря на свою популярность Altavista не очень подходит для поиска в русскоязычном Интернете, т.к. индексирует в основном англоязычную его часть.

К ведущим российским словарным ИПС относятся: Яndex (http://yandex.ru), Рамблер (http://www.rambler.ru), Апорт (http://www.aport.ru).

Наиболее развитый сервис поиска русскоязычной информации предоставляет сервер Яndex (http://www.yandex.ru/). В Яndex пользователь может просто написать по-русски фразу, описывающую то, что он хочет найти. Система самостоятельно проанализирует и обработает его запрос, а затем постарается найти все, что относится к заданной теме. Ну, а в том случае, если нужных документов не обнаружится, можно продолжить поиск через AltaVista, куда автоматически передается уже обработанный системой запрос. Но до передачи запроса AltavVista вряд ли дойдет, так как база Яndex содержит порядка 2 000 000 документов и постоянно обновляется. Проблема больше состоит в том, что поисковая машина в результате вашего запроса генерирует гигантский список адресов URL с короткими описаниями. Яndex позволяет конкретизировать запрос пользователя для сокращения этого списка до разумных пределов. Он может на запрос либо набрать фразу по аналогии с предыдущими системами, либо, используя, специальные операторы, составить строку, поясняющую Яndex, каким требованиям должна отвечать, интересующая его информация.

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

Подытожим достоинства ИПС словарного типа.

— широкий охват web-ресурсов;

— не требуется дорогой ручной труд разработчиков классификатора и систематизаторов.

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

1.2 Сравнение основных российских поисковых систем В настоящее время существует ряд общеизвестных русскоязычных поисковых серверов, пользующихся высокой популярностью. Это Яндех (www.yandex.ru или www.ya.ru), Апорт (www.aport.ru) и Рамблер (www.rambler.ru). Произведем сравнение их структуры и характеристик.

1.2.1 Поисковая система Рамблер Поисковая машина «Рамблер» начала работу в октябре 1996 года, на стартовом этапе содержала всего 100 тысяч документов. «Рамблер» не был первой отечественной поисковой системой, однако в первый год своего существования (когда весь русский веб с приемлемой степенью правдоподобия индексировался «Рамблером», «Апортом», «Русской поисковой машиной», а также шведской и калифорнийской AltaVista) вынес основной груз поисковых запросов. Вторая версия «Рамблера» начала разрабатываться летом 2000 года, в марте нынешнего года приняла достаточно законченные очертания. В нее были введены функции, давно уже имевшиеся в конкурирующих системах. Она учитывает координаты слов, обучена строгой и нечеткой морфологии, связывает поиск с каталогом, в качестве которого используется Top100 (http://top100.rambler.ru/), группирует результаты поиска по сайтам, ищет по числам. Достаточно удачная архитектура продукта позволяет «Рамблеру» иметь для поисковика количество серверов в 2 раза меньшее, чем у «Яндекса», и в 3 раза меньшее, чем у «Апорта» .

" Паук" «Рамблера» производит индексирование в новостях 5 раз в день; в сайтах, входящих в Top100, — 1 раз в день; все прочие посещаются не чаще, чем 1 раз в две недели. Рамблер не индексирует личные странички, находящиеся на публичных зарубежных серверах (geocities, tripod и других), а страницы подобных отечественных сайтов (narod, boom) обходит медленней, чем другие ресурсы. Поскольку новостными считаются всего около 40 сайтов, выгодно иметь на своих страницах счетчик Top100 для быстрого отображения страниц в поисковой машине «Рамблера». К тому же, в рейтинг Top100 можно вносить подробные аннотации объемом до 4 Кб [2, 5].

1.2.2 Поисковая система Апорт Поисковая машина «Апорт» была впервые продемонстрирована в феврале 1996 года на пресс-конференции «Агамы» по поводу открытия «Русского клуба». Тогда она искала только по сайту russia.agama.com. Потом она начала искать по четырем, потом по шести серверам… Короче, день рождения и фактический старт системы сильно «размазались» по времени, а официальная презентация «Апорта» состоялась только 11 ноября 1997 года. К тому времени в его базе был проиндексирован первый миллион документов, расположенных на 10 тысячах серверов. Создателем системы выступила компания «Агама» — разработчик программного обеспечения для платформы Windows, главным из которых являлся корректор орфографии «Пропись». Лингвистические разработки «Агамы» использовались при создании поисковой машины, в которой, скажем, в отличие от «Рамблера», изначально учитывалась морфология слов и осуществлялась по желанию клиента проверка орфографии запроса.

Важнейшими свойствами первой версии «Апорта» являлся перевод запроса и результатов поиска на английский язык и обратно, а также реконструкция всех проидексированных страниц из собственной базы (что означает возможность просмотра страниц, уже несуществующих в оригинале). «Апорт 2000″ стал первым русским поисковиком, построенным на основе выдачи результатов по отдельно взятым сайтам. Для разделения ресурсов на сайты используется информация, которую „Апорту“ предоставляет каталог AtRus или сведения, введенные в „Апорт“ владельцами ресурсов. На худой конец, приходится опираться на алгоритм, который позволяет по некоторым формальным признакам выделить отдельные сайты. „Апорт 2000″ стал первой российской поисковой машиной, практически реализовавший две базовых технологии американской поисковой машины Google. Первая — учет “ ранга страницы» (Page Rank), который характеризует ее популярность (вычисляется по количеству ссылок на ресурс из внешнего Интернета: вес ссылки с популярного сайта выше, чем вес ссылки с менее популярного; ссылки, включающие слова запроса, имеют больший вес, чем, скажем, слово «здесь»). Вторая — обработка запроса, ориентируясь на HTML-код страницы (к примеру, анализ текста, содержащегося между тегами шрифтов h2 и h6 дает больший приоритет для первого варианта). В «Апорт 2000» учитывается также вхождение слов запроса в URL. Среди недокументированных особенностей — больший приоритет сайтам, получившим высшую и элитную лигу в каталоге AtRus.

Еще на этапе разработки «Апорта 2000» в него были заложены «крючечки», позволяющие корректировать приоритеты в выдаче результатов с учетом посещаемости сайтов по счетчику Aport Top 1000 и для сайтов, чье название в службах реальных имен является синонимом или совпадает со словами запроса (так как любая служба имен модеририруется, и полной чуши в ее данных быть не может). Обе эти возможности до сих пор не реализованы. Пользователи «Апорта» (в отличие завсегдатаев «Яндекса») мало пользуются расширенным поиском (на 8000 загрузок простой страницы приходится 300 вызовов страницы «Расширенный поиск»).

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

1.2.3 Поисковая система Яндекс Эта поисковая система Интернета — часть проекта фирмы Comptek по разработке набора средств полнотекстовой индексации и поиска в текстовых данных с учетом морфологии русского языка. Яndex расшифровывается как Языковый Индекс или, в английском написании, Yandex — Yet Another Index.

Как указывается в документе на сервере, продукты Яndex предназначены для работы с большими объемами русских текстов всех типов — в виде файлов различных форматов, полей баз данных и страничек Интернет.

Поисковая машина Яndex была запущена в эксплуатацию сравнительно недавно — в конце сентября 1997 года и область поиска системы — русскоязычный Интернет. Отличительные особенности системы, в соответствии с описанием на http://yandex.ru:

— полнотекстовый поиск с полным учетом морфологии русского и английского языков

— мощный язык запросов (в том числе возможность поиска с расстоянием)

— возможность запроса на естественном языке

— корректная обработка сленговых слов

— возможность поиска похожего документа

— очень компактный индекс

— подсветка слов из запроса в найденных документах

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

— высокая скорость поиска.

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

Яndex обеспечивает индексацию одновременно с морфологическим разбором. Это позволяет создавать компактный индекс — около 30% исходных текстов, сохраняя достаточно высокую скорость индексации — 1−2 Мб/мин. Такая технология дает возможность почти полного снятия омонимии на этапе индексации.

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

Нынешняя версия Яndex функционирует с 23 мая 2001 года. Ее главное нововведение, которое потребовало неизбежной перестройки ядра, — ранжирование по ссылкам. Другие нововведения относятся, главным образом, к переформулированию системой запросов пользователя: «что такое предмет» преобразуется в «предмет — это…», а если запрос начинается на слово «как», то в результатах в первую очередь пытаются выдать FAQ или иной справочный документ. Новый «Яндекс» стал «понимать» альтернативную лексику, которая входит в 5 процентов запросов. Только в последней версии Яндекса индекс цитируемости стал непосредственно использоваться поисковой машиной.

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

1.2.4 Результаты сравнения поисковых систем Популярность поисковых серверов Яндекс, Апорт и Рамблер связана с несколькими факторами, особо выделить из которых необходимо три:

1. Все они обладают большой поисковой базой, поэтому нужный документ рано или поздно в этой базе будет найден

2. Они снабжены довольно неплохими алгоритмами поиска.

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

Несмотря на популярность и преимущества, системы все же имеют недостатки. В первую очередь это связано все же с недостаточной релевантностью результатов поиска. Алгоритмы ее определения все еще далеки от совершенства, поэтому можно увидеть появление новых систем, которые без особых усилий становятся общепризнанными во всем мире (например, www.Google.com). Изменение же поисковых алгоритмов у существующих систем может иногда связано с рядом трудностей. По этой причине разработка новых поисковых систем с новыми поисковыми алгоритмами актуальна в настоящее время.

1.3 Основные функции поисковых систем

1) Сканирование Internet.

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

2) Индексирование документов.

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

3) Поиск.

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

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

1) Самым простым методом является поиск куска текста в документах — аналог тому поиску, что используется в документах Microsoft Office или Windows Commander. Преимущество этого метода — его простота. Реализуется это на Паскаль с помощью одной команды — pos. Еще одно преимущество — нет необходимости использовать поисковую базу — поиск осуществляется непосредственно в документах. Этот метод поиска самый примитивный и обладает рядом недостатков. Один из них — это невозможность найти текст, если слова запроса непосредственно не следуют друг за другом. Другой недостаток — практическая невозможность определить, какой документ больше подходит по запросу пользователя. Таким образом, практически невозможно определить релевантность найденных документов запросу пользователя. Подобные алгоритмы используются сейчас в основном для поиска на локальных страницах одного или нескольких сайтов. В крупных поисковых системах — не используется.

2) Поиск по частоте встречаемости слов. Суть метода заключается в следующем. Сначала формируется база данных, содержащая частоту вхождения слов в документ. Поиск производится именно по этой базе. Результаты выдаются в соответствии с частотными характеристиками — чем чаще встречаются слова — тем более релевантный результат. На практике это оказывается не всегда так. Например, часто суть документа описывается его заголовком (который встречается один раз), а в тесте документа рассматриваются эти вопросы более подробно, но не обязательно с теми же словами. Так, если документ имеет названием «Структура компьютера», то внутри него рассматриваются компоненты компьютера, их взаимосвязь и т. д., но может больше не встречаться строка «Структура компьютера». По этой причине приведенный метод оценит релевантность документа не правильно (не очень высоко). Еще одной сложностью метода является то, как оценить релевантность документа если частота встречаемости слов в одном запросе различна — например, слова «Структура» — 3%, а «компьютера» — 1%?

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

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

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

Рассмотрим непосредственно используемые алгоритмы поиска.

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

Разные авторы называют эту модель индексирования и поиска по-разному: векторной, линейной, или алгебраической. Будет справедливо, если представление документов и поиск информации в массиве разделим на две модели. Следуя этой логике, векторной будем называть модель описания информационного массива, а линейной — модель поиска информации в массиве. Такое разделение обусловлено тем, что документы записываются в виде двоичных векторов, в то время как поисковые запросы — это линейные преобразования над этими векторами.

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

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

Документ — это двоичный вектор размерности D. Если термин входит в документ, то в соответствующем разряде этого двоичного вектора проставляется 1, в противном же случае — 0. Обычно все операции в линейной модели индексирования и поиска документов выполняются над поисковыми образами документов, но при этом их, как правило, называют просто документами.

Информационный поток или массив L представляют в виде матрицы размерности NxD, где в качестве строк выступают поисковые образы N документов.

(1.4)

где — термин, — документ.

При таком рассмотрении можно сформулировать процедуру обращения к информационной системе следующим образом:

где — вектор запроса, — вектор отклика системы на запрос.

Это традиционное определение процедуры поиска документов в ИПС, которое используется Солтоном с 1977 года. Оно было введено для решения проблемы автоматического индексирования документов, но оказалось чрезвычайно полезным и для описания процедуры поиска.

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

Начало применению запросов типа «Like This» положила система WAIS. Именно в ней был впервые сформулирован отказ от использования традиционных информационно-поисковых языков булевого типа, и было заявлено о переносе центра тяжести информационного поиска на языки, основанные на вычислении меры близости «документ-запрос». Основная причина такого подхода — желание снять с пользователей заботу по формулированию запросов на информационнопоисковых языках и дать им возможность использовать обычный естественный язык. Ради справедливости следует отметить, что от запросов на естественном языке практически сразу отказались. Система просто проводила нормализацию лексики и удаляла из списка терминов запроса общие и стоп-слова. Тем самым практически один в один выполнялись условия линейной модели индексирования и поиска. После этой процедуры система вычисляла меру близости по выражению и в соответствии с полученными значениями ранжировала информационный массив. Практически все ИПС Интернета устроены по этому принципу.

Можно привести много мер близости, однако в современных распределенных ИПС Интернет реально используются лишь несколько.

(1.5)

(1.6)

(1.7)

(1.8)

где — мера близости документа и запроса ;

— число терминов запроса;

— -ый документ индекса

— {1, если из документа есть ссылка на документ; 0, иначе};

— {1, если из документа есть ссылка на документ; 0, иначе},

— {1, если документ содержит термин; 0, иначе}

Наиболее популярными из них являются:

— расширенный двоичный алгоритм поиска;

— алгоритм наибольшего цитирования;

— TFxIDF алгоритм (предложен и уточнён Солтоном в 1979 году);

— расширенный векторный алгоритм поиска.

Следует отметить, что наиболее эффективным из этих алгоритмов является TFxIDF, который и используется в большинстве ИПС (RBSE, WAIS, WebCrawler, Lycos, OpenText, Lycos и Altavista).

Одним из компонентов меры близости TFxIDF является частота встречаемости терминов в массиве документов.

Обычно плотность функции распределения частоты встречаемости терминов описывают гиперболическим распределением, известным как закон Зипфа.

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

Суть алгоритма Солтона в том, что для индексирования используют те термины, которые имеют высокую частоту встречаемости внутри документа и низкую во всем информационном массиве. Сама характеристика вычисляется как отношение частоты встречаемости термина в документе к частоте встречаемости термина в массиве. Используя эту меру системы индексирования, документу приписывают первые 20−40 символов, которые и составляют его поисковый образ. Выбор этой меры объясняется простыми прагматическими соображениями, которые становятся очевидными при сравнении выражения с другими способами взвешивания терминов.

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

— для того чтобы использовать взвешивание, следует иметь насыщенный словарь,

— термины индексирования находятся в окрестностях максимума частотного распределения терминов.

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

Но и Lycos, и OpenText, и Altavista, и другие системы Интернета применяют линейную модель индексирования и поиска, используя различительную силу термина в алгоритмах автоматического индексирования и поиска. Следовательно, применяемые алгоритмы ограничивают словарь, допуская его незначительный рост.

Именно это и осуществляют все реально функционирующие системы, ограничивая размер поискового образа документа 20−40 наиболее «тяжелыми» терминами из содержания. При этом в словарь попадают только термины поисковых образов. Следует также отметить, что источником терминов индексирования, в большинстве случаев выступает не весь документ, а только отдельные его части: заголовок, гипертекстовые ссылки, подзаголовки, специальные поля. Таким образом, удается контролировать размер словаря и оставаться в рамках линейной модели индексирования и поиска.

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

1.5 Сравнение параметров, использующихся в алгоритмах определения релевантности документов

Проведем сравнение конструктивных элементов, используемых при определении релевантности российскими поисковыми системами.

Таблица 1.1 — Параметры, учитываемые при определении релевантности

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

Все системы учитывают конструктивные элементы страниц, такие как тэги H1-H6, выделенные слова (Strong). Пользуется популярностью элемент Alt тэга IMG, являющийся пояснением к рисунку. Он используется во всех системах.

С мета-тэгами системы работают менее эффективно. Так, ключевые слова (Keywords) ни в одной системе не участвуют в определении релевантности, а описание (Description) используется лишь частично на Yandex и Aport, причем значимость их не велика. Заголовок страницы (Title) учитывают все системы.

Yandex использует для определения релевантности страницы также количество ссылок на нее с других сайтов (так называемый индекс цитирования). Rambler располагает результаты в соответствии с позициями сайтов в рейтинге Top100.Rambler.ru

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

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

1.6 Постановка задачи

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

В дипломной работе требуется разработать:

— базовые компоненты поисковой системы,

— алгоритм, способный искать документы и выдавать релевантные результаты поиска,

— произвести исследование алгоритма.

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

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

2. Теоретическая часть

2.1 Разработка информационной базы

Пусть необходимо занести в поисковую базу информацию с набора сайтов. Под сайтом будем понимать набор ресурсов, расположенных в одном домене и его поддоменах. Так, ресурсы aaa.bbb.ru/link/12.htm, aaa.bbb.ru/index.html будут относиться к сайту aaa.bbb.ru, а ресурсы ccc.bbb.ru/index.htm и aaa.ddd.ru/index.htm — нет. Представим множество индексируемых сайтов множеством. Каждый конкретный сайт представим как .

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

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

Рассмотрим тэги, которые имеет смысл индексировать (заносить в поисковую базу):

TITLE — один из главных тэгов, который используется при поиске. Большинство поисковых систем так или иначе используют его для поиска и выдачи результатов.

H1 — служит для обозначения заголовков (самых больших) внутри документов.

H2 — служит для обозначения подзаголовков заголовка H1.

H3 — заголовок.

H4 — заголовок.

H5 — заголовок.

H6 — заголовок.

Мета-тэг KEYWORDS — служит для задания ключевых слов документа.

Мета-тэг DESCRIPTION — служит для задания описания документа.

Alt — служит для обозначения всплывающей подписи для рисунка.

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

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

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

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

На основе вышеперечисленных рассуждений была разработана структура информационной базы поисковой системы.

Рисунок 2.1 — ER-диаграмма поисковой базы.

Опишем эти таблицы:

1) Site — таблица индексируемого сайта. Содержит информацию о сайте целиком. Эта таблица соответствует множеству .

Таблица 2.1 — Структура таблицы Site