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

Мы рассмотрим несколько современных проектов в области информационного поиска. Эти проекты можно разделить на две группы:

  • основные проекты, которые могут быть добавлены в любую коллекцию (INQUERY, SMART);
  • сетевые проекты, которые имеют дело с проблемами включения WWW, USENET и других аспектов Internet (Harvest).

    Рассмотрены способы представления документов, индексирования и поиска в этих системах. SMART и Harvest доступны в исходных кодах, для системы INQUERY предлагаются только демонстрационные версии и техническая документация.

    Система SMART (System for the Manipulation and Retrieval of Texts) - это экспериментальная автоматическая информационно-поисковая система, реализующая векторную модель информационного поиска. Основная задача SMART - обеспечение возможности проведения исследований в области систем информационного поиска с поддержкой стандартных процедур индексирования, поиска и оценки. В системе используются разнообразные методы автоматического анализа текстов и автоматического индексирования, например словари синонимов, иерархическое упорядочивание терминов, статистические и синтаксические методы получения словосочетаний. Система разрабатывалась как максимально гибкая, поэтому она не настроена на какое-либо конкретное обеспечение, имеет достаточно простой исходный код и может работать (с минимальными модификациями) практически на любой Unix-платформе.

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

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

    Предполагается существование набора документов в оперативном режиме (on-line). Потенциально любой документ содержит несколько различных типов информации. Возможно включение: даты публикации, автора документа, получателя документа, списка ключевых слов, места документа внутри иерархии, названия, реферата, списка использованной литературы и др. Текст документа может содержать несколько типов дополнительной информации, например даты, имена собственные, время, числа. При выдаче документов на запрос может быть полезен каждый из этих типов информации. Чтобы их различать организуются типы классификации (classification type, ctype) для каждого понятия. Поисковый образ документа состоит из списка терминов, ctype и веса для каждого термина. Запросом пользователя может служить предложение естественного языка, список ключевых слов, пример релевантного документа. Система создает поисковый образ запроса. Это может быть просто список ключевых слов и их весов (как в поисковом образе документа) либо более сложные конструк ции. Информация отыскивается не в процессе точного сравнения, ведущего к выдаче всех документов, которые в точности соответствуют поисковому образу запроса, а посредством метода сравнения векторов, когда для каждой заданной пары "запрос-документ" подсчитывается значение некоторого коэффициента подобия. Это дает возможность ранжировать выданные документы в порядке убывания "запрос-документ", а также выдавать нужное число документов в зависимости от требований отдельных пользователей. Результаты выдачи оцениваются в терминах полноты и точности. В системе SMART выбран метод изменения запросов, известный под названием "обратная связь по релевантности". Небольшое количество документов, наиболее полно отвечающих запросу, выдается пользователю, который, в свою очередь, должен разделить их на релевантные, т. е. отвечающие его информационной потребности, и нерелевантные. Эти оценки релевантности возвращаются в систему и автоматически используются для изменения запросов таким образом, что бы термины запросов, присутствующие в релевантных документах, "продвигались" (путем увеличения их веса), а термины, присутствующие в нерелевантных документах, одновременно понижались. В дальнейшем термины из релевантных документов добавляются в запрос, а термины из нерелевантных - удаляются. Таким образом формулируется новый запрос, предположительно более схожий с релевантными, чем первоначальный. Система может быть получена по адресу: ftp://ftp.cs.cornell.edu/pub/smart/.

    INQUERY

    Эта система, разработанная CIIR (Center for Intelligent Information Retrieval) Массачусетского университета, использует сетевую архитектуру Байеса. Она состоит из двух частей: сети документов и сети запросов. Сеть документов статична для данной коллекции. Элементы, представляющие документы, соединены с элементами, представляющими термины; для данного документа вычисляется вероятность того, что конкретный термин описывает тематику документа. В сети запросов термины запроса соединяются в узлы, представляющие, как эти термины могут быть объединены (например, вероятность AND - это результат произведения отдельных вероятностей каждого термина узла). Эти узлы могут быть объединены для представления информационной потребности пользователя. В процессе поиска система соединяет сеть документов и сеть запросов и вычисляет условную вероятность того, что информационная потребность удовлетворяется каждым данным документом. Затем документы ранжируются по вероятности. Возможно модифицирование и ретрозапросов, и постоянно действующих запросов (коррекция по релевантности и маршрутизация (routing) соответственно). Реализованная в INQUERY сетевая модель вывода (inference net model) поддерживает поиск, основанный на комбинировании данных. Различные представления текста (такие, как слова, словосочетания, параграфы или выделенные вручную ключевые слова) и различные версии запроса (на естественном языке или в выражениях булевой алгебры) могут быть объединены в последовательную вероятностную структуру.

    INQUERY состоит из 5 подсистем: индексирования документов, выделения слов, близких терминам запроса (WORDFINDER), обработки и оценки запросов, обратной связи по релевантности (и маршрутизации).

    В процессе индексирования проводится:

  • анализ структуры документа - определение начала и конца документа, а также и начала и конца каждого текстового сегмента;
  • лексический и синтаксический анализ - определение границ слов, выделение стоп-слов и основ слов;
  • распознавание некоторых собственных имен: городов США, стран, названий компаний, фамилий и имен.

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

    Запросы в INQUERY можно вводить как на естественном языке, так и на языке запросов системы (или их комбинации). Текст запроса преобразуется в строчные буквы, определяются стоп-слова и основы слов, к каждому термину запроса добавляется оператор #SUM. Ниже приведен пример автоматически организованного запроса:

    #WSUM
    ( 1.0 !Terms from !title? field:
    2.0 #UW50 ( Control of Insider Trading )
    2.0 #PHRASE ( #USA Control ) 5.0
    #PHRASE ( Insider Trading )
    ! Terms from !con? field:
    2.0 #PHRASE( securities law) 2.0 bill 2.0 
    egislation 2.0 regulation
    2.0 rule 2.0 #3( Insider Trading
    Sanctions Act)
    2.0 #3( Insider Trading and Securities
    Fraud Enforcement Act )
     2.0 #3( Securities and Exchange
    Commission) 2.0 SEC
    2.0 #3(Commodity Futures Trading
    Commission) 2.0 CFTC
    2.0 #3( National Association of Securities Dealers) NASD
    ! Terms from !desc? field:
    1.0 proposed 1.0 enacted 1.0 changes 1.0 #PHRASE ( #USA laws )
    1.0 regulations 1.0 designed 1.0 prevent
    2.0 #NOT(#FOREIGNCOUNTRY) )

    После формирования сети запросов подсистема поиска ранжирует документы по вероятности их релевантности запросу. Вероятности соответствия узла запросу вычисляются как произведение частоты встречаемости термина в отдельных документах и обратной документной частоты. Значения нормализуются и могут быть изменены пользователем при запуске программы. В INQUERY реализована возможность автоматической коррекции запроса на основании обратной связи по релевантности: системой выбираются из релевантных документов термины, которые затем добавляются в запрос; затем все термины в запросе заново взвешиваются. Информацию о системе можно получить по адресу: http://ciir.cs.umass.edu/inqueryhomepage.html.

    Harvest

    Система Harvest реализует эффективные средства сбора и индексирования информации, поддерживает различные типы индексов, позволяющие учитывать особенности каждого массива информации, обеспечивает кэширование найденной информации и репликацию индексов. Состоит из подсистем: Gatherer (Сумматор), Broker (Брокер), Index/Search (Индексирование/Поиск) , Replicator (Репликатор), Object Cache (Кэш объектов). Эффективность системы обеспечивается комбинацией оптимизируемого программного обеспечения сбора и гибкой схемы распространения собранной информации между индексами. Сумматор собирает индексируемую информацию, а Брокер предлагает интерфейс запроса к собранным данным. Сумматор и Брокер используют для общения протокол значений атрибутов Summary Object Interchange Format (SOIF) и могут быть организованы различными способами, что обеспечивает гибкость и эффективное применение сети и серверов.

    На рис.1 представлена архитектура Harvest. Подсистема Сумматор обеспечивает эффективный и оптимизируемый способ сбора индексируемой информации. Данные могут собираться локально (это более эффективно, но требует кооперации машин) или удаленно (сбор информации осуществляется по стандартным протоколам FTP/Gopher/ HTTP). Пользователи могут определить способ сбора информации (локальный или удаленный); способ и тип представления данных, а также какие данные будут представлены в содержании и как они будут выбираться. Сумматор периодически сканирует объекты, управляет кэшированием индексируемой информации.

    Брокер обеспечивает индексно-независимый интерфейс, который может быть легко настроен для включения новых индексов. Подсистема запрашивает информацию от одной или нескольких подсистем-Сумматоров или других Брокеров и постоянно обновляет индексы. Брокер сохраняет уникальный идентификатор, а также "время жизни" каждого индексируемого объекта, выбрасывает старую информацию и вызывает подсистему поиска, когда получает запрос на новый поиск или обновление. Подсистема может быть сконфигурирована для прекращения и повторного сбора информации от определенных Сумматоров. Система Harvest регистрирует информацию о каждой Сумматоров, Брокеров, Кэшей и Репликаторов в Internet с помощью Harvest Server Registry (HSR). Последний используется при создании новых Сумматоров или Брокеров для исключения дублирования работы; при обращении к конкретному Брокеру во время поиска; при размещении Кэшей и Репликаторов. В Брокере применяются различные типы запросов, наличие той или иной возможности обусловлено выбранной пои сковой машиной. Сегодня наиболее мощная (и широко распространенная) из них Glimpse. Glimpse (GLobal IMPlicit Search) - это система индексирования, которая проводит быстрый поиск как в персональной файловой системе, так и среди больших массивов данных. Поисковая машина Glimpse состоит из нескольких программ. Из них наиболее важные это glimpse (программа поиска), glimpseindex (программа индексирования), agrep и glimpseserver (сервер поисковой машины Glimpse). Glimpse поддерживает три типа индексов: очень маленький (2-3% размера всех файлов), маленький (7-9%) и средний (20-30%). Чем больше индекс, тем быстрее поиск. Для большинства приложений оптимальным представляется выбор маленького индекса (glimpseindex -o). Glimpse поддерживает большинство опций команды agrep (agrep - более мощная версия grep и стандартная часть glimpse), включая приблизительное совпадение (обнаружение слов с ошибками), булевы запросы и некоторые ограниченные формы регулярных выражений. WebGlimpse добавляет поисковые возможности к Website: помещает маленькую кнопку вниз каждой HTML-страницы и позволяет проводить поиск среди соседей по странице или по всему серверу.

    Информация о системе может быть получена по адресу: http://glimpse.cs.arizona.edu:1994/.

    В Glimpse поддерживаются запросы с учетом регистра символов или без учета регистра символов; возможность поиска по части слова, целому слову или словосочетанию (например, "информационный поиск"); булевы операторы AND/OR; приблизительное написание ключевых слов (если неизвестно точное написание слова); структурированные запросы; возможность показывать только соответствующие строки или целые найденные записи (скажем, для цитат); возможность ограничения числа возвращенных строк; ограниченная форма регулярных выражений (например, при поиске по приставке или суффиксу). Структурированный запрос имеет форму: tag-name : value, где tag-name - имя атрибута, а value - искомое значение (список атрибутов см. ниже). Для формирования сложных запросов ключевые слова и структурированные запросы могут быть объединены с помощью булевых операторов И и ИЛИ. При отсутствии круглых скобок приоритет операций устанавливается слева направо. Словосочетания и регулярные выражения должны быть заключены в двойные кавычки, до пустим "фундаментальные исследования" или "исслед.*". Glimpse поддерживает некоторые типы регулярных выражений: ^joe соответствует "joe" в начале строки; joe$ - "joe" в конце строки; [a-ho-z] - любому символу между a и h и между o и z; . - любому одиночному символу, за исключением символа перевода строки; c* - нулю или большему количеству вхождений символа "c" ; * - любому числу символов расширения; * - символу " *". Использование регулярных выражений в запросе может значительно замедлить поиск. Регулярные выражения в настоящее время ограничены приблизительно 30 символами, не включая метасимволы. Регулярные выражения не пересекают границы слова (потому что в индекс заносятся только слова). Так, например, "lin. * lng" найдет "linking" или "flinching", но не "linear programming".

    Список основных атрибутов:

    Abstract - краткий реферат

    Author - автор

    Description - краткое описание

    Keywords - ключевые слова

    Last-Modification-Time - время последнего обновления

    Title - заголовок URL

    Подсистема поиска и индексирования - Harvest - определяет основной интерфейс Брокер-Индексатор, который может поддерживать различные поисковые машины, удовлетворяющие следующим основным требованиям: поддержка булевых запросов на атрибутах, поддержка обновлений. Сегодня в числе этих машин - WAIS, Glimpse и Nebula, в дальнейшем будут также включены Ingres и аудио-, видеопоисковые машины. Glimpse поддерживает эффективные по размеру и гибкие интерактивные запросы, Nebula обеспечивает быстрый поиск и сложные запросы (вместе с исходным кодом Harvest поставляется только Glimpse). Репликатор - Harvest работает со слабо связанной распределенной реплицируемой файловой системой mirror-d, одна из функций которой - копирование Брокера. Mirror-d построена поверх иерархической подсистемы групповых коммуникаций flood-d. Каждая система mirror-d периодически обменивается информацией с ближайшими соседями, чтобы определить, были ли неудачные обновления и почему. Подсистема может быть настроена на определенный уровень реплик ации, топологию и частоту обновлений. Кэш объектов - эта подсистема включена для уменьшения сетевого трафика. Кэш посылает дейтаграммы запроса всем соседям и родителям и запрашивает информацию с того сервера, который ответил первым. Подсистема кэширует Gopher-, HTTP- и FTP-объекты, а также последние DNS-соответствия. В Кэше могут быть настроены различные иерархические отношения между кэшами на различных уровнях сети, время ожидания, максимальный размер кэшируемых объектов. Система может быть получена по адресу: http://harvest.cs.colorado.edu/harvest/gettingsoftware.html.

    Заключение

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


    И. Кузина - сотрудница РНЦ "Курчатовский институт". С ней можно связаться по электронной почте по адресу: ira@citmgu.ru.

    Поделитесь материалом с коллегами и друзьями