На правах рукописи

Соченков Илья Владимирович

РЕЛЯЦИОННО-СИТУАЦИОННЫЕ СТРУКТУРЫ

ДАННЫХ, МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ

ПОИСКОВО-АНАЛИТИЧЕСКИХ ЗАДАЧ

Специальность: 05.13.17 – Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва, 2014

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

доктор физико-математических наук, профессор

Научный руководитель:

Осипов Геннадий Семенович

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

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

федеральное государственное бюджетное

Ведущая организация:

образовательное учреждение высшего профессионального образования «Национальный исследовательский университет "МЭИ"»

Защита состоится «16» октября 2014 г. в 16 часов 00 минут на заседании диссертационного совета Д 002.017.02 в федеральном государственном бюджетном учреждении науки Вычислительном центре им. А.А. Дородницына Российской академии наук по адресу: 119333, Москва, ул. Вавилова, д. (конференц-зал).

С диссертацией можно ознакомиться в библиотеке ВЦ РАН и на официальном сайте ВЦ РАН: http://www.ccas.ru/

Автореферат разослан « 28 » августа 2014 г.

Ученый секретарь диссертационного совета Д 002.017.02, доктор физико-математических наук Рязанов В.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Современные ИАС включают в себя инструменты решения следующих задач:

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

реферирование результатов полнотекстового поиска, а также отдельных документов;

поиск текстовых заимствований в коллекциях документов;

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

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

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

В настоящее время созданы методы лингвистического анализа текстов и разработаны программные системы, позволяющие автоматически выполнять морфологический, синтаксический и семантический анализ предложений текста: АОТ1, Solarix2, NLTK3, FreeLing4 и другие. Вычислительная Автоматическая Обработка Текста (АОТ). / [Электронный ресурс] URL:

http://www.aot.ru (дата обращения 23.01.2014) эффективность этих систем и уровень качества лингвистического анализа позволяют применять их для обработки больших коллекций текстов. Однако в существующих ИАС, как правило, не применяются наукоёмкие методы лингвистического анализа текстов, поскольку в настоящее время отсутствуют эффективные методы хранения и обработки лингвистической информации, необходимой для решении поисково-аналитических задач, например, морфологических признаков, синтаксических связей, категориальносемантических значений (ролей) и семантических отношений на структурах текстов. Реляционные базы данных и стандартные инвертированные индексы не позволяют эффективно хранить и совместно использовать эту лингвистическую информацию, в то время как использование этой информации обеспечивает повышение качества решения задач аналитической обработки больших коллекций текстовых документов. В настоящей диссертационной работе предложен метод оценки сходства текстов с использованием лексикоморфологической, синтаксической и семантической информации, а также структуры данных и алгоритмы информационного поиска на основе этого метода, обладающие большей эффективностью и обеспечивающие более высокое качество результатов, нежели существующие методы решения поисково-аналитических задач в ИАС, что свидетельствует об актуальности темы исследования.

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

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

Solarix: Компьютерная лингвистика. / [Электронный ресурс] URL:

http://www.solarix.ru/ (дата обращения 05.03.2014) Natural Language Toolkit. / [Электронный ресурс] URL: http://nltk.org/ (дата обращения 05.03.2014).

Bird S. Natural Language Processing with Python. / O'Reilly Media Inc, Freeling: An Open Source Suite Of Language Analyzers. / [Электронный ресурс] URL:

http://nlp.lsi.upc.edu/freeling/ (дата обращения 05.03.2014) Justin Zobel, Alistair Moffat. «Inverted files for text search engines». /ACM Computing Surveys (CSUR). Vol. 38, №2, 2006. Article 6. doi:10.1145/1132956. Задачи исследования:

1. Разработка лексико-морфологических, синтаксических и семантических критериев оценки сходства текстов, а также метода оценки сходства текстов на основе этих критериев.

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

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

4. Разработка и программная реализация алгоритмов информационного поиска на основе многокритериальной оценки сходства текстов.

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

Для решения поставленных задач применены следующие методы исследования:

1. Методы теории множеств и алгебры логики.

2. Методы объектно-ориентированного проектирования программного обеспечения.

3. Методы исследования качества результатов информационного поиска.

В ходе решения поставленных задач получены следующие новые научные результаты:

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

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

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

4. Разработаны и исследованы следующие алгоритмы поисковоаналитической обработки текстовой информации:

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

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

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

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

Результаты исследований по теме диссертационной работы использованы при выполнении научно-исследовательских работ по следующим проектам Минобрнауки РФ, программам ОНИТ РАН и грантам РФФИ:

1. «Создание методов и программных средств выявления перспективных направлений научных исследований в России и за рубежом по данным из открытых источников на основе потребностей реального сектора экономики и обеспечения конкурентных позиций отечественных производителей на перспективных рынках инновационных товаров и услуг и созданных научно-технических заделов» (в рамках ФЦП «Научные и научно-педагогические кадры инновационной России», ГК № 16.740.11.0753, 2011–2013 г.г.).

2. «Создание программного комплекса информационно-аналитической поддержки научно-технической деятельности на основе вычислительного семантического поиска и анализа неструктурированной текстовой информации» (в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007—2013 годы», ГК № 07.551.11.4003, 2011– 3. «Разработка вычислительных методов объективной оценки качества научно-технических документов на естественных языках» (в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007—2013 годы», ГК № 14.514.11.4018, 2011–2013 г.г.).

4. «Исследование и разработка методов и алгоритмов анализа связанности сложно-структурированных данных в научно-технической сфере» (в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007—2013 годы», ГК № 14.514.11.4024, 2011–2013 г.г.).

5. «Исследование и разработка программного обеспечения понимания неструктурированной текстовой информации на русском и английском языках на базе создания методов компьютерного полного лингвистического анализа» (в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007—2013 годы», ГК № 07.514.11.4134, 2011– 6. «Развитие методов анализа полуструктурированной информации и моделирования целенаправленного поведения» (в рамках ФЦП «Научные и научно-педагогические кадры инновационной России», ГК № П952, 2009–2011 г.г.).

7. Проект «Система высокоточного интеллектуального поиска, индексации и анализа информации для поддержки принятия решений»

(проект ПР4 «Исследование и разработка параллельных алгоритмов анализа больших объемов текстовой информации из глобальной сети и алгоритмов принятия решений на основе когнитивных методов»

программы «ТРИАДА», 2006–2007 г.г.).

8. «Развитие методов и программных средств многоязычного семантического поиска» (в рамках проекта 2.6 ОНИТ РАН 2009– 9. «Развитие методов и технологии семантического поиска и анализа научных публикаций Exactus Expert» (в рамках проекта 2.9 ОНИТ РАН 2012–2013 г.г.).

10. «Разработка и исследование структур данных и алгоритмов поисковоаналитической обработки текстовой информации» (в рамках проекта 14мол_а РФФИ 2014–2015 г.г.) Созданное программное обеспечение (ПО), включающее программную реализацию структур данных и алгоритмов поисково-аналитической обработки текстовой информации, внедрено в следующих системах:

электронная библиотека международных клинических руководств6 в Медицинском центре Банка России;

портал «Руконт» – национальный цифровой ресурс7 в виде информационно-поисковых сервисов портала;

информационно-аналитическая система Exactus Expert8 и поисковая машина Exactus9.

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

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

XIII национальная конференция по искусственному интеллекту с международным участием (КИИ: Россия, Белгород, Белгородский государственный технологический университет, 2012 г.);

European Intelligence and Security Informatics Conference (IEEE EISIC: (Greece, Athens);

Назаренко Г.И., Плотникова В.А., Смирнов И.В., Соченков И.В., Тихомиров И.А.

Программные средства создания и наполнения полнотекстовых электронных библиотек / «Электронные библиотеки: перспективные методы и технологии, электронные коллекции: XII Всероссийская научная конференция RCDL’ 2010, Казань, Россия - 2010. – С38-42.

Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека на базе технологии Контекстум / [Электронный ресурс] URL: http://www.rucont.ru/ (дата обращения 16.02.2014) Osipov, G.; Smirnov, I.; Tikhomirov, I. and Shelmanov, A. Relational-Situational Method for Intelligent Search and Analysis of Scientific Publications. / In Proceedings of the Workshop on Integrating IR technologies for Professional Search Moscow, Russian Federation, March 24, 2013, p.57- Завьялова О.С., Киселёв А.А., Осипов Г.С., Смирнов И.В., Тихомиров И.А., Соченков И.В. Система интеллектуального поиска и анализа информации Exactus на РОМИП-2010 / Труды российского семинара по оценке методов информационного поиска РОМИП'2010. - Казань: Казан. ун-т, 2010. С49-69.

Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем – всероссийская конференция с международным участием в 2010, 2011 г.г. (Россия, Москва, Российский университет дружбы народов) XII Всероссийская научная конференция RCDL’ 2010: «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» (Россия, Казань, 2010 г.) Российский семинар по оценке методов информационного поиска в 2008– Семнадцатая международная Конференция "Крым 2010" (Россия, Геленджик, 2010 г.).

Информационные системы, содержащие в своём составе программную реализацию разработанных структур данных и алгоритмов поисковоаналитической обработки текстовой информации, представлены на российских и международных выставках программного обеспечения и информационных технологий SofTool (в 2010–2013 г.г.) и CeBIT (в 2008–2014 г.г.).

Публикации. Всего по теме исследования опубликовано 14 работ: 6 из них в рецензируемых журналах из списка ВАК РФ, 8 в материалах российских и международных конференций. Получен патент Российской Федерации на изобретение и 3 свидетельства о государственной регистрации программ для ЭВМ.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Рассматриваются существующие методы компьютерного анализа текстов:

токенизация, морфологический анализ и лемматизация (определение леммы по словоформе некоторой лексемы11), синтаксический анализ и семантический анализ (включающий в себя установление семантических значений («ролей») слов и понятий в текстах (semantic role labeling, или SLR) и разрешение кореференции). Описаны также программные системы, реализующие рассмотренные методы.

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

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

Рассматриваются универсальное множество D лемм – словарь нормальных форм всех лексем ЕЯ, – множество всевозможных форм (словоформ) всех лексем ЕЯ, множество текстов E и произвольный текст E. Этот текст содержит конечное множество словоупотреблений W wi.

Далее определены:

Лемма – каноническая (словарная) форма слова Лексема – совокупность парадигматических форм одного слова, как элемента лексики естественного языка. Одной лексеме, как правило, соответствует одна статья в словаре – Бинарное отношение на множестве словоупотреблений W текста и множестве D нормальных форм лексем: W D, сопоставляющее w W d D : w, d. При этом, вообще говоря, у каких-либо словоупотреблений имеется более одного варианта нормализации (для – Бинарное отношение на множестве словоупотреблений W текста и множестве всевозможных форм различных лексем: W. Это отношение определяет форму каждого словоупотребления в тексте:

– Конечное множество меток (тегов) T={ti}, и бинарное отношение W T, сопоставляющее каждому словоупотреблению некоторую метку (тег гипертекстовой разметки или разметки по метаданным, например, для словоупотреблений в заголовке текста, в списке авторов и – Числовая функция, задающая вес («значимость») меток: (t).

– Числовая функция, задающая вес словоупотребления в тексте: v( w ).

Разбиение множества словоупотреблений на предложения (возможно, ik,…,jk – последовательность индексов словоупотреблений в тексте, входящих в k-е предложение.

Для учёта синтаксических зависимостей между словоупотреблениями в тексте определены следующие объекты:

– Конечное множество типов синтаксических связей: SR12.

– Бинарное отношение на множестве словоупотреблений: W W, представляющее всевозможные синтаксические связи между словоупотреблениями. Синтаксические структуры рассматриваются в виде деревьев, и считается, что в паре элементов wi, w j первый элемент – wi W – соответствует главному словоупотреблению (ГС), а словоупотреблению.

А.Сокирко. Семантические словари в автоматической обработке текста (по материалам системы ДИАЛИНГ) / Дисс канд.т.н. // [Электронный ресурс] URL:

http://www.aot.ru/docs/sokirko/sokirko-candid-1.html (дата обращения 23.01.2014) разбиение множества, где каждое из отношений z определяет тип синтаксической связи z SR для пар словоупотреблений wi, w j z.

Для представления семантической информации в текстах определены:

Конечное множество категориально-семантических значений синтаксем Roles, называемых для краткости "семантическими значениями".

словоупотреблениям текста семантические значения соответствующих синтаксем15. Каждое словоупотребление может иметь 0 и более семантических значений в тексте.

Множество типов отношений R на множестве значений синтаксем16.

Бинарное отношение W W, определяющее семантически связанные словоупотребления в тексте17.

разбиение множества, где каждое отношение x определяет тип семантической связи x R для пар словоупотреблений wi, w j x, где Разработанное представление текстовой информации является модификацией реляционно-ситуационной модели (РСМ) текстовой информации, предложенной Г.С. Осиповым и Г.А. Золотовой, для решения информационно-аналитических задач.

Во втором параграфе второй главы введены критерии оценки сходства текстов и описан метод многокритериальной оценки сходства текстов.

Золотова Г.А., Онипенко Н.К., Сидорова М.Ю. Коммуникативная грамматика русского языка. – М. 2004. – 544 с.

G. Osipov. Methods for extracting semantic types of natural language statements from texts. // In 10th IEEE International Symposium on Intelligent Control, Monterey, California, USA, В общем случае в тексте синтаксема является некоторой синтаксической конструкцией. Например, синтаксема может быть представлена синтаксической группой (предложной или именной). При решении задачи информационного поиска будем связывать семантическое значение не с синтаксемой в целом, а с главным словом синтаксической конструкции, представляющей синтаксему.

Осипов Г.С. Приобретение знаний интеллектуальными системами. // М.: Наука.

Физматлит, Осипов Г.С. Методы искусственного интеллекта. – М.: ФИЗМАТЛИТ, 2011. – Сходство эталонного текста E и сопоставляемого с ним текста E оценивается по множествам предложений этих текстов: S и S соответственно. Для произвольных предложений s S и s S определено множество w, d & w, d – множество пар совпадающих по нормальной форме словоупотреблений, называемых соответственными.

Далее определены критерии оценки сходства предложений s и s.

1. Покрытие предложения-эталона предложением сопоставляемого текста :

В качестве функции для определения весов v( w ) может применяться классическая оценка информационной значимости на основе inverse document Frequency18 (IDF) или характеристика тематической значимости (ХТЗ), если для эталонного текста s известна его тематическая принадлежность.

2. Общая оценка информационной значимости слов предложенияэталона s в предложении s сопоставляемого текста :

В этой формуле функционал несовпадение форм словоупотреблений w, w :

В качестве весов v( w ) могут использоваться IDF или ХТЗ, а в качестве функции для определения весов v '( w ) – классическая оценка term frequency20 (TF) или её модификации21.

S.E. Robertson, C.J. van Rijsbergen and P.W. Williams. «Probabilistic models of indexing and searching». / In R.N. Oddy Information Retrieval Research, pp. 35-56, London, 1981. Butterworths.

Р.Е. Суворов, И.В. Соченков. Определение связанности научно-технических документов на основе характеристики тематической значимости. // Искусственный интеллект и принятие решений. М.: ИСА РАН, №1, 2013. C.33- Joachims, T. «A Probabilistic Analysis of the Rocchio Algorithm with TFIDF for Text Categorization». / DTIC Document, 1996.

3. Оценка сходства предложения-эталона s и предложения s сопоставляемого текста на основе совпадения синтаксических множество пар соответственных словоупотреблений в эталонном предложении s и сопоставляемом предложении s, для которых совпадают (по нормальным формам лексем) главные w, w N s,s и зависимые w, w N s,s слова, а сами словоупотребления связаны в контексте эталонного и сопоставляемого предложения однотипными 4. Оценка сходства предложения-эталона s и предложения s сопоставляемого текста на основе совпадения семантических словоупотреблений с семантическими значениями в предложении эталонного текста, что для них в сопоставляемом тексте имеются соответственные словоупотребления, которым приписаны такие же семантические значения.

5. Оценка сходства предложения-эталона s и предложения s сопоставляемого текста на основе семантических связей:

Joaquin Perez-Iglesias. «Integrating the Probabilistic Model BM25: BM25F into Lucene», 2009 / [Электронный ресурс] URL: http://nlp.uned.es/~jperezi/Lucene-BM25/ (дата обращения 23.03.2014) w ', a SemRoles – множество значений синтаксем, приписанных в тексте тем словоупотреблениям w’, которые связаны в этом тексте со словоупотреблением w всевозможными семантическими связями.

Общая оценка сходства предложения s текста-эталона и предложения s сопоставляемого текста определяется взвешенной суммой:

В формуле (7) набор L={i|i=1..5} ( n 1 ) задаёт набор параметров метода, определяющих вклад каждого из критериев оценки сходства в итоговую величину. Из всех возможных предложений s в сопоставляемом тексте выбираются те, которые наилучшим образом (в смысле максимизации оценки (7)) соответствуют предложению эталона s :

Общая оценка сходства текста-эталона по отношению к тексту выражается следующей формулой:

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

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

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

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

Представлены разработанные структуры данных, необходимые для представления информации о текстовых документах в ИАС, структуры инвертированных индексов, а также алгоритмы их построения на этапе индексирования документов.

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

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

Каждому ключу сопоставлена последовательность -ЭД – пост-лист. Схема ЭД ИПИ представлена на рисунке 1. Каждый -ЭД занимает в памяти ЭВМ байт, что позволяет эффективно реализовать представление последовательностей в памяти ЭВМ в виде массивов.

РЕЗЕРВ

Рисунок 1 – Схема элементов данных разработанного Для описания модели данных ИПИ в диссертации введены следующие определения.

Определение 3.1. Последовательность -ЭД, относящихся к употреблениям некоторой лексемы в тексте отдельно взятого документа назовём -цепочкой; -цепочка строится по следующим правилам:

1. В начале цепочки размещается 1-ЭД.

2. За ним следует 2-ЭД, соответствующий первому (по порядку) употреблению лексемы в тексте.

3. За ним опционально следует 3-ЭД, если с рассматриваемым употреблением лексемы связана некоторая семантическая информация.

4. Далее следуют чередующиеся 2-ЭД и 3-ЭД (опционально), соответствующие остальным употреблениям рассматриваемой лексемы в Определение 3.2. Для представления информации обо всех употреблениях некоторой лексемы всех документах коллекции применяется последовательность -цепочек – -последовательность. -последовательность формируется с помощью конкатенации -цепочек по следующему правилу: цепочка 1 предшествует 2 тогда и только тогда, когда код документа, представляемого -цепочкой 1 меньше кода документа, представляемого цепочкой 2.

Определение 3.3. Объект, указывающий на текущий обрабатываемый ЭД в последовательности элементов, называется итератором.

На классе -цепочек индуцируется линейный порядок (-правило-1) и частичный порядок на классе -ЭД внутри -цепочки (-правило-2). В совокупности -правило-1 и -правило-2 вводят отношение частичного порядка на классе -ЭД в -последовательностях – рисунок 2.

Рисунок 2 – Пример упорядочения -ЭД в -последовательностях Это отношение частичного порядка, однако, не позволяет сравнивать ЭД двух -последовательностей, что требуется, например, в алгоритме слияния (merge) двух упорядоченных множеств. Вводимое Для устранения этого недостатка введено следующее -правило-3: из двух сравниваемых -ЭД m1 и m2, входящих в некоторую -последовательность ( m1, m2 ), ЭД m