Содержание к диссертации
Введение
ГЛАВА 1. Автоматическая обработка текстов как основной этап реализации естественно языкового интерфейса 17
1.1. Основные понятия и определения 17
1.2. Уровни обработки текстов 19
1.3. Автоматическая обработка текстов и области ее применения 22
1.3.1. Понятие и задачи автоматической обработки текстов 22
1.3.2. Системы автоматической обработки текстов 26
ГЛАВА 2. Метод генерации и определения форм слов естественных языков 33
2.1. Задачи генерации и определения форм слов естественных языков и методы их решения 33
2.1.1. Принципы морфологической обработки текстов 33
2.1.2. Преимущества и недостатки методов
морфологической обработки текстов 40
2.2. Метод генерации и определения форм слов с помощью представления формообразования последовательностью преобразований 58
2.2.1. Модель формообразования естественного языка 58
2.2.2. Алгебраическое представление модели формообразования 64
2.2.3. Алгоритмы генерации и определения форм слов 67
2.2.4. Решение задач генерации и определения форм слов в пространстве состояний 70
2.2.5. Решение задач генерации и определения форм слов и синтаксического анализа с помощью теории унификации
2.3. Анализ особенностей формообразования естественных языков 82
2.3.1. Русский язык 83
2.3.2. Английский язык 83
2.3.3. Немецкий язык 84
2.3.4. Испанский язык 84
2.3.5. Финский язык 85
2.3.6. Условие применимости алгоритмов генерации и определения к языку 85
2.3.7. Утверждение о представлении формообразования в виде цепочек преобразований 86
2.4. Некоторые аспекты метода генерации и определения форм слов 88
2.4.1. Цепочка преобразований как алгоритмическая система 88
2.4.2. Автоматизированное построение цепочек преобразований по основе и словоформе 90
2.4.3. Применение алгоритмов генерации и определения
форм слов для словообразования 97
2.5. Система генерации и определения форм слов 98
2.5.1. Структура системы 98
2.5.2. Декларативная часть системы 98
2.5.3. Процедурная часть системы 102
2.5.4. Пример генерации и определения форм слов 106
2.5.5. Количественные характеристики системы генерации и определения форм слов 114
2.6. Направления усовершенствования и использования метода генерации и определения форм слов 117
2.6.1. Способы уменьшения просматриваемых цепочек преобразований при определении форм слов 117
2.6.2. Метод морфологического представления текста 121
2.7. Некоторые замечания по данной главе 125
2.7.1. Особенности предложенного метода генерации и определения форм слов 125
2.7.2. Предсказание грамматического значения словоформ, отсутствующих в словарях системы 126
Основные результаты 127
ГЛАВА 3. Метод обработки количественных числительных естественных языков 130
3.1. Задачи обработки числительных 130
3.2. Методы решения задач обработки числительных. Грамматика Г. Хардегри 132
3.3. Трехуровневая обобщенная модель числительного 136
3.4. Разработка алгоритмов синтеза и анализа числительных с использованием нормальных алгоритмов Маркова
3.4.1. Нормальные алгоритмы Маркова 142
3.4.2. Алгоритм синтеза целой части числительных 144
3.4.3. Алгоритм анализа целой части числительных 148
3.4.4. Алгоритм синтеза дробной части числительных 151
3.4.5. Алгоритм анализа дробной части числительных
3.5. Порядок действий при выполнении операций над числительными 154
3.6. Особенности правил образования и алгоритмов преобразований числительных естественных языков 158
3.6.1. Характеристики образования числительных естественных языков 158
3.6.2. Русский язык 159
3.6.3. Английский язык 167
3.6.4. Немецкий язык 168
3.6.5. Испанский язык 171
3.6.6. Финский язык 173
3.6.7. Анализ алгоритмов преобразований естественных языков 175
3.7. Машинный перевод числительных с помощью трехуровневой обобщенной модели числительного и числа 177
Основные результаты 179
ГЛАВА 4. Метод устранения ограничения нормальных алгоритмов маркова 181
4.1. Ограничение нормальных алгоритмов Маркова и метод его устранения 181
4.2. Модификации нормальных алгоритмов Маркова 184
4.3. Линейные нормальные алгоритмы 186
4.4. Решение задачи обращения с помощью линейных нормальных алгоритмов 188
4.5. Сводимость нормальных алгоритмов Маркова к линейным нормальным алгоритмам 195
4.6. Задача удвоения строки и ее решение с помощью линейных нормальных алгоритмов 197
4.7. Сводимость линейных нормальных алгоритмов к обобщенным нормальным алгоритмам 205
4.8. Представление цепочек формообразования с помощью нормальных алгоритмов Маркова и линейных нормальных алгоритмов 207
4.9. Усовершенствование алгоритмов обработки числительных с помощью линейных нормальных
алгоритмов 208
Основные результаты 210
ГЛАВА 5. Практическая реализация методов обработки форм слов и числительных в информационных системах 213
5.1. Задачи главы 213
5.2. Системы проверки знаний с динамической генерацией вариантов заданий 214
5.2.1. Понятие автоматизированных обучающих систем и их классификация 214
5.2.2. Система проверки знаний по морфологии естественных языков на основе системы генерации и определения форм слов 216
5.2.3. Интернет-приложения для обработки количественных числительных и система проверки знаний правил их образования количественных числительных естественных языков 218
5.2.4. Система проверки произношения и знаний грамматики естественных языков с динамической генерацией вариантов заданий 221
5.2.5. Система проверки знаний функционирования алгоритмических моделей 222
5.2.6. Система автоматизированного проектирования систем проверки знаний 223
5.3. Информационные системы с использованием разработанных методов обработки форм слов и числительных 225
5.3.1. Система анализа статей коллективных договоров 225
5.3.2. Интеллектуальная диалоговая информационно-справочная система 227
5.3.3. Система синхронного машинного перевода 229
Основные результаты 231
Заключение 233
Список литературы
- Автоматическая обработка текстов и области ее применения
- Решение задач генерации и определения форм слов и синтаксического анализа с помощью теории унификации
- Особенности правил образования и алгоритмов преобразований числительных естественных языков
- Сводимость нормальных алгоритмов Маркова к линейным нормальным алгоритмам
Введение к работе
Актуальность темы исследования и степень ее разработанности. Взаимодействие пользователя с ЭВМ на естественном языке предполагает автоматическую обработку текстов (АОТ) для понимания запроса пользователя и формирования ответа на них. При этом выдвигается требование, чтобы диалог мог вестись на нескольких языках. Это требование обусловлено двумя тенденциями современного мира, способствующими образованию многоязычной среды. Во-первых, появление межгосударственных союзов и объединений (например, Европейского Союза). Во-вторых, повышение статуса языков национальных меньшинств на государственном и региональных уровнях (Индия, ЮАР).
Для реализации многоязычных интерфейсов необходимо решать задачи машинного перевода, индексации и анализа текстов на нескольких языках. Однако существующие методы решения перечисленных задач ориентируются на один или несколько языков. Поэтому возникает необходимость разработки универсальных методов АОТ различных уровней, в том числе и морфологического уровня.
Данные тенденции, а также глобализация обостряют необходимость в специалистах со знанием нескольких языков. Поэтому актуальным становится разработка автоматизированных обучающих систем (АОС) по различным разделам языкознания, в том числе и морфологии естественных языков. Универсальные методы различных уровней АОТ могут быть использованы для построения перспективных систем проверки знаний, входящих в состав любой АОС, с динамической генерацией вариантов заданий.
Значительный вклад в развитие естественно-языковых интерфейсов и АОТ внесли такие ученые России, как Ю.Д. Апресян, Г.Г. Белоногов, В.М. Брябрин, О.С. Кулагина, А.А. Ляпунов, М.Г. Мальковский, Ю.Н. Марчук, И.А. Мельчук, А.С. Нариньяни, Р.Г. Пиотровский, Э.В. Попов, Д.А. Поспелов, В.А. Фомичев и др., а также зарубежные специалисты Т. Виноград (Т. Winograd), В.А. Вудс (W.A. Woods), К. Коскенниеми (К. Koskenniemi), М. Портер (М. Porter), Г. Хардегри (G. Hardegree), Н. Хомский (N. Chomsky), Р. Шенк (R. Schank) и др.
В большинстве научных работ перечисленных исследователей, связанных с разработкой методов морфологического уровня АОТ, рассматривается только один естественный язык или даже естественный язык с некоторыми ограничениями. В остальных работах, посвященных разработке многоязычных методов, возможность обработки других языков, кроме рассмотренных, теоретически не доказывается. Вопросы, связанные с обработкой числительных, в научных работах практически не обсуждаются, хотя эта проблема имеет важное значение в задачах машинного перевода, обработки речи и в обучении естественным языкам.
Алгоритмы решения задач описываются в рамках алгоритмических систем (моделей). Одной из алгоритмических моделей являются нормальные алгоритмы, предложенные А. А. Марковым в середине прошлого века. Однако их исследования продолжаются, о чем свидетельствуют современные публикации. Исследованию нормальных алгоритмов Маркова посвящены работы Н.М. Нагорного, И.А. Цветкова, Г. С. Цейтина и др.
Объект исследования: методы морфологической обработки текстов и способы описания формообразования естественных языков.
Предмет исследования: модели и алгоритмы генерации и определения форм слов естественных языков различных групп и семейств с их последующей реализацией в виде программных систем.
Цель и задачи исследования. Целью диссертационной работы является разработка моделей, методов и алгоритмов, позволяющих описывать и реализовывать формообразование полной парадигмы слов и обрабатывать числительные, универсальных для естественных языков различных групп и семейств, с их последующей реализацией в программных системах естественно-языкового человеко-машинного взаимодействия, АОТ и автоматизации обучения.
Для достижения цели необходимо решить следующие задачи:
-
разработать модель формообразования и метод генерации и определения полной парадигмы слов естественных языков различных групп и семейств;
-
разработать обобщенную трехуровневую модель числительного и метод обработки количественных числительных естественных языков различных групп и семейств, ускоряющий и упрощающий операции с ними;
-
исследовать нормальные алгоритмы Маркова, выявить их ограничения и предложить метод устранения этих ограничений;
-
реализовать предложенные модели и методы в программных системах морфологического анализа и синтеза форм слов и обработки числительных, а также системах проверки знаний с динамической генерацией вариантов заданий.
Методология и методы исследования. Для решения поставленных задач использовались элементы теорий графов, множеств, унификации, формальных грамматик и алгоритмов. Для практической проверки работоспособности предложенных методов использовалось разработанное программное обеспечение.
Основные научные результаты, полученные автором и выносимые на защиту.
-
Модель, позволяющая описывать формообразование полной парадигмы слов естественных языков различных групп и семейств.
-
Алгоритмы генерации и определения форм слов на основе предложенной модели формообразования и алгоритм, позволяющий автоматизировать построение цепочек преобразований на основе предложенной классификации образования форм слов.
-
Трехуровневая обобщенная модель числительного, являющаяся промежуточным этапом при обработке числительных и позволяющая сократить трудоемкость этих операций и упростить добавление новых языков.
-
Алгоритмы, позволяющие преобразовывать количественные числительные к предложенной модели числительного и обратно.
-
Метод устранения ограничения нормальных алгоритмов Маркова путём введения линейного вычислительного процесса и модификация нормальных алгоритмов Маркова, реализующая этот метод и позволяющая разрабатывать алгоритмы с линейной трудоемкостью.
-
Программные системы генерации и определения форм слов и обработки числительных, реализующие предложенные модели и алгоритмы и подтверждающие их адекватность и работоспособность.
Научная новизна. В диссертационной работе были получены следующие результаты.
-
Предложена модель, описывающая формообразование в виде цепочек преобразований, и в отличии от существующих моделей впервые доказана ее применимость к языкам различных групп и семейств. На основе данной модели разработаны алгоритмы, генерирующие и определяющие словоформы и составляющие вместе с моделью метод генерации и определения словоформ. Предложен алгоритм, автоматизирующий построение цепочек преобразований и упрощающий описание формообразование в терминах модели оператором-лингвистом.
-
Разработаны трехуровневая обобщенная модель числительного, являющаяся промежуточным этапом в операциях с количественными числительными различных языков и позволяющая сократить трудоемкость данных операций, а также алгоритмы преобразования числительных, записанные с помощью нормальных алгоритмов Маркова, составляющие метод обработки числительных. Введение промежуточного этапа упростило добавление новых языков в отличии от аналогичных подходов.
-
Выявлено ограничение нормальных алгоритмов Маркова, состоящее в невозможности реализовывать линейный вычислительный процесс, и предложен метод устранения данного ограничения. Разработана модификация нормальных алгоритмов Маркова (линейные нормальные алгоритмы), реализующая данный метод, и в ее рамках реализованы алгоритмы, сокращающие трудоемкость решения задач обращения и удвоения и число подстановок в схеме.
-
Разработано Интернет-приложение для обработки и перевода количественных числительных русского, английского, немецкого, испанского и финского языков через промежуточный этап в виде трехуровневой обобщенной модели. Интернет-приложением пользуются ежемесячно более 1 000 пользователей со всех постоянно обитаемых континентов, в том числе из более 200 университетов США, России, Канады и других стран. На основе предложенных методов генерации и определения форм слов и обработки числительных разработаны про-
граммные системы проверки знаний с динамической генерацией вариантов заданий и пояснений к неправильным ответам.
Теоретическая значимость работы заключается в разработке моделей и методов морфологической обработки текстов на естественных языках различных групп и семейств, исследовании нормальных алгоритмов Маркова и разработке их модификации, позволяющей устранить ограничения этой алгоритмической модели.
Практическая значимость работы. Разработанные методы и алгоритмы обработки форм слов и количественных числительных являются универсальными и позволяют решать соответствующие задачи для различных языков. Данные методы могут быть использованы как составные части многоязычных методов и систем АОТ, что позволит их упростить и уменьшить время разработки за счет универсальности предложенных методов. С помощью разработанной модификации нормальных алгоритмов Маркова были описаны некоторые алгоритмы данной работы. Результаты исследования могут быть использованы в учебных курсах по системам искусственного интеллекта и компьютерной лингвистике. Ежемесячно Интернет-приложение, разработанное на основе метода обработки числительных, используют более 1 000 человек из более 80 стран мира.
Достоверность научных положений, теоретических выводов и практических результатов диссертационной работы подтверждается соответствием результатов моделирования разработанных методов и алгоритмов правилам морфологии естественных языков, результатами работы программных средств, реализованных на основе предложенных методов, используемых во всем мире и имеющих государственную регистрацию в ФГУ «Федеральный институт промышленной собственности Федеральной службы по интеллектуальной собственности, патентам и товарным знакам» (ФГУ ФИПС, РОСПАТЕНТ), актами внедрения результатов диссертационной работы.
Реализация и внедрение результатов диссертационной работы. Диссертационная работа включает исследования, выполненные в Рязанском государственном радиотехническом университете (РГРТУ) в рамках госбюджетных НИР № 9-07Г «Разработка математических моделей, методов и алгоритмов обработки больших потоков информации в сложно организованных вьгаислительных структурах», № 8-08Г «Разработка теоретических основ автоматизации семантического анализа текстовых документов, проходящих правовую экспертизу», № 7-09Г «Разработка математических методов и алгоритмов передачи и обработки цифровой информации для поддержки интеллектуальных систем управления», № 6-11Г «Разработка теоретических основ управления качеством социально-образовательных отношений и необходимого правового и информационного обеспечения», № 1-12Г «Разработка и создание интеллектуального автоматизированного комплекса управления ресурсами в динамических информационно-телекоммуникационных системах», № 11-12Г «Разработка математических моделей, методов и алгоритмов обработки больших объемов
информации в сложно организованных системах искусственного интеллекта», в которых автор работы являлся исполнителем.
Метод генерации и определения форм слов и метод обработки количественных числительных были использованы в системе автоматизированного анализа коллективных договоров, разработанной в ведомственной лаборатории автоматизированного анализа коллективно-договорных актов образования, учредителем которой является Центральный Совет профсоюза работников народного образования и науки РФ, для сравнения их статей и, в случае их изменения, определения степени их различия. Использование данных методов позволило ускорить работу экспертов с данной системой по анализу статей коллективных трудовых договоров и эффективность системы в целом.
Модель формообразования, трехуровневая обобщенная модель числительного, метод генерации и определения форм слов и метод обработки числительных были реализованы в интерфейсе экспертной сети для переводчиков , разрабатываемой компанией ТИСС (Белгородская область). Предложенные модели и методы позволили добавить в интерфейс полезные инструменты для перевода. Немаловажным преимуществом этих моделей и методов является их независимость от языка.
Метод генерации и определения форм слов использовался в агентстве недвижимости 000 «ИНКОМ-Сокол» (г. Москва) для ввода и анализа текста объявлений о купле, продаже и аренде объектов недвижимости. Применение разработанного метода позволило реализовать запросы к базе недвижимости не только с помощью выбора параметров, но и на естественном языке, что упростило работу с базой.
Системы проверки знаний, разработанные на основе методов генерации и определения форм слов и обработки числительных, используются в учебном процессе учебных заведений г. Рязани: филиала Московского государственного университета экономики, статистики и информатики, филиала НОУ ВПО «Московский институт экономики, менеджмента и права», МОУ «Средняя школа №45» и МОУ «Средняя общеобразовательная школа №49». Результаты диссертационной работы внедрены в учебный процесс РГРТУ для студентов специальности 230105 - «Программное обеспечение вычислительной техники и автоматизированных систем» в курсах «Математическая логика и теория алгоритмов», «Системы искусственного интеллекта» и «Проектирование систем искусственного интеллекта», для студентов специальности 080801 - «Прикладная информатика (в экономике)» в курсе «Интеллектуальные информационные системы».
Интернет-приложение обработки количественных числительных, которое доступно всем пользователям сети Интернет, используется в более 200 университетах России, США, Канады и других стран.
Апробация результатов работы. Научные результаты работы докладывались и обсуждались на 9-10, 12-16-й Международных научно-технических конференциях «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (г. Рязань, 2000-2001,
2004-2005, 2008, 2010 гг.), 7-й Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (г. Таганрог, Ростовская область, 2004 г.), 9-16, 18-й Всероссийских научно-технических конференциях студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (г. Рязань, 2004-2011, 2013 гг.), Международной научно-практической конференции «Электронные средства и системы управления» (г. Томск, 2004 г.), 30, 32-34-й Всероссийских научно-практических семинарах и научно-технических конференциях «Сети, системы связи и телекоммуникации», «Информационные и телекоммуникационные технологии. Подготовка специалистов для инфокоммуникационной среды» (г. Рязань, 2005, 2007-2009 гг.), Научной конференции, посвященной 80-летию Московского государственного университета печати (г. Москва, 2009 г.), Научно-практической конференции «Традиции и инновации в лингвистике и лингвообразовании» (г. Арзамас, Нижегородская область, 2011г.), 27-й Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (г. Пенза, 2011 г.), 11-й Международной научно-практической конференции «Интеллект и наука» (г. Железногорск, Красноярский край, 2011г.), 2-й Всероссийской научно-методической конференции «Инновации и традиции науки и образования» (г. Сыктывкар, Республика Коми, 2011 г.), 3-й Всероссийской научно-методической конференции «Методы обучения и организация учебного процесса в вузе» (г. Рязань, 2013 г.), 12-й Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых «Техника XXI века глазами молодых ученых и специалистов» (г. Тула, 2013 г.), 5-6-й Межвузовских школах-семинарах «Задачи системного анализа, управления и обработки информации» (г. Москва, 2014-2015 гг.), International Conference on Computer Technologies in Physical and Engineering Applications 2014 (ICCTPEA-2014) (г. Санкт-Петербург).
Публикации. По теме диссертации опубликованы 88 печатных работ, из них 26 в соавторстве, включая 1 работу в базе данных Scopus. В их числе 23 статьи в изданиях из «Перечня ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученых степеней кандидата и доктора наук», 1 статья в издании на английском языке, 27 статей в научных журналах и межвузовских сборниках, 30 тезисов докладов Международных и Всероссийских конференций и семинаров, 7 свидетельств о государственной регистрации программы для ЭВМ в РОСПАТЕНТе.
Личный вклад автора. Все результаты диссертационной работы, в том числе постановка задач, разработка и исследование предложенных методов, основные научные результаты и выводы принадлежат лично автору. Программное обеспечение предложенных методов разработано под руководством и при непосредственном участии автора. Участие
соавторов заключалось в консультациях, совместной разработке программных средств и получении экспериментальных результатов на основе предложенных автором методов.
Структура и объем диссертационной работы. Диссертационная работа общим объемом 279 страниц состоит из введения, пяти глав, содержащих 47 рисунков и 17 таблиц, заключения, списка литературы из 193 наименований и приложений.
Соответствие паспорту специальности. Диссертационная работа представляется по специальности 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей» и соответствует п. 7, поскольку в ней предложены модели и методы морфологической обработки текстов, являющиеся составной частью любого естественно-языкового человеко-машинного интерфейса.
Автоматическая обработка текстов и области ее применения
Алгоритм выбирает вторую гипотезу, так как строка содержит меньше морфем, чем первая и возвращает ее в качестве результата работы.
Преимущества метода: в качестве аффиксов могут использоваться как окончания, так и приставки; возможность реализации не только для русского языка.
Недостатки метода: сложность алгоритма морфологического анализа; сложная структура словарей системы; сложность заполнения словарей системы; СОС содержит несколько основ одного слова; отсутствие возможности обработки аналитических форм слов.
Д.Е. Шуклин предложил для решения задач морфологического анализа текста и анализа словоизменения использовать семантическую нейронную сеть [152] (начало 2000-х гг.). В качестве структуры семантической нейронной сети, выполняющей морфологический анализ, применяется синхронизированное линейное дерево. Автор так описывает свой метод.
«Линейное дерево состоит из подслоев нейронов. Каждому синхронизированному подслою соответствует фронт волны обработки. Нейроны первого подслоя соответствуют первой букве слова, второго - второй и так далее. Общее количество подслоев равно максимальному количеству букв в одном слове. Первый подслой состоит из нейронов, распознающих первую букву, второй слой состоит из нейронов распознающих первые две буквы, третий - первые три буквы. Упрощенный фрагмент синхронизированного линейного дерева, распознающего слова «мама», «маме», «машина» и «машине» представлен на рисунке 2.3.
Каждый нейрон в упрощенном синхронизированном линейном дереве является синхронизированным конъюнктором и имеет одну входную связь с нейроном из предыдущего подслоя, соответствующим предыдущей букве слова, и одну входную связь с нейроном из слоя рецепторов, соответствующим текущей букве. Каждый нейрон может иметь выходную связь с неограниченным количеством нейронов из следующего подслоя обработки» [152].
Структура нейронной сети морфологического разбора слов «мама», «маме», «машина», «машине» «Различным вариантам состояния входного потока символов в нейронной сети соответствуют различные варианты состояния этой сети. Результатом анализа, извлеченным из обработанной части текста в течение одного кванта времени, является мгновенное состояние синхронизированного линейного дерева. Мгновенное состояние включает в себя мгновенный снимок множества нейронов, множества связей между нейронами и множества внутренних состояний нейронов. Количество нейронов в сети ограниченно, нейроны имеют конечное число состояний и связей, поэтому слой анализа текста в виде синхронизированного линейного дерева представляет конечный автомат. Переход из одного состояния в другое происходит при подаче на слой разбора текста очередного символа входной последовательности» [152].
Преимущества метода: возможность использования математического аппарата нейронных сетей для морфологического и синтаксического анализа; возможность описывать большое число типов изменений при формообразовании; в качестве аффиксов могут использоваться как окончания, так и приставки; возможность реализации не только для русского языка.
Недостатки метода: необходимость построения нейронной сети сложной структуры для простых преобразований; при увеличении количества обрабатываемых слов значительно увеличивается количество нейронов и сложность структуры нейронной сети; отсутствие возможности синтеза форм слов; отсутствие возможности обработки аналитических форм слов.
И.М. Ножов в своей диссертационной работе предложил морфологический анализ без словаря [87] (конец 1990-х гг.) для системы автоматизированной индексации документов. Алгоритм анализа основан на самообучении программы на массивах текстов и совмещает два подхода: 1) лингвистический - формализованная грамматика для построения морфологических гипотез; 2) математический - метод корреляции, позволяющий унифицировать морфологическую гипотезу. Морфологический анализ без словаря применяется для индексирования текстовой БД, в результате чего строится грамматический СОС и связанный с ним индекс документов, предназначенный для полнотекстового поиска по БД.
По результатам морфологического анализа словоформы соотносятся с той или иной лексемой, словоформы одной лексемы объединяются в отдельные классы, однозначно определяются грамматические значения словоформ и индексируются тексты по встретившимся в них основам.
Для морфологического анализа используется минимальный объем исходной информации: таблица предлогов и таблица местоимений и числительных, имеющих нерегулярное склонение.
Результаты морфологического анализа объединяются в СОС данной БД, каждая статья которой задается тройкой значений [основа, часть речи, парадигматический класс]. Морфологический анализатор состоит из трех модулей: 1) статический массив флексий и правила формализованной грамматики русской морфологии, построенной на основе грамматического словаря А. А. Зализняка [40]; 2) модуль, использующий правила формализованной грамматики для построения морфологического дерева словоформы, в узлах которого хранятся все возможные гипотезы об основах и грамматических значениях словоформы; 3) метод, позволяющий отнести словоформу к лексеме и отсечь неверные варианты.
Преимущества метода: простота словарей системы, их минимальный объем; определение словоформ, отсутствующих в словарях системы; реализация методов во втором и третьем модулях, не зависящих от языка.
Недостатки метода: возможен только анализ, но не синтез; правильный результата анализ может получен с вероятностью меньшей 1; результат анализа не позволяет проводить в дальнейшем семантический анализ; трудоемкое построение в ходе анализа «леса» - нескольких деревьев и матричные вычисления для отсеивания неправильных вариантов; ориентация на флек 51 тивный анализ по окончанию; отсутствие возможности обработки аналитических форм слов.
Рассмотрим методы генерации и определения форм слов, предложенные зарубежными специалистами и применимые в том числе и для русского языка.
Киммо Коскенниеми из Университета Хельсинки (Финляндия) предложил двухуровневую модель для определения и генерации форм слов [171, 172] (начало 1980-х гг.).
Модель включает два уровня представления: лексический и поверхностный, между которыми вводятся правила (соответствия). Лексический уровень формируется путем применения правил естественного языка без учета контекста, а поверхностный уровень учитывает контекст, в котором эти правила используются.
Решение задач генерации и определения форм слов и синтаксического анализа с помощью теории унификации
Чаще всего, префикс в формах отсутствует, поэтому соответствующее преобразование исключается из цепочки.
Данная классификация цепочек преобразований является полной, то есть любая цепочка может быть отнесена к одному из перечисленных типов, так как если цепочка не будет отнесена к типам 1-3, то она будет отнесена к типу 4 согласно утверждению 2.1. На основе данной классификации предлагается алгоритм автоматизированного построения цепочек преобразований по основе и словоформе (рисунок 2.13), который заключается в выделении и поиске в форме F левой части L и правой части Q основы S, анализе их относительных позиций и проверки условий для определения типа цепочки.
Алгоритм построения цепочек преобразований Если форма F - аналитическая, то она разбивается на составляющие ее слова, и далее обрабатывается каждое слово (блоки 1, 2, 11). Это необходимо для выделения знаменательного и служебного слов аналитической формы. В словоформах «был бы» или «буду будить» основы «бы(тъ)» или «буд{итъ)» соответственно могут быть найдены дважды, что приводит к неправильному формированию цепочки.
Если форма F - синтетическая, то она обрабатывается целиком. В основе S выделяются левая часть L и правая часть Q по алгоритму, который будет рассмотрен далее, и осуществляется поиск их в текущем слове (блок 3). Далее определяется тип формируемой цепочки преобразований: первого типа (блоки 4, 5), второго типа (блоки 6, 7), третьего типа (блоки 8, 9). Если определить тип цепочки не удалось, то формируется цепочка четвертого типа (блок 9). После окончания цикла выбирается цепочка R минимального типа (блок 12). На выходе алгоритма формируется цепочка преобразований R одного из четырех типов.
Алгоритм построения цепочек преобразований формирует цепочку преобразований R для любой пары входных значений основы S и формы F, так как классификация цепочек преобразований является полной.
При построении цепочек преобразований необходимо разделить основу на левую и правую часть, чтобы определить тип цепочки (блок 3). Рассмотрим вспомогательный алгоритм выделения в форме F левой части L и правой части Q основы S (рисунок 2.14). Алгоритм состоит в выделении сначала левой части основы, и поиске в оставшейся подстроке правой части.
На вход алгоритма поступает форма F целиком или одно из составляющих ее слов. Предполагается, что левая часть L формы F представляет собой основу S, а средняя часть М и правая части Q - пустые строки (блок 1). Чтобы выделить левую L и правую Q части основы S, необходимо сначала найти левую часть L. Для этого от левой части L отделяется буква справа и присоединяется к правой части Q слева (блок 3). Такое преобразование повторяется до тех пор, пока левая часть L не будет найдена в форме F или в левой части L
не останется букв (блок 2). Далее те же действия повторяются для правой части Q (блоки 4-5).
Пусть необходимо построить цепочку для получения из основы «сон» формы единственного числа творительного падежа «сном». Выде 96 лим в форме «сном» левую и правую части основы «сон». Данное формообразование описывается цепочкой типа 2в приведенной выше классификации цепочек преобразований.
В результате в форме F = «сном» найдены левая часть L = «с» и правая часть Q = «н» основы S = «сон», поэтому цепочка для данного формообразования имеет тип 2в: R = (сон сн, +ом). Алгоритм построения цепочек преобразований позволяет автоматически строить цепочки преобразований любых видов формообразования. Однако может возникнуть необходимость ручной корректировки построенных цепочек для того, чтобы описать с помощью данных цепочек формообразование всех слов данного типа формообразования. Поэтому построение цепочек названо «автоматизированным», а не «автоматическим».
Данные алгоритмы легли в основу системы автоматизированного построения цепочек преобразований (XAPHIRIA), зарегистрированной в РОСПАТЕНТе (приложение А). 2.4.3. Применение алгоритмов генерации и определения форм слов для словообразования Предлагаемый метод генерации и определения форм слов предназначен для описания формообразования или словоизменения.
Другой областью применения разработанных алгоритмов является словообразование. Словообразование заключается в образовании новых слов в языке «по существующим моделям с помощью аффиксации, чередования звуков, словосложения, стяжения, развития новых значений и других средств» [133]. Пример словообразования: «дом» - «домик» - «домашний». Модель образования новых слов можно описать с помощью цепочек преобразований.
В многих языках существуют части слова, придающие словам, в которых они встречаются, различные семантические оттенки: уменьшительно-ласкательные, уничижительные и т. п. Разработанные алгоритмы могут использоваться для выявления таких частей слов. При анализе цепочки выделяются преобразования, которые носят словообразовательный характер и придают слову различные семантические оттенки, и на основе этого анализа корректируется семантическое значение слова.
Особенности правил образования и алгоритмов преобразований числительных естественных языков
Целая часть числительного Ni состоит из числа ноль С0 или последовательности і + 1 триад NH. В числительном обязательно присутствует первая слева триада, остальные триады могут отсутствовать. Триады Т разделены названиями порядка триад М. В случае отсутствия триады, отсутствует и соответствующее ей название порядка.
Дробная часть числительного N2 состоит из последовательности названий цифр. Правило записи дробной части N2 рекурсивное: дробная часть состоит либо из названия цифры Ті или С0, либо из названия цифры Ті или С0 и оставшейся части дробной части N2. Последняя цифра дробной части может быть как нулем, так и отличной от нуля.
Третий уровень модели числительного описывает порядок сотен, десятков и единиц в триаде.
Существуют три вида триад Т: триады, в которых обязательно присутствуют единицы Ть десятки Т2, сотни Т3. В триаде Т3 помимо сотен могут присутствовать десятки и/или единицы. В триаде Т2 помимо десятков могут присутствовать единицы. Триаду Ті составляют только единицы. Триады, содержащие только нули, в числительном отсутствуют.
Пример 3.5. Запишем с помощью грамматики предложенной модели числительное, соответствующее числу 34 567,89 (рисунок 3.6). Обойдя конечные вершины (выделены на рисунке) слева направо, получим нормализованное числительное C3DiC4MiC5D2C6DiC7EC8C9.
Предлагаемая модель числительного является результатом анализа правил образования числительных естественных языков различных групп и семейств и развитием грамматики Г. Хардегри.
Для формальных грамматик существуют нормальная форма Хомского (бинарная нормальная форма) и нормальная форма Грейбах [28]. Нормальные формы необходимы для представления грамматик в одном виде. Однако структуру числительного описывают только грамматика Хардегри и грамматика модели числительного. Поэтому предложенная грамматика записана в той же форме, что и грамматика Хардегри.
Модель числительного описывает структур только количественных числительных, но не порядковых, так как общие закономерности построения порядковых числительных свойственны только родственным языкам, например, английскому и немецкому языкам. Поэтому построение модели трудноосуществимо для различных по правилам образования порядковых числительных естественных языков.
Предложенная модель числительного будет использована в методе обработки количественных числительных естественных языков. Помимо модели числительного, метод также включает алгоритмы обработки числительных: 1) алгоритмы синтеза и анализа числительных; 2) алгоритмы преобразований «модель-язык» и «язык-модель». 3.4. Разработка алгоритмов синтеза и анализа числительных с использованием нормальных алгоритмов Маркова
Для записи алгоритмов обработки числительных воспользуемся нормальными алгоритмами Маркова [27, 72, 78, 79], одной из алгоритмических моделей. Входными и выходными объектами данной алгоритмической модели являются слова в некотором алфавите, поэтому нормальные алгоритмы
Маркова наилучшим образом подходят для формализованного описания алгоритмов обработки числительных.
Нормальный алгоритм Маркова состоит из упорядоченного списка подстановок, называемого нормальной схемой. Схема состоит из простых и заключительных подстановок:
Заключительные подстановки, которые заканчиваются символом «», завершают выполнение алгоритма, а простые подстановки - нет. Выполнение нормального алгоритма над строкой S осуществляется следующим образом. Нормальная схема просматривается сверху вниз до тех пор, пока не будет найдена подстановка, левая часть которой содержит подстроку, входящую в строку S. Если подстановка найдена, то в строке S производится замена, и просмотр схемы начинается заново, иначе алгоритм заканчивает выполнение. Другим условием завершения работы нормального алгоритма является выполнение заключительной подстановки.
Введем следующие соглашения. Под трудоемкостью нормального алгоритма Маркова понимается количество выполненных подстановок, необходимых для решения задачи. В алгоритмах используются вспомогательные символы (указатели), не входящие в алфавиты Z и С и обозначаемые греческими буквами.
Данные обозначения являются расширением нормальных алгоритмов Маркова. Обозначения добавление символа к строке слева и справа имеют трудоемкость одной подстановки, введены для сокращения и понятности записи алгоритмов и могут быть реализованы нормальными алгоритмами, которые в работе [72] именуются левым присоединяющим алгоритмом и правым присоединяющим алгоритмом соответственно.
Отметим, что правила перезаписывания, использованные Г. Хардегри, схожи с нормальными алгоритмами Маркова.
Для простоты и наглядности целесообразно разработать отдельно четыре алгоритма для синтеза и анализа числительных: синтеза и анализа целой части и синтеза и анализа дробной части числительных.
Эти и большая часть алгоритмов данной главы, работают по одному принципу. В начало или в конец обрабатываемого числительного или числа устанавливается указатель, который имеет один или два индекса в зависимо 145 сти от задач. Значения индексов, их сочетания и символы перед указателями определяют, какая ситуация сложилась в ходе решения задачи и какие подстановки будут выполняться на данном этапе.
Алгоритм синтеза целой части числительных преобразует целую часть числа в целую часть числительного модели. Нормальная схема алгоритма синтеза состоит из следующих пронумерованных подстановок.
Сводимость нормальных алгоритмов Маркова к линейным нормальным алгоритмам
Возможность сводимости алгоритмов объясняется тем, что линейный нормальный алгоритм позволяет выполнять подстановки в том же порядке, что и нормальный алгоритм Маркова.
Сводимость схемы любого нормального алгоритма Маркова к схеме линейного нормального алгоритма влечет два следствия: 1) любую задачу, которую можно решить с помощью нормального алгоритма Маркова, можно решить и с помощью линейного нормального алгоритма; 2) трудоемкость любого линейного нормального алгоритма будет не хуже трудоемкости нормального алгоритма Маркова, но не наоборот.
Обратная сводимость линейных нормальных алгоритмов к нормальным алгоритмам Маркова возможна при выполнении двух условий: 1) в каждой строке схемы находится только одна подстановка; 2) метка строки равна левой части подстановки строки.
Работа алгоритма начинается с добавления указателя а к строке слева (подстановка 9). После этого происходит удвоение символов строки с перемещением указателя а вправо и вставки указателей Р между удвоенными символами строки (подстановки 1-2). С помощью подстановок 3-6 копии символов строки перемещаются влево, чтобы восстановить исходную строку, при этом указатели Р служат левой и правой границами перемещения символов строки. Когда все символы строки перемещены влево и строка удвоена, то есть между указателями Р находится не более одного символа строки, из строки удаляются указатели Р и указатель а (подстановки 7-8). После этого алгоритм заканчивает свое выполнение.
Ha последнем шаге алгоритма получена строка babbab - результат удвоения строки bab. При m = 3 трудоемкость алгоритма удвоения составит Тмощ = 3(3 - 1)/2 + 2-3 + 2 = 11 шагов, что совпадает с количеством шагов в данном примере. Задачу удвоения можно решить и с помощью предложенных линейных нормальных алгоритмов. Для удвоения элементов строки необходимо добавлять последовательно к строке справа или слева копии элементов строки (рисунок 4.2). Трудоемкость такого алгоритма будет линейной, как и трудоемкость задачи удвоения в общем.
Поясним работу алгоритма. Строка S не содержит вспомогательных символов аир, поэтому первой выполняется подстановка 4. В результате строка имеет вид PocS. Далее выполняются подстановки 1 или 2 в зависимости от символа, который находится справа от указателя а. Работу этих подстановок можно записать так: S pS axvS" S xpS xayS". Здесь S и S" - подстроки строки S, символы х и у - символы а или Ь. До и после выполнения подстановки слева от указателей аир находятся одинаковые подстроки, что доказывает удвоение символов. Когда справа от указателя а не остается символов строки складывается ситуация SpSa. В этом случае выполняется подстановка 3, удаляющая указатели а и р. Результатом работы алгоритма является строка SS. Принцип работы алгоритма иллюстрирует рисунок 4.2.
Назовем предложенный алгоритм линейным нормальным алгоритмом удвоения А. Его трудоемкость Тудв определяется по следующей формуле:
В результате работы алгоритма получена удвоенная строка babbab. Алгоритм удвоения Б работает по тому же принципу и имеет ту же трудоемкость. Другие предложенные линейные нормальные алгоритмы удвоения приведены в [112]. Трудоемкость и количество подстановок предложенных линейных нормальных алгоритмов удвоения А-Б, а также нормальных алгоритмов удвоения, предложенных в работах А.А. Маркова и Н.М. Нагорного [72] и В.А. Мощенского [79], представлены в таблице 4.2. Алгоритмы удвоения также были предложены И.А. Цветковым в своих модификациях.
Сравнение характеристик нормальных алгоритмов удвоения Название алгоритма удвоения Трудоемкость Количествоподстановокалгоритма Тип алгоритма Нормальный алгоритм удвоения А.А. Маркова и Н.М. Нагорного m2/2 + 5т/2 + 2 п2 + n + 4 Полиномиальный (квадратичный) Нормальный алгоритмудвоенияВ.А. Мощенского т2/2 + Зт/2 + 2 п2 + n + 3 Полиномиальный (квадратичный) Линейные нормальные алгоритмы удвоения А-Б 2т+ 3 2п + 3 Линейные Использование линейных нормальных алгоритмов и в случае задачи удвоения позволило снизить трудоемкость, сделав ее линейной, а также уменьшить количество подстановок схемы.
На основе линейного нормального алгоритма удвоения опишем линейный нормальный алгоритм сведения нормального алгоритма Маркова к линейному нормальному алгоритму. Алгоритм сведения перерабатывает схему нормального алгоритма Маркова в схему линейного нормального алгоритма, используя правила сведения алгоритмов из раздела 4.5.
Разрабатываемый алгоритм сведения использует в качестве входных и выходных данных нормальную схему, записанную в виде строки. При такой записи подстановки записываются последовательно, а также используются следующие обозначения:
Пусть множество Н = {Нь Н2, ..., Нк} - множество символов, использующихся в левых и правых частях подстановок сводимого нормального алгоритма, множество G= {#, , х, 0, } - множество элементов подстановок, а множество J = {є, ф} - множество вспомогательных символов алгоритма сведения. Между множествами справедливы следующие соотношения: