Основы технологий текстового поиска
Содержание
Введение
1. Основные понятия
2. Принципы текстового поиска
3.
Средства лингвистической
4. Модели поиска
Список
литературы
Введение
Обмен информацией в обществе осуществляется главным образом в текстовой форме. Поэтому не случайно, что весьма значительную долю информационных ресурсов современных информационных систем составляет текстовая информация. Разработкам эффективных технологий хранения, обработки и поиска текстовой информации стало уделяться большое внимание уже на ранних стадиях развития информационных систем. Активные исследования и практические разработки в этой области начались еще в 50-х годах прошлого века, с того времени, когда средства вычислительной техники обеспечили возможность ввода-вывода текстовой информации.
Среди информационных систем, имеющих дело с текстовой информацией, наиболее распространенными являются системы текстового поиска. Их задача заключается в том, чтобы находить в хранимой в компьютере коллекции текстовых документов на естественном языке такие документы, которые интересуют пользователя.
Первые автоматизированные
1.
Основные понятия
В зависимости от характера поддерживаемых информационных ресурсов информационно-поисковые системы было принято разделять на две категории: фактографические и документальные. Фактографические ИПС оперировали фактами, представленными в виде сущностей реального мира и их свойств, и позволяли находить сущности .
Документальные ИПС предназначены для хранения и поиска документов, содержащих тексты на естественных языках. Такие ИПС и представляют собой ранние системы текстового поиска.
Разрабатывавшиеся в этот период системы текстового поиска назывались дескрипторными ИПС. В таких системах содержание каждого текстового документа и пользовательских поисковых запросов описывается наборами слов или словосочетаний, называемых дескрипторами.
Одной из наиболее распространенных областей применения дескрипторных систем был библиографический поиск. В таких системах хранятся коллекции библиографических описаний документов, и система позволяет находить публикации заданного автора, публикации, выпущенные указанным издательством и/или вышедшие в некотором году и т.п.
В процессе развития средств вычислительной техники компьютеры обрели устройства внешней памяти прямого доступа достаточно большого объема, значительно повысилась производительность процессоров. Это позволило создать и практически использовать в документальных ИПС более совершенные технологии, называемые технологиями полнотекстового поиска.
Благодаря возможности хранения и обработки в таких системах полных текстов документов удалось в большой мере автоматизировать процессы лингвистического анализа и поиска документов. Были разработаны подходы к автоматизации составления ряда используемых при этом словарей и тезаурусов. В технологиях полнотекстового поиска важное место занимают статистические методы анализа документов.
В настоящее время перспективные разработки в рассматриваемой области концентрируются вокруг авторитетной международной конференции по текстовому поиску ТRЕС (Техt Retrieval Соnfегеnсе).
Активное развитие технологий текстового поиска и информационных потребностей пользователей стимулировали трансформацию ИПС из систем текстового поиска в системы более общего класса, которые имеют дело не только с текстовыми документами, но и с документами, содержащими информацию иной природы. В мультимедийных системах содержание их объектов поиска — документов — составляет сочетание информационных ресурсов, представленных в различных средах, — текстовых элементов, статических изображений, аудиоданных (музыкальные произведения, текст, произнесенный голосом, и т.п.), мультфильмов, видеоклипов и т.п.
В последние годы наряду с термином информационно-поисковая система (Information Retrieval System) стал употребляться термин система текстового поиска (Техt Search System или Техt Retrieval System).
Значительное место в технологиях текстового поиска занимает обработка естественного языка, т.е. компьютерное решение задач, связанных с пониманием, анализом, выполнением различных операций над текстами на естественном языке, а также с их генерацией. Этот класс задач относят к области искусственного интеллекта.
В
современных технологиях
Возникли такие совершенно новые направления, как обнаружение информации в глобальной компьютерной сети, текстовый поиск в Веб, мультиязыковой поиск.
Ресурсы современных вычислительных систем позволяют хранить огромные объемы информационных ресурсов в системах текстового поиска, осуществлять в них не только технические, но и алгоритмически сложные процедуры обработки хранимых коллекций документов — их классификацию, кластеризацию, глубинный анализ текстов, перевод документов с одного языка на другой и т.д.
Системы текстового поиска оказали значительное влияние на формирование специфического класса информационных систем, называемых системами управления документами. В таких системах важная роль отводится не только методам обработки естественного языка, созданным для работы с текстовыми документами, но и организации групповой разработки документов, их хранения, распространения и конечно же технологиям текстового поиска.
Сформировалась
индустрия коммерческого
Содержательное разнообразие такой информации на естественных языках довольно велико — это могут быть статьи, опубликованные в газетах и журналах, разнообразные технические руководства, отчеты, книги, диссертации, письма, законодательные акты и пр.
Основная единица информации в системах текстового поиска называется документом. Документ — это не юридическая сущность, а содержательно законченная идентифицируемая уникальным образом единица информации, представленная на каком-либо естественном языке.
Полнотекстовые системы текстового поиска оперируют электронными документами, т.е. документами, хранимыми в памяти компьютеров и доступными для автоматизированной обработки. Необходимо иметь документ в оцифрованном виде, т.е. в таком формате, что каждая литера текста этого документа программно-доступна. Представление текстового документа в оцифрованном виде может быть создано, например, с помощью:
• ввода содержания документа с клавиатуры с использованием какого-либо текстового редактора;
• сканирования его с бумажного носителя и использования программы распознавания оптических символов (Optikal Character Recognition – OCR);
• генерации текста программным путем распознавателями голоса или какими-либо другими способами.
Совокупность хранимых в системе документов по-разному называется в разных системах (поисковый массив, архив и т.п.). В последнее время для этой цели часто используется термин «коллекция документов». Каждая система текстового поиска, вообще говоря, может поддерживать несколько различных коллекций документов.
Документы хранятся в системе текстового поиска для того, чтобы удовлетворять информационные потребности пользователей. Представление информационных потребностей пользователя в форме, воспринимаемой программным обеспечением системы текстового поиска, называется пользовательским запросом (или просто запросом). Необходимым компонентом содержания пользовательского запроса является описание тех свойств, которыми обладают документы, интересующие пользователя. Это описание естественно называть критерием поиска.
Следует
подчеркнуть, что единицей гранулярности
поиска, в большинстве систем текстового
поиска является именно документ, а
не какая-либо его порция. Хранящиеся
в системе документы, которые
соответствуют
Релевантность документа не обязательно должна оцениваться в терминах двузначной логики («да — нет»). В таких случаях уместно говорить о степени релевантности документа, понимая ее как значение этой функции. Некоторые системы текстового поиска выдают пользователю множества документов, полученных в результате обработки запросов, упорядочивая документы по убыванию степени релевантности. Такое упорядочение найденных документов называют их ранжированием. Пользователь более эффективно может анализировать ранжированное множество результирующих документов запроса. С большой вероятностью наиболее интересующие его документы из числа найденных находятся в начале выводимого списка документов.
В силу различных причин, связанных, в частности, с трудностями автоматизации понимания естественного языка, а также с неточностью отображения информационных потребностей пользователя в запросе, в результате обработки пользовательского запроса могут быть найдены документы, не соответствующие информационным потребностям пользователя. Такое явление называется информационным шумом.
2.
Принципы текстового поиска
Рассмотрим теперь основные принципы построения современных систем текстового поиска.
Источники сложности современных систем текстового поиска. В отличие от технологий ранних информационно-поисковых систем развитые современные технологии текстового поиска обеспечивают поиск интересующих пользователя документов на основе их информационного содержания, а не только по наборам дескрипторов или значениям каких-либо атрибутов, ассоциированных с этими документами (год издания, автор, издательство и т.п.). Эти атрибуты, хотя и могут, в частности, быть уникальными идентификаторами документов, но никак не зависят от их содержания.
Представления документов. Коллекции документов, хранимых в системах текстового поиска, могут быть довольно крупными. Довольно большой объем могут иметь и содержащиеся в документах тексты. Поэтому нереально рассчитывать на то, что система текстового поиска сможет анализировать полные тексты хранимых документов в процессе обработки пользовательских запросов, даже если эта система базируется на очень мощном компьютере. Производительность такой системы была бы не слишком высока.
Выход из положения заключается в том, чтобы в процессе обработки пользовательского запроса работать не с самими документами, а с некоторыми структурированными представлениями их содержания, которые называют представлениями документов (в некоторых публикациях их называют также представителями документа). Использование представления документа вместо непосредственно самого документа позволяет избежать трудоемкого процесса просмотра и анализа полного его содержания на стадии поиска и вместе с тем использовать преимущества структурированного представления для повышения эффективности поиска.
В современных системах текстового поиска используются различные подходы к построению представлений хранимых документов. От характера используемых представлений документов существенно зависит качество поиска — его точность, полнота, производительность и другие характеристики. Поскольку введенные в систему текстовые документы остаются, как правило, неизменными на протяжении всего времени их существования в системе, построение представления каждого имеющегося в системе документа можно осуществлять однократно на этапе его ввода в систему.
Индексирование документов. Представление документа обычно конструируется на основе множества свойств (атрибутов) этого документа. В простых системах текстового поиска эти атрибуты, как уже указывалось, вообще не являются какими-либо компонентами содержания документа. В качестве таких атрибутов могут использоваться какие-либо внешние (по отношению к тексту документа) его характеристики, и совсем не обязательно, чтобы они идентифицировали его уникальным образом. Можно, например, использовать регистрационный номер документа в архиве, дату его регистрации, название организации — получателя документа, указание места его хранения и пр. В качестве таких внешних атрибутов документов могут также использоваться рубрики классификаторов документов или элементы метаданных Дублинского ядра.
Дублинское ядро (Dublin Core — DC) — это набор элементов метаданных, смысл которых описан вербально и зафиксирован в спецификации определяющего его стандарта
Текущая версия спецификаций Дублинского ядра DC 1.1 была принята в качестве стандарта DCMI в 1999 г. Она включает 15 элементов метаданных. К ним относятся:
• Title (название ресурса);
• Creator (лицо, организация или служба, ответственные за подготовку содержания ресурса);
• Subject (тема, обсуждаемая в содержании ресурса);
• Description (описание содержания ресурса в свободной форме);
• Publisher (лицо, организация или служба, обеспечивающие доступ к ресурсу);
• Contributor (другие участники подготовки содержания ресурса помимо указанного в Creator)',
• Date (дата создания или предоставления доступа к ресурсу);
• Туре (жанр, категория или другие характеристики природы ресурса);
• Format (характер представления ресурса);
• Identifier (точная ссылка на ресурс);
• Source (ссылка на источник, из которого продуцирован данный ресурс);
• Language (язык представления ресурса);
• Relation (ссылка на ресурс, связанный с данным);
• Coverage (область пространства, времени и т.д., к которой относится содержание ресурса);
• Rights (права интеллектуальной собственности на ресурс и т.п.).
Квалификаторы — это уточнители семантики элементов метаданных Дублинского ядра и их значений в различных конкретных случаях их применения. Если квалификатор, указанный для некоторого элемента метаданных Дублинского ядра, оказался неизвестным для приложения Веб, то он должен игнорироваться.
Принятый DMCI в 2000 г. набор квалификаторов включает квалификаторы двух категорий: квалификаторы, которые уточняют семантику элементов метаданных ядра, и квалификаторы, определяющие способ кодирования значений его элементов, что позволяет адекватным образом их интерпретировать.
В настоящее время ведется работа по уточнению как приведенного состава набора элементов метаданных, так и их квалификаторов. На основе спецификаций DC 1.1 в 2001 г. был принят национальный американский стандарт ANSI/NISO Z39.85-2001.
В любом случае ассоциированные с документом атрибуты, идентифицирующие документ и/или характеризующие его содержание, называются его индексирующими свойствами. На основе индексирующих свойств документов в системе текстового поиска строится вспомогательная структура данных, позволяющая по их значениям или по значениям некоторой функции, использующей их в качестве аргументов, эффективным образом (без полного просмотра содержания документов и без полного их перебора) обнаруживать в системных коллекциях документ или документы, которым эти атрибуты соответствуют, и при необходимости осуществлять быстрый доступ к этим документам. Такая вспомогательная структура данных называется индексом, а процесс назначения документу указанных атрибутов — индексированием документа.
ИПС, в которых используется рассматриваемый подход, называются дескрипторными системами. Такие системы используются до настоящего времени. Индексирование документа в них сводится к назначению для него совокупности дескрипторов.
Индексирование документов в системах текстового поиска может осуществляться на основе их названий, аннотаций или полного текста.
Критерии релевантности документов. В процессе обработки пользовательского запроса системе необходимо оценивать релевантность очередного рассматриваемого документа. Для решений этого вопроса его представление должно сопоставляться по некоторому критерию релевантности (критерию близости) с представлением запроса.
Вид критерия близости зависит от подхода, используемого в системе для формирования представлений документов и запросов. В дескрипторных системах обычно используются теоретико-множественные критерии. Другие варианты критерия — указанные множества дескрипторов равны или их пересечение не пусто. В продвинутых системах текстового поиска используются более сложные критерии близости.
Общие принципы текстового поиска. Современные системы текстового поиска используют довольно широкий спектр подходов к представлению и индексированию хранимых документов, к представлению пользовательских запросов, к оценке релевантности документов. Однако как в простых, так и в продвинутых системах используются некоторые общие принципы организации поиска. Эти общие принципы заключаются в следующем.
При
вводе документа в систему
осуществляется индексирование документа
и строится его представление, которое
будет далее выступать
Далее, на основе индексирующих свойств конкретных документов, полученных извне системы или выявленных самой системой путем анализа содержания документов, система формирует и поддерживает индекс для каждой коллекции хранимых в ней документов.
При
поступлении в систему
Наконец,
собственно поиск заключается в
том, что каким-либо эффективным
образом (не прямым перебором, а обычно
с помощью рационально
3.
Средства лингвистической
При обработке полнотекстовых документов в системах текстового поиска приходится иметь дело со средствами обработки естественного языка
Средства обработки естественного языка в системах текстового поиска позволяют выделять из анализируемых текстовых документов и пользовательских запросов термы (слова, словосочетания или фразы) — носители их содержания, выявлять зависимости между этими термами, принимать во внимание их концептуальные связи в контексте данной предметной области, строить на этой основе представления документов, трансформировать поисковые запросы пользователей в удобную для реализации поиска форму, осуществлять расширение запросов для повышения полноты поиска.
Для выполнения указанных функций в большинстве систем рассматриваемого класса используются комплексы средств лингвистической поддержки.
Системные словари. В системах текстового поиска, имеющих дело с обработкой естественного языка, могут поддерживаться словари общеязыковой лексики и лексики предметной области. Такие словари служат для морфологического анализа текста, для обеспечения отождествления слов в различных грамматических формах в процессе поиска, а также для построения некоторых видов представлений документов и запросов.
Тезаурусы. Важную роль в анализе и формировании формализованного представления текстовых документов играют специальные словари, называемые тезаурусами. Тезаурус — это словарь основных понятий языка, обозначаемых отдельными словами или словосочетаниями, с определенными семантическими связями между ними.
Тезаурус может быть общеязыковым (например, тезаурус русского языка) или ориентированным на какую-либо предметную область
В настоящее время применяются два способа создания тезаурусов — ручной и автоматический. Тезаурус, созданный вручную, может быть универсальным, независимым от конкретной коллекции документов. На практике часто используют автоматическое создание тезаурусов.
В системах, использующих тезаурус, он позволяет, например, при поиске по ключевым словам расширять запрос, включая в него синонимы первоначально заданных пользователем ключевых слов и обеспечивая тем самым более полный поиск. Могут быть отождествлены синонимы в документе и в запросе. Тезаурусы также часто используются в процессе ручного или автоматического индексирования документов.
Онтологии. Для адекватной интерпретации пользователем и/или системой содержания текстовых документов и поисковых запросов, представленных на естественном языке, система должна располагать контекстом, который определяет основные понятия предметной области и различного рода семантические связи между ними. Это описание не зависит от содержащихся в системных коллекциях конкретных документов и представляет собой спецификацию концептуализации предметной области системы. Выраженная явным образом такая спецификация называется онтологией предметной области.
Онтология предметной области может поддерживаться в системе с различной степенью формализованности. В простейшем случае она представляется в виде некоторого вербального описания. В более сложном случае онтология представляется в формализованном виде на языках представления знаний, допускающих логический вывод. Такие системы называют интеллектуальными.
Другой неформальный способ описания онтологии, который довольно широко применяется в системах текстового поиска, — это представление ее в форме тезауруса предметной области системы.
Для
формального описания онтологии
в развитых системах используются языки
логики первого порядка. Они допускают
возможности логического
Одной
из последних разработок, посвященных
созданию средств формального описания
онтологии, является стандарт языка определения
онтологии для информационных ресурсов
Веб — Web Ontology Language.
4.
Модели поиска
Наиболее развитые технологии текстового поиска обеспечиваются в настоящее время полнотекстовыми системами. Как уже было показано, существуют различные подходы к построению таких систем.
Понятие модели поиска. Ключевым понятием, характеризующим технологию поиска в той или иной конкретной системе, является модель поиска. Под моделью поиска понимается сочетание: способа формирования представлений документов; способа формирования представлений поисковых запросов; вида критерия релевантности документов.
Разнообразие функциональных возможностей различных систем текстового поиска связано именно с различием реализованных в них моделей поиска.
Простейшие модели поиска. К их числу относятся, модели поиска дескрипторных ИПС и систем, использующих Дублинское ядро.
Другим примером простейших моделей поиска являются модели, основанные на классификаторах. В модели, основанной на классификаторе, документы представляются идентификаторами классов в иерархической структуре классификатора, к которым относится данный документ. Критерием релевантности документа является условие, что класс документа совпадает с каким-либо классом в представлении запроса или является его подклассом.
В более сложном случае в моделях поиска, основанных на классификаторе, допускается указание в запросе нескольких классов классификатора. При этом релевантными считаются документы, принадлежащие какому-либо из указанных в запросе классов или его подклассу. Такая модель поиска близка к рассматриваемой далее булевской модели.
Модели контекстного поиска. В моделях контекстного поиска используется представление документа как совокупности всевозможных встречающихся в его тексте слов и словосочетаний, не считая так называемых стоп-слов. Стоп-слова — это служебные слова (предлоги, союзы и т.п.), которые встречаются практически в любом документе. Поиск документов, содержащих такие слова, привел бы к выдаче полной коллекции документов в ответ на запрос. Поэтому такие слова не могут использоваться в качестве индексирующих свойств документов.
