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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования «Курский государственный университет»

Кафедра программного обеспечения и администрирования информационных систем

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

на соискание квалификации математик - программист

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

Автор работы Абрамов Алексей Викторович

Обозначение дипломной работы ВКРС.КГУ.010503.65.10.001

Группа МОАИС-53

Специальность: 010503.65 «Математическое обеспечение и администрирование информационных систем»

Руководитель дипломной работы

А. В. Абрамов

Консультанты по разделам:

Технологический В. Г. Белов

Нормоконтроль В. Г. Белов.

Заведующий кафедрой ПО и АИС

А.П. Жмакин

Курск 2010г.

SUMMARY

Qualifying work is devoted to problem of automatic text processing. The urgency of improvement of this methodology is unconditional. The saved up huge text data, both on the scale of the separate organisations, and in Internet does claimed set of problems connected with the analysis of the text information.

The purpose of work consists in working out and realisation the morphological dictionary in the form of treelike structure, and methods and algorithms to work with it.

The used programming language - Java.

Work is declared on 102 pages of the typewritten text, consists of conducting, system engineering and conclusions.

Keywords of work: «Automatic text processing», «morphology», «the morphological dictionary», «the frequency analysis», «the thematic analysis».

The created qualifying work is claimed and actual.

1. ВВЕДЕНИЕ

Проблема автоматической (интеллектуальной) обработки текстов на естественном языке возникла в конце 60 - начале 70-х. гг. С тех пор работа по созданию систем АОТ продвинулась достаточно далеко - имеется как положительный, так и не совсем опыт их создания. Это в первую очередь связано с невысоким качеством распознавания фраз, жестких требований к синтаксису «естественного языка», а также больших затрат машинного времени и ресурсов, необходимых для их работы. Практически во всех системах машинного понимания текста используется ограниченный естественный язык, поскольку полной и строгой формальной модели ни для одного естественного языка пока не создано[1].

Актуальность разработки и усовершенствования методологии АОТ безусловна. Накопленные огромные текстовые данные, как в масштабе отдельных организаций, так и в Internet делают востребованными следующие задачи связанные с анализом текстовой информации[2]:

· получение сводной аналитической информации по массиву текстов;

· поиск целевой информации в массиве текстов;

· структурирование данных, содержащихся в разрозненном виде в массиве текстов;

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

· извлечение знаний из текстов и заполнение баз знаний;

· классификация текстов на основе извлеченной информации.

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

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

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

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

Задача - Исследование методов и технологий автоматической обработки ЕЯ-текстов.

2. РАЗРАБОТКА СИСТЕМЫ

2.1 Анализ альтернатив

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

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

Morphlogy - определяет словоформы слов, корни и начальные формы. Для реализации поиска с учетом словоформ данная система получает корень слова и просто проводит поиск по базе данных SQL-оператором LIKE.

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

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

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

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

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

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

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

2.2 Анализ требований к системе

2.2.1 Описание предметной области

Модель предметной области изображена на рисунке 1.

Рисунок 1- Модель предметной области

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

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

Алгоритмы морфологического анализа делятся на две группы: словарные и бессловарные. Бессловарные алгоритмы более компактны и производительны, но обладают не высокой точностью. На практике используют словарный метод, предполагающий наличие словаря основ и флексий. Морфологический словарь - это словарь, в котором дается разъяснение значения и употребления слов и их грамматических категорий, а также хранятся словоформы. По словарю отыскиваются допустимые наборы атрибутов для каждой графемы. Одной графеме может соответствовать несколько наборов атрибутов. В этом случае принято говорить о так называемой морфологической омонимии.

В других случаях варианты порождаются разными лексемами. В задачу морфологического анализа входит установление соответствия между словоформой в принятой орфографической записи и именем соответствующей лексемы с набором ее морфологических характеристик. Простейшим способом установления соответствия является использование словаря словоформ, где каждой словоформе ставится в соответствие ее структура. Однако данный путь не применим для русского языка, так как полная парадигма русского глагола включает 225 словоформ. Например, лексема ДЕЛАТЬ должна обрабатываться 225 индивидуальными правилами[5].

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

- приставка (префикс),

- основа,

- муффикс,

- окончание.

Набор характеристик всей словоформы образуется объединением характеристик составляющих ее морф. Набор характеристик морфы состоит из одной или нескольких характеристик, представляющих собой значения соответствующих морфологических признаков. В [5] для русского языка выделяются 12 морфологических признаков:

1) часть речи (существительное, прилагательное, глагол, наречие, числительное, предлог, композит, союз, частица);

2) одушевленность (одушевленное, неодушевленное);

3) род (мужской, женский, средний);

4) число (единственное, множественное);

