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

Fi SEARCH - Windows Internet Explorer

h«p:№ww*.benran.ru,'Zgw/Ep:gi e

Поиск в отмеченных источниках данных

Гчмш.: *»«■««■« _Утаж.

сея}ха;

- //aVO-IUHWli

_ tun списки

Ф'грмст; ■ . . номер колыч*стео.

^r smtoetiMHX летев: *

запаси.

Результат поиска по запросу'

3S

p<ero i: wccc-, нацмен; 36 :-a<\|f.

{i PRTSfNJ Windows internet Explorer

- £ httf j'^/j^w .benran.gi.f..

^PRESENT

j_ -lot-'K i ГЛСПЧ-

www.benran.ru ^a-ii- contralTdev.-ifier (JJS RA.S! 'J451S1

placeOfFufclicsti.oi,- "JSA

d«teOfFuk-ii.c»Civ-a: 2005 2C04, iOOi ZO'J? 20C1 2000 1399 1996 1&Ч4 1993, 193: 199Q

i бозе^з'- ->a hoick

Рис. 7.15. Фрагмент диалога с WAlS-серверами с использованием шлюза

(окончание):

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

Прежде чем описать проблемы построения информацион- но-поисковых систем Web и пути их решения, рассмотрим типовую структуру такой системы. В различных публикациях, посвященных конкретным системам, приводятся схемы, которые отличаются друг от друга только применением конкретных программных решений, но не принципом организации различных компонентов системы. Поэтому рассмотрим эту схему (рис. 7.16) на примере, представлен­ном в работе [28], где:

User Client — программа просмотра конкретного информаци­онного ресурса. В настоящее время наиболее популярны мульти- протокольные программы типа Netscape Navigator, MS Internet Explorer. Такая программа обеспечивает просмотр документов World Wide Web, Gopher, WAIS, FTP-архивов, почтовых списков рассылки и групп новостей Usenet. В свою очередь все эти ин­формационные ресурсы являются объектом поиска ИПС;

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

Search Engine — поисковая машина — служит для трансля­ции запроса пользователя, который подготавливается на инфор­мационно-поисковом языке (ИПЯ), в формальный запрос сис­темы, поиска ссылок на информационные ресурсы сети и выда­чи результатов этого поиска пользователю;

Рис. 7.16. Структура ИПС для Internet

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

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

Spider (Index Robot) — робот-индексировщик — служит для сканирования Internet и поддержки базы данных индекса в акту­альном состоянии. Эта программа является основным источни­ком информации о состоянии информационных ресурсов сети;

Web Sites — это те информационные ресурсы, доступ к кото­рым обеспечивает ИПС.

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

Как видно из рис. 7.16, первичным документальным массивом ИПС Internet является все множество документов следующих ос­новных типов: HTML-страницы, Gopher-файлы, документы WAIS, записи архивов FTP, новости Usenet, статьи почтовых спи­сков рассылки. Все это довольно разнородная информация, кото­рая представлена в виде различных, никак не согласованных друг с другом форматов данных. Здесь есть текстовая, графическая, ау­диоинформация и вообще все, что может быть в указанных выше типах хранилищ. Естественно, возникает вопрос, как информа- ционно-поисковая система должна со всем этим работать.

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

Если быть более точным, то документу приписывается век­тор, размерность которого равна числу терминов, которыми можно воспользоваться при поиске. При булевой векторной мо­дели элемент вектора равен 1 или 0, в зависимости от наличия или отсутствия термина в ПОДе документа. В более сложных моделях термины взвешиваются, т. е. элемент вектора равен не 1 или 0, а некоторому числу, которое отражает соответствие дан­ного термина документу. Именно последняя модель наиболее популярна в информационно-поисковых системах Internet. Су­ществуют и другие модели описания документов — вероятност­ная модель информационных потоков и поиска, модель поиска в нечетких множествах. Анализ преимуществ и недостатков при­менения этих моделей при реализации информационно-поиско­вых систем в Internet — это тема специального исследования. Здесь имеет смысл обратить внимание читателя лишь на то, что пока именно линейная модель применяется в системах Lycos, WebCrawler, AltaVista, OpenText, AliWeb и ряде других. Исследо­вания по применению других моделей также ведутся, например в рамках проекта AltaVista.

Таким образом, первая задача,которую должна решить ин- формационно-поисковая система, — это приписывание списка ключевых слов документу или информационному ресурсу. Имен­но эта процедура и называется индексированием.

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

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

Теперь представим себе трудности такой процедуры в ди­намичной среде Internet, где ресурсы постоянно появляются и исчезают. При создании программы Veronica для поиска в GopherSpace предполагалось, что все серверы должны быть за­регистрированы, и таким образом велся учет наличия или отсут­ствия ресурса. Veronica раз в месяц проверяла наличие докумен­тов Gopher и обновляла свою базу данных поисковых образов документов Gopher.

В World Wide Web ничего подобного нет. Для решения этой задачи используются программы сканирования сети или робо- ты-индексировщики. Разработка роботов — довольно нетриви­альная задача, поскольку существует опасность зацикливания ро­бота или попадания на виртуальные страницы. Все системы име­ют своего робота, который просматривает сеть, находит новые ресурсы, приписывает им термины и помещает в базу данных индекса. Главная проблема заключается в том, чтобы определить, какие термины приписывать документам, откуда их брать, ведь ряд ресурсов вообще не является текстом. В настоящее время различные роботы используют для индексирования следующие источники для пополнения своих виртуальных словарей:

• гипертекстовые ссылки;

• заголовки (title);

• заглавия (HI, Н2и т. п.);

• аннотации;

• списки ключевых слов;

• полные тексты документов;

• сообщения администраторов о своих Web-страницах.

Для индексирования Telnet, Gopher, FTP, нетекстовой ин­формации используются главным образом URL, для новостей Usenet и почтовых списков — поля Subjectи Keywords.Наи­больший простор для построения ПОДов дают HTML-доку­менты.

Однако не следует думать, что все термины из перечислен­ных выше элементов документов попадают в их поисковые об­разы. Очень активно применяются списки запрещенных слов (stop-words) и общих слов(предлоги, союзы и т. п.), которые не могут быть использованы для индексирования, кроме того, час­то производится нормализация лексики. Таким образом, даже то, что в OpenText, например, называется полнотекстовым ин­дексированием,реально является выбором слов из текста доку­мента и результатом сравнения с целым набором различных словарей, после чего термин попадает в поисковый образ доку­мента, а потом и в индекс системы. Для того чтобы не раздувать словарей и индексов (а индекс Lycos, например, равен 4 Тбайт), применяется такое понятие, как «вес» термина. Документ обыч­но индексируется списком от 40 до 100 наиболее значимых тер­минов.

Поисковый аппарат. После того как ресурсы заиндексирова- ны, т. е. система составила массив поисковых образов, начинает­ся построение поискового аппарата системы.Совершенно оче­видно, что лобовой просмотр файла или файлов ПОДов займет много времени, что абсолютно неприемлемо для интерактивной системы, которой является Web. Для того чтобы можно было бы­стро находить информацию, в базе данных ПОДов строится ин­декс. Индекс в большинстве систем — система связанных между собой файлов, которая нацелена на быстрый поиск данных по за­просу пользователя. Структура и состав индексов различных сис­тем могут отличаться друг от друга и зависят от многих факторов. К этим факторам можно отнести и размер массива поисковых об­разов, и информационно-поисковый язык системы, и размеще­ние различных компонентов системы, и т. п. Рассмотрим структу­ру индекса, приведенную в [28]. Этот проект выбран потому, что он позволяет не только выполнять булевский поиск, контекстный поиск и взвешенный поиск, но и реализовывать ряд других воз­можностей, которые отсутствуют во многих поисковых системах.

Индекс рассматриваемой системы состоит из таблицы иден­тификаторов страниц (Page-ID),таблицы ключевых слов(Keyword-ID),таблицы модификации страниц, таблицы заго­ловков, таблицы гипертекстовых связей, инвертированного спи­ска (IL)и прямого списка (FL).

Page-idотображает идентификаторы страниц в URL этих страниц, Keyword-ID— каждое ключевое слово в уникальный идентификатор этого слова, таблица заголовков — идентифика­тор страницы в заголовок страницы, таблица гипертекстовых ссылок — идентификатор страниц в гипертекстовую ссылку на эту страницу. Инвертированный список ставит в соответствие ка­ждому ключевому слову список пар (номер документа, идентифи­катор страницы, позиция слова в странице). Прямой список — это массив поисковых образов страниц. Все эти файлы так или иначе используются при поиске, но главным среди них, безуслов­но, является файл инвертированного списка. Результат поиска в этом файле — это объединение и/или пересечение списков иден­тификаторов страниц. Результирующий список, который преоб­разовывается в список заголовков, снабженных гипертекстовыми ссылками, возвращается пользователю в его программу просмот­ра Web.

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

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

Информационно-поисковый язык системы. Однако индекс — это только часть поискового аппарата, причем скрытая от поль­зователя. Второй частью этого аппарата является информацион­но-поисковый язык. ИПЯ позволяет сформулировать запрос к системе в довольно простой и доходчивой форме. Уже давно ос­талась позади романтика создания ИПЯ как естественного язы­ка. Именно этот подход использовался в системе WAIS на пер­вых стадиях ее реализации. Если даже пользователю предлагает­ся вводить запросы на естественном языке, то это не значит, что система будет осуществлять семантический разбор запроса поль­зователя. Обычно фраза разбивается на слова, из этого списка удаляются запрещенные и общие слова, иногда производится нормализация лексики, а затем все слова связываются либо ло­гическим and, либо or.Таким образом, запрос типа

>Software that is used on Unix Platform

будет преобразован в:

>Unix AND Platform AND Software

что будет означать примерно следующее: «Найти все документы, в которых слова Unix, Platform и Software встречаются одновременно».

Возможны и варианты. Так, в большинстве систем фраза «Unix Platform» будет опознана как ключевая и не будет разде­ляться на отдельные слова. Другой подход заключается в вычис­лении меры близости между запросом и документом. Именно этот подход используется, например, в Lycos. В этом случае мера близости вычисляется в соответствии с векторной моделью представления документов и запросов. К настоящему времени известно около дюжины различных мер близости. Наиболее час­то применяется косинус угла между поисковым образом доку­мента и запросом пользователя. Именно эта мера соответствия документа запросу и выдается в качестве справочной информа­ции при списке найденных документов.

Одним из наиболее развитых языков запросов современных информационно-поисковых систем Internet обладает AltaVista. Кроме обычного набора and, or, not, эта система позволяет ис­пользовать near. Последний оператор дает возможность органи­зовать контекстный поиск. Все документы в системе разбиты на поля, поэтому в запросе можно указать, в какой части документа пользователь хочет увидеть ключевое слово (в ссылке, заголовке и т. п.). Можно также задать поле ранжирования выдачи и кри­терий близости документов запросу.

Краткие характеристики АИПС для WWW-пространства

Lycos (http://mnr.lycos.com). Как и большинство систем, Lycos дает возможность использовать для работы с простым за­просом достаточно изощренный метод поиска. В простом запро­се в качестве поискового критерия вводится предложение на ес­тественном языке. Lycos производит нормализацию запроса, удаляя из него так называемые stop-слова, и только после этого приступает к его выполнению. Почти сразу выдается информа­ция о числе документов на каждое слово, а уже позже и список ссылок на формально релевантные документы. Релевантность — это мера соответствия найденного системой документа потреб­ности пользователя. В списке напротив каждого документа ука­зываются его мера близости запросу, число слов из запроса, ко­торые попали в документ, и оценочная мера близости, которая может быть больше или меньше формально вычисленной. Нель­зя вводить операторы в строке вместе с терминами, но использо­вать логику через систему меню Lycos позволяет. Это относится к расширенной форме запроса, предназначенной для использо­вания искушенными пользователями системы, которые уже нау­чились пользоваться этим механизмом.

Таким образом, мы видим, что Lycos относится к системе с языком запросов типа «Like this», но предполагается его расши­рение и на другие способы организации поисковых предписаний.

AltaVista (http://www.altavista.digital.com). С точки зрения информационно-поискового языка наиболее интересным в AltaVista является возможность расширенного поиска. Здесь стоит сразу выделить, что в отличие от многих систем AltaVista поддерживает одноместный оператор not. Кроме того, есть еще и оператор near, который реализует возможность контекстного поиска, когда термины должны располагаться рядом в тексте до­кумента. AltaVista разрешает поиск по ключевым фразам, при этом она имеет довольно большой словарь этих фраз. Помимо всего прочего при поиске в AltaVista можно задать имя поля, где должно встретиться слово. Это может быть гипертекстовая ссыл­ка, апплет, название образа, заголовок и ряд других полей. Ре­ально эту систему можно отнести к системе с расширенным бу­левым поиском.

Yahoo. Данная система появилась в сети одной из первых. В настоящее время Yahoo сотрудничает со многими производи­телями средств информационного поиска, и на различных ее серверах используется различное программное обеспечение. На взгляд авторов, это самая незатейливая информационная служ­ба, которая сосредоточилась на информации о Web как таковой. ИПЯ Yahoo достаточно прост: все слова следует вводить через пробел, и они соединяются либо and, либо or.В результат поис­ка не включаются степени соответствия документа запросу, а только подчеркиваются слова из запроса, которые встретились в документе. При этом не производится нормализация лексики и не проводится анализ на «общие» слова. Хорошие результаты поиска получаются только тогда, когда пользователь знает, что информация в базе данных Yahoo точно имеется. Ранжирование производится по числу терминов запроса в документе. Yahoo от­носится к классу простых традиционных систем с ограниченны­ми возможностями поиска.

OpenText (http://index.opentext.net). Информационная система OpenText представляет собой самый коммерциализиро­ванный информационный продукт в сети. Все описания больше напоминают рекламу, чем реальное руководство по работе. Сис­тема позволяет провести поиск с использованием логических коннекторов, размер запроса ограничен тремя терминами или фразами. В данном случае речь идет о расширенном поиске. При выдаче результатов поиска сообщается степень соответст­вия документа запросу и размер документа. Система позволяет также улучшить результаты поиска в стиле традиционного буле- вого поиска.

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

InfoSeek (http://infoseek.com). Система InfoSeek обладает довольно развитым информационно-поисковым языком, кото­рый позволяет не просто указывать, какие термины должны встречаться в документах, но и своеобразно взвешивать их. До­стигается это с помощью специальных знаков: «+» — термин обязан быть в документе, «—о — термин обязан отсутствовать в документе. Помимо этого InfoSeek позволяет проводить то, что называется контекстным поиском. Это значит, что, используя специальную форму запроса, можно потребовать последователь­ной совместной встречаемости слов. Кроме того, можно указать, что некоторые слова должны совместно встречаться не только в одном документе, но и в отдельном параграфе или заголовке. Есть возможность и указания ключевых фраз. Ключевая фраза от последовательной встречаемости отличается тем, что фраза всегда ищется как единое целое, а при последовательной встре­чаемости слова могут стоять рядом, но в произвольном порядке. Ранжирование при выдаче осуществляется по числу терминов запроса в документе, по числу фраз запроса в документе, за вы­четом общих слов. Все эти факторы используются как вложен­ные процедуры.

Подводя краткое резюме, можно сказать, что InfoSeek отно­сится к традиционным системам с элементом взвешивания тер­минов при поиске.

Интерфейс системы. Важным фактором качества И ПС явля­ется вид представления информации в программе-интерфейсе. При этом различают два типа страниц: страницы запросов и страницы результатов поиска.

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

На схеме, представленной на рис. 7.13, есть так называемые сохраненные запросы пользователя. В большинстве систем это просто фраза на ИПЯ, которую можно расширить за счет добав­ления новых терминов и логических операторов. Но это только один тип использования сохраненных запросов. В традицион­ных системах это называется расширением или уточнением за­проса в зависимости от того, что получаем в результате преобра­зования запроса: увеличение размера выборки или ее сокраще­ние. При этом традиционная система хранит не запрос как таковой, а результат поиска,т. е. список идентификаторов доку­ментов, который объединяется/пересекается со списком, полу­ченным при поиске документов по новым терминам. К сожале­нию, возможность сохранения списка идентификаторов найден­ных документов в World Wide Web практически отсутствует, что связано с особенностью протоколов взаимодействия програм­мы-клиента и сервера системы, которые не поддерживают сеан­совый режим работы.

Как понятно из вышеизложенного, результат поиска в базе данных ИПС — это список указателей на удовлетворяющие за­просу документы. Различные системы представляют этот список по-разному. В некоторых системах выдается только список ссы­лок, а в таких системах, как Lycos, AltaVista, Yahoo, кроме ссы­лок, дается еще и краткое описание, которое заимствуется либо из заголовков, либо из тела самого документа. Кроме того, систе­ма сообщает степень близости документа запросу. В Yahoo, на­пример, сообщается, сколько терминов запроса содержится в по­исковом образе документа, и в соответствии с этим ранжируется результат поиска. В Lycos выдается мера соответствия документа запросу и ранжирование производится по этому параметру. Обычно пользователь имеет возможность уточнить запрос.

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

Кроме ссылок на документы в списке, полученном пользова­телем, могут оказаться ссылки на части документов или на их поля. Это происходит при наличии ссылок типа http:// host/path#markили ссылок по схеме WAIS. Возможны ссылки и на скрипты, но обычно такие ссылки роботы пропускают, и система не индексирует. Если с HTTP-ссылками все более или менее понятно, то ссылки WAIS — это гораздо более сложные объекты. Дело в том, что WAIS реализует архитектуру распреде­ленной информационно-поисковой системы. Это значит, что одна ИПС, например Lycos, строит поисковый аппарат над поис­ковым аппаратом другой системы — WAIS. При этом серверы WAIS имеют свои собственные локальные базы данных. При за­грузке документов в WAIS администратор может описать струк­туру документов, т. е. разбить их на поля, и хранить документы как один файл. Индекс WAIS будет ссылаться на отдельные доку­менты и их поля как на самостоятельные единицы хранения. В этом случае программа просмотра ресурсов Internet должна уметь работать с протоколом WAIS, чтобы получить доступ к этим документам.

Перечисленные возможности и поисковые технологии в до­статочной степени иллюстрируются далее на примере поисковых машин Yandex и Rambler.