Принципы текстового поиска

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

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

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

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

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

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

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

Хранящиеся в системе документы, которые соответствуют пользовательскому запросу, называются релевантными. Релевантность документа необязательно должна оцениваться в терминах двузначной логики («да-нет»). В ряде развитых систем используются более тонкие оценки, вычисляемые как значения специально подобранной числовой функции, которая принимает значения в интервале [0, 1 ]. В таких случаях уместно говорить о степени релевантности документа,понимая ее как значение этой функции.Можно также упорядочивать множества документов, полученных в результате обработки пользовательских запросов, по убыванию степени релевантности. Такое упорядочение найденных документов называют ранжированием.

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

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

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

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

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

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

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

индексированием по содержанию и индексированием по заголовкам документов.

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

поисковым образом документа.

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

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

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

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

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

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

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

Технически в системах рассматриваемого класса строится индекс по всем встречающимся в них словам и словосочетаниям, кроме стоп-слов. При этом для индексирования документа слова, выделенные из его текста с помощью поддерживаемых в системе словарей и грамматического разбора, приводятся сначала к «каноническому виду» — к единственному числу, именительному падежу, выделяются корни слов и т.п. Документ считается релевантным, если какие-либо слова или словосо-четания из запроса встречаются с точностью до грамматических форм в тексте документа. Иногда используется более жесткий критерий релевантности — вхождение в текст документа всех названных в запросе слов и словосочетаний и т.д. Нужно заметить, что идея использования слов из текста документа для его индексирования была предложена Г. Ланом (Н.Р. Luhn) в 1957 году.

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

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

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

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

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

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

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

В настоящее время существует два способа создания тезаурусов — вручную и автоматически. Тезаурус,созданный вручную,может быть универсальным,независимым от конкретной коллекции документов. Он может быть общеязыковым (например, тезаурус русского языка) или ориентированным на какую-либо предметную область. Лексика тезауруса может включать множество слов и/или фраз. В нем могут поддерживаться различные типы семантических связей между лексическими единицами: синонимы, антонимы, связи типа «целое-часть», «род-вид», «используется для»,«работает в» и т.д. Набор связей может быть зависимым или независимым от конкретной предметной области.

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

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

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

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

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

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

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

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

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

Первоначальная версия Дублинского ядра, которая включала 13 элементов, была предложена на состоявшемся в 1995 году в Дублине (США) симпозиуме,

организованном Online Computer Library Center (OCLC) и National Center for Supercomputing Applications (NCSA) для описания информационных ресурсов библиотечных систем, в частности информационных ресурсов Web и т.п. Развитие Дублинского ядра поддерживается специально учрежденной для этой цели организацией — Инициативой по метаданным Дублинского ядра (Dublin Core Metadata Initiative, DCMI).

Текущая версия спецификаций Дублинского ядра DC 1.1 была принята в качестве стандарта DCMI в июле 1999 года. Она включает 15 элементов метаданных. В настоящее время ведется работа как по уточнению этого состава набора элементов метаданных, так и по введению факультативных атрибутов (квалификаторов) для этих элементов метаданных, которые в конкретных областях применения уточняли бы их содержание и игнорировались в случае, когда приложение с ними «незнакомо». Некоторый предварительный список квалификаторов был принят в качестве рекомендации DCMI в июле 2000 года. Он содержит квали-фикаторы двух категорий: квалификаторы, которые уточняют семантику элементов метаданных ядра, и квалификаторы, определяющие способ кодирования значений его элементов, что позволяет адекватным образом их интерпретировать.

В качестве внешних атрибутов могут использоваться рубрики классификаторов

документов или элементы метаданных Дублинского ядра.

Дублинское ядро ( Dublin Core— DC ) —это набор элементов метаданных, смыслкоторых описан вербально и зафиксирован в спецификации определяющего его стандарта.

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

Дублинское ядро находит все более широкое распространение в последние годы.

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

Текущая версия спецификаций Дублинского ядра DC 1.1 была принята в качестве стандарта в 1999 г.

Она включает 15 элементов метаданных:

• Title (название ресурса);

• Creator (лицо,организация или служба,ответственные за подготовку содержанияресурса);

• Subject (тема,обсуждаемая в содержании ресурса);

• Description (описание содержания ресурса в свободной форме);

• Publisher (лицо,организация или служба,обеспечивающие доступ к ресурсу);

• Contributor (другие участники подготовки содержания ресурса помимо указанного в

Creator);

• Date (дата создания или предоставления доступа к ресурсу);

• Туре (жанр,категория или другие характеристики природы ресурса);

• Format (характер представления ресурса);

• Identifier (точная ссылка на ресурс);

• Source (ссылка на источник,из которого продуцирован данный ресурс);

• Language (язык представления ресурса);

• Relation (ссылка на ресурс,связанный с данным);

• Coverage (область пространства,времени и т.д.,к которой относится содержаниересурса);

• Rights (права интеллектуальной собственности на ресурс и т.п.).

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

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

По этой причине в 2000 г. для Дублинского ядра DMCI была предложена концепция квалификаторов и опубликован их первоначальный состав.

Квалификаторы —это уточнители семантики элементов метаданных Дублинскогоядра и их значений в различных конкретных случаях их применения.

Например, для элемента Date можно указать, что имеется в виду время создания ресурса, время его доступности или время, в течение которого его содержание имеет силу, и т.д.

Для значения элемента Relation можно указать, что оно представлено в формате URL.

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

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

— это представление ее в форме тезауруса предметной области системы, как это было рассмотрено выше.

Для формального описания онтологии в развитых системах используются языки логики первого порядка. Они допускают возможности логического вывода.Довольно широкоераспространение получил для представления онтологии язык указанной категории KIF (Knowledge Interchange Format) [33], разработанный в начале 90-х годов в Лаборатории систем знаний (KSL) Стэнфордского университета. Первоначально он разрабатывался как формальный язык для обеспечения обмена знаниями между различными системами, основанными на знаниях.

На основе расширения языка KIF в той же лаборатории была создана исследовательская система Ontolingua [35, 43], поддерживающая формирование и представление онтологии в некотором каноническом формате, благодаря чему обеспечивается их совместное использование и/или переносимость в среды различных оперирующих с ними систем. Онтологию, заданную в каноническом формате, можно легко транслировать в разнообразные системы, использующие различный синтаксис для представления знаний и обладающие различными возможностями рассуждений.

Одной из последних разработок, посвященных созданию средств формального описания онтологии, является стандарт языка определения онтологии для информационных ресурсов Web — OWL (Web Ontology Language) [44, 45]. Работа над этим стандартом проводится Рабочей группой по онтологиям для Web консорциума W3C. Язык OWL ос-нован на логиках описаний (см. раздел 4.8). Он, несомненно, найдет применение в интеллектуальных системах поиска информационных ресурсов в среде Web второго поколения.