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

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

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

Дипломная работа

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

Медведев С.А.

Москва, 2019

Аннотация

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

Annotation

This work is devoted to the development and writing of a program capable of making morphological and syntactic analysis of texts in natural language (Russian). Existing approaches of solving this problem are reviewed, a method of morphemic, morphological and syntactic analysis is developed, the structure of the software that implements the proposed method is developed. A description of the program and the results of its testing are compiled. Recommendations on the applicability of the developed software are given.

Оглавление

Введение

1. Аналитическая часть

1.1 Цель

1.2 Актуальность

1.3 Общий анализ этапов анализа текстов

1.4 Подробный анализ морфологического и синтаксического этапов

1.5 Обзор существующих морфологических анализаторов текстов на естественном языке

1.6 Обзор существующих синтаксических анализаторов текстов на естественном языке

1.7 Задачи

1.8 Функциональные требования

2. Конструкторская часть

2.1 Обоснование выбора алгоритмической и инструментальной базы

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

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

2.4 Объединение морфологического и синтаксического анализаторов

3. Технологическая часть

3.1 Детали реализации разработанного метода

3.1.1 Класс «word»

3.1.2 Класс «morph»

3.1.3 Класс «substring»

3.1.4 Класс «sintax»

3.2 Апробация

3.3 Выводы

Заключение

Список использованных источников

Введение

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

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

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

1. Аналитическая часть

1.1 Цель

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

1.2 Актуальность

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

1.3 Общий анализ этапов анализа текстов

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

На основе работы Т.В. Ермоленко и А.С. Гайдамаки[1] можно выделить 4 основных стадии анализа естественного текста - графематическую, морфологическую, синтаксическую и семантическую.

Графематический анализ является приведением текста, полученного анализатором на вход, к удобному для дальнейшей работы состоянию. Так, авторы работы[1] предъявляют к данному этапу следующие требования:

разбиение текста на графемы, абзацы и предложения;

определение границ предложений;

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

определение регистра слов;

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

распознавание имен собственных;

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

распознавание формул (математических и химических)

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

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

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

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

1.4 Подробный анализ морфологического и синтаксического этапов

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

Морфологическая стадия анализа, как уже говорилось выше, является сопоставлением каждого слова текста с какой-то известной словоформой. На данный момент самым распространенным решением является работа анализатора через лемматический словарь. Таким образом, к программе прилагается база данных, содержащая морфологическую информацию для большинства (в идеале - всех) существующих словоформ. Проблема данного подхода двойственна. Во-первых, из-за необходимости постоянного поиска информации в огромной базе данных и интеграции этих данных в дальнейшую работу программы время работы становится достаточно большим. Более того, оно возрастает пропорционально увеличению лемматического словаря, а изменчивость реального языка требует регулярно дополнять и изменять словарь. К тому же в общем виде возможен морфологический анализ «псевдоестественных», то есть не существующих в реальном языке, но подчиняющихся формальным правилам словообразования, слов. Основываясь на лемматическом словаре, работа с псевдоестественными словами становится невозможна. Авторы работы [1] рассматривают эту стадию следующим образом: «В результате [морфологического] анализа для каждой словоформы текста определяется ее морфологическая информация (МИ) и осуществляется лемматизация - приведение текстовых форм слова к словарным (начальным)». Таким образом, основными задачами данной стадии являются получение морфологической информации о слове и сопоставление его с начальной словоформой. Причем, необходимость начальной словоформы связана в большей степени с необходимостью дальнейшего семантического анализа и в контексте данной работы является вторичной.

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

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

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

Синтаксическая стадия анализа, как уже упоминалось выше, заключается в построении синтаксической модели. Для этого в первую очередь необходимо определить требования, предъявляемые к синтаксической модели. Так, Зимовец Наталья Викторовна и Санивская Елена Анатольевна в своей статье «Синтаксические модели предложения: подходы к выделению»[2] обозначают 5 требований к синтаксической модели: воспроизводимость, обобщенность, значимость, минимальность и внутренняя организованность.

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

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

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

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

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

Исходя из всего вышесказанного, можно определить необходимый для данной работы общий вид модели. Она будет выражена деревом зависимостей, корнем которого будет являться один из членов основы предложения, остальными вершинами - прочие входящие в предложение слова, ребрами - связи, а относительной удаленностью вершин от корня - относительная зависимость членов предложения. Такая модель априорно минимальна и организована, при этом она удобна для дальнейшего использования и весьма наглядна. Более того - при использовании такой модели алгоритм разложения в нее предложения становится схож с алгоритмом BFS. Вначале будет задаваться корень (например - подлежащее, так как его свойства позволяют более точно выделить его в большинстве предложений), потом - напрямую связанные с ним слова, и так далее до тех пор, пока предложение не будет полностью разложено в модель.

1.5 Обзор существующих морфологических анализаторов текстов на естественном языке

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

В России существует крупная ежегодная компьютерно-лингвистическая конференция Dialogue, в рамках которой проводятся сравнения различных программ для анализа текстов. В частности, в 2010 году темой соревнования программ Dialogue Evaluation 2010 была именно морфология [3]. В первую очередь следует рассмотреть критерии оценивания результатов работы морфологических анализаторов. Оценка определялась по семи критериям, каждый из которых мог быть зачтен либо не зачтен данной программе. Соревнование включало в себя разделы, приведённые в таблице 1 (согласно [3]).

Таблица 1. Критерии, по которым проводилась оценка на соревновании

Разделы соревнования	Задача
Лемматизация	Правильно определить лемму (исходную форму) словоформы. Оценивается наличие правильной леммы среди всего множества лемм, представленных в разборе.
Части речи	Правильно определить часть речи, к которой принадлежит исходная словоформа. Оценивается наличие правильной части речи среди всего POS, представленного в разборе.
Морфология (другие грамматические теги)	Правильно определить грамматические теги, которые характеризуют исходную словоформу, например, род, число, падеж, время и т.д. Оценивается наличие правильного набора грамматических тегов, представленных в разборе.
Редкие слова	Дорожка посвящена словам, для которых системы со встроенным грамматическим словарем не могут найти соответствия в словаре и вынуждены строить гипотезы относительно их леммы, части речи и других грамматических характеристик. Для систем без встроенного словаря трудности представляют слова с редким типом словоизменения. В рамках данной дорожки ставится задача правильно определить лемму и часть речи, которые характеризуют исходную словоформу. Оценивается наличие правильной пары {лемма; часть речи} среди всех вариантов, представленных в разборе.
«Грязные» тексты	Дорожка посвящена оценке морфологического анализа в текстах, в которых в большом количестве присутствуют словоформы, записанные с ошибками. Это могут быть автоматически распознанные сканы, тексты чатов и т.п. В рамках данной дорожки ставится задача правильно определить лемму и часть речи, которые характеризуют исходную словоформу. Оценивается наличие правильной пары {лемма; часть речи} среди всех вариантов, представленных в разборе.
Разрешение неоднозначностей: лемма	Правильно определить лемму (исходную форму) словоформы. Система должна предлагать единственно правильный/наиболее вероятный вариант из всех возможных. Если в разборе представлено несколько вариантов лемматизации, оценивается первая по счету лемма.
Разрешение неоднозначностей: часть речи	Правильно определить часть речи, к который принадлежит исходная словоформа. Система должна предлагать единственно правильный/наиболее вероятный вариант из всех возможных. Если в разборе представлено несколько вариантов POS, оценивается первая по счету POS.

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

Cir_morph - морфологический анализ русского и английского языков. В случае с русским языком, анализ происходит по сокращенной, а потом по полной версии словаря Зализняка. На момент соревнования данный словарь насчитывал 130 000 лемм. Также существует возможность построения гипотез при отсутствии леммы в словаре и имеются некоторые эвристики - невозможные парадигмы, приставки, суффиксы, пользовательский словарь и тому подобные [3].

Упомянутый выше словарь Зализняка используется во многих русских лингвистических парсерах, таких как Starling, mystem, RuMor и другие [4]. В подобных программах в большинстве случаев критерием истинности является наличие идентичной или соответствующей словоформы в базовом словаре. Эвристики и гипотезы в таких случаях являются лишь дополнительным средством анализа. Судя по протоколу соревнования Dialogue [3], данный комбинированный метод оправдывает себя, однако в данной работе нам хотелось бы рассмотреть вариант алгоритма, не требующего для анализа словаря лемм и способного равнозначно анализировать как естественные, так и псеводестественные (образованные искусственно при помощи естественных правил словообразования) словоформы. Тем не менее, нельзя не отметить, что алгоритмы, реализованные в Cir_morph, себя очень хорошо зарекомендовали. К сожалению, код программы не является открытым, из-за чего нет возможности подробно их изучить.

Pymorphy - некоммерческий проект с открытым кодом, созданный на базе aot.ru. Во многом схож со своим исходником, но реализация алгоритмов упрощена, что позволило создать короткий, понятный и удобно расширяемый код в ущерб производительности [3].

Этот анализатор написан на языке Python и является свободно распространяемой библиотекой. Как сказано на его официальном сайте, Pymorphy позволяет:

приводить слово к нормальной форме [5];

ставить слово в нужную форму, например, ставить слово во множественное число, менять падеж слова и т.д. [5];

модифицировать фильтр шаблонов (template filter), который позволяет реализовывать необходимые функции прямо в шаблоне django (так, возможно приводить несогласованные части текста к согласованным предложениям, задав параметры согласования вручную) [5];

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

Как видно из приведенного описания, функционал программы весьма разнообразен. Однако, как и в ранее рассмотренном случае с программой Cir_morph, здесь используется словарь. Однако, на официальном сайте, в разделе «Возможности библиотеки» [5], наглядно демонстрируется возможность проводить анализ псевдоестественных слов.

Естественно, существует еще множество аналогичных программ, которые в данной работе не рассматриваются, но не могут считаться хуже, чем две вышеуказанные. Пожалуй, одна из самых известных и точных - ABBYY Compreno [6].

1.6 Обзор существующих синтаксических анализаторов текстов на естественном языке

Как и морфологические, синтаксические парсеры также уже существуют в немалом количестве. В данной работе будут рассмотрены парсеры, представленные в рамках конференции Dialogue 2012, когда темой был именно синтаксис[7].

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

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

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

В соревновании принимали участие многие программы. Ниже будут рассмотрены некоторые из них.

Семантико-синтаксический анализатор SEMSIN. Данный анализатор включает в себя морфологический модуль, принцип работы которого схож с описанным в одной из моих предыдущих работ. В любом случае, подробно останавливаться на морфологии сейчас не имеет смысла. Важно лишь заметить, что при первой обработке токенов каждому приписывается как морфологическая, так и синтаксическая, и даже семантическая информация, в то время как в моей предыдущей эти процессы предполагалось проделывать последовательно. «Затем цепочка токенов обрабатывается с помощью системы продукционных правил с целью снижения неоднозначности и перехода от линейной схемы предложения к синтаксическому дереву. Система делает попытку применения каждого из правил последовательно ко всем токенам и при выполнении указанных в правиле условий совершает определенные действия».[8] Как видно из данной цитаты, данный парсер стремиться построить полное дерево, последовательно распределяя в нем размеченные токены в соответствии с системой правил. Данный подход кажется оптимальным, наиболее соответствующим описанным выше требованиям и подходящим для взятия за основу в данной работе.

Синтаксический и семантический парсер, основанный на лингвистических технологиях ABBYY compreno. Упоминание данного парсера является обязательным, поскольку ABBYYзанимает лидирующие позиции в разработке автоматических анализаторов текстов на естественных языках. Логика работы данного парсера близка к описанной выше, но имеет одно значительное преимущество - ссылки вне дерева, «non-tree links»[9]. Это внешние информационные блоки, позволяющие в виде исключений обрабатывать анафоры, разрывные связи и прочие нелокальные связи. В рамках данной работы этот метод реализован не будет, однако его практическая польза очевидна, а отдельные его элементы могут быть включены в реализацию позже, по мере необходимости.

На конференции Dialogue Evaluation 2012 также были представлены и другие синтаксические парсеры, такие как ETAP и SyntAutom, однако общий принцип работы и них схож с вышеописанными, а разбор деталей реализации невозможен из-за закрытого кода.

1.7 Задачи

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

Разработка и настройка морфологического анализатора, работающего без лемматического словаря (на базе морфемного анализа и набора морфемно-морфологических соответствий).

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

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

Сборка блоков в единый программный комплекс.

Тестирование, сбор статистической информации.

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

1.8 Функциональные требования

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

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

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

В случае корректного ввода программа передает текст в блок морфологического анализа.

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

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

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

После построения дерева программа выводит его в виде набора зависимых слов для каждого слова введенного текста (предложения).

2. Конструкторская часть

2.1 Обоснование выбора алгоритмической и инструментальной базы

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

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

Алгоритм КМП. Алгоритм Кнута-Моррса-Пратта позволяет за линейное время находить подстроку в строке. Для этого сначала рассчитывается префикс-функция строки вида f_str = «морфема» + # + «слово». Таким образом, искомая морфема становится префиксом (началом) общей строки, но по-прежнему отделена от обрабатываемого слова. Префикс-функция определяется для каждого среза [0:i], где i [1:f_str.size()]. Она рассчитывает максимальную длину такого префикса, который также является суффиксом. Например, для среза «абв#ллабв» значением префикс-функции будет 3. Из этого примера также легко видеть необходимость в разделителе. Поскольку символ # не может входить в слово, значение префикс-функции заведомо не превысит длины искомой подстроки, что крайне важно для исключения ошибок. Данный алгоритм будет являться основой морфемного разбора слова, который, в свою очередь, обеспечит морфологический анализ.

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

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

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

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

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

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

Значительные трудности возникают при анализе слов с нулевым окончанием. Здесь стоит отойти от лингвистического понятия окончания и использовать, например, свойство существительных 3-го склонения оканчиваться на -ь. К сожалению, в контексте описываемого алгоритма ошибка в пользу неверно опознанных окончаний возрастет. Так, слово «мать», в соответствии с этим алгоритмом, будет однозначно считаться глаголом, так как окончание -ать имеет большую степень доверия, чем окончание -ь.

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

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

Следующим этапом проектирования стало применение не линейного, а рекурсивного алгоритма, схожего по структуре с DFS. Здесь учитываются уже не только окончания, но также суффиксы и приставки. Последние нужны не столько для получения конкретных данных, сколько для удаления из слова всех морфем, кроме корня. Вариантов разбора с помощью поиска подстроки (например, алгоритмом Кнута -- Морриса -- Пратта) может быть несколько. Поэтому для дополнительной проверки можно использовать базу корней. При нахождении соответствия выделенного корня с одним из корней базы можно сделать вывод о том, что данный вариант разбора с высокой вероятностью верен. Однако, ранее было принято решение в данной программе базу корней не использовать, так что это является, скорее, перспективой развития.

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

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

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

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

На выходе имеется массив объектов класса «слово», каждый из элементов которого знает свой набор выделенных суффиксов и окончаний, остаток от этого разбора (неразобранную часть слова) и ту словоформу, которая была изначально в тексте (слово до разбора).

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

Код формируется следующим образом:

[тип аффикса] + [часть речи] + [род / лицо] + [число] + [падеж / время].

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

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

Так, окончание -ю может принадлежать существительному 1 склонения в винительном падеже, существительному 2 склонения в дательном падеже и глаголу I или II спряжения. При этом анализируемое слово на деле может оказаться прилагательным женского рода в винительном падеже. Поэтому в базе для каждого спорного аффикса должны быть указаны все варианты. Зачастую неоднозначность пропадает при дальнейшем анализе, когда находятся новые аффиксы, подтверждающие или опровергающие тот или иной вариант. Также возможно повышение точности путем учитывания сочетаемости слов в предложении.

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

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

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

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

Каждой позиции символа в морфологическом коде соответствует набор допустимых символов. В случае если по данному параметру слово не имеет значения (например, глагол не может иметь падежа), значением соответствующей позиции является «*». Это важно для сохранения порядка позиций, также при сопряжении с морфологическим анализатором это позволит оставлять пустыми неопознанные параметры и использовать для улучшения качества анализа эвристический алгоритм. Возможные коды для каждого из параметров описаны в таблице 2.

Таблица 2. Коды параметров

Параметр	Значение	Описание
Часть речи	n	Существительное
	a	Прилагательное
	v	Глагол
	p	Предлог
	c	Союз
Род	m	Мужской
	f	Женский
	n	Средний
Лицо	1	Первое
	2	Второе
	3	Третье
	i	Инфинитив
Падеж	n	Именительный
	g	Родительный
	d	Дательный
	a	Винительный
	i	Творительный
	p	Предложный
Число	s	Единственное
	p	Множественное

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

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

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

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

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

2.4 Объединение морфологического и синтаксического анализаторов

Исходя из описанного выше, должен существовать метод, позволяющий передавать информацию от морфологического к синтаксическому модулю. Его базовая реализация, разработанная в рамках данной работы, представляет собой класс, способный принимать и передавать объекты класса «word», хранящие в себе информацию о каждом отдельном слове. Неразмеченное предложение может быть подано в синтаксический анализатор прямиком с потока ввода и не нуждается в промежуточном пункте связи. Подробнее про классы, представленные в рамках разрабатываемого ПО, ниже. Однако, как следует из описания алгоритма морфологического анализатора, для каждого отдельного слова может существовать набор морфологических гипотез. Одна из задач связующего элемента - отсев заведомо некорректных. Для этой цели могут применяться различные алгоритмы. В текущей версии происходит отсев пустых гипотез, все остальные передаются в синтаксический анализатор, причем за одну передачу проходит только один набор. Когда синтаксический модуль подтверждает завершение обработки набора, передается следующий. Таким образом, происходит перебор всех возможных комплектов гипотез.

3. Технологическая часть

3.1 Детали реализации разработанного метода

3.1.1 Класс «word»

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

Структура типа info хранит информацию об «очках», говорящих в пользу того или иного морфологического свойства. Очки набираются в соответствии с набором морфем и заранее заданной в морфемной таблице информации.

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

Аффиксы представляют собой структуру вида pair<string, string>, где первый элемент пары - сам аффикс, а второй - его морфологический код.

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

3.1.2 Класс «morph»

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

vector <pair<string, string>> table_suf, table_end, table_prep, table_conj;

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

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

3.1.3 Класс «substring»

Данный класс служит лишь для поиска подстроки в строке. Для этого используется алгоритм КМП, более подробно описанный выше. Выделение поиска подстроки в отдельный класс позволит при необходимости использовать другие поисковые алгоритмы, а также упростит понимание структуры кода.

3.1.4 Класс «sintax»

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

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

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

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

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

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

...