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

ВВЕДЕНИЕ.

1 СОСТОЯНИЕ ВОПРОСА. ОБЗОР И АНАЛИЗ ЛИТЕРАТУРНЫХ ИСТОЧНИКОВ.

1.1 .Общие принципы построения и структура информационно-поисковой системы.

1.2 Информационно-поисковые языки.

1.2.1 Логический поиск.

1.2.2 Взвешенный поиск.

1.2.3 Линейная .модель индексирования и поиска.

1.2.4 Поиск в нечетких множествах.

1.2.5 Пороговые модели.

1.2.6 Кластерная модель.

1.2. 7 Вероятностная модель.

1.2.8 Коррекция запроса по релевантности.

1.2.9 Поиск по смыслу.

1.2.10 Поиск по шаблону.

1.2.11 Итеративный поиск.

1.3 Формальные модели естественного языка.

1.3.1 Общие сведения.

1.3.2 Средства смыслоотождествления в ИПС.

1.3.3 Классификация ИПЯ.

1.3.4 Эволюция информационно-поисковых языков.

1.4 Программные системы для поиска информации.

1.4.1 Документальная ИПС Артефакт.

1.4.2 Система DtSearch.

1.4.3 Oracle ConText Cartridge (OCC).

1.4.4 Excalibur Retrieval Ware.!.

1.4.5 TEXIS.

1.4.6 Mndex.

1.4.7 Евфрат.

1.5 Сравнение существующих поисковых систем и обоснование необходимости разработки.

1.6 Постановка задачи.

1.7 Выводы.

2 ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ ИНТЕЛЛЕКТУАЛЬНОЙ ИНФОРМАЦИОННО-ПОИСКОВОЙ СИСТЕМЫ.'.

2.1 Семантико-синтаксический анализ и синтез текстов на естественных языках.

2.1.1 Семантико-синтаксическая структура текстов.

2.1.2 Элементы структурной лингвистики.

2.1.3 Синтаксический анализ текстов.

2.1.4 Определение значимости слов на основе законов Ципфа.

2.1.5 Иерархическая векторная модель представления документов в информационном поиске.

2.2 Лингвистический процессор.

2.2.1 Блок лексического анализа.

2.2.2 Блок морфологического анализа.

2.2.3 Блок синтаксического анализа.

2.2.4 Блок семантического анализа.

2.3 Вероятностный синтаксический анализ.

2.3.1 Структурные и вероятностные методы анализа.

2.3.2 Вероятностные КС-грамматики.

2.3.3 Метод генетических алгоритмов.

2.3.4 Метод распознавания образов.

2.3.5 Метод дерева решений.

2.3.6 Алгоритм вероятностного синтаксического анализа.

2.4 Выводы.

3 РАЗРАБОТКА И СОЗДАНИЕ ИНТЕЛЛЕКТУАЛЬНОЙ ПОИСКОВОЙ СИСТЕМЫ.

3.1 Индексирование документов.

3.1.1 Система индексирования.

3.1.2 Анализ и классификация способов индексирования.

3.2 Файловые структуры для хранения и поиска информации.

3.2.1 Основная терминология при описании структур файлов.

3.2.2 Последовательные файлы.

3.2.3 Инвертированные файлы.

3.2.4 Индексно-последовательные файлы.

3.2.5 Мультисписки.

3.2.6 Ячеистые мультисписки.

3.2.7 Кольцевые структуры.

3.2.8 Заплетенные списки.

3.3 Выбор и обоснование языка программирования.

3.4 Алгоритмическое и программное конструирование интеллектуальных систем для поиска информации.

3.4.1 Общие положения.

3.4.2 Нахождение начальной формы слова.

3.4.3 Нахождение неключевых слов.

3.4.4 Объекты для нахождения синонимов.

3.4.5 Реализация поиска в базе данных документов.

3.4.6 Реализация интеллектуальной надстройки к поисковым машинам сети Интернет.

3.4.7 Конструирование пользовательского интерфейса.

3.5 Руководство пользователя.

3.5.1 Требования к оборудованию и установка программы.

3.5.2 Запуск программы.

3.5.3 Основное окно программы.

3.5.4 Ввод запроса.

3.3.5 Задание области поиска.

3.5.6 Поиск документов.

3.5. 7 Выдача результатов.

3.6 Выводы.

4 ОЦЕНКА ЭФФЕКТИВНОСТИ РАБОТЫ ИНТЕЛЛЕКТУАЛЬНОЙ

ПОИСКОВОЙ СИСТЕМЫ.

4.1. Эффективность и релевантность поиска.

4.1.1 Качество информационно-поисковых систем.

4.1.2 Методы улучшения качества поиска.

4.1.3 Эффективность поиска.

4.2 Тестирование интеллектуальной ИПС.

4.2.1 Тестирование эффективности поиска.

4.2.2 Поиск документов MS Word :.

4.2.3 Поиск электронных таблиц MS Excel.

4.2.3 Поиск Web-страниц.

4.2.4 Тестирование скорости поиска.

4.3 Выводы.

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

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

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

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

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

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

Методы исследования.

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

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

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

Практическая ценность. Основным достоинством разработанной ИПС является ускорение поиска нужной информации и повышение эффективности делопроизводства в организациях с большим количеством электронных документов самых различных форматов. Поэтому дополнительным условием при создании ИПС являлась поддержка индексирования и поиска не только текстовых и HTML файлов, но и всего спектра используемых в офисной работе форматов: документов Word, электронных таблиц Excel, презентаций PowerPoint, баз данных Access и, конечно, Web-страниц в формате HTML.

Дополнительной возможностью разработанной системы является передача преобразованного запроса для поиска по базам данных популярных российских и зарубежных поисковых машин Интернета. В этом случае программа выступает в роли интеллектуальной надстройки к поисковым механизмам сети Интернет, в том числе к системам Altavista, Rambler, Япёех.

В настоящее время в рамках проектов комплексной автоматизации управленческого и бухгалтерского учета, проводимых ООО «Инфотэкс», система внедрена на более 20 предприятиях Ханты-Мансийского округа (акт внедрения прилагается).

Апробация работы.

Основные этапы работы докладывались и обсуждались на X Международной конференции " Применение новых технологий в образовании " (Троицк, 1999), 8-ом Международном науч.-техн. семинаре " Проблемы передачи и обработки информации в сетях и системах телекоммуникаций "(Рязань, 1999), Всероссийской науч,-техн. конференции " Новые информационные технологии в научных исследованиях и в образовании " (Рязань, 2000), Второй международной научно-технической конференции "Измерение, контроль, информатизация" (Барнаул, 2001).

Публикации. По теме диссертации опубликовано 10 печатных работ. Из них: 1 учебное пособие, 1 монография, 4 статьи и 4 тезисов докладов на вышеперечисленных конференциях.

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

Структура и объем работы

Работа содержит 29 рисунков, 8 таблиц, библиографию из 32 наименований на 3 страницах и приложения на 28 страницах.

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

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

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

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

В приложении приведены фрагменты исходного текста на языке С++ разработанной интеллектуальной поисковой системы.

4.3 Выводы

1. Рассмотрены понятия эффективности и релевантности поиска.

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

3. Проанализирована связь между полнотой и точностью поиска естественно-языковых текстов.

1,600

1,400

1,200 ф 1,000 о к 5 0,800

Ф

О. m 0,600

0,400

0,200

0,000

20 40 60 80 100 Объем индекса документов, Мб

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

5. Рассмотрены практические примеры тестирования интеллектуальной поисковой системы на электронных документах разных форматов с использованием запросов на русском языке.

ЗАКЛЮЧЕНИЕ

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

1. Разработаны принципы построения и структура интеллектуальной информационно-поисковой системы.

2. Исследованы уровны формальных моделей естественного языка.

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

4. Исследована структура лингистического процессора - одного из ключевых элементов интеллектуальной поисковой системы с естественно-языковой ориентацией.

5. Рассмотрен перспективный подход к обработке естественноязыковых текстов - статистический (вероятностный) метод анализа на основе дерева принятия решений.

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

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

8. Разработаны алгоритмы автоматического индексирования естественно-языковых текстов в интеллектуальных поисковых системах.

9. Проведен анализ специальных структур файлов для хранения информации и ее поиска по совокупности ключевых слов.

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

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

1. Частиков А.П., Волков С.С. Поиск информации с использованием запросов на естественном языке. Применение новых технологий в образовании // Материалы X Международной конференции / Фонд новых технологий в образовании «Байтик» - Троицк, 1999.

2. Частиков А.П., Волков С.С. Применение запросов на естественном языке в интеллектуальных поисковых системах. Сб. научных трудов "Аппаратные и программные средства систем управления в пищевой промышленности". / Кубан. Гос. Технол. ун-т. -Краснодар, 1999.

3. Частиков А.П., Волков С.С. Анализ файловых структур для хранения и поиска информации. Труды КубГТУ, том VII, серия "Информатика и управление". / Кубан. Гос. Технол. ун-т. -Краснодар, 2000.

4. Частиков А.П., Волков С.С. Применение автоматической классификации документов в информационно-поисковых системах. Труды КубГТУ, том VII, серия "Информатика и управление". / Кубан. Гос. Технол. ун-т. - Краснодар, 2000.

5. Частиков А.П., Волков С.С. Тенденции развития интеллектуальных поисковых систем. Новые информационные технологии в научных исследованиях и в образовании // Материалы Всероссийской науч.-техн. конференции / Рязан. гос. радиотехн. акад. - Рязань, 2000.

6. Частиков А.П., Волков С.С. Статистический распознаватель в интеллектуальном поиске информации. Измерение, контроль, информатизация: Материалы второй международной научнотехнической конференции. / Алтайский Гос. Технич. ун-т. -Барнаул, 2001.

7. Частиков А.П., Волков С.С. Интеллектуальные поисковые системы. Учебное пособие / Просвещение - Юг. - Краснодар, 2001.

8. Частиков А.П., Волков С.С. Интеллектуализация процессов поиска текстовой информации. — Монография / Просвещение Юг. -Краснодар, 2002.

9. Андреев A.M., Березкин Д.В., Брик А.В. Лингвистический процессор для информационно-поисковой системы // Компьютерная хроника , 1998. № 11 стр. 79 - 100.

10. D. Manning, R. Carpenter. Probabilistic Parsing Using Left Corner Language Models. 1997. // Опубликовано на сервере www.xxx.lang.gov/cmp-lg.

11. A. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Т. 1. Синтаксический анализ. М.: Мир, 1978. — 612 с.

12. R.M. Losee. Learning Syntactic Rules and Tags with Genetic Algorithms for Information Retrieval and Filtering: An Empirical Basis for Grammatical Rules. // Information Processing & Management, 1995. // Опубликовано на сервере www.xxx.lang.gov/cmp.lg.

13. Карпова Г.Д., Пирогова Ю.К., Кобзарева Т.Ю., Микаэлян Е.В. Компьютерный синтаксический анализ: описание моделей и направлений разработок. // Итоги науки и техники (серия "Вычислительные науки"). Т.6. —М.: ВИНИТИ, 1991.

14. Искусственный интеллект. — В 3-х кн. Кн.2. Модели и методы: Справочник. / Под ред. Д.А. Поспелова. —М.: Наука, 1990.

15. Попов Э.В. Общение с ЭВМ на естественном языке. —М.: Наука, 1982.

16. Щетинин В.Г. Многослойная самоорганизация нейронных сетей оптимальной сложности// Автоматика и вычислительная техника. -Рига, 1998J4.-С.30-37.

17. Ivakhnenko A.G., Ivakhnenko G.A. and Mbller J.A., Self-Organization of Neural Networks with Active Neurons, Pattern Recognition and Image Analysis, v.4, no.2, pp.185-196, 1995.

18. Salton G., McGill M. J. Introduction to modern infomation retrieval. MacGraw-Hill, 1983.

19. Козачков Jl.С. Системы потоков научной информации. К. 1973.

20. Ефимов А.Н., Шойхер М.В., Использование информационных свойств World Wide Web для повышения эффективности средств поиска

21. Реброва М.П. Автоматическая классификация в системах обработки информации: Поиск документов. -М.: Радио и связь, 1983.

22. Белоногов Г.Г., Кузнецов Б.А. Языковые средства автоматизированных информационных систем. М.:Наука, 1983.

23. Рыбаков Ф.И. Автоматическое индексирование на естественном языке. М.:Энергия, 1980.

24. Рубашкин В.Ш. Представление и анализ смысла в интеллектуальных информационных системах. — М.:Наука, 1989.

25. Попов Э.В. Общение с ЭВМ на естественном языке. —М.: Наука, 1982.

26. Дубинский А. Г. Иерархическая векторная модель представления текстовых документов в информационном поиске (Опубликовано на сайте http://dubinsky.nm.ru/ 99/tl l/99tl 1 .htm)

27. Дубинский А.Г. Пути улучшения качества функционирования информационно-поисковых систем глобальной сети. http://dubinsky.nm.ru/00/s3/00s3.htm

28. Осипов Г.С. Приобретение знаний интеллектуальными системами: Основы теории и технологии.- М.: Наука. Физматлит, 1997.- 112с.