Студент-дипломник __________________________

Руководитель работы _________________________

СОДЕРЖАНИЕ

Введение

1. Анализ систем организации поиска во Всемирной Глобальной сети

1.1 Информационно-поисковые системы

1.2 Гипертекстовые документы

1.3 Классификация современных информационно-поисковых систем

1.4 Описание механизма поиска информационно-поисковых систем

1.5 Поисковые роботы.

1.6 Обзор и рейтинги основных мировых поисковых систем

1.7 Перспективы дальнейшего развития поисковых систем

2. Разработка структуры поисковой системы «Бета-поиск»

2.1 Обоснование выбора инструментария реализации информационной системы

2.2 Проектирование информационно-поисковой системы

2.3 Описание интерфейса информационно-поисковой системы

Заключение

Список использованной литературы

Введение

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

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

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

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

Актуальность темы.

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

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

Цель дипломной работы:

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

Основные задачи дипломной работы:

- произвести анализ процесса организации поиска во Всемирной Глобальной сети;

- разработать информационно-поисковую систему, демонстрирующую механизм поиска информации в сети Интернет.

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

Структура дипломной работы. Состоит из введения, двух разделов, заключения, списка использованных источников. Работа содержит 7 таблиц, 13 рисунков и 2 диаграммы, систематизирующих основные ее положения.

1. Анализ систем организации поиска во Всемирной Глобальной сети

1.1 Информационно-поисковые системы

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

История развития информационно-поисковых систем

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

Каталоги ссылок широко использовались ранее, но практически утратили свою популярность в настоящее время. Причина этого очень проста - даже современные каталоги, содержащие огромное количество ресурсов, представляют информацию лишь об очень малой части сети Интернет. Самый большой каталог сети DMOZ (или Open Directory Project) содержит информацию о 5 миллионах ресурсов. В то время, как Google насчитывает 8 миллиардов.

Первой полноценной поисковой системой стал проект WebCrawler, появившийся в 1994 году.

В 1995 году появились поисковые системы Lycos и AltaVista. Последняя долгие годы Alta Vista была лидером в области поиска информации в Интернет.

В 1997 году Сергей Брин и Лари Пейдж создали Google, самую популярную на сегодняшний момент поисковую систему в мире.

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

В настоящее время существует 3 основных международных поисковых системы - Google, Yahoo и MSN Search, имеющих собственные базы и алгоритмы поиска. Большинство остальных поисковых систем использует в том или ином виде результаты 3 перечисленных. Например, поиск AOL (search.aol.com) и Mail.ru используют базу Google, а AltaVista, Lycos и AllTheWeb - базу Yahoo [2].

В России основной поисковой системой является Яндекс, за ним идут Rambler, Google.ru, Aport, Mail.ru и КМ.ru, а в Казахстане популярными являются Kaz.kz и Poisk.kz.

1.2 Гипертекстовые документы

Под гипертекстовым документом понимают документ, содержащий так называемые ссылки на другой документ. Реализовано все это через протокол передачи гипертекста HTTP (HyperText Transfer Protocol).

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

Гипертекстовые документы создаются на базе языка HTML (HyperText Markup Language). Этот язык весьма прост, управляющие коды его, которые, собственно, и компилируются обозревателем для отображения на экране, состоят из текста ASCII. Ссылки, списки, заголовки, картинки и формы называются элементами языка HTML, которые позволяют щелчком мыши перейти к просмотру другого документа.

Существует два способа создания гипертекстовых документов. Можно воспользоваться одним из WYSIWYG HTML-редакторов (например, Netscape Composer, основы работы с котором рассмотрены в разделе «Обработка текста на ЭВМ», Microsoft FrontPage, HotDog, или др.), для работы с которыми не требуется специальных знаний о внутренней структуре создаваемого документа. Этот способ позволяет создавать документы для WWW без знания языка HTML. HTML-редакторы автоматизируют создание гипертекстовых документов, избавляют от рутинной работы. Однако их возможности ограничены, они сильно увеличивают размер получаемого файла и не всегда полученный с их помощью результат соответствует ожиданиям разработчика. Но, безусловно, этот способ незаменим для новичков в деле подготовки гипертекстовых документов.

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

Как уже отмечалось, HTML-документ содержит символьную информацию. Одна ее часть - собственно текст, т.е. данные, составляющие содержимое документа. Другая - теги (markup tags), называемые также флагами разметки, - специальные конструкции языка HTML, используемые для разметки документа и управляющие его отображением. Именно теги языка HTML определяют, в каком виде будет представлен текст, какие его компоненты будут исполнять роль гипертекстовых ссылок, какие графические или мультимедийные объекты должны быть включены в документ. Графическая и звуковая информация, включаемая в HTML-документ, хранится в отдельных файлах. Программы просмотра HTML-документов (браузеры) интерпретируют флаги разметки и располагают текст и графику на экране соответствующим образом. Для файлов, содержащие HTML-документы, приняты расширения.htm или.html.

Прописные и строчные буквы при записи тегов не различаются. В большинстве случаев теги используются парами. Пара состоит из открывающего (start tag) и закрывающего (end tag) тегов. Синтаксис открывающего тега:

<имя_тега [атрибуты]>

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

</имя_тега>

Атрибуты тега записываются в следующем формате:

имя [= «значение»]

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

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

Последовательность символов, составляющая текст, может состоять из пробелов, табуляций, символов перехода на новую строку, символов возврата каретки, букв, знаков препинания, цифр, и специальных символов (например, +, #, $, @), за исключением следующих четырех символов, имеющих в HTML специальный смысл: < (меньше), > (больше), & (амперсенд) и " (двойная кавычка). Если необходимо включить в текст какой-либо из этих символов, то следует закодировать его особой последовательностью символов.

К специальным символам можно отнести и неразрывный пробел. Использование этого символа - один из способов увеличить расстояние между некоторыми словами в тексте. Обычные пробелы использовать для этих целей нельзя, так как группа подряд идущих пробелов интерпретируется браузером как один [3].

1.3 Классификация современных информационно-поисковых систем

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

Поисковые каталоги

Для того, чтобы как-то упростить задачу навигации по существующим ресурсам, были созданы системы, названные поисковыми каталогами или просто каталогами. Яркими представителями поисковых каталогов на Западе являются Yahoo и Open Directory, в России Mavica.net, List.ru, в Украине - Topping, UaPortal и др.

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

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

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

Полнотекстовые поисковые системы

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

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

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

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

- интерпретация операций, зависящих от порядка расположения слов в тексте (операций контекстной близости слов и др.);

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

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

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

Метапоисковые системы

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

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

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

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

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

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

Несмотря на очевидные преимущества систем метапоиска, и они не лишены существенных недостатков, среди которых очень большое время поиска. Пользователям приходится долго ожидать, пока метапоисковая система опросит каждую полнотекстовую систему и на основании полученных результатов поиска сформирует собственные, наиболее удовлетворяющие, с ее точки зрения, потребностям пользователя [4].

1.4 Описание механизма поиска информационно-поисковых систем

информационный поисковый система робот

Состав поисковых систем

Поисковые системы обычно состоят из трех компонентов:

- агент (паук или кроулер), который перемещается по Сети и собирает информацию;

- база данных, которая содержит всю информацию, собираемую пауками;

- поисковый механизм, который люди используют как интерфейс для взаимодействия с базой данных [5].

Принципы работы поисковых систем

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

Для простоты восприятия информации о классификации поисковых систем была составлена следующая схема, изображенная на рисунке 1.1:

Рисунок 1.1 - Схема классификации поисковых систем.

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

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

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

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

Основное отличие поисковых систем (зона D) от каталогов - автоматический «робот», или «паук», который постоянно сканирует Internet, ищет в нем новые сайты, накапливает эту информацию в индексных файлах базы данных. Информация в Internet-каталоги, так же как в традиционные библиотечные, заносится либо авторами новых сайтов, либо обслуживающим персоналом каталога. Пользование поисковыми системами и каталогами абсолютно бесплатно, вот почему в настоящее время это самый доступный и демократичный вид информационных ресурсов [6].

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

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

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

Кроулеры просматривают заголовки и возвращают только первую ссылку.

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

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

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

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

Когда кто-либо хочет найти информацию, доступную в Интернет, он посещает страницу поисковой системы и заполняет форму, детализирующую информацию, которая ему необходима. Здесь могут использоваться ключевые слова, даты и другие критерии. Критерии в форме поиска должны соответствовать критериям, используемым агентами при индексации информации, которую они нашли при перемещении по Сети [7].

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

1. Количество слов запроса в текстовом содержимом документа (т.е. в html-коде).

2. Тэги, в которых эти слова располагаются.

3. Местоположение искомых слов в документе.

4. Удельный вес слов, относительно которых определяется релевантность, в общем количестве слов документа. Эти принципы применяются всеми поисковыми системами. А представленные ниже используются некоторыми, но достаточно известными (вроде AltaVista, HotBot).

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

6. Индекс цитируемости - как много ссылок на данную страницу ведет с других страниц, зарегистрированных в базе поисковика.

База данных выводит ранжированный подобным образом список документов с HTML и возвращает его человеку, сделавшему запрос. Различные поисковые механизмы также выбирают различные способы показа полученного списка - некоторые показывают только ссылки; другие выводят ссылки с первыми несколькими предложениями, содержащимися в документе или заголовок документа вместе со ссылкой.

Когда происходит переход по ссылке к одному из документов, который интересует пользователя, этот документ запрашивается у того сервера, на котором он находится [7, с. 20].

Алгоритмы поиска

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

Некоторые из этих закономерностей были подмечены Джорджем Зипфом (George К. Zipf); он опубликовал свои законы в 1949 году. Пять лет спустя знаменитый математик Беноит Мандлеброт (Benoit Mandlebrot) внес небольшие изменения в формулы Зипфа. добившись более точного соответствия теории практике. Хотя некоторые исследователи и подвергают исследования Зипфа острой критике, без учета подмеченных им закономерностей сегодня не способна работать ни одна система автоматического поиска информации.

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

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

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

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

Это также означает, что самое популярное слово в английском языке (the) употребляется в 10 раз чаще, чем слово, стоящее на десятом месте, в 100 раз чаще, чем сотое, и в 1000 раз чаще, чем тысячное.

Значение вышеупомянутой постоянной в разных языках различно, но внутри одной языковой группы она остается неизменной. Так, например, для английских текстов постоянная Зипфа равна приблизительно 0,1. Для русского языка постоянная Зипфа равна примерно 0,06-0,07.

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

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

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

С другой стороны, каждый Web-сайт получает большую часть посетителей, пришедших по гиперссылкам из небольшого количества сайтов, а из всего остального Web-пространства на него приходит лишь небольшая часть посетителей. Таким образом, объем входящего трафика от ссылающихся Web-сайтов также подчиняется распределению Зипфа.

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

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

Чтобы испытать свою разработку, ученый решил проанализировать тексты всех президентских докладов о положении в США (State of the Union addresses) начиная с 1790 года. В итоге получилось, что в период Войны за независимость американских колоний часто употреблялись слова militia («ополчение») и British («британский»), а в период с 1947 по 1959 годы наблюдался «скачок» в использовании слова atomic («атомный»). Таким образом, ученому удалось доказать работоспособность системы [8].

Использование закона Зипфа поисковыми машинами

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

Можно предположить, что наиболее значимые для текста слова лежат в средней части представленного графика. Оно и понятно: слова, которые встречаются слишком часто,-это предлоги, местоимения и т.д. (в английском, немецком и некоторых других языках-еще и артикли). Редко встречающиеся слова также в большинстве случаев не несут особого смыслового значения, хотя иногда, наоборот, весьма важны для текста (об этом будет сказано чуть ниже). Каждая поисковая система решает, какие слова отнести к наиболее значимым, по-своему, руководствуясь общим объемом текста, частотными словарями и т.п. Если к числу значимых слов будут отнесены слишком многие, важные термины будут забиты «шумом» случайных слов. Если диапазон значимых слов будет установлен слишком узким, за его пределами окажутся термины, несущие основную смысловую нагрузку.

Для того чтобы безошибочно сузить диапазон значимых слов, создается словарь «бесполезных» слов, так называемых стоп-слов (а словарь, соответственно, называется стоп-лист). Например, для английского текста стоп-словами станут артикли и предлоги the, a, an, in, to, of, and, that... и др. Для русского текста в стоп-лист могли бы быть включены все предлоги, частицы и личные местоимения: на, не, для, это, я, ты, он, она и др.

Исключение стоп-слов из индекса ведет к его существенному сокращению и повышению эффективности работы. Однако некоторые запросы, состоящие только из стоп-слов (типа «to be or not to be»), в этих случаях уже не пройдут. Неудобство вызывают и некоторые случаи полисемии (многозначности слова в зависимости от контекста). Например, в одних случаях английское слово «can» как вспомогательный глагол должно быть включено в список стоп-слов, однако как существительное оно часто несет большую содержательную нагрузку.

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

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

Пространственно-векторная модель поисковой системы

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

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

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

1.5 Поисковые роботы

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

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

Использование поисковых роботов

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

Статистический анализ

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

Обслуживание гипертекстов

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

Робот типа MOMSPIDER, который проверяет ссылки, может помочь автору документа в обнаружении подобных мертвых ссылок, и также может помогать в обслуживании гипертекстовой структуры. Также роботы могут помочь в поддержании содержания и самой структуры, проверяя соответствующий HTML-документ, его соответствие принятым правилам, регулярные модернизации, и т.д., но это обычно не используется. Возможно, данные функциональные возможности должны были бы быть встроены при написании окружающей среды HTML-документа, поскольку эти проверки могут повторяться в тех случаях, когда документ изменяется, и любые проблемы при этом могут быть решены немедленно [11].

Зазеркаливание

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

Исследование ресурсов

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

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

Комбинированное использование

Простой робот может выполнять более чем одну из вышеупомянутых задач. Например робот RBSE Spider выполняет статистический анализ запрошенных документов и обеспечивает ведение базы данных ресурсов. Однако, подобное комбинированное использование встречается, к сожалению, весьма редко.

Повышение затрат и потенциальные опасности при использовании поисковых роботов

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

Сетевой ресурс и загрузка сервера

Роботы требуют значительной пропускной способности канала сервера. Во-первых роботы работают непрерывно в течение длительных периодов времени, часто даже в течение месяцев. Чтобы ускорить операции, многие роботы делают параллельные запросы страниц с сервера, ведущие в последствии к повышенному использованию пропускной способности канала сервера. Даже удаленные части Сети могут чувствовать сетевую нагрузку на ресурс, если робот делает большое количество запросов за короткий промежуток времени. Это может привести к временной нехватке пропускной способности сервера для других пользователей, особенно на серверах с низкой пропускной способностью, поскольку Интернет не имеет никаких средств для балансирования нагрузки в зависимости от используемого протокола.

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

Помимо предъявления требований к Сети, робот также предъявляет дополнительные требования к самому серверу. В зависимости от частоты, с которой он запрашивает документы с сервера, это может привести к значительной загрузке всего сервера и снижению скорости доступа других пользователей, обращающихся к серверу. К тому же, если главный компьютер используется также для других целей, это может быть вообще неприемлемо. В качестве эксперимента автор управлял моделированием 20 параллельных запросов от своего сервера, функционирующего как Plexus сервер на Sun 4/330. Несколько минут машину, замедленную использованием паука, вообще невозможно было использовать. Этот эффект можно почувствовать даже последовательно запрашивая страницы.

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

Обновление документов

Как уже было упомянуто, базы данных, создаваемые роботами, могут автоматически обновляться. К сожалению, до сих пор не имеется никаких эффективных механизмов контроля за изменениями, происходящими в Сети. Более того, нет даже простого запроса, который мог бы определить, которая из ссылок была удалена, перемещена или изменена. Протокол HTTP обеспечивает механизм "If-Modified-Since", посредством которого агент пользователя может определить время модификации кэшированного документа одновременно с запросом самого документа. Если документ был изменен, тогда сервер передаст только его содержимое, так как этот документ уже был прокэширован.

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

Роботы / агенты клиента

Загрузка Сети является особой проблемой, связанной с применением категории роботов, которые используются конечными пользователями и реализованы как часть веб-клиента общего назначения (например, Fish Search и tkWWW робот). Одной из особенностей, которая является обычной для этих роботов, является способность передавать обнаруженную информацию поисковым системам при перемещении по Сети. Это преподносится как усовершенствование методов исследования ресурсов, так как запросы к нескольким удаленным базам данных осуществляются автоматически. Однако, по мнению автора, это неприемлемо по двум причинам. Во-первых, операция поиска приводит к большей загрузке сервера, чем даже простой запрос документа, поэтому обычному пользователю могут быть причинены значительные неудобства при работе на нескольких серверах с большими издержками, чем обычно. Во-вторых, ошибочно предполагать, что одни и те же ключевые слова при поиске одинаково релевантны, синтаксически правильны, не говоря уже об оптимальности для различных баз данных, и диапазон баз данных полностью скрыт от пользователя. Например, запрос " Форд и гараж " мог бы быть послан базе данных, хранящей литературу 17-ого столетия, базе данных, которая не поддерживает булевские операторы или базе данных, которая определяет, что запросы относительно автомобилей должны начаться со слова "автомобиль: ". И пользователь даже не знает это.

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

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

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

"Интеллектуальные агенты" и " цифровые помощники", предназначенные для использования конечным пользователем, который ищет информацию в Интернет, являются в настоящее время популярной темой исследований в компьютерной науке, и часто рассматриваются как будущее Сети. В то же время это действительно может иметь место, и уже очевидно, что автоматизация неоценима для исследований ресурсов, хотя требуется проводить еще больше исследований для того, чтобы их сделать их использование эффективным. Простые управляемые пользователем роботы очень далеки от интеллектуальных сетевых агентов: агент должен иметь некоторое представление о том, где найти определенную информацию (то есть какие услуги использовать) вместо того, чтобы искать ее вслепую. Рассмотрим ситуацию, когда человек ищет книжный магазин; он использует "Желтые страницы" для области, в которой он проживает, находит список магазинов, выбирает из них один или несколько, и посещает их. Клиентский робот шел бы во все магазины в области, спрашивая о книгах. В Сети, как и в реальной жизни, это неэффективно в малом масштабе, и совсем должно быть запрещено в больших масштабах.