Содержание к диссертации
ВВЕДЕНИЕ 5
ГЛАВА 1. ИССЛЕДОВАНИЕ МЕТОДОВ ПОСТРОЕНИЯ
ПОЛНОТЕКСТОВЫХ ПОИСКОВЫХ ИНДЕКСОВ 12
АНАЛИЗ МОДЕЛЕЙ ИНФОРМАЦИОННОГО ПОИСКА 12
АНАЛИЗ МЕТОДОВ ПОЛНОТЕКСТОВОЙ ИНДЕКСАЦИИ ТЕКСТА.... 19
МЕСТО ПОЛНОТЕКСТОВОГО ПОИСКА СРЕДИ ЗАДАЧ В ИНФОРМАЦИОННОМ ПОИСКЕ. 21
ОСНОВНЫЕ МЕТОДЫ ПОСТРОЕНИЯ ПОЛНОТЕКСТОВЫХ ИНДЕКСОВ 22
ВЫВОД О ПРИМЕНИМОСТИ МЕТОДОВ ИНДЕКСИРОВАНИЯ ДЛЯ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ 37
13. АНАЛИЗ ПОИСКАЛО ЭЛЕКТРОННОЙ БИБЛИОТЕКЕ 38
ПРОБЛЕМАТИКА ОРГАНИЗАЦИИ ПОИСКА 38
АНАЛИЗ МЕТОДА СТЕММИНГА 40
1.4. ВЫБОР МЕТОДОВ ИНДЕКСИРОВАНИЯ, ДОПУСКАЮЩИХ ИЕРАРХИЧЕСКУЮ
ОРГАНИЗАЦИЮ ПАМЯТИ 41
ИЕРАРХИЯ ПАМЯТИ 41
ВЫБОР МЕТОДОВ ИНДЕКСИРОВАНИЯ 43
ВЫВОДЫ 45
ГЛАВА 2. ПОСТРОЕНИЕ И ПРИМЕНЕНИЕ МОРФОЛОГИЧЕСКОГО
ИНДЕКСА 46
УПРОЩЁННОЕ ОПИСАНИЕ МОРФОЛОГИИ СЛОВА 46
МОДЕЛЬ ИНФОРМАЦИОННОГО ПОИСКА, УЧИТЫВАЮЩАЯ МОРФОЛОГИЮ ТЕКСТА 47
ПОСТРОЕНИЕ И ИСПОЛЬЗОВАНИЕ ПОИСКОВОГО ИНДЕКСА 50
БЛОЧНАЯ СТРУКТУРА ПОИСКОВОГО ИНДЕКСА 50
СТРУКТУРА БЛОКА ИНДЕКСА 51
НАПОЛНЕНИЕ ИНДЕКСА 52
УЛУЧШЕНИЕ ИНДЕКСА 54
2.4. УЛУЧШЕНИЕ ИНДЕКСА С ПОМОЩЬЮ НЕЙРОННОЙ СЕТИ 58
ОШИБКИ УЛУЧШЕНИЯ ПОИСКОВОГО ИНДЕКСА 63
МОДИФИЦИРОВАННАЯ НЕЙРОННАЯ СЕТЬ ДЛЯ ОБРАБОТКИ ТЕКСТА 67
2.5. ПОИСК ПО МОРФОЛОГИЧЕСКОМУ ИНДЕКСУ 74
2.6. ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ПОИСКОВОГО ИНДЕКСА 77
СИГНАТУРА ПЕРВОГО ТИПА 78
СИГНАТУРА ВТОРОГО ТИПА 79
МОДИФИКАЦИЯ МЕТОДА РАЗРЕШЕНИЯ КОЛЛИЗИЙ "ОТКРЫТОЙ АДРЕСАЦИЕЙ" 80
ЛЕКСИКОГРАФИЧЕСКАЯ СОРТИРОВКА, УСКОРЯЮЩАЯ ПОИСК МАКСИМАЛЬНОЙ ДОПОЛНИТЕЛЬНОЙ МОРФЕМЫ В СЛОВЕ 84
ВЫВОДЫ 86
ГЛАВА 3. МОДЕЛИРОВАНИЕ ПРОЦЕССА ОБУЧЕНИЯ
ПРЕДЛОЖЕННОЙ НЕЙРОННОЙ СЕТИ 88
МОДЕЛИРОВАНИЕ ЯЗЫКА 88
ВОЗДЕЙСТВИЯ СО СТОРОНЫ ДОПОЛНИТЕЛЬНЫХ МОРФЕМ 90
ВЕРОЯТНОСТИ ИЗМЕНЕНИЙ РАЗНЫХ ТИПОВ ПРИ ОБУЧЕНИИ ДОПОЛНИТЕЛЬНЫХ МОРФЕМ 91
СООТНОШЕНИЯ ВЕРОЯТНОСТЕЙ ДЛЯ ДОПОЛНИТЕЛЬНЫХ МОРФЕМ 93
33. ВЕСОВЫЕ КОЭФФИЦИЕНТЫ РАЗНЫХ ТИПОВ ВОЗДЕЙСТВИЙ ДЛЯ
ДОПОЛНИТЕЛЬНЫХ МОРФЕМ 95
ВЫВОДЫ ПО ОБУЧЕНИЮ ДОПОЛНИТЕЛЬНЫХ МОРФЕМ 96
ОЦЕНКА СООТНОШЕНИЙ ВЕСОВЫХ КОЭФФИЦИЕНТОВ ВОЗДЕЙСТВИЙ НА ГРАНИЦУ РАЗБИВКИ СО СТОРОНЫ ДОПОЛНИТЕЛЬНОЙ МОРФЕМЫ 98
3.4. ОБУЧАЮЩИЕ ВОЗДЕЙСТВИЯ СО СТОРОНЫ ОСНОВНЫХ ЧАСТЕЙ СЛОВ 102
UNDER-STEMMING 104
СЛУЧАИ OVER-STEMMING 105
СОВПАДЕНИЕ ГРАНИЦ РЕАЛЬНЫХ МОРФЕМ С ГРАНИЦАМИ ВЫДЕЛЕННЫХ МОРФЕМ 106
ОШИБОЧНЫЕ ВОЗДЕЙСТВИЯ ВСЛЕДСТВИЕ СЛУЧАЙНОГО СОВПАДЕНИЯ ПОДСТРОК СИМВОЛОВ 107
3.5. СООТНОШЕНИЯ ВЕРОЯТНОСТЕЙ ДЛЯ ОСНОВНЫХ ЧАСТЕЙ СЛОВ ПРИ НОВОМ
ПОДХОДЕ 107
UNDER-STEMMING 108
СЛУЧАИ OVER-STEMMING 111
СОВПАДЕНИЕ ГРАНИЦ РЕАЛЬНЫХ МОРФЕМ С ГРАНИЦАМИ ВЫДЕЛЕННЫХ МОРФЕМ I 13
ВЕСОВЫЕ КОЭФФИЦИЕНТЫ ВОЗДЕЙСТВИЙ НА ГРАНИЦУ РАЗБИВКИ СО СТОРОНЫ ОСНОВНОЙ ЧАСТИ СЛОВА 116
СООТНОШЕНИЕ ВОЗДЕЙСТВИЙ НА ГРАНИЦУ РАЗБИВКИ СО СТОРОНЫ ОСНОВНЫХ ЧАСТЕЙ СЛОВ И ДОПОЛНИТЕЛЬНЫХ МОРФЕМ 119
3.7.1. ВЕСОВЫЕ КОЭФФИЦИЕНТЫ ДЛЯ ВОЗДЕЙСТВИЙ СО СТОРОНЫ МОРФЕМ РАЗЛИЧНЫХ
ТИПОВ 120
4
3.7.2. ОПРЕДЕЛЕНИЕ НОРМИРУЮЩЕГО КОЭФФИЦИЕНТА А 121
РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТА 124
ОЦЕНКА ЭФФЕКТИВНОСТИ УЛУЧШЕННОГО ПОИСКОВОГО ИНДЕКСА 125
ТЕСТОВАЯ КОЛЛЕКЦИЯ 125
ОЦЕНКА КАЧЕСТВА ИНДЕКСАЦИИ 127
ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ 129
АНАЛИЗ РЕЗУЛЬТАТОВ 135
ВЫВОДЫ 136
ЗАКЛЮЧЕНИЕ 138
ЛИТЕРАТУРА 140
ПРИЛОЖЕНИЯ 150
ПРИЛОЖЕНИЕ 1. ИНФОРМАЦИЯ О НАПРАВЛЕНИЯХ И УЧАСТНИКАХ
КОНФЕРЕНЦИИ TREC 151
ПРИЛОЖЕНИЕ 2. ТЕСТОВАЯ КОЛЛЕКЦИЯ, ИСПОЛЬЗОВАВШАЯСЯ ПРИ
ИСПЫТАНИЯХ ПРОГРАММНЫХ МОДУЛЕЙ РАЗРАБОТАННОЙ СИСТЕМЫ 155
ПРИЛОЖЕНИЕ 3. ПОВЫШЕНИЕ КАЧЕСТВА ПОИСКОВОГО ИНДЕКСА НА ОСНОВЕ
РЕАКЦИИ ПОЛЬЗОВАТЕЛЯ 156
ПРИЛОЖЕНИЕ 4. ОПИСАНИЕ СИТУАЦИЙ, РАССМАТРИВАЕМЫХ ПРИ
МОДЕЛИРОВАНИИ ПРОЦЕССА ОБУЧЕНИЯ МСНС 159
ПРИЛОЖЕНИЕ 5. АЛГОРИТМЫ ПОИСКА НАИБОЛЬШЕЙ ОБЩЕЙ ПОДСТРОКИ.,.., 165
Введение к работе
При возникновении задачи перевода в электронный вид, например, библиотеки, фонд которой состоит из сотен тысяч книг, встаёт вопрос об обеспечении возможности эффективного поиска нужной информации по поисковому образу. Причем под образом можно понимать любую совокупность характеристик. В данной работе под поисковым образом будем понимать некоторое множество слов, отражающих смысл документа.
Кроме того, в реальных поисковых системах поиск, как правило, опосредован: отбор ведется по вторичным документам, таким как библиографические и реферативные описания. При этом эффективность поиска (по крайней мере, сокращение времени просмотра) обеспечивается за счет систематизации массива по предметному, алфавитному или каким-либо другим признакам.
Проблеме информационного поиска посвящен ряд форумов. Среди них наиболее известны TREC, SIGIR и CLEF [1, 2, 3]. На форуме TREC 2004 запланирован новый трек, названный Terabyte Track. Это направление посвящено поиску по совокупности документов размера примерно порядка 1 Тб. (Overview TREC 2003, In Proceedings of the twelfth Text REtrieval Conference, TREC 2003, NIST Special Publication 500-255, 2003). К вопросам полнотекстового поиска на TREC относится направление TREC 2003 Robust Retrieval Track. Это направление было предложено только в 2003 году, и в нём приняли участие 16 групп участников из 93-х, участвовавших в форуме. Целью является совершенствование обычного ad-hoc поиска, ориентированного на поиск текста в узко специальных областях.
На актуальность решения данных вопросов обращают внимание последние публикации по данной тематике [4]. Вопросам информационного поиска применительно для электронных библиотек в последние годы в нашей стране посвящен ряд научных работ. Например, кандидатская диссертация Сбойчакова К. О. на тему "Автоматизированная система смысловой обработки
б текстов при создании электронных фондов библиотеки" 2003 года. В нашем вузе в 2004 году была защищена кандидатская диссертация Андриенко Е. В. на тему "Исследование и разработка методов и моделей поиска адекватной информации в полнотекстовых базах данных".
Процедура поиска - это рутинный перебор массива документов, более или менее полно соответствующих интересующей теме, сосредоточенных в электронных хранилищах. Отбор обыкновенно проводится по значениям реквизитов или поисковым терминам. В компьютерных технологиях процесс отбора поисковых терминов из документов, из которых будет составляться поисковый образ, называется индексированием. Уточним это понятие.
Индексирование (indexing, индексация) это первичный процесс обработки документов для создания служебной информации, отражающей содержание данных документов. Подобная служебная информация называется индексом. Для индекса можно провести примерную аналогию с описанием литературных источников в виде аннотации, представленной в реферативной карточке традиционной библиотеки.
Таким образом, при переводе информации в электронный формат, отсканированный текст должен быть распознан и далее специально обработан для построения его индивидуального индекса. Однако задача построения полнотекстового индекса больших массивов текстов, например, объемом в сотни тысяч страниц, является одной из проблем компьютерного поиска. Здесь подлежат решению следующие вопросы:
полная автоматизация построения индекса без участия человека;
разработка способов сегментации индекса, с целью построения быстрых процедур его обработки;
результаты поиска должны быть удовлетворительными для пользователя и не требовать дополнительной информации из самих электронных документов;
Индекс должен включать слова из документов, совокупность которых позволяет максимально отразить смысл документов. Это отражение или соответствие между документом и его индексом называется в технике поисковых систем релевантностью. Таким образом, к индексу предъявляются два противоречивых требования: с одной стороны он максимально должен быть релевантен документу, а с другой стороны должен быть минимального объема. Отсюда вытекает еще одна проблема — как осуществить отбор слов из документа с учетом выполнения этих требования. Определение взаимной релевантности неодинаковых слов путём выделения общих морфологических составляющих так же на данный момент исследуется рядом учёных. Например, программа Linguistica профессора Джона Голдсмита (John A. Goldsmith). Данный проект разрабатывается в Чикагском университете и представлен на сайте humanities.uchicago.edu/facithy/goldsmith). Все они объединяются общим понятием стемминга. Определим точнее это понятие.
Стемминг - метод выделения морфологически постоянных частей слов путём удаления известных частей слов, выполняющих заведомо вспомогательную роль, в соответствии с заранее предопределёнными правилами.
Из публикаций на данную тематику [5, 6] следует, что на данный момент стемминг является наиболее применимым и наиболее эффективным методом повышения полноты ответов поисковых систем на пользовательские запросы. Наиболее известный алгоритм стемминга называется стимером Портера и предназначен для английского языка. Правила удаления переменных частей слов в морфологии конкретного языка составляются специалистами вручную, что также требует автоматизации.
Настоящая диссертационная работа выполнена в рамках данной проблематики и ставит своей целью разработку и исследование методов, алгоритмов и программ для автоматического полнотекстового индексирования документов в массивах большого объема.
В рамках поставленной цели в диссертации решаются следующие основные задачи'.
разработка метода, алгоритма, и реализация программных средств для автоматического выделения морфологических составляющих в словах текста;
разработка метода для определения взаимной похожести слова запроса и слова документа, позволяющего учесть совпадение дополнительных морфологических частей слов;
разработка эффективной структуры поискового индекса, позволяющей хранить информацию на разных языках и допускающей распределение частей индекса по различным устройствам хранения информации и реализация программных средств построения и управления таким индексом;
разработка метода оценки преимущества улучшенного морфологического индекса в сравнении с индексом, не учитывающим информацию о морфологии естественного языка.
Предметом исследования диссертационной работы являются методы и алгоритмы автоматического полнотекстового индексирования документов в массивах большого объема.
Научная новизна. В результате проведённых диссертационных исследований были разработаны:
метод и средства автоматического изучения морфологии естественного языка на основе кластеризации и нейросетевого подхода с использованием статистического анализа;
распределенный морфологический индекс, содержащий дополнительную информацию о морфологии слов и позволяющий хранить информацию на разных языках с ее распределением по различным устройствам хранения информации;
3) метод определения похожести запроса, состоящего из нескольких слов, и многостраничного документа, учитывающий совпадение дополнительных морфем слов.
Практическая ценность. На основе теоретических исследований, проделанных в диссертационной работе, получены следующие практические результаты:
Реализованы программные средства, осуществляющие:
a. индексирование распознанного текста,
b. улучшение построенного индекса с целью определения взаимной
релевантности близких слов с одинаковыми основными частями, но с
разными дополнительными морфемами и отсутствия релевантности
для разных слов, похожих по написанию.
c. оценку качества полученного поискового индекса.
Реализованная система индексирования и поиска может быть
использована:
a. для полнотекстового поиска по тексту, представленному в формате, не
допускающем проведения непосредственного последовательного
поиска, что может быть использовано при организации электронных
библиотек и других электронных хранилищ данных;
b. для автоматического формирования индексов и словарей большого
объёма, содержащих информацию о морфологии содержащихся в них
слов, на основе которых могут решаться задачи распознания
синтаксической структуры текста на естественном языке в рамках
проверки орфографии, автоматической фильтрации сообщений и
документов, автоматическом поиске спама;
c. для автоматического определения морфологии текста на естественном
языке, поддающемся стемминг-обработке.
Достоверность основных положений работы и применимость предложенных методов подтверждается использованием теории вероятностей, кластерного анализа и самообучающихся нейронных сетей и подтверждается результатами проведенных модельных экспериментов
На защиту выносятся следующие результаты диссертационного исследования:
методы и алгоритмы автоматического изучения морфологии текста, не требующие априорной информации о морфологии естественного языка;
организация структуры поискового индекса, позволяющего хранить информацию на разных естественных языках и допускающего распределение частей индекса по различным устройствам хранения информации;
методы оценки преимущества улучшенного морфологического индекса в сравнении с индексом, не учитывающим информацию о морфологии текста.
Использование результатов работы.
Результаты работы использованы при построении электронной библиотеки ТРТУ при выполнении проекта НФПК, (по контракту №A2/069/S/l на тему: «Разработка и создание комплекса электронной библиотеки для повышения эффективности обучения в вузе с широкой сетью филиалов»), в электронной библиотеке международной лаборатории ELDIC и в учебном процессе по магистерской программе 552805 «Интеллектуальные системы» для проведения научных исследований в области скантехнологий и электронных архивов.
Апробация работы.
Основные результаты работы докладывались на Всероссийских научных конференциях аспирантов и студентов "Техническая кибернетика, радиоэлектроника и системы управления", проводившихся в Таганроге в 2002 и 2004 годах, на VIII Всероссийской научно-технической конференции VIII ВНТК "Информационные технологии в науке, проектировании и производстве"
11 (Ниж. Новгород: МВВО АТН РФ, 2003 г.), VI Всероссийской научной конференции с международным участием "Новые информационные технологии. Разработка и аспекты применения" (Таганрог: ТРТУ, 2003 г.), всероссийских научных конференциях молодых учёных и аспирантов "Информационные технологии, системный анализ и управление" (Таганрог: ТРТУ, 2003, 2004 гг.), Международной научно-методической Интернет-конференции "Информационные технологии в образовательной среде современного вуза" (Белгород: БГТУ им. В.Г. Шухова, 2004 г.), а так же, VII Всероссийской конференции молодых ученых и аспирантов с международным участием "Новые информационные технологии. Разработка и аспекты применения" (Таганрог: ТРТУ, 2004 г.).
Публикации. По теме диссертации опубликовано 10 печатных работ, в которых отражены основные результаты диссертации.
Структура и объём работы.
Диссертация включает введение, три главы, заключение, список литературы и пять приложений. Основная часть работы изложена на 149 страницах машинописного текста, 50 рисунках, 89 формулах и 9 таблицах.