5) падеж (именительный, родительный, партитивный, дательный, винительный, творительный, предложный, местный);

6) степень сравнения (сравнительная, превосходная);

7) краткость (краткое);

8) репрезентация (изъявительное наклонение, повелительное наклонение, инфинитив, причастие, деепричастие);

9) вид (несовершенный, совершенный);

10) время (настоящее, будущее, прошедшее);

11) лицо (первое лицо, второе лицо, третье лицо);

12) пассивность (страдательный, действительный).

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

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

2.2.2 Требования пользователя к программному изделию

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

1) объект - морфологический словарь,

2) основная функция - частотный анализ текста,

3) возможность дополнения морфологического словаря,

4) возможность редактирования и дополнения стоп-словаря,

5) загрузка словарей из текстовых файлов,

6) возможность установки порогового значения при частотном анализе,

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

8) вывод результатов - на экран и в файл,

9) форматы вывода - txt,

10) требования к операционной среде - ос windows 2000/xp/vista,

11) требования к языку программирования - java.

2.2.3 Входные данные

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

2.2.4 Выходные данные

Список возможных ключевых слов с указанием их частоты появления в заданном тексте.

2.2.5 Требования к интерфейсу

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

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

2.2.6 Требования к составу и параметрам технических средств

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

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

- процессор, аналогичный Intel Pentium 4 и выше;

- оперативная память объемом не менее 512 Мб;

- накопитель на жестком диске со свободным местом 100 Мб;

- видеоадаптер SVGA;

- клавиатура;

- манипулятор типа “мышь”.

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

В комплект поставки программного продукта должны входить следующие компоненты:

- исходные тексты модулей, согласно заданию на дипломную работу, в среде Net Beans 6.0;

- программная документация;

- откомпилированный JAR-файл.

Продукт должен размещаться в виде исходных, или откомпилированных файлов на гибких магнитных дисках. В процессе работы могут использоваться Flash, CD-R/-RW, DVD-R/RW, или другие носители информации.

2.2.7 Модель вариантов использования

В соответствии с основными требованиями пользователя можно выделить следующие действующие лица (Таблица 1).

Таблица 1 - Действующие лица

Термин	Значение
Пользователь	Лицо, желающее провести частотный анализ текста

Набор функций (вариантов использования) реализуемый разрабатываемой программной системой представлен в таблице 2.

Таблица 2 - Набор вариантов использования

Термин	Значение
Дополнить морфословарь	Добавление словоформ в словарь
Открыть стоп-словарь	Открытие файла стоп-словаря и подгрузка его в память в соответствующую структуру данных
Выход	Закрытие программы
Редактировать стоп-словарь	Редактирование динамической структуры словаря с возможностью последующего сохранения в файл.
Сохранение результатов анализа	Сохранение результирующего списка в файл
Анализ	Запуск анализа текста
Поиск словоформ	Поиск группы родственных слов для заданного пользователем слова

В соответствии с выделенными вариантами использования и действующими лицам составим диаграмму вариантов использования (Рисунок 2).

Рисунок 2 - Диаграмма вариантов использования

2.2.8 Описание варианта использования «Редактировать стоп-словарь»

Для каждого варианта использования разрабатывается сценарий, на основании которого определяется поведение системы. Ниже приведен сценарий (основной поток событий) для варианта использования «Редактировать стоп-словарь» (таблица 3).

Таблица 3 - Сценарий варианта использования «Редактировать стоп словарь»

Действия пользователя	Действия системы
1. Выбор в меню системы «Редактирование стоп словаря».	2. Система обрабатывает запрос, подгружает стоп-словарь и открывает форму редактирования.
3. Выбор положения редактируемого слова в списке с помощью мыши	4. Система запоминает индекс слова.
5. Нажатие кнопки «Редактировать». (Альтернативный поток A1)	6. Систем подгружает в поле для редактирования выбранное слово.
7. Ввод необходимых исправлений и нажатие кнопки «ОК».	8. Система обрабатывает запрос, сохраняет изменения, и отображает новое слово в списке.
9. Нажатие кнопки «Сохранить» (Альтернативный поток A2)	10. Система сохраняет данные в файл, закрывает форму редактирования. Вариант использования завершается.

Альтернативный поток А1. Нажата кнопка «Удалить»

Удаление выбранного слова и переход к пункту 3.

Альтернативный поток А2. Нажата кнопка «Выход»

Отмена всех внесенных изменений, закрытие диалогового окна. Вариант использования завершается.

Предусловия. Пользователь должен открыть в меню системы вкладку «Файл»и в появившемся контекстном меню выбрать «Редактировать стоп-словарь».

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

2.2.9 Верификация прецедентов на полноту и непротиворечивость

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

В таблице 4 представлено соответствие между требованиями пользователя и выделенными вариантами использования.

Таблица 4 - Соответствие требования пользователя и вариантов использования

Требования пользователя
	Открыть стоп-словарь	Редактировать стоп-словарь	Дополнить морфословарь	Выход	Анализ	Сохранение результатов анализа	Поиск словоформ
Стоп-словарь	+	+
Морфословарь			+
Анализ текста					+
Редактирование и дополнение стоп словаря	+	+
Дополнение морфословаря			+
Возможность поиска группы морфологически родственных слов для заданного слова.							+
Статистика					+	+
Форматы вывода - txt						+

2.3 Описание метода поиска ключевых слов

Метод поиска ключевых слов (слов «кандидатов») будем рассматривать как функцию F.

где - искомое множество ключевых слов,

- множество информационных элементов текстового фрагмента. Схематично данная функция представлена на рисунке 3.

Рисунок 3 - Функция поиска ключевых слов

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

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

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

Для разрешения коллизий используется линейный список. Структура элемента данного списка приводится на рисунке 4.

Рисунок 4 - Структура элемента списка таблицы лексем

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

Рисунок 5 - Структура вершины словаря

Поле флагов содержит в себе несколько признаков: признак окончания слова, признак основы, признак главного слова в группе родственных слов. Подробно структура поля приведена на рисунке 6.

Рисунок 6 - Структура поля флагов

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

Рисунок 7 - Поиск родственных слов

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

Алгоритм данного «склеивания» представлен на рисунке 8.

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



Рисунок 8 - Алгоритм «склеивания»

Итак, алгоритм выбора и подсчета ключевых слов входного потока представлен на рисунке 9.

Рисунок 9 - Алгоритм поиска ключевых слов

На выходе системы получаем множество слов - «кандидатов» вида

где - слово-«кандидат»,

- вес «кандидата».

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

2.4 Использованные механизмы языка Java

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

2.4.1 Управление памятью

Java - объектно-ориентированный язык программирования, разработанный компанией Sun Microsystems. Приложения Java обычно компилируются в специальный байт-код, поэтому они могут работать на любой виртуальной Java-машине (JVM) независимо от компьютерной архитектуры. Другой важной особенностью технологии Java является гибкая система безопасности благодаря тому, что исполнение программы контролируется виртуальной машиной. Основные возможности языка[7]:

- автоматическое управление памятью;

- расширенные возможности обработки исключительных ситуаций;

- богатый набор средств фильтрации ввода/вывода;

- набор стандартных коллекций, таких как массив, список, стек и т. п.;

- наличие простых средств создания сетевых приложений;

- наличие классов, позволяющих выполнять HTTP-запросы и обрабатывать ответы;

- встроенные в язык средства создания многопоточных приложений;

- унифицированный доступ к базам данных:

- поддержка шаблонов (начиная с версии 1.5);

- параллельное выполнение программ.

В языке Java невозможно явное удаление объекта из памяти -- вместо этого реализована так называемая «сборка мусора»[8], являющейся одной из форм автоматического управления памятью.

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

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

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

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

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

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

2.4.2 Класс JList библиотеки Swing

Класс JList имеет несколько конструкторов: public JList() - cоздает пустой список, public JList(Object[] listData) - cписок на основе массива объектов, public JList(Vector listData) - cписок из элементов вектора, public JList(ListModel dataModel) - самый абстрактный и гибкий вариант. Создается класс, реализующий интерфейс ListModel и обеспечивающий элементы для списка из любого источника.

Для отображения элементов JList использует стандартный для JFC(Java Foundation Classes) прием[10]. В списке отображаются строки, полученные путем вызовов метода toString для объектов, входящих в список. Класс JList является довольно сложной по структуре конструкцией и, как и многие другие классы Swing, построен на базе архитектуры MVC (Model-View-Controller).

Для построения модифицируемого списка используется интерфейс ListModel и классы AbstractListModel и DefaultListModel. Список типа JList работает с данными, составляющими собственно список, не напрямую, а через специальный объект "модель данных". Интерфейс ListModel определяет минимальный набор методов, который требуется классу JList от "модели данных". Эти методы позволяют узнать количество элементов в списке (метод getSize), выбрать элемент списка (метод getElementAt), а также зарегистрировать и отключить слушателей (методы addListDataListener и removeListDataListener ).

Класс DefaultListModel удовлетворяет интерфейсу ListModel, имеет методы для добавления элементов в список (методы add и addElement), модификации существующих элементов (setElementAt) и удаления из списка (ряд методов remove). Для реализации модифицируемого списка типа JList можно: построить объект класса DefaultListModel, построить объект класса JList с использованием конструктора public JList(ListModel dataModel), передав ему в качестве параметра построенный объект класса DefaultListModel. Выполнять модификации списка через объект класса DefaultListModel - визуальное представление списка при этом будет меняться автоматически.

2.5 Разработка архитектуры системы

2.5.1 Разбиение задачи на подзадачи

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

- разработка библиотеки классов морфологического словаря,

- разработка библиотеки классов стоп-словаря,

- разработка модуля графематического анализа и создания таблицы лексем,

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

Архитектуру системы можно представить в виде диаграммы пакетов, составляющих структуру проекта (рисунок 10).

Рисунок 10 - Диаграмма пакетов проекта

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

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

Пакет interfaces содержит классы, через которые осуществляется взаимодействие пользователя с системой.

2.5.2 Разработка библиотеки классов словарей

Структуру библиотеки классов морфословаря и стоп-словаря можно представить в виде следующей диаграммы классов (рисунок 11).

Рисунок 11 - Диаграмма классов пакета dictionaries

В рамках программной модели классы Btree и Leaf являются реализацией морфологического словаря. При этом класс Btree предназначен для построения структуры сильноветвящегося дерева, в котором непосредственно хранятся словоформы языка. В свою очередь, объекты класса Leaf являются вершинами указанного дерева. В классе Hash реализована хеш-функция[6] и методы создания хеш-таблиц с её помощью. Класс StopMain отвечает за загрузку стоп-словаря в оперативную память и реализует метод поиска стоп-слов.

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

Атрибуты класса представлены в таблице 5.

Таблица 5 - Атрибуты класса MorphMain

Название	Назначение	Тип	Начальное значение
MD	Указатель на корень дерева	Btree	null
listosnov	Вершина дерева, помеченная признаком основы	Leaf	null
postosnov	Аффикс текущей словоформы	String	“”
flagosnov	Устанавливается во время поиска словоформ, свидетельствует о нахождении вложенных основ	Boolean	False
flagpost	Свидетельствует, найден ли аффикс текущей словоформы	Boolean	False
Info	Хранит статистическую информацию о результатах последнего анализа	String	“”

Класс имеет ряд других вспомогательных атрибутов служебного назначения (для связи с формами и т. п.). Поиск родственных слов реализует метод getRelativesWords(). Его реализация приведена в разделе 2.6.3.

Спецификация класса MorphMain на языке OCL приведена на рисунке 12.

context MorphMain inv: self.MD != null

Рисунок 12 - Инвариант класса MorphMain

2.5.3 Разработка библиотеки классов разбора и частотного анализа

Структуру библиотеки классов разбора и анализа можно представить в виде следующей диаграммы классов (рисунок 13).

морфологический анализатор обработка текст

Рисунок 13 - Диаграмма классов пакета analysis

Класс SortTree используется для построения бинарного дерева сортировки, необходимого для корректного получения результатов анализа. Класс StartOptions содержит настройки работы системы, такие как пути к файлам словарей, а также порог частоты по умолчанию. Класс Parser реализует графематический разбор текста, и формирует таблицу лексем. Класс Union ялвяется управляющим классом и реализует алгоритм склеивания словоформ (см. приложение 1, стр. 57, метод Execute()), рассмотренный в подразделе 2.3. Объекты класса ForListElem является элементами списка таблицы лексем, использующегося для разрешения коллизий при хешировании.

Атрибуты класса ForListElem приведены в таблице 6.

Таблица 6 - Атрибуты класса ForListElem

Название	Назначение	Тип	Начальноезначение
word	Хранит лексему(слово из текста)	String	“”
count	Частота повторения лексемы в тексте	int	1
count_word	Количество словоформ, встречающихся в тексте	Int	1
in_dict	Отражает наличие текущей лексемы в морфологическом словаре	boolean	False
deleted	Отражает признак удаления словоформы. Используется при свертке словоформ	Boolean	False

Спецификация класса ForListElem на языке OCL приведена на рисунке 14.

context ForListElem inv:

self.word != null and

self.count_word >= 0 and

self.count >=0

Рисунок 14 - Инвариант класса ForListElem

2.5.4 Разработка библиотеки классов взаимодействия с пользователем

Структуру библиотеки интерфейсных классов можно представить в виде следующей диаграммы классов (рисунок 15).

Рисунок 15 - Диаграмма классов пакета interfaces

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

2.6 Реализация системы

2.6.1 Общие сведения

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

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

2.6.2 Основные объекты интерфейса пользователя

Список и краткое описание форм, которыми обладает проект, показаны в таблице 7.

Таблица 7 - Основные формы проекта

Имя	Назначение
MainForm	Главное окно программы, предназначенное для проведения анализа текста
AppendForm	Диалоговое окно, используемое для дополнения морфологического словаря
EditStopDict	Диалоговое окно, предназначенное для редактирования стоп-словаря
FormsFind	Диалоговое окно, предназначенное для поиска группы родственных слов по запросу пользователя
Config	Диалоговое окно для изменения настроек комплекса

Внешний вид формы MorphMain представлен на рисунке 16.



Рисунок 16 - Форма MorphMain

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

Таблица 8 - Структура формы MorphMain

№	Наименование компонента	Тип компонента	Назначение
1	jMenu1	JMenu	Главное меню программы
2	jTextArea1	JTextArea	Отображает анализируемый текст
3	jTable1	JTable	Таблица, отображает промежуточные результаты анализа
4	jTextArea3	JTextArea	Текстовое поле, отображает слова из текста, отстутствующие в морфологическом словаре
5	jButton2	JButton	Кнопка, закрывает основное окно
6	jButton1	JButton	Кнопка, запускает процесс анализа текста
7	jButton4	JButton	Кнопка, предназначена для сохранения результатов анализа
8	jButton6	JButton	Кнопка, очищает поле представления текста, поле неизвестных слов, таблицу промежуточных результатов и поле результатов анализа
9	jProgressBar1	JProgressBar	Отображает прогресс выполнения процесса анализа
10	jTextArea2	JTextArea	Текстовое поле, отображает результаты анализа (список ключевых слов)
11	jSlider1	JSlider	Устанавливает для анализа порог частоты

Внешний вид формы AppendFormпредставлен на рисунке 17.

Рисунок 17 - Форма AppendForm

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

Таблица 9 - Структура формы AppendForm

№	Наименование компонента	Тип компонента	Назначение
1	jTextField1	JTextField	Текстовое поле для ввода новой группы морфологически родственных слов
2	jButton2	JButton	Добавляет группу слов в файл словаря
3	jButton1	JButton	Закрывает форму

Внешний вид формы FormsFind представлен на рисунке 18.

Рисунок 18 - Форма FormsFind

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

Таблица 10 - Структура формы FormsFind

№	Наименование компонента	Тип компонента	Назначение
1	jTextField1	JTextField	Поле для ввода слова, для которого ищутся словоформы
2	jButton2	JButton	Запускает процесс поиска словоформ
3	jButton1	JButton	Закрывает форму

Внешний вид формы EditStopDict представлен на рисунке 19.

Рисунок 19 - Форма EditStopDict

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

Таблица 11 - Структура формы EditStopDict

№	Наименование компонента	Тип компонента	Назначение
1	jList1	JList	Отображает содержимое стоп-словаря
2	jTextField1	JTextField	Текстовое поле, предназначенное для ввода и редактирования стоп-слов
3	jButton3	JButton	Удаляет выбранное слово из стоп-словаря
4	jButton2	JButton	Предназначена для добавления нового слова в стоп-словарь
№	Наименование компонента	Тип компонента	Назначение
5	jButton4	JButton	Предназначена для редактирования выбранного стоп-слова
6	jButton5	JButton	Сохраняет в файл внесенные изменения
7	jButton1	JButton	Отменяет внесенные изменения и закрывает форму

Внешний вид формы Config представлен на рисунке 20.

Рисунок 20 - Форма Config.

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

Таблица 12 - Структура формы Config

№	Наименование компонента	Тип компонента	Назначение
1	jTextField1	JTextField	Содержит путь к файлу морфологического словаря
2	jTextField2	JTextField	Содержит путь к файлу стоп- словаря
3	jSpinner1	JSpinner	Поле для ввода порога частоты
4	jButton2	JButton	Сохраняет введенные изменения
5	jButton1	JButton	Закрывает форму

2.6.3 Программная реализация классов

Ниже приводится пример программной реализации части основных классов: MorphMain(рис. 21, 22, 23, 24), ForListElem(рис. 21), Btree(рис. 25, 26, 27, 28, 29). Полностью код программы приведен в приложении 1 (стр. 51).

public class ForListElem {

public ForListElem()

{

word = "";

count = 1;

count_forms = 1;

in_dict = true;

flagdeleted = false;

}

public String word;

public int count;

public int count_forms;

public boolean in_dict;

public boolean flagdeleted;

}

Рисунок 20 - Программная реализация класса ForListElem

public MorphMain(startwindow j1, Start_options s) {

MD = new btree();

tf = j1;

tops_count = 0;

words_count = 0;

flagosnov = false;

flagpostosnov = false;

info = "";

so = s;

}

public void setCurrentBase(String h)

{

if (!flagpostosnov)

{

postosnov = h;

flagpostosnov = true;

}

}

public void setListOsnov(leaf y)

{

if (!flagosnov)

{

listosnov = y;

} }

Рисунок 21 - Программная реализация класса MorphMain.

flagosnov = false;

flagpostosnov = false;

postosnov = "";

listosnov = null;

}

private String innerjoin(String a,String b)

{

int k;

String l;

l = "";

k = a.length();

if (b.length() < k ) k = b.length();

for (int i = 0;i<k;i++)

{

if (a.charAt(i)==b.charAt(i)) l+=a.charAt(i);

else break;

}

return l;

}

public String selectOsn(String words[])

{

String h;

int j;

h = words[0];

for (int i = 1;i<words.length;i++)

{

h = innerjoin(h,words[i]);

}

return h;

}

}

public boolean getRelativeWords(DefaultListModel d,String word,boolean show)

{

try {

String base = null;

if (MD.simpleSearch(word, false, this) == null)

{

if (show) f.jTextArea3.append(word+"\n");

Reset();

return false;

}

MD.backSearch(word, this);

if (this.listosnov != null){ leaf l; base = word.substring(0,word.length()-this.postosnov.length()+1);

Рисунок 22 -. Программная реализация класса MorphMain

if (listosnov.getNextLevel() != null)

this.listosnov.getNextLevel().CrawlforMM(d,base,listosnov.getUin());

if (listosnov.getFlagIn_MainWord())

d.insertElementAt(base, 0);

}

else {

if (show) f.jTextArea3.append(word+"\n"); f.jTextArea3.append(word+"\n");

Reset();

return false;

}

Reset();

}

catch (Exception ex) {

return false;

}

return true;

}

public void LoadInOM()

{

String h1[] = null;

String h = null;

try {

BufferedReader in = new BufferedReader(new FileReader(so.getPForms()));

String j = "ёйцукенгшщзхъэждлорпавыфячсмитьбю";

j += j.toUpperCase();

int k,ik;

Graphics d;

d = tf.getGraphics();

d.setFont(new Font("Courier New", Font.BOLD, 12));

d.setColor(Color.BLACK);

d.drawString("Инициализация интерфейса и загрузка словаря...", 8, tf.getHeight()-45);

k=0;

while (in.readLine() != null) k++;

tf.jProgressBar1.setMaximum(k);

k = 1;

ik = 0;

in.close();

in = new BufferedReader(new FileReader(so.getPForms()));

while ((h = in.readLine()) != null )

{

k++;

continue;

Рисунок 23 - Программная реализация класса MorphMain

for (int i = 0;i<h1.length;i++)

h1 = h.split(" ");

h1[i]=h1[i].toLowerCase().trim().replace('ё', 'е');

MD.addNewWord(h1[0],false, true,k);

for (int i = 1;i<h1.length;i++ )

{

if (!h1[i].equals("-"))

MD.addNewWord(h1[i],false, false,k);

}

String y;

y = selectOsn(h1);

if (!y.isEmpty())

MD.addNewWord(y,true, false,k);

tf.jProgressBar1.setValue(k);

ik+=h1.length;

k++;

}

DefaultListModel lis;

lis = new DefaultListModel();

MD.Crawl1(lis, "",this);

f = new MainWindow();

f.jSlider1.setValue(so.getLimit());

f.LoadDictionary(this);

tf.setVisible(false);

f.setVisible(true);

} catch (Exception ex) {

javax.swing.JOptionPane.showMessageDialog(null, "Файл словаря не найден. Проверьте настройки.");

System.exit(0);

ex.printStackTrace();

}

}

Рисунок 24 - Программная реализация класса MorphMain.

//массив символов алфавита и их параметров

private leaf alpha[];

public leaf[] getAlphabit()

{

return alpha;

}

public btree() {

// level = 0;

fillAlphabit();

}

//заполняет массив буквами русского алфавита...

private void fillAlphabit()

{

Рисунок 25 - Программная реализация класс Btree

alpha = new leaf[32];

int i;

i = 0;

for (char l = 'а';l<='я';l++)

{

alpha[i] = new leaf();

alpha[i++].setLetter(l);

}

}

public static int getIndexbyLetter(char x)

{

int s;

s = -1;

if (x == 'ё') return getIndexbyLetter('е');

else

for (char h = 'а';h<=x;h++)

s++;

return s;

}

public static char getLetterByIndex(int i)

{

char s;

s = 'а'-1;

if (i < 0 || i > 32) return s = ' ';

else

for (int j = 0;j<=i;j++)

s++;

return s;

}

//возвращет объект класса, который содержит последнюю букву искомого слова

//соответственно, если такое слово есть в словаре

//второй параметр - указание остановиться поиску, на очередном этапе

//если встретится признак основы

public leaf simpleSearch(String sw,boolean stop_on_base,MorphMain mm) throws Exception

{

char curr_add_let; //добавляемая в данный момент буква

leaf watching_elem;//объект класса, содержащий эту букву

int index;//номер объекта в алфавите

String h;//остаток строки, без первой буквы

btree down;//ниже следующий уровень дерева

curr_add_let = sw.charAt(0);

if (curr_add_let== 'ё') curr_add_let = 'е';

index = getIndexbyLetter(curr_add_let);

if (index < 0 || index > 32) throw new Exception("Такие буквы недопустимы -"+sw);

else {

watching_elem = alpha[index];

Рисунок 26 - Программная реализация класс Btree

if (!watching_elem.getFlagIn_Use()) return null;

if (stop_on_base)

if (watching_elem.getFlagBase())

{

mm.setCurrentBase(sw);

return watching_elem;

}

if (sw.length() == 1 )

{

if (watching_elem.getFlagEndWord()) return watching_elem;

else return null;

}

//иначе продолжим спуск

else

{

//отбросим первую букву

h = sw.substring(1);

down = watching_elem.getNextLevel();

if (down == null) return null;

else return watching_elem.getNextLevel().simpleSearch(h,stop_on_base,mm);

}

}

}

public void backSearch(String sw,MorphMain d) throws Exception

{

char curr_add_let; //добавляемая в данный момент буква

leaf watching_elem;//объект класса, содержащий эту букву

int index;//номер объекта в алфавите

String h;//остаток строки, без первой буквы

btree down;//ниже следующий уровень дерева

if (sw.isEmpty()) return;

curr_add_let = sw.charAt(0);

if (curr_add_let== 'ё') curr_add_let = 'е';

index = getIndexbyLetter(curr_add_let);

if (index < 0 || index > 32) throw new Exception("Такие буквы недопустимы -"+sw);

else {

watching_elem = alpha[index];

if (watching_elem.getFlagIn_Use())

{

if (sw.length() != 1 )

{

h = sw.substring(1);

down = watching_elem.getNextLevel();

if (down != null)

Рисунок 27 - Программная реализация класс Btree

watching_elem.getNextLevel().backSearch(h,d);

if (watching_elem.getFlagBase())

{

d.setListOsnov(watching_elem);

d.setCurrentBase(sw);

System.out.println("Обновил тут");

} } } } }

//добавляет новое слово, возможно помечает его как основу

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

public void addNewWord(String sw, boolean poss_osn, boolean poss_main,int ui ) throws Exception

{

char curr_add_let; //добавляемая в данный момент буква

leaf watching_elem;//объект класса, содержащий эту букву

int index;//номер объекта в алфавите

String h;//остаток строки, без первой буквы

btree down;//ниже следующий уровень дерева

curr_add_let = sw.charAt(0);

if (curr_add_let== 'ё') curr_add_let = 'е';

index = getIndexbyLetter(curr_add_let);

if (index < 0 || index > 32) throw new Exception("Такие буквы недопустимы");

else {

watching_elem = alpha[index];

watching_elem.setFlagIn_Use(true);

//если текущая буква последняя в добавляемом слове

if (sw.length() == 1 )

{

if (poss_osn) watching_elem.setFlagOsnova(true);

else watching_elem.setFlagEndWord(true);

if (poss_main) watching_elem.setFlagMainWord(true);

watching_elem.setUin(ui);

}

else

{

h = sw.substring(1);

down = watching_elem.getNextLevel();

//если текущая вершина была листом, создадим новый уровень

if (down == null)

{

down = new btree();

//down.level = (byte) (level +1);

watching_elem.setNextLevel(down);

}

watching_elem.getNextLevel().addNewWord(h,poss_osn,poss_main,ui);

} } }

public void Crawl(DefaultListModel lis,String word)

{

//tree s;//просматриваемый на данном этапе алфавит

leaf d;//просматриваемый елемент

Рисунок 28 - Программная реализация класс Btree

for (int i = 0;i<32;i++)

{

d = this.alpha[i];

if (d.getFlagIn_Use())

{

if (d.getFlagEndWord())

{

if (d.getFlagIn_MainWord())

lis.insertElementAt(word+getLetterByIndex(i), 0);

else

lis.addElement(word+getLetterByIndex(i));

}

if (d.getNextLevel() != null)

d.getNextLevel().Crawl(lis,word+getLetterByIndex(i));

}

}

}

public void CrawlforMM(DefaultListModel lis,String word,int ui)

{

leaf d;//просматриваемый елемент

for (int i = 0;i<32;i++)

{

d = this.alpha[i];

if (d.getFlagIn_Use())

{

if (d.getFlagEndWord())

{

if (d.getUin() == ui){

if (d.getFlagIn_MainWord())

lis.insertElementAt(word+getLetterByIndex(i), 0);

else

lis.addElement(word+getLetterByIndex(i));

}

}

if (d.getNextLevel() != null)

d.getNextLevel().CrawlforMM(lis,word+getLetterByIndex(i),ui);

}

}

}

2.7 Тестовые примеры анализа

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

Рисунок 30 - Форма после завершения анализа. Тест №1

В таблице 13 приведены результаты работы программы(1) и частотного анализа, проведенного вручную(2).

Таблица 13 - Результаты анализа для теста №1

Слово	Частота 1	Частота 2
«Предложение»	1	1
«мысль»	1	1
«выражать»	1	1
«вопрос»	1	1
«побуждение»	1	1
«воля»	1	1
«эмоция»	1	1
«содержать»	1	1

Алгоритм работает корректно.

В качестве входных данных для второго теста выбран текстовый фрагмент, в котором содержатся морфологически родственные слова: «На компьютерном столе было предусмотрено место для принтера. Под столом размещался системный блок». Очевидно, слова «столе» и «столом» являются родственными и должны быть приведены к нормальной форме «стол» с показателем частоты равным 2. На рисунке 31 приведен внешний вид форм после завершения анализа.

Рисунок 31 - Форма после завершения анализа. Тест №2

В таблице 14 приведены результаты работы программы(1) и частотного анализа, проведенного вручную(2).

Таблица 14 - Результаты анализа для теста №2

Слово	Частота 1	Частота 2
«стол»	2	2
«предусмотрено»	1	1
«системный»	1	1
«блок»	1	1
«размещался»	1	1
«принтер»	1	1
«компьютерный»	1	1
«место»	1	1

Алгоритм работает корректно.

В качестве входных данных для третьего теста выбран текст, приведенный в приложении 3 (см. стр. ). Порог частоты установлен равным 5. На рисунке 32 приведен внешний вид форм после завершения анализа.

Рисунок 32 - Форма после завершения анализа. Тест №3

В таблице 15 приведены результаты работы программы(1) и частотного анализа, проведенного вручную(2).

Таблица 15 - Результаты анализа для теста №3

Слово	Частота 1	Частота 2
«особь»	11	11
«популяция»	11	11
«га»	10	10
«решение»	9	9
«оператор»	9	9
«хромосома»	7	7
«приспособленность»	7	7
«мутация»	7	7
«алгоритм»	6	6
«отбор»	6	6
«рулетка»	5	5
«скрещивание»	5	5
«селекция»	5	5
«ген»	5	5

Исходя из результатов тестирования следует, что алгоритм работает корректно.

3. ВЫВОДЫ

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

Список использованной литературы

1. Андреев, А.М. Лингвистический процессор для информационно-поисковой системы [Текст] / А. М. Андреев, Д. В. Березкин, А. В. Брик. - Компьютерная хроника, 2008. - с. 79-100.

2. Кормалев, Д. А. Приложения технологии извлечения информации из текста: теория и практика [Текст] / Д. А. Кормалев. - Вестник РУДН, Серия Прикладная и компьютерная математика. Т. 2, № 1. 2006. - с. 120-127

3. Найханова, Л.В. Методы и алгоритмы трансляции естественно-языковых запросов к базе данных в SQL-запросы [Текст] : Монография / Л. В. Найханова, И. С. Евдокимова. - Улан-Удэ: Изд-во ВСГТУ, 2006. - 148 с.

4. Шемякин, Ю. И. Начала компьютерной лингвистики [Текст] : Учебное пособие / Ю. И. Шемякин. - М.: Издательство МГОУ, А/О «Росвузнаука», 2008. - 81 с.

5. Апресян, Ю. Д. Лингвистический процессор для сложных информационных систем [Текст] / Ю. Д. Апресян, И. М. Богуславский, Л. Л. Иомдин. - М.: Наука, 2010, - 256 с.

6. Кубенский, А.А. Создание и обработка структур данных в примерах на Java. Серия "Мастер" [Текст] / А. А. Кубенский. - СПб.: БХВ-Петербург, 2006. - 336 с.

7. Эккель, Б. Философия Java [Текст] / Б. Эккель. - СПб.: Питер, 2007. - 976 с. - ISBN 5-88782-105-1

8. Герберт, Ш. Искусство программирования на Java [Текст] / Ш. Герберт, Д. Холмс. - М.: Диалектика, 2006.- 336 с. - ISBN 0-07-222971-3

9. http://www.javable.com/tutorials/fesunov/lesson18/ [Электронный ресурс]

10. http://java.sun.com/javase/technologies/desktop/ [Электронный ресурс]

Приложение 1

ИСХОДНЫЙ КОД

package analysis;

public class ForListElem {

public ForListElem()

{