Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
Буштедт В. Поляков В.
(Национальный исследовательский технологический университет «МИ-СиС»)
БЛОЧНЫЙ АЛГОРИТМ ДЛЯ СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА С ИСПОЛЬЗОВАНИЕМ РАСШИРЕННОЙ НОТАЦИИ1
В данной работе описывается расширенная математическая постановка задачи, включающая нотацию для блочного алгоритма синтаксического анализатора, которая существенно расширяет возможности алгоритма чанкинга и демонстрирует универсальный характер разрабатываемой модели. Часть эвристик, направленных на сокращение количества ложно выделенных чанков, разработанных в предыдущих работах претерпевают изменения при введении расширенной нотации синтаксического анализатора. Метод поиска чанков с применением эвристик получил название «Right-Chunk 4». Сделана формальная постановка задачи. Выполнена компьютерная реализация метода поиска чанков, результатом которой является программный комплекс «Chunk-Creator 4». Проведена оценка качества работы.
Ключевые слова: компьютерная лингвистика, парсинг, синтаксический анализ, чанкинг, искусственный интеллект, блочный алгоритм, расширенная нотация синтаксического анализа.
A BLOCK ALGORITHM FOR PARSER USING EXPANDED NOTATION
This paper describes an extended mathematical formulation, which includes a notation for the block parser algorithm, which significantly expands the capabilities of the algorithm of the chunkig and demonstrates the universality of the developed model. Part of heuristics aimed at reducing the number of falsely identified chunks, developed in previous work are changing with the introduction of the expanded notation parser. Search method chunks using heuristics called "Right-Chunk 4". Made a formal description of the problem. Computer realization of the search method chunks, a software package "Chunk-Creator 4", was implemented. The evaluation of the quality of its work was done.
Keywords: ^mputational linguistics, parsing, chunking, block algorithm, the extended notation parsing.
Введение
Задача синтаксического анализа является одной из сложных задач компьютерной лингвистики. Исследования в этой области начались еще в 1960х годах. Были созданы различные системы [1, 2, 3, 10], которые позволяли проводить синтаксический анализ предложений на естественном языке. Эти разработки существенно продвинули теорию и практику синтаксического анализа, однако, полученные программные реализации не достигали стопроцентной точности анализа. Большинство современных синтаксических анализаторов выполнены как «черные ящики», когда на вход подается предложение, а на выходе получается синтаксическое дерево. Это существенно затрудняет процесс их тестирования.
Нами было принято решение о проведении исследований, связанных с работой частичного синтаксического анализа, так называемого «Чанкера» (от англ. слова «chunk» - глыба, ломоть - то есть нечто грубое и общее, в смысле частичного синтаксического анализа по срав-
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант №9-07-97007-р-поволжье_а).
нению с полным). Преимущества данного подхода заключаются в том, что для описания процесса синтаксического анализа требуется минимум грамматических правил и словарей. Кроме того, блочный алгоритм делает прозрачными все этапы синтаксического анализа, дает возможность учета вклада каждого блока (этапа) и в перспективе позволяет проводить постепенные улучшения отдельных этапов. При синтаксическом анализе текста на естественном языке основной проблемой является разрешение неоднозначностей.
Формальная постановка задачи
В нашем исследовании задача чанкинга решается в ограниченном масштабе, так как мы выявляем чанки только с именами существительными (ИС). Это мотивировано дальнейшим использованием результатов чанкинга для построения лексико-синтаксических портретов существительных [9], которые далее используются для разрешения многозначности ИС.
В работе [9] нами выполнена формальная постановка решения задачи частичного синтаксического анализа с использованием упрощенной нотации и предложено ее математическое описание в теоретико-множественной форме записи. Для выявления чанков сформулированы простые условия проверки, которые задают известные из грамматики русского языка синтаксические правила согласования и подчинения. Предложенная в [9] нотация описывают большинство словосочетаний в русском языке. В работе [9] предлагается тринадцать эвристик, направленных на уменьшение количества ложно выявленных чанков и, следовательно, повышающих качество работы частичного синтаксического анализатора. Однако существует ряд грамматических конструкций, которые не могут быть описаны предложенной структурой чанка. Например, условия в [9] не описывают словосочетания, в которых присутствуют наречия, частицы же, бы, не, ни, однородные члены, составные глаголы.
Структурная схема работы блочного алгоритма для проведения синтаксического анализа приведена в таблице 1.
Таблица 1
Этапы блочного алгоритма синтаксического анализатора
Номер этапа Наименование
1 Вход
2 Фильтр ограничения расстояния от опорного (главного) до зависимого слова
3 Правила формирования чанков (фильтры, основанные на правилах грамматической сочетаемости /согласования и подчинения/ в русском языке
4 Эвристики класса А (фильтры, основанные на правилах непротиворечивости; должны применяться на этапе построения набора чанков)
5 Эвристики класса В (фильтры, основанные на правилах уникальности главных членов предложения)
6 Эвристики класса С (фильтры, основанные на правилах построения дерева синтаксического подчинения)
7 Ролевые фильтры
8 Контекстные фильтры
9 Выход
В настоящей работе рассматриваются применение всех блоков из приведенного алгоритма за исключением ролевых и контекстных фильтров. Кроме того, предложена расширенная нотация, направленная на устранение указанных ограничений.
Расширенная нотация для работы синтаксического анализатора
Для получения более полных результатов анализа предложения возможно использовать расширенную нотацию для работы синтаксического анализатора. Фактически нами предлагается решение, в котором можно путем модификации нотации правил и небольшой модернизации алгоритма чанкинга учитывать следующие явления в русском языке:
• Сослагательное наклонение у глаголов, возникающее в русском языке при использовании указателя сослагательного наклонения - частицы «бы»;
• Присутствие отрицания в предложении на основе исследования наличия отрицательных частицы «не/ни», которые могут быть перед существительным, прилагательным, причастием, глаголом, деепричастием и наречием;
• Присутствие предлога как падежной характеристики существительного;
• Наличие союзов «и/или» в предложении с однородными членами;
• Наличие составных глаголов в предложении.
Для этой цели используются так называемые модификаторы, которые данные явления представляют как способы модификации базовой грамматической характеристики слова. Необходимость применения такого подхода возникла вследствие того, что в русском языке одна часть грамматических характеристик передаются морфологическими, а другая часть -лексическими средствами. Например, при нахождении частицы «бы» в предложении, наклонение глагола, стоящего перед или после этой частицы, меняется на сослагательное и слово «бы» исключается из дальнейшего рассмотрения. При обнаружении частиц «не/ни», которые являются одним из видов семантических модификаторов, для слова, следующего за этой частицей, в кортеж грамматических характеристик добавляется помета о том, что это слово употребляется в данном случае с отрицанием. А сама частица как слово исключается из дальнейшего рассмотрения. Предлог в этом случае станет выступать как дополнительная падежная характеристика существительных. То есть для каждого существительного к имеющимся морфологическим характеристикам будет добавлена еще одна, определяющая, стоит ли перед данным существительным предлог и какой он. Предлог как слово при дальнейшем анализе исключается из рассмотрения. В случае с однородными членами будет использоваться составной элемент чанка, когда несколько чанков, в составе которых меняются только однородные члены, будут объединены в один чанк, где будет присутствовать группа объединенных элементов. Составные глаголы (начинать делать, заставлять учиться и т. д.) в расширенной нотации также будут объединяться в составные элементы чанков. Для этого будет использоваться очередная дополнительная характеристика. Каждое слово из каждой группы составных глаголов по отдельности не рассматривается при дальнейшем анализе. Введение расширенной нотации приводит к усложнению алгоритма анализа, но одновременно позволяет сделать набор эвристик более простым и универсальным. Фактически данная расширенная нотация предполагает введение после морфологического анализа дополнительного этапа предсинтаксического анализа для выявления модификаторов.
Выводы
Чанкинг, как модель частичного синтаксического анализа, позволяет выявлять мелкие синтаксические конструкции (чанки), которые затем могут использоваться для улучшения качества поиска в тексте. Блочный алгоритм позволяет сделать этапы синтаксического анализа более прозрачными, обеспечивая шаг за шагом их оценку и улучшение. Это актуально, так как многолетний опыт создания синтаксических анализаторов по модели «черного ящика» [1, 10] не позволил добиться стопроцентной точности анализа. Расширенная нотация по-
зволяет учесть некоторые элементы русского синтаксиса в простой и изящной манере путем
введения модификаторов базовой грамматической характеристики слова. Будущие исследования планируется направить на создание ролевых и контекстных фильтров.
ЛИТЕРАТУРА
1. Богуславский И.М., Валеев Д.Р., Иомдин Л.Л., Сизов В.Г. Синтаксический анализатор системы ЭТАП и его оценка с помощью глубоко размеченного корпуса русских текстов // Труды Международной конференции «Корпусная лингвистика - 2008». СПб.: Санкт-Петербургский государственный университет, 2008.
2. Попов Э.В. Общение с ЭВМ на естестве
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.