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

 

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

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

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

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

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

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

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

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

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

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

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

А. В. Абрамов

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

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

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

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

А.П. Жмакин

Курск 2010г.

SUMMARY

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.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.used programming language - Java.is declared on 102 pages of the typewritten text, consists of conducting, system engineering and conclusions.of work: «Automatic text processing», «morphology», «the morphological dictionary», «the frequency analysis», «the thematic analysis».created qualifying work is claimed and actual.

1. ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-основа,

-муффикс,

-окончание.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.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 Разработка архитектуры системы

.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Указатель на корень дереваBtreenulllistosnovВершина дерева, помеченная признаком основыLeafnullpostosnovАффикс текущей словоформыStringflagosnovУстанавливается во время поиска словоформ, свидетельствует о нахождении вложенных основBooleanFalseflagpostСвидетельствует, найден ли аффикс текущей словоформыBooleanFalseInfoХранит статистическую информацию о результатах последнего анализа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Хранит лексему(слово из текста)StringcountЧастота повторения лексемы в текстеint1count_wordКоличество словоформ, встречающихся в текстеInt1in_dictОтражает наличие текущей лексемы в морфологическом словареbooleanFalsedeletedОтражает признак удаления словоформы. Используется при свертке словоформBooleanFalse

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

context ForListElem inv:.word != null and.count_word >= 0 and.count >=0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

№Наименование компонентаТип компонентаНазначение1jMenu1JMenuГлавное меню программы2jTextArea1JTextAreaОтображает анализируемый текст3jTable1JTableТаблица, отображает промежуточные результаты анализа4jTextArea3JTextAreaТекстовое поле, отображает слова из текста, отстутствующие в морфологическом словаре5jButton2JButtonКнопка, закрывает основное окно6jButton1JButtonКнопка, запускает процесс анализа текста7jButton4JButtonКнопка, предназначена для сохранения результатов анализа8jButton6JButtonКнопка, очищает поле представления текста, поле неизвестных слов, таблицу промежуточных результатов и поле результатов анализа9jProgressBar1JProgressBarОтображает прогресс выполнения процесса анализа10jTextArea2JTextAreaТекстовое поле, отображает результаты анализа (список ключевых слов)11jSlider1JSliderУстанавливает для анализа порог частоты

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

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

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

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

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

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

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

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

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

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

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

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

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

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

№Наименование компонентаТип компонентаНазначение1jList1JListОтображает содержимое стоп-словаря2jTextField1JTextFieldТекстовое поле, предназначенное для ввода и редактирования стоп-слов3jButton3JButtonУдаляет выбранное слово из стоп-словаря4jButton2JButtonПредназначена для добавления нового слова в стоп-словарь№Наименование компонентаТип компонентаНазначение5jButton4JButtonПредназначена для редактирования выбранного стоп-слова6jButton5JButtonСохраняет в файл внесенные изменения7jButton1JButtonОтменяет внесенные изменения и закрывает форму

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

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

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

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

№Наименование компонентаТип компонентаНазначение1jTextField1JTextFieldСодержит путь к файлу морфологического словаря2jTextField2JTextFieldСодержит путь к файлу стоп- словаря3jSpinner1JSpinnerПоле для ввода порога частоты4jButton2JButtonСохраняет введенные изменения5jButton1JButtonЗакрывает форму

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

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

public class ForListElem {

public ForListElem()

{= "";= 1;_forms = 1;_dict = true;= false;

}String word;int count;int count_forms;boolean in_dict;boolean flagdeleted;

}

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

MorphMain(startwindow j1, Start_options s) {= new btree();= j1;_count = 0;_count = 0;= false;= false;= "";= s;

}void setCurrentBase(String h)

{(!flagpostosnov)

{= h;= true;

}

}void setListOsnov(leaf y)

{(!flagosnov)

{= y;

} }

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

= false;= false;= "";= null;

}String innerjoin(String a,String b)

{k;l;= "";= a.length();(b.length() < k ) k = b.length();(int i = 0;i<k;i++)

{(a.charAt(i)==b.charAt(i)) l+=a.charAt(i);break;

}l;

}String selectOsn(String words[])

{h;j;= words[0];(int i = 1;i<words.length;i++)

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

}h;

}

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

{{base = null;(MD.simpleSearch(word, false, this) == null)

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

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

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

(listosnov.getNextLevel() != null).listosnov.getNextLevel().CrawlforMM(d,base,listosnov.getUin());(listosnov.getFlagIn_MainWord()).insertElementAt(base, 0);

}{(show) f.jTextArea3.append(word+"\n"); f.jTextArea3.append(word+"\n");();false;

}();

}(Exception ex) {false;

}true;

}void LoadInOM()

{h1[] = null;h = null;{in = new BufferedReader(new FileReader(so.getPForms()));j = "ёйцукенгшщзхъэждлорпавыфячсмитьбю";+= j.toUpperCase();k,ik;d;= tf.getGraphics();.setFont(new Font("Courier New", Font.BOLD, 12));.setColor(Color.BLACK);.drawString("Инициализация интерфейса и загрузка словаря...", 8, tf.getHeight()-45);=0;(in.readLine() != null) k++;.jProgressBar1.setMaximum(k);= 1;= 0;.close();= new BufferedReader(new FileReader(so.getPForms()));((h = in.readLine()) != null )

{++;;

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

for (int i = 0;i<h1.length;i++)= h.split(" ");[i]=h1[i].toLowerCase().trim().replace('ё', 'е');.addNewWord(h1[0],false, true,k);(int i = 1;i<h1.length;i++ )

{(!h1[i].equals("-")).addNewWord(h1[i],false, false,k);

}y;= selectOsn(h1);(!y.isEmpty()).addNewWord(y,true, false,k);.jProgressBar1.setValue(k);+=h1.length;++;

}lis;= new DefaultListModel();.Crawl1(lis, "",this);= new MainWindow();.jSlider1.setValue(so.getLimit());.LoadDictionary(this);.setVisible(false);.setVisible(true);

} catch (Exception ex) {.swing.JOptionPane.showMessageDialog(null, "Файл словаря не найден. Проверьте настройки.");.exit(0);.printStackTrace();

}

}

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

//массив символов алфавита и их параметровleaf alpha[];leaf[] getAlphabit()

{alpha;

}btree() {

// level = 0;();

}

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

{

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

= new leaf[32];i;= 0;(char l = 'а';l<='я';l++)

{[i] = new leaf();[i++].setLetter(l);

}

}static int getIndexbyLetter(char x)

{s;= -1;(x == 'ё') return getIndexbyLetter('е');(char h = 'а';h<=x;h++)++;s;

}static char getLetterByIndex(int i)

{s;= 'а'-1;(i < 0 || i > 32) return s = ' ';(int j = 0;j<=i;j++)++;s;

}

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

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

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

//если встретится признак основыleaf simpleSearch(String sw,boolean stop_on_base,MorphMain mm) throws Exception

{curr_add_let; //добавляемая в данный момент букваwatching_elem;//объект класса, содержащий эту буквуindex;//номер объекта в алфавитеh;//остаток строки, без первой буквыdown;//ниже следующий уровень дерева_add_let = sw.charAt(0);(curr_add_let== 'ё') curr_add_let = 'е';= getIndexbyLetter(curr_add_let);(index < 0 || index > 32) throw new Exception("Такие буквы недопустимы -"+sw);{_elem = alpha[index];

Рисунок 26 - Программная реализация класс Btree(!watching_elem.getFlagIn_Use()) return null;(stop_on_base)(watching_elem.getFlagBase())

{.setCurrentBase(sw);watching_elem;

}(sw.length() == 1 )

{(watching_elem.getFlagEndWord()) return watching_elem;return null;

}

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

{

//отбросим первую букву= sw.substring(1);= watching_elem.getNextLevel();(down == null) return null;return watching_elem.getNextLevel().simpleSearch(h,stop_on_base,mm);

}

}

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

{curr_add_let; //добавляемая в данный момент букваwatching_elem;//объект класса, содержащий эту буквуindex;//номер объекта в алфавитеh;//остаток строки, без первой буквыdown;//ниже следующий уровень дерева(sw.isEmpty()) return;_add_let = sw.charAt(0);(curr_add_let== 'ё') curr_add_let = 'е';= getIndexbyLetter(curr_add_let);(index < 0 || index > 32) throw new Exception("Такие буквы недопустимы -"+sw);{_elem = alpha[index];(watching_elem.getFlagIn_Use())

{(sw.length() != 1 )

{= sw.substring(1);= watching_elem.getNextLevel();(down != null)

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

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

{.setListOsnov(watching_elem);.setCurrentBase(sw);.out.println("Обновил тут");

} } } } }

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

//или как главное слово в группе морфологически родственных словvoid addNewWord(String sw, boolean poss_osn, boolean poss_main,int ui ) throws Exception

{curr_add_let; //добавляемая в данный момент букваwatching_elem;//объект класса, содержащий эту буквуindex;//номер объекта в алфавитеh;//остаток строки, без первой буквыdown;//ниже следующий уровень дерева_add_let = sw.charAt(0);(curr_add_let== 'ё') curr_add_let = 'е';= getIndexbyLetter(curr_add_let);(index < 0 || index > 32) throw new Exception("Такие буквы недопустимы");{_elem = alpha[index];_elem.setFlagIn_Use(true);

//если текущая буква последняя в добавляемом слове(sw.length() == 1 )

{(poss_osn) watching_elem.setFlagOsnova(true);watching_elem.setFlagEndWord(true);(poss_main) watching_elem.setFlagMainWord(true);_elem.setUin(ui);

}

{= sw.substring(1);= watching_elem.getNextLevel();

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

{= new btree();

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

}_elem.getNextLevel().addNewWord(h,poss_osn,poss_main,ui);

} } }void Crawl(DefaultListModel lis,String word)

{

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

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

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

{= this.alpha[i];(d.getFlagIn_Use())

{(d.getFlagEndWord())

{(d.getFlagIn_MainWord()).insertElementAt(word+getLetterByIndex(i), 0);.addElement(word+getLetterByIndex(i));

}(d.getNextLevel() != null).getNextLevel().Crawl(lis,word+getLetterByIndex(i));

}

}

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

{d;//просматриваемый елемент(int i = 0;i<32;i++)

{= this.alpha[i];(d.getFlagIn_Use())

{(d.getFlagEndWord())

{(d.getUin() == ui){(d.getFlagIn_MainWord()).insertElementAt(word+getLetterByIndex(i), 0);.addElement(word+getLetterByIndex(i));

}

}(d.getNextLevel() != null).getNextLevel().CrawlforMM(lis,word+getLetterByIndex(i),ui);

}

}

}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СловоЧастота 1Частота 2«особь»1111«популяция»1111«га»1010«решение»99«оператор»99«хромосома»77«приспособленность»77«мутация»77«алгоритм»66«отбор»66«рулетка»55«скрещивание»55«селекция»55«ген»55

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

3. ВЫВОДЫ

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

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

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

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

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

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

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

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

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

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

9.#"justify">10.#"justify">Приложение 1

ИСХОДНЫЙ КОД

package analysis;

public class ForListElem {ForListElem()

{= "";= 1;_forms = 1;_dict = true;= false;

}String word;int count;int count_forms;boolean in_dict;boolean flagdeleted;

}

class Load_Text extends Thread {

File f2;interfaces.frameLoad x;MainWindow w;Load_Text(File FileName,interfaces.frameLoad f,MainWindow _w)

{=f;= FileName;= _w;

}

void run(){t,y = "";u;= "";= 0;.setVisible(true);{out = new BufferedReader(new FileReader(f2));((y=out.readLine()) != null )

{t += y+"\n";++;.jLabel3.setText(u+"");

}.close();.jTextArea1.setText(t);.jTextArea1.setCaretPosition(1);.setEnabled(true);.dispose();

}(Exception ex) {System.out.println("Error"+ex.getMessage());}

}

}

analysis;

dictionaries.Hash;javax.swing.DefaultListModel;

/**

*

* @author Администратор

*/class Parser {

int hash(String str) {sum = 0;(int i = 0; i<str.length(); i++)

{sum += code(str.charAt(i));}(100*sum + 454) % 500;}

int code(char c) {"абвгдеёжзийклмнопрстуфхцчшщъыьэюя".indexOf(Character.toLowerCase(c))+1;}

int Parse(String x,DefaultListModel T[], Hash qw)

{flag_currnet_dividers = false;cur_lexem;count;=0;dd;d;f;deviders = "\n?!-{}[] ,./+-:;=-)(*№%«»$#";_lexem = "";i,adr,collision;= 0;= 0;= x.trim();(x.length() != 0 || x == null)(i < x.length())

{

(flag_currnet_dividers)

{(deviders.indexOf(x.charAt(i)) == -1)

{= hash(cur_lexem);.out.println(cur_lexem+" "+adr);(!qw.hasWord(cur_lexem.toLowerCase()))(T[adr] == null)

{[adr] = new DefaultListModel();= new ForListElem();.word = cur_lexem;[adr].addElement(dd);

}else{

d = T[adr];= false;

for (int p = 0;p<d.getSize();p++)

{= (ForListElem) d.getElementAt(p);

if (dd.word.equals(cur_lexem))

{.count++;= true;;

}

}

(!f)

{= new ForListElem();.word = cur_lexem;.addElement(dd);

}

}_lexem = "";++;_currnet_dividers = false;-;

}

}{

(deviders.indexOf(x.charAt(i)) != -1)_currnet_dividers = true;

_lexem+=x.charAt(i);

}++;

}

// System.out.println(cur_lexem);= hash(cur_lexem);(!qw.hasWord(cur_lexem.toLowerCase()))(T[adr] == null)

{[adr] = new DefaultListModel();= new ForListElem();.word = cur_lexem;[adr].addElement(dd);

}else{

d = T[adr];= false;

for (int p = 0;p<d.getSize();p++)

{= (ForListElem) d.getElementAt(p);

if (dd.word.equals(cur_lexem))

{.count++;= true;;

}

}

(!f)

{= new ForListElem();.word = cur_lexem;.addElement(dd);

}

}count;

}

}

javax.swing.DefaultListModel;javax.swing.JTextArea;java.util.Vector;

class SortTree {

int count_word;DefaultListModel group_words;SortTree left;SortTree right;

SortTree(int x,ForListElem x1){= null;= null;_word = x;_words = new DefaultListModel();_words.addElement(x1);

}

void add(int count,ForListElem word)

{(count == count_word)

{_words.addElement(word);

}(count < count_word)

{(left == null) left = new SortTree(count,word);

{.add(count, word);

}

}

{(right == null) right = new SortTree(count,word);

{.add(count, word);

}

}

}

void CrawlTable(Vector<Vector<Object>> x,DefaultListModel termins,int limit)

{ if (right != null) right.CrawlTable(x,termins,limit);i;el;(i = 0;i<group_words.size();i++)

{= (ForListElem) group_words.getElementAt(i);(!el.word.equalsIgnoreCase("")){

(count_word >= limit ) termins.addElement("«"+el.word+"» - "+el.count);<Object> curRow = new Vector<Object>();

.add(el.word);.add(count_word);.add(el.count_forms);.add(el.in_dict);

.add(curRow);

}

}(left != null) left.CrawlTable(x,termins,limit);

}

}

analysis;

class Start_options {

String PForms;String PStop;int Limit;

Start_options()

{= "c:\\text\\stems.txt";= "c:\\text\\Stop_Slovo.txt";= 33;

}String getPForms()

{PForms;

}

String getPStop()

{PStop;

}

int getLimit()

{Limit;

}

void setParam(String x )

{k[];= x.split("=");(k[0].equalsIgnoreCase("PathForms"))= k[1].trim();if (k[0].equalsIgnoreCase("PathStop"))= k[1].trim();if (k[0].equalsIgnoreCase("DefaultLimit"))

Limit = Integer.parseInt(k[1].trim());

}

}

analysis;dictionaries.StopMain;dictionaries.MorphMain;interfaces.MainWindow;java.io.File;java.util.Vector;javax.swing.DefaultListModel;javax.swing.ListSelectionModel;javax.swing.table.DefaultTableModel;

class Union extends Thread{

MainWindow frame;int limit;

Union (MainWindow x)

{= x;

}

void setLimit(int p)

{= p;

}

void run()

{();

}

void Execute()

{Hash[];= new DefaultListModel[500];x;MM;{= frame.getMorphDict();p;= new SortTree(0,new ForListElem());= new Parser();cls;= new StopMain();f;time;= System.currentTimeMillis();codeee,count;= new File(MM.so.getPStop());.LoadStop(f);

//System.out.println(cls.getHashTable());.jProgressBar1.setStringPainted(true);.jProgressBar1.setString("Выделение лексем...");=x.Parse(frame.getTextArea().getText(),Hash,cls.getHashTable());

e,q;= new DefaultListModel();fo;

.jProgressBar1.setString("Объеденение словоформ...");.jProgressBar1.setMinimum(0);.jProgressBar1.setMaximum(Hash.length);(int i =0;i<Hash.length;i++)

{.jProgressBar1.setValue(i);(Hash[i] != null)

{

=(DefaultListModel) Hash[i];

// e - список по в хеш-таблицеsize_of_list;_of_list = e.getSize();(int o = 0 ;o<size_of_list;o++)

{

.clear();= (ForListElem) e.getElementAt(o);(fo.flagdeleted) continue;flag;

// q - список родственных слов для текущего элемента fo

flag = MM.getRelativeWords(q, fo.word.toLowerCase().trim(),true);

.in_dict=flag;size_of_list_MR;_of_list_MR = q.size();(int o1=0;o1<size_of_list_MR;o1++)

{wordwatch;// текущее слово из списка словоформ

wordwatch = q.getElementAt(o1).toString().toLowerCase().trim();= x.hash(wordwatch);(!wordwatch.equalsIgnoreCase(fo.word))

if (Hash[codeee] != null) //если словоформа имеется в тексте

{ // Hash[codeee] - список по хеш-коду словоформы

for (int o2 = 0;o2<Hash[codeee].getSize();o2++)

{pop; //текущий элемент списка Hash[codeee]= (ForListElem)Hash[codeee].getElementAt(o2);(!pop.flagdeleted)(pop.word.equalsIgnoreCase(wordwatch))

{.count+=((ForListElem)Hash[codeee].getElementAt(o2)).count;.count_forms++;

((ForListElem)Hash[codeee].getElementAt(o2)).flagdeleted=true; //Hash[codeee].removeElementAt(o2);

}

}

}

}

//надо заменить на главное слово

String MainWord;

if (!q.isEmpty()){= q.firstElement().toString().trim();HashCode;= x.hash(MainWord);(Hash[HashCode] == null)

{nx;= new DefaultListModel();ne;= new ForListElem();.count = fo.count;.count_forms = fo.count_forms;.flagdeleted = fo.flagdeleted;.in_dict = fo.in_dict;.word = MainWord;.addElement(ne);

// e.removeElementAt(o);

((ForListElem)e.getElementAt(o)).flagdeleted=true;//!!!!!!!![HashCode] = nx;

}

{ne;= new ForListElem();.count = fo.count;.count_forms = fo.count_forms;.flagdeleted = fo.flagdeleted;.word = MainWord;.in_dict = fo.in_dict;[HashCode].addElement(ne);

// e.removeElementAt(o);

((ForListElem)e.getElementAt(o)).flagdeleted=true;//!!!!!!!!

}

}

}

}

.jProgressBar1.setString("Сортировка...");.jProgressBar1.setMinimum(0);.jProgressBar1.setMaximum(Hash.length);(int i =0;i<Hash.length;i++)(Hash[i] != null)

{t;

(int l= 0;l<Hash[i].getSize();l++)

{= (ForListElem) Hash[i].getElementAt(l);(!t.flagdeleted).add(t.count,t);

}

}ter;= new DefaultListModel();<Vector<Object>> tableData = new Vector<Vector<Object>>();.CrawlTable(tableData,ter,limit);

(int i = 0; i < ter.getSize();i++).jTextArea2.append(ter.getElementAt(i).toString()+", ");<String> columnName = new Vector<String>();.add("Слово");.add("Частота");

columnName.add("Количество словоформ");.add("Наличие в словаре");

DefaultTableModel model = new DefaultTableModel(tableData, columnName){

/**

* @author Subbotin B.P.

* @see #"justify">?Лист 1: постановка задачи,

?Лист 2: модель предметной области,

?Лист 3: функция поиска ключевых слов,

?Лист 4: структура таблицы лексем,

?Лист 5: структура элемента списка таблицы,

?Лист 6: структура вершины дерева морфологического словаря,

?Лист 7: структура поля признаков,

?Лист 8: структура морфологического словаря,

?Лист 9: схема алгоритма поиска,

?Лист 10: схема алгоритма склеивания,

?Лист 11: модель вариантов использования,

?Лист 12: интерфейс программы,

?Лист 13: тестовый пример анализа.

Графический материал выполнен в программе Компас-3D, и представлен ниже.

Приложение 3

Текст для тестового примера анализа

ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ

Генетические алгоритмы (ГА) - это стохастические, эвристические оптимизационные методы, впервые предложенные Холландом (1975). Они основываются на идее эволюции с помощью естественного отбора, выдвинутой Дарвином (1857).

. Введение в генетические алгоритмы

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

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

ГА состоит из следующих компонент:

Хромосома. Решение рассматриваемой проблемы. Состоит из генов.

Начальная популяция хромосом.

Набор операторов для генерации новых решений из предыдущей популяции.

Целевая функция для оценки приспособленности (fitness) решений.

Чтобы применять ГА к задаче, сначала выбирается метод кодирование решений в виде строки. Фиксированная длина (l-бит) двоичной кодировки означает, что любая из 2l возможных бинарных строк представляет возможное решение задачи.

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

. Операторы ГА

Стандартные операторы для всех типов генетических алгоритмов это: селекция, скрещивание и мутация.

.1 Селекция

Оператор селекции (reproduction, selection) осуществляет отбор хромосом в соответствии со значениями их функции приспособленности. Существуют как минимум два популярных типа оператора селекции: рулетка и турнир.

Метод рулетки (roulette-wheel selection) - отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Psel(i) вычисляемой по формуле:

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

Оператор селекции типа колеса рулетки

с пропорциональными функции приспособленности секторами

Турнирный отбор (tournament selection) реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2.

.2. Скрещивание

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

Рис. 2. Одноточечный оператор точка разрыва равна трем)

.3. Мутация

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

Оператор мутации (четвертый ген мутировал)

. Алгоритм работы ГА

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

Алгоритм работы простого ГА выглядит следующим образом:

Результаты обработки текста программой представлены на рисунке 33.

Рисунок 33. Результаты обработки текста

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

Больше работ по теме: