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

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

Кизянов Александр Фёдорович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ И СРЕДСТВ ПОЛНОТЕКСТОВОГО ИНДЕКСИРОВАНИЯ ИНФОРМАЦИИ С УЧЁТОМ МОРФОЛОГИИ ЕСТЕСТВЕННОГО ЯЗЫКА

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

Таганрог 2005

Работа выполнена на кафедре математического обеспечения и применения ЭВМ Таганрогского государственного радиотехнического университета

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

Доктор технических наук, профессор, ВИШНЯКОВ Юрий Муссович

Официальные оппоненты:

доктор технических наук, профессор ЧЕРНУХИН Юрий Викторович кандидат технических наук СПИРИДОНОВ Олег Борисович

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

Южно-Российский региональный центр информатизации высшей школы (ЮГИНФО), г. Ростов на Дону

Защита состоится 29 сентября 2005г. в 14.20 на заседании диссертационного совета Д 212.259.02 Таганрогского государственного радиотехнического университета по адресу: 347928, Таганрог, ГСП-17а, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан

Учёный секретарь диссертационного совета д.т.н., проф.

Бабенко Л. К.

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

Актуальность темы. При создании больших электронных архивов, например, таких как электронные библиотеки, фонд которой состоит из сотен тысяч книг, необходимо обеспечить возможности эффективного поиска документов, содержащих необходимую информацию. Данная проблема настолько актуальна, что ей посвящён ряд международных конференций. Среди них наиболее известны TREC, SIGIR и CLEF. На форуме 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 2003 Robust Retrieval Track. Это направление было предложено только в 2003 году, оно направлено на совершенствование ad-hoc поиска в узкоспециальных областях.

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

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

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

Таким образом, можно выделить следующие проблемы полнотекстового поиска, подлежащие решению:

■ автоматизация построения индекса, позволяющая обойтись без учасшя человека;

ЩИОТЯЛИЯР .

ммтш I

■ разработка принципов сегментации индекса с целью построения быстрых процедур его обработки;

■ создание методов поиска локализованных в индексе с заданной степенью релевантности.

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

Задачи работы. Решение задач автоматического полнотекстового индексирования предполагает решение трёх основных задач:

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

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

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

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

Объект исследования - методы полнотекстового индексирования и информационного поиска.

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

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

Положения, выносимые на защиту.

1) методы и алгоритмы автоматического изучения морфологии набора слов, не требующего априорной информации о морфологии языка;

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

*•«< «•!•*

* *

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

Научная новизна.

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

1) метод и средства автоматического изучения морфологии естественного языка на основе кластеризации и нейросетевого подхода с использованием статистического анализа;

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

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

Значимость полученных результатов для теории и практики.

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

На основе теоретических результатов, полученных в диссертационной работе, получены следующие результаты:

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

■ подготовку растровых изображений к распознаванию,

■ индексирование распознанного текста,

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

• оценку качества полученного поискового индекса.

Реализованная система индексирования и поиска может быть использована:

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

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

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

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

Апробация работы. Основные результаты работы докладывались на Всероссийских научных конференциях аспирантов и студентов 'Техническая кибернетика, радиоэлектроника и системы управления", проводившихся в Таганроге в 2002 и 2004 годах, на VIII Всероссийской научно-технической конференции VIII ВНТК "Информационные технологии в науке, проектировании и производстве" (Ниж. Новгород: МВВО АТН РФ, 2003 г.), VI Всероссийской научной конференции с международным участием "Новые информационные технологии. Разработка и аспекты применения" (Таганрог: ТРТУ, 2003 г.), Всероссийских научных конференциях молодых учёных и аспирантов "Информационные технологии, системный анализ и управление" (Таганрог: ТРТУ, 2003, 2004 гг.), Международной научно-методической Интернет-конференции "Информационные технологии в образовательной среде современного вуза" (Белгород: БГТУ им. В.Г. Шухова, 2004 г.), а так же, VII Всероссийской конференции молодых ученых и аспирантов с международным участием "Новые информационные технологии. Разработка и аспекты применения" (Таганрог: ТРТУ, 2004 г.).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При рассмотрении самого распространённого на сегодняшний день метода автоматического морфологического анализа - метода стимминга, выявлены основные недостатки такого подхода:

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

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

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

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

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

■ организации процесса поиска без обращения непосредственно к проиндексированному тексту. ^

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

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

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

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

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

3) разработка автоматического метода анализа морфологии текста на естественном языке, не зависящего от правил выделения частей слов, составляемых вручную;

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

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

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

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

[слово] = [префикс]+[осн.часть]+[постфикс]\ (1)

причём количество таких морфем каждого типа меньше числа полученных таким образом слов. На основе (1) для автоматического анализа морфологии было разработано упрощённое описание морфемной структуры слова:

[Рге] [М)'г] [Рвг].

(2)

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

Для обеспечения поддержки многоязычности, тематического разделения и возможности распределения по разным устройствам хранения информации, была разработана блочная структура поискового индекса. Каждый блок строится и обрабатывается при поиске самостоятельно. Каждому блоку соответствует конкретный язык и тематика. Тематика блока задаётся вручную, а язык определяется по принадлежности символов слова в блоке. Размер блока ограничен, и при необходимости может быть создано любое нужное количество блоков для одного и того же языка и тематического раздела. Блок индекса (см. Рис 1) представляет собой надстройку над инвертированным файлом, который и содержит полную информацию обо всех точках индексации.

Рис. 1. Структура блока поискового индекса

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

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

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

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

В основу данного подхода положены предположение (1) и упрощённое описание морфологии слова (2). Улучшение реализуется с применением разработанной в рамках этой работы модифицированной самообучающейся нейронной сети для обработки текстовой информации (МСНС).

Преимущество метода определения морфологии текста на основе применения МСНС по сравнению с методом стимминга:

■ автоматически определяется морфология слов представленных в блоке индекса.

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

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

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

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

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

■ присутствие в паре слов одинаковых морфем считается равновероятным для морфем этого типа;

■ символы из алфавита делятся на две группы - часто встречающиеся и редко встречающиеся;

■ вероятность случайного совпадения в паре слов отдельных редко встречающихся символов считается равной нулю, а совпадения часто встречающихся символов принимаются равновероятными;

■ вероятность случайного совпадения подстрок в словах равна вероятности совместной совпадения входящих в них символов.

Так же, было проведено разделение процессов обучения МСНС на обучение по основным частям слов и по дополнительным морфемам в зависимости от того, похожесть морфем какого типа вызвала этот процесс. Были выделены три возможных типа изменения морфемы в процессе обучения: расширение морфемы, сокращение морфемы и закрепление границы разбивки.

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

Для обучения МСНС по основным частям слов и дополнительным морфемам по отдельности:

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

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

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

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

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

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

В заключении формулируются основные научные и практические результаты диссертационного исследования:

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

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

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

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

5) Разработан метод автоматического изучения морфологической структуры слов на основе применения нейронной сети. Это метод автоматического изучения морфологии слов, основанный на применении МСНС. Применением этого метода достигается автоматическое определение повторяющихся частей слов, использующихся в словах, сохранённых в блоке индекса поисковой системы.

В приложении 1 приводятся сводная таблица по участникам конференций TR.EC за период 1992-2003 гг. и списки участников ТЛЕС-2002 и ТЯЕС-2003.

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

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

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

которые рассматриваются при моделировании процесса обучения МСНС в третьей главе.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В ходе проведённых исследований, получены следующие новые результаты: I

л

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

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

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

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

5) Проведено формальное моделирование процесса обучения МСНС, показавшее эффективность её применения для выделения морфем в ' словах естественного языка.

6) Разработан метод оценки эффективности поискового индекса, построенного с помощью МСНС, по сравнению с индексом, в котором ' не учитывается информация о морфологии слов. С применением разработанного метода проведена оценка качества поискового индекса, построенного во время эксперимента. Показано, что, благодаря учёту морфологии слов, эффективность поиска повысилось.

Результаты работы использованы при построении электронной библиотеки ТРТУ при выполнении проекта НФПК, (по контракту

№A2/069/S/l на тему: «Разработка и создание комплекса электронной библиотеки для повышения эффективности обучения в вузе с широкой сетью филиалов»), в электронной библиотеке международной лаборатории ELDIC и в учебном процессе по магистерской программе 552805 «Интеллектуальные системы» для проведения научных исследований в области скантехнологий и электронных архивов.

СПИСОК ПУБЛИКАЦИЙ

1. Кизянов А. Ф. Рассмотрение возможности расширения индексации текста на основе стимминга с возможностью автоматической индексации текста на произвольном языке // Перспективные информационные технологии и интеллектуальные системы. №3(19)/2004. http ://р itis.tsure.ru/files 19/12 .pdf

2. Вишняков Ю. М., Хашковский В. В., Кизянов А. Ф. Построение полнотекстовой поисковой системы на основе нейронной сети // Материалы VIII Всероссийской научно-технической конференции VIH ВНТК "Информационные технологии в науке, проектировании и производстве". Н. Новгород. 2003. С. 15.

3. Вишняков Ю. М., Хашковский В. В., Кизянов А. Ф. Метод частичного морфологического анализа кластеризацией текстового массива на неизвестном языке // Материалы VIII Всероссийской научно-технической конференции VIII ВНТК "Информационные технологии в науке, проектировании и производстве". Н. Новгород. 2003. С. 16.

4. Вишняков Ю. М., Кизянов А. Ф. Самообучающийся морфологический анализатор для статического корпуса текстов // Сборник трудов VI Всероссийской научной конференции с международным участием "Новые информационные технологии. Разработка и аспекты применения". Таганрог: Таганрогский радиотехнический университет, 2003. С.479-482.

5. Вишняков Ю. М., Кизянов А. Ф. Корректировка разбивки слов на морфемы с помощью самообучающейся нейронной сети // Материалы Международной научно-методической Интернет-конференции "Информационные технологии в образовательной среде современного вуза". Белгород: Изд-во БГТУ им. В.Г. Шухова. 2004. С.31-36.

6. Вишняков Ю. М., Кизянов А. Ф. Усовершенствованная самообучающаяся нейронная сеть для корректировки разбивки слова на морфемы // Материалы VII Всероссийской конференции молодых ученых и аспирантов с международным участием "Новые инфор-

»146 0 6

мационные технологии. Разработка и аспекты применения". Таганрог. 2004.

7. Кизянов А. Ф. Повышение качества отсканированных изображений текста // Материалы VII Всероссийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" КРЭС-2004. Таганрог. 2004. С.121.

8. Кизянов А. Ф. Построение полнотекстовой поисковой системы для нужд электронной научной библиотеки // Материалы Всероссийской научной конференции молодых учёных и аспирантов "Информационные технологии, системный анализ и управление". Таганрог: Таганрогский радиотехнический университет, 2003. С.60.

9. Кизянов -А. Ф. Организация индекса поисковой системы библиотеки Н Материалы II Всероссийской научной конференции молодых учёных, аспирантов и студентов "Информационные технологии, системный анализ и управление". Таганрог. 2004. С.89-90.

10. Кизянов А. Ф. Автоматическое изучение морфологии произвольного текста // Материалы II Всероссийской научной конференции молодых учбных, аспирантов и студентов "Информационные технологии, системный анализ и управление". Таганрог. 2004. С. 91-92.

Личный вклад автора в работах, написанных в соавторстве, состоит в следующем: [2,3,4] - разработка метода кластеризации слов по дополнительным морфемам, [5, б] - разработка самообучающейся нейронной сети для обработки текста

РНБ Русский фонд

2006-4 15578

п. мшпиа

Соискатель

Тип.ТРТУ Заказ тир. /ООэкз.

ВВЕДЕНИЕ.

ГЛАВА 1. ИССЛЕДОВАНИЕ МЕТОДОВ ПОСТРОЕНИЯ ПОЛНОТЕКСТОВЫХ ПОИСКОВЫХ ИНДЕКСОВ.

1.1. АНАЛИЗ МОДЕЛЕЙ ИНФОРМАЦИОННОГО ПОИСКА.

1.2. АНАЛИЗ МЕТОДОВ ПОЛНОТЕКСТОВОЙ ИНДЕКСАЦИИ ТЕКСТА.

1.2.1. МЕСТО ПОЛНОТЕКСТОВОГО ПОИСКА СРЕДИ ЗАДАЧ В ИНФОРМАЦИОННОМ ПОИСКЕ.

1.2.2. ОСНОВНЫЕ МЕТОДЫ ПОСТРОЕНИЯ ПОЛНОТЕКСТОВЫХ ИНДЕКСОВ.

1.2.3. ВЫВОД О ПРИМЕНИМОСТИ МЕТОДОВ ИНДЕКСИРОВАНИЯ ДЛЯ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ.

1.3. АНАЛИЗ ПОИСКА ПО ЭЛЕКТРОННОЙ БИБЛИОТЕКЕ.

1.3.1. ПРОБЛЕМАТИКА ОРГАНИЗАЦИИ ПОИСКА.

1.3.2. АНАЛИЗ МЕТОДА СТЕММИНГА.

1.4. ВЫБОР МЕТОДОВ ИНДЕКСИРОВАНИЯ, ДОПУСКАЮЩИХ ИЕРАРХИЧЕСКУЮ ОРГАНИЗАЦИЮ ПАМЯТИ.

1.4.1. ИЕРАРХИЯ ПАМЯТИ.

1.4.2. ВЫБОР МЕТОДОВ ИНДЕКСИРОВАНИЯ.

ВЫВОДЫ.

ГЛАВА 2. ПОСТРОЕНИЕ И ПРИМЕНЕНИЕ МОРФОЛОГИЧЕСКОГО ИНДЕКСА.

2.1. УПРОЩЁННОЕ ОПИСАНИЕ МОРФОЛОГИИ СЛОВА.

2.2. МОДЕЛЬ ИНФОРМАЦИОННОГО ПОИСКА, УЧИТЫВАЮЩАЯ МОРФОЛОГИЮ ТЕКСТА.

2.3. ПОСТРОЕНИЕ И ИСПОЛЬЗОВАНИЕ ПОИСКОВОГО ИНДЕКСА.

2.3.1. БЛОЧНАЯ СТРУКТУРА ПОИСКОВОГО ИНДЕКСА.

2.3.2. СТРУКТУРА БЛОКА ИНДЕКСА.

2.3.3. НАПОЛНЕНИЕ ИНДЕКСА.

2.3.4. УЛУЧШЕНИЕ ИНДЕКСА.

2.4. УЛУЧШЕНИЕ ИНДЕКСА С ПОМОЩЬЮ НЕЙРОННОЙ СЕТИ.

2.4.1. ОШИБКИ УЛУЧШЕНИЯ ПОИСКОВОГО ИНДЕКСА.

2.4.2. МОДИФИЦИРОВАННАЯ НЕЙРОННАЯ СЕТЬ ДЛЯ ОБРАБОТКИ ТЕКСТА.

2.5. ПОИСК ПО МОРФОЛОГИЧЕСКОМУ ИНДЕКСУ.

2.6. ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ПОИСКОВОГО ИНДЕКСА.

2.6.1. СИГНАТУРА ПЕРВОГО ТИПА.

2.6.2. СИГНАТУРА ВТОРОГО ТИПА.

2.6.3. МОДИФИКАЦИЯ МЕТОДА РАЗРЕШЕНИЯ КОЛЛИЗИЙ "ОТКРЫТОЙ АДРЕСАЦИЕЙ".

2.6.4. ЛЕКСИКОГРАФИЧЕСКАЯ СОРТИРОВКА, УСКОРЯЮЩАЯ ПОИСК МАКСИМАЛЬНОЙ ДОПОЛНИТЕЛЬНОЙ МОРФЕМЫ В СЛОВЕ.

ВЫВОДЫ.

ГЛАВА 3. МОДЕЛИРОВАНИЕ ПРОЦЕССА ОБУЧЕНИЯ ПРЕДЛОЖЕННОЙ НЕЙРОННОЙ СЕТИ.

3.1. МОДЕЛИРОВАНИЕ ЯЗЫКА.

3.2. ВОЗДЕЙСТВИЯ СО СТОРОНЫ ДОПОЛНИТЕЛЬНЫХ МОРФЕМ.

3.2.1. ВЕРОЯТНОСТИ ИЗМЕНЕНИЙ РАЗНЫХ ТИПОВ ПРИ ОБУЧЕНИИ ДОПОЛНИТЕЛЬНЫХ МОРФЕМ.

3.2.2. СООТНОШЕНИЯ ВЕРОЯТНОСТЕЙ ДЛЯ ДОПОЛНИТЕЛЬНЫХ МОРФЕМ.

3.3. ВЕСОВЫЕ КОЭФФИЦИЕНТЫ РАЗНЫХ ТИПОВ ВОЗДЕЙСТВИЙ ДЛЯ ДОПОЛНИТЕЛЬНЫХ МОРФЕМ.

3.3.1. ВЫВОДЫ ПО ОБУЧЕНИЮ ДОПОЛНИТЕЛЬНЫХ МОРФЕМ.

3.3.2. ОЦЕНКА СООТНОШЕНИЙ ВЕСОВЫХ КОЭФФИЦИЕНТОВ ВОЗДЕЙСТВИЙ НА ГРАНИЦУ РАЗБИВКИ СО СТОРОНЫ ДОПОЛНИТЕЛЬНОЙ МОРФЕМЫ.

3.4. ОБУЧАЮЩИЕ ВОЗДЕЙСТВИЯ СО СТОРОНЫ ОСНОВНЫХ ЧАСТЕЙ СЛОВ.

3.4.1. UNDER-STEMMING.

3.4.2. СЛУЧАИ OVER-STEMMING.

3.4.3. СОВПАДЕНИЕ ГРАНИЦ РЕАЛЬНЫХ МОРФЕМ С ГРАНИЦАМИ ВЫДЕЛЕННЫХ МОРФЕМ

3.4.4. ОШИБОЧНЫЕ ВОЗДЕЙСТВИЯ ВСЛЕДСТВИЕ СЛУЧАЙНОГО СОВПАДЕНИЯ ПОДСТРОК СИМВОЛОВ.

3.5. СООТНОШЕНИЯ ВЕРОЯТНОСТЕЙ ДЛЯ ОСНОВНЫХ ЧАСТЕЙ СЛОВ ПРИ НОВОМ ПОДХОДЕ.

3.5.1. UNDER-STEMMING.

3.5.2. СЛУЧАИ OVER-STEMMING.

3.5.3. СОВПАДЕНИЕ ГРАНИЦ РЕАЛЬНЫХ МОРФЕМ С ГРАНИЦАМИ ВЫДЕЛЕННЫХ МОРФЕМ

3.6. ВЕСОВЫЕ КОЭФФИЦИЕНТЫ ВОЗДЕЙСТВИЙ НА ГРАНИЦУ РАЗБИВКИ СО СТОРОНЫ ОСНОВНОЙ ЧАСТИ СЛОВА.

3.7. СООТНОШЕНИЕ ВОЗДЕЙСТВИЙ НА ГРАНИЦУ РАЗБИВКИ СО СТОРОНЫ ОСНОВНЫХ ЧАСТЕЙ СЛОВ И ДОПОЛНИТЕЛЬНЫХ МОРФЕМ.

3.7.1. ВЕСОВЫЕ КОЭФФИЦИЕНТЫ ДЛЯ ВОЗДЕЙСТВИЙ СО СТОРОНЫ МОРФЕМ РАЗЛИЧНЫХ ТИПОВ.

3.7.2. ОПРЕДЕЛЕНИЕ НОРМИРУЮЩЕГО КОЭФФИЦИЕНТА А.

3.8. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТА.

3.9. ОЦЕНКА ЭФФЕКТИВНОСТИ УЛУЧШЕННОГО ПОИСКОВОГО ИНДЕКСА.

3.9.1. ТЕСТОВАЯ КОЛЛЕКЦИЯ.

3.9.2. ОЦЕНКА КАЧЕСТВА ИНДЕКСАЦИИ.

3.9.3. ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ.

3.9.4. АНАЛИЗ РЕЗУЛЬТАТОВ.

ВЫВОДЫ.

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

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

Проблеме информационного поиска посвящен ряд форумов. Среди них наиболее известны 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, uchiccigo.eda/facaltv/goldsmith). Все они объединяются общим понятием стемминга. Определим точнее это понятие.

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

Из публикаций на данную тематику [5, 6] следует, что на данный момент стемминг является наиболее применимым и наиболее эффективным методом повышения полноты ответов поисковых систем на пользовательские запросы. Наиболее известный алгоритм стемминга называется стимером Портера и предназначен для английского языка. Правила удаления переменных частей слов в морфологии конкретного языка составляются специалистами вручную, что также требует автоматизации.

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

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

• разработка метода, алгоритма, и реализация программных средств для автоматического выделения морфологических составляющих в словах текста;

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

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

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

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

Научная новизна. В результате проведённых диссертационных исследований были разработаны:

1) метод и средства автоматического изучения морфологии естественного языка на основе кластеризации и нейросетевого подхода с использованием статистического анализа;

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

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

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

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

• Реализованная система индексирования и поиска может быть использована: a. для полнотекстового поиска по тексту, представленному в формате, не допускающем проведения непосредственного последовательного поиска, что может быть использовано при организации электронных библиотек и других электронных хранилищ данных; b. для автоматического формирования индексов и словарей большого объёма, содержащих информацию о морфологии содержащихся в них слов, на основе которых могут решаться задачи распознания синтаксической структуры текста на естественном языке в рамках проверки орфографии, автоматической фильтрации сообщений и документов, автоматическом поиске спама; c. для автоматического определения морфологии текста на естественном языке, поддающемся стемминг-обработке.

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

На защиту выносятся следующие результаты диссертационного исследования'.

• методы и алгоритмы автоматического изучения морфологии текста, не требующие априорной информации о морфологии естественного языка;

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

• методы оценки преимущества улучшенного морфологического индекса в сравнении с индексом, не учитывающим информацию о морфологии текста.

Использование результатов работы.

Результаты работы использованы при построении электронной библиотеки ТРТУ при выполнении проекта НФГТК, (по контракту №A2/069/S/l на тему: «Разработка и создание комплекса электронной библиотеки для повышения эффективности обучения в вузе с широкой сетью филиалов»), в электронной библиотеке международной лаборатории ELDIC и в учебном процессе по магистерской программе 552805 «Интеллектуальные системы» для проведения научных исследований в области скантехнологий и электронных архивов.

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

Основные результаты работы докладывались на Всероссийских научных конференциях аспирантов и студентов "Техническая кибернетика, радиоэлектроника и системы управления", проводившихся в Таганроге в 2002 и 2004 годах, на VIII Всероссийской научно-технической конференции VIII ВНТК "Информационные технологии в науке, проектировании и производстве"

Ниж. Новгород: МВВО АТН РФ, 2003 г.), VI Всероссийской научной конференции с международным участием "Новые информационные технологии. Разработка и аспекты применения" (Таганрог: ТРТУ, 2003 г.), всероссийских научных конференциях молодых учёных и аспирантов "Информационные технологии, системный анализ и управление" (Таганрог: ТРТУ, 2003, 2004 гг.), Международной научно-методической Интернет-конференции "Информационные технологии в образовательной среде современного вуза" (Белгород: БГТУ им. В.Г. Шухова, 2004 г.), а так же, VII Всероссийской конференции молодых ученых и аспирантов с международным участием "Новые информационные технологии. Разработка и аспекты применения" (Таганрог: ТРТУ, 2004 г.).

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

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

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

Результаты работы использованы при построении электронной библиотеки ТРТУ при выполнении проекта НФГТК, (по контракту №A2/069/S/l на тему: «Разработка и создание комплекса электронной библиотеки для повышения эффективности обучения в вузе с широкой сетью филиалов»), в электронной библиотеке международной лаборатории ELDIC и в учебном процессе по магистерской программе 552805 «Интеллектуальные системы» для проведения научных исследований в области скантехнологий и электронных архивов.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

5) Проведён формальный эксперимент для процесса обучения МСНС, показавший эффективность применения нейронной сети для выделения морфем в словах естественного языка.

6) Разработан метод оценки эффективности поискового индекса, построенного с помощью МСНС, по сравнению с индексом, в котором не учитывается информация о морфологии слов. С применением разработанного метода проведена оценка качества поискового индекса, построенного во время эксперимента. Показано, что, благодаря учёту морфологии слов, эффективность поиска повысилось.

1. D. Harman. Overview of the third text retrieval conference. 1. Proceedings Third Text Retrieval Conference (TREC-3), pp. 1-19, National Institute of Standards and Technology Special Publication 500-207, Gaithcrs-burg, Maryland (1995).

2. William Hersh and Paul Over. SIGIR workshop on interactive retrieval at TREC and beyond. SIGIR Forum, 34(l):24-27, Spring 2000.

3. M. F. Porter. An algorithm for suffix stripping. Program, 14:130-137. 1980.

4. H. L. Resnikoffand J. L. Dolby (1965), The Nature of Affixing in Written English. Part 1, in Mechanical Translation, 8, No. 3 (1965), Part 11 in Mechanical Translation 9, No. 2 (1966).

5. Karen Sparck Jones. Information Retrieval Experiment. Butterworths, London, 1981. G. Salton and M. J. McGill, editors. Introduction to Modern Information Retrieval. McGraw-Hill, 1983.

6. S. E. Robertson and K. Sparck Jones. Relevance weighting of search terms. Journal of the American Society for Information Science. 27:129-146. 1976.

7. К. W. Church and W. A. Gale. Inverse document frequency: a measure of deviations from Poisson. In Armstrong et al. (eds.). NLP using very large corpora, Kluwer Academic Publishers, 1999.

8. J.M. Ponte and W.B. Croft. A language modeling approach to information retrieval. In Proceedings of the 21st ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'98), 1998.

9. D. Hiemstra. A linguistically motivated probabilistic model of information retrieval. In Proceedings of the Second European Conference on Research and Advanced Technology for Digital Libraries (ECDL), pages 569-584, 1998.

10. D. Hiemstra and W. Kraaij. Twenty-One at TREC-7: Ad-hoc and cross-language track. In Proceedings of-the seventh Text, Retrieval Conference TREC-7, pages 227-238. NIST Special Publication 500-242, 1999.

11. D. R. H. Miller, T. Leek and R. M. Schwartz. BBN at TREC-7: using hidden markov models for information retrieval. In Proceedings of the seventh Text Retrieval Conference, TREC-7. pages 133-142. NIST Special Publication 500242, 1999.

12. D. R. H. Miller, T. Leek and R. M. Schwartz. A hidden Markov model information retrieval system. In Proceedings of the 22nd ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'99), pages 214221, 1999.

13. A. Berger and J. Lafferty. Information retrieval as statistical translation. In Proceedings of the 22nd ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'99), pages 222-229, 1999.

14. A. Berger and J. Lafferty. The Weaver system for document retrieval. In Proceedings of the eighth Text Retrieval Conference, TREC-8, NIST Special Publications.

15. D. Hiemstra and F. M. G. de Jong. Disambiguation strategies for cross-language information retrieval. In Proceedings of the third European Conference on Research and Advanced Technology for Digital Libraries (ECDL). pages 274293, 1999.

16. W. Kraaij, R. Pohlmann and D. Hiemstra. Twenty-One at TRJEC-8: using language technologie for information retrieval. In Proceedings of the eighth Text Retrieval Conference, TREC-8, NIST Special Publications.

17. K. Ng. A maximum likelihood ratio information retrieval model. In Proceedings of the eighth Text Retrieval Conference, TREC-8. NIST Special Publications.

18. F. Song and W.B. Croft. A general language model for information retrieval. In Proceedings of Eighth International Conference on Information and Knowledge Management (CIKM'99), 1999.

19. G. Salton, E. A. Fox and H. Wu. Extended boolean information retrieval. Communications of the ACM. 26(11): 1022-103 6, 1983.

20. Maron M.E., Kuhns J.L. On relevance, probabilistic indexing and information retrieval. Jornal of the ACM, No. 7, 1960, pp. 216-244.

21. Седжвик Роберт. Фундаментальные алгоритмы на С. СПб: ООО "ДиаСофтЮП", 2003. 1136 с.

22. Stolcke. 1994. Bayesian Learning of Probabilistic Language Models. Ph. D. thesis, University of California at Berkeley, Berkeley, CA.

23. J. H. Lee. Analyzing the effectiveness of extended boolean models in information retrieval. Technical Report TR95-1501. Cornell University. 1995. http://cs-tr.cs.cornell.edu/.

24. C. P. Paice. Soft evaluation of boolean search queries in information retrieval systems. Information, Technology: Research and Development, 3(l):33-42, 1984.

25. R. Baeza-Yates and Berthier Ribeiro-Neto. Modern Information Retieval. ACM Press, 1999.

26. Кохонен Т. Ассоциативные запоминающие устройства: Пер. с англ. М.: Мир, 1982.-384 е., ил.

27. D. Е. Knuth. The Art of Computer Programming: Sorting and Searching, volume 3. Addison-Wesley, Reading, Mass. (1973).

28. U. Manber and S. Wu. Glimpse: a tool to search through entire file systems. Technical Report 93-34, Department of Computer Science, The University of Arizona, Tucson, Arizona (1993).

29. Fredkin E., Commun. ACM, 3, 490-499 (1960).

30. Martin J., Computer Data Base Organization, 2nd printing, Prentice-Hall, Englewood Cliffs, N. J., 1977. Имеется перевод: Мартин Дж. Организация баз данных в вычислительных системах. - М.: Мир, 1978.

31. Flores I., Data Structure and Management, Prentice-Hall, Englewood Cliffs, N. J., 1970.

32. D. R. Morrison. PATRICIA practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM, 15(4):514-o34 (1968).

33. R. Baeza-Yates, E. F. Barbosa and N. Ziviani. Hierarchies of indices for text searching. In Proceedings RIAO'94 Intelligent Multimedia Information Retrieval Systems and Management, pp. 11-13. Rockefeller University, New York (1994).

34. Gonnet, G. H., Baeza-Yates, R. Handbook of Algorithms and Data Structures, 2nd edition, Addison Wesley, 1991.

35. U. Manber and G. Myers. Suffix arrays: a new method for on-line string searches. ACM-SIAMSymposium on Discrete Algorithms, pp. 319-327 (1990).

36. G. H. Gonnet. Pat 3. 1: An efficient text searching system. Center for the New Oxford English. Dictionary. University of Waterloo, Canada (1987).

37. G. Navarro. An optimal index for Pat arrays. In N. Ziviani, R. Baeza-Yates and G. Guimaracs, editors, Proceedings Third South American Workshop on String

38. Processing, Carleton University Press International Informatics Scries, v. 4, pages 214-227, Recife, Brazil (1996).

39. Baeza-Yates, R. A. Bounded Disorder: The Effect of the Index. Theoretical Computer Science, 168(1): 21-38 (1996).

40. Вишняков Ю. M. Введение в теорию алгоритмов: Учебное пособие. Ч. 1. Таганрог: Таганрогский радиотехнический университет, 1995. 86 с.

41. Вишняков Ю. М. Системное программирование. Конечные распознаватели. Таганрог, радиотехн. ин-т. Таганрог. 1991. 74 с.

42. Linda Schamber. Relevance and information behavior. Annual Review of Information Science and Technology, 29:3-48, 1994.1 http://www. nlpir. nist.gov/proiects/trecvL2 http://research.nii.ac.jp/ntcir,3 http://clef.iei.pi.cnr.it)

43. G. Salton. Automatic Information Organization and Retrieval. McGraw-Hill. New York. 1968.

44. M.E. Maron and J.L. Kuhns. On relevance, probabilistic indexing and information retrieval Journal of the ACM, 1960.

45. Кизянов А. Ф. Повышение качества отсканированных изображений текста // Материалы VII Всероссийской научной конференции студентов иаспирантов "Техническая кибернетика, радиоэлектроника и системы управления" КРЭС-2004. Таганрог. 2004. с. 121.

46. Кизянов А. Ф. Организация индекса поисковой системы библиотеки // Материалы II Всероссийской научной конференции молодых учёных, аспирантов и студентов "Информационные технологии, системный анализ и управление". Таганрог. 2004. сс. 89-90.

47. Кизянов А. Ф. Автоматическое изучение морфологии произвольного текста // Материалы II Всероссийской научной конференции молодых учёных, аспирантов и студентов "Информационные технологии, системный анализ и управление". Таганрог. 2004. сс. 91-92.

48. Макконелл Дж. Основы современных алгоритмов. 2-е дополненное издание. Москва: Техносфера, 2004. — 368с.

49. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ / Пер. с англ. Под ред. А. Шеня. М.: МЦНМО, 2002. - 960 е.: 263 ил.

50. Когаловский М. Р. Перспективные технологии информационных систем. -М.: ДМК Пресс; М.: Компания АйТи, 2003. 288 с.

51. Круглов В. В., Борисов В. В., Искуственные нейронные сети: Теория и практика — М.: Горячая линия Телеком, 2001.

52. И. В. Сегалович. Как работают поисковые системы. Статья на сайте http://www.dialog-21 .ги/

53. Принципы самоорганизации. Пер. с англ. /Под ред. Лернера А. Я. М.: Мир, 1966.

54. Ден Маргулис, Классическое руководство по цветокоррекции, М.: РТВ-Медиа, 2001. 400с.: илл.

55. Иванченко А. Г., Персептрон — системы распознавания образов.// К.: Наукова думка. 1972.

56. У. Дал, Э. Дейкстра, К. Хор, Структурное программирование, М.: Мир, 1975,-247 с.

57. С. Faloutsos. Signature files. In W. В. Frakes and R. Baeza-Yates, editors, Information Retrieval Data Structures and Algorithms, pp. 44-45, Prentice-Hall, Englcwoods Cliff, N. J. (1992).

58. D. A. Ford and S. Christodoulakis. File organizations for optical disks. In W. B. Frakes and R. Baeza-Yates, editors, Information Retrieval Data Structures and Algorithms, pp. 83-101, Prentice-Hall, Englewoods Cliff, N. J. (1992).

59. G. H. Gonnet. Unstructured data base or very efficient text searching. In Proceedings of the Second ACM SIGACT/SIGMOD Symposium on Principles of Database Systems, pp. 117-124, Atlanta, Georgia (1983).

60. K. Sparck Jones and C. van Rijsbergen. Report on the need for and provision of an "ideal" information retrieval test collection. British Library Research and Development Report 5266, Computer Laboratory, University of Cambridge, 1975.

61. H.R. Turtle and W.B. Croft. A comparison of text retrieval models. The Computer Journal, 35(l):279-289, 1992.

62. Ellen M. Voorhees. Variations in relevance judgments and the measurement of retrieval effectiveness. Information, Processing and Management, 36:697-716, 2000.

63. J. G. Wolff. 1982. Language acquisition, data compression and generalization. Language and Communication, 2(l):57-89.

64. S. К. M. Wong and Y. Y. Yao. On modelling information retrieval with probabilistic inference. ACM Transactions on Information Systems, 13(l):38-68, 1995.

65. R. J. Solomonoff. 1960. The mechanization of linguistic learning. In Proceedings of the 2nd International Conference on Cybernetics, pages 180-193.

66. G. Salton, editor. The SMART Retrieval System: Experiments in Automatic Document Processing. Prentice-Hall, Inc. Englewood Cliffs, New Jersey, 1971.

67. Ramakrishna, M. and Mukhopadhyay, P. "Analysis of Bounded Disorder file organization", Proc. 7th PODS, San Francisco, 1988, 117-125.

68. Ramakrishna, M. "Bounded Disorder File Organization", IEEE Trans, on Knowledge Engineering 6 (1994), 79-85.

69. Ramamohanarao K., Lloyd, J. W. Dynamic Hashing Schemes. The Computer Journal, Vol. 25(4), 1982, pp. 478-485.

70. D. C. Olivier. 1968. Stochastic Grammars and Language Acquisition Mechanisms. Ph. D. thesis, Harvard University, Cambridge, Massachusetts.

71. Litwin, W. and Lomet, D. "A New Method for Fast Data Searches with Keys", IEEE Software 4, 2 (1987), pp. 16-24.

72. Larson, P-A. Linear Hashing with Partial Expansions. In Proceedings of 6th. Conf. V. L. Data Bases, Montreal, Canada, ACM, October 1980, pp. 224-232.

73. Z. Harris. 1968. Mathematical Structure of Language. Wiley, New York.