Синтаксический разбор предложения русского языка

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

Обработка естественного языка — общее направление искусственного интеллекта и математической лингвистики. Оно изучает проблемы компьютерного анализа и синтеза естественных языков.

В общем, процесс анализа предложения естественного языка выглядит следующим образом: (1) разбиение предложения на синтаксические единицы — слова и словосочетания; (2) определение грамматических параметров каждой единицы; (3) определение синтаксической связи между единицами. На выходе — абстрактное дерево разбора.

1. Разбиение предложения на синтаксические единицы


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

Например,

 Парадигма слова "рука": [рука, руки, руке, руку, рукой, о руке] 

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

Каждое слово в предложении определяется тройкой:

  1. строка словоформы/словосочетания («писал»)
  2. нормальная форма слова («писать»)
  3. набор грамматических параметров ( ['VERB', 'sing', 'musc', 'tran', 'past'] )

Таким образом, разбиение предложения "Ясно дело, он не придет на встречу" будет иметь следующий вид:

['Ясно дело', 'он', 'не', 'придет', 'на', 'встречу']
здесь 'ясно дело' - устойчивое выражение, неизменяемое 

2. Определение грамматических параметров (граммем)


Граммемой называется элемент грамматической категории; различные граммемы одной категории исключают друг друга и не могут быть выражены вместе. Для каждой словоформы определяем набор из семи граммем:

[ ЧАСТЬ РЕЧИ, ЧИСЛО, ЛИЦО, РОД, ПАДЕЖ, ВАЛЕНТНОСТЬ, ВРЕМЯ ]

В качестве источника будем использовать словарь OpenCorpora и интерфейс к нему - pymorphy2. Для поиска правила в грамматике по данному набору граммем будем представлять их в общем виде:

  'яблоки' [NOUN,plur,neut,accs] -> [NOUN,?numb,?per,?gend,accs,None,None] 
здесь '?' означает, что параметр может принимать произвольное значение 

3. Определение синтаксической связи между словами


Для определения синтаксической связи между словами будем использовать контекстно-свободную грамматику и LR-анализ.

Грамматика и LR-анализ


Формальная грамматика — способ описания языка в виде так называемых продукций. Например:

a -> ab | ac

означает, что правило 'a' порождает 'ab' ИЛИ 'ac'.

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

Для описания русского языка будем использовать теорию грамматики составляющих (phrase structure grammar), которая утверждает что всякая сложная грамматическая единица складывается из двух более простых и не пересекающихся единиц, называемых её непосредственными составляющими. Выделяют следующие составляющие:

(1) Именная группа (NP)

NP[case='nomn'] -> N[case='nomn'] | ADJ[case='nomn'] NP[case='nomn'] | …

То есть номинативная именная группа — это существительное в номинативном падеже ИЛИ прилагательное в номинативном падеже + номинативная именная группа ИЛИ другое.

(2) Глагольная группа (VP)

VP[tran] -> V[tran] NP[case='ablt'] | ADJ VP[tran] | …

Другими словами, транзитивная глагольная группа — это транзитивный глагол + аблативная именная группа ИЛИ краткое прилагательное + транзитивная глагольная группа ИЛИ другое.

(3) Предложная группа (PP)

 PP -> PREP NP[case='datv'] | ... 

Предложная группа — это предлог + именная дативная группа ИЛИ другое.

(4) Полное предложение (S)

S -> NP[case='nomn'] VP[tran]

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

  def agreement(self, node_left, node_right):
                       
                       ...
                       if (numb1 and numb2): 
				if (numb1 != numb2): return False;
			if (per1 and per2):
				if (per1 != per2): return False;
			if (gend1 and gend2):
				if (gend1 != gend2): return False;
		return True;

Неполным предложением называется такое предложение, где опущена именная часть. Как правило, в таких предложениях глагольная группа выражена безличным глаголом. Например, "Мне хочется гулять", "Светает". Эллептическим предложением называется предложение, где опущена глагольная часть, она заменяется знаком тире. Например, "За спиной – лес. Справа и слева – болота".

Для того, чтобы определить принадлежность данного предложения к языку грамматики будем использовать алгоритм LR-анализа. Данный алгоритм предполагает построение дерева разбора снизу вверх (от листьев к корню). Ключевым элементов алгоритма является метод «переноса-свертки» (англ. shift-reduce):

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

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

Дерево

Для представления синтаксической связи в предложении используется бинарное дерево, где листья — это слова (терминалы) с набором граммем, а узлы — правила (претерминалы). Корнем является предложение (нетерминал).

Узел дерева определяется следующим образом:

class Node:
	def __init__(self, word=None, tag=None, grammemes=None, leaf=False):
		self.word = word; # строка слова
		self.tag = tag; # здесь тэг - претерминал, 
который соотвествует промежуточному правилу грамматики  
		self.grammemes = grammemes; # набор граммем
		self.leaf = leaf;
		self.l = None;
		self.r = None;
		self.p = None;


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

	def build(self, sent):
		for word in sent:
			new_node = Node(word[0], word[1], word[2], leaf=True)
			self.nodes.append(new_node)

Далее осуществляется LR-анализ. Каждой свертке соответствует объединение двух узлов или листьев под общим предком. Узлу предка присваивается тэг-претерминал, который соответствует правилу грамматики, кроме того предок принимает граммемы главного члена группы, например, в глагольной группе V[tran] PRCL (e.g. «хотел бы») признаки будут приняты от транзитивного глагола V[tran], а не от частицы PRCL; а в именной группе NP[case='nomn'] NP[case='gent'] (e.g.«отец детей») признаки будут приняты от существительного в номинативе.

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

	def reduce(self):
		self.reduce_ADJ() # прилагательные
		self.reduce_NP() # именные группы
		self.reduce_PP() # предложные
		self.reduce_VP() # глагольные
		self.reduce_S() # полные и неполные предложения

Такой порядок важен, так как исключает возможность «упустить» некоторые члены предложения. Сначала формируются прилагательные вместе с модификаторами (e.g. безумно красивый), затем именные группы, предложные и наконец глагольные. После этого идет поиск полных/неполных предложений, если таковые отсутствуют, то дерево не имеет корня, а значит и предложение не принадлежит языку грамматики.

Рассмотрим условный пример построение дерева:

sent = "Я пишу письмо старому другу"
def build(self, sent):
		for word in sent:
			new_node = Node(word[0], word[1], word[2], leaf=True)
			self.nodes.append(new_node)



NP[case='nomn'] -> NPRO[case='nomn']
NP[case='accs'] -> N[case='accs']
NP[case='datv'] -> ADJ[case='datv'] NP[case='datv']



VP[tran] -> V[tran] NP[case='accs'] 



VP[tran] -> VP[tran] NP[case='datv'] 



S -> NP[case='nomn']  VP[tran]



Конкретный пример разбора двусоставного предложения:

import analyzer
parser = analyzer.Parser()
sent = "Пустыня внемлет богу, и звезда с звездою говорит."
t = parser.parse(sent)
t[0].display()
S
       NP[case='nomn'] 
           Пустыня ['NOUN', 'sing', 'femn', 'nomn']
   VP[tran]
           VP[tran] 
                 внемлет ['VERB', 'sing', '3per', 'tran', 'pres']
           NP[case='datv'] 
                 богу ['NOUN', 'sing', 'datv']
S
       NP[case='nomn'] 
           звезда ['NOUN', 'sing', 'femn', 'nomn']
   VP[tran]
     PP
               PREP 
                       с ['PREP']
               NP[case='ablt'] 
                       звездою ['NOUN', 'sing', 'femn', 'ablt']
           VP[tran] 
                 говорит ['VERB', 'sing', '3per', 'tran', 'pres']

Проблемы


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

  1. Раскрытие анафор. Живой человек понимает анафору исходя из здравого смысла и контекста, а для компьютера это, очевидно, не всегда просто.
  2. Омонимия — совпадение в звучании и написании языковых единиц, значения которых не связаны друг с другом. Один из способ решения — вероятностные методы. В предложении "Я знаю это хорошо" вероятность того, что "это" является местоимением, а не частицей будет больше. Для таких методов требуется достаточный большой корпус.
  3. Свободный порядок слов приводит к тому, что толкование предложения может быть неоднозначным. Например, «Бытие определяет сознание» — что определяет что? В русском языке свободный порядок слов компенсируется развитой морфологией, служебными словами и знаками препинания, но в большинстве случаев для компьютера это представляет дополнительную проблему.
  4. Не все люди пишут грамотно. В сети люди склоны использовать сокращения, неологизмы, эллипсы и другие вещи, которые могут противоречить литературной норме. Из-за этого использование контекстно-свободных грамматик и словарей не всегда возможно.

Заключение


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

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 19

    +4
    Стоит только ввести неоднозначность какое слово относится к какой фразе (что человек разрешает по смыслу) и эти грамматики перестают работать в любом языке.
      0
      Можно доработать и будет работать и с такими
        0
        надо правила вплоть до значений каждого слова, то есть кибернетическую обьектную модель common sence.
          +1
          Можно сделать общие правила и при тестировании уже доделывать, выхватывая неправильно разобранные
            0
            Можно сделать общие правила

            согласен только их изначально будет не 1000 и даже не 10к а несколько больше
              0
              Не думаю, что при более 10к вариации 1 человек справится. И тем более один может и не сможет вспомнить/придумать столько вариаций
    • UFO just landed and posted this here
      +1
      Проект доступен для использования и редактирования.


      Я не смог найти в проекте упоминание о лицензиях под которыми этот проект. ИМХО, но без хоть какой-то лицензии проект очень опасно использовать и тем более редактировать.
        +1
        Лицензия добавлена — MIT.
        +1
        Я правильно понял, что вы пытаетесь написать парсер (даже не токенизатор, а именно синтаксический анализатор) натурального языка (уровень 0 иерархии Хомского), используя LR-парсер на основе контекстно-свободной грамматики (уровень 2 иерархии Хомского)?

        Один уже спрашивал на StackOverflow, как подобное провернуть (правда, там был парсер на 3 уровне против языка 2 уровня, но суть та же): RegEx match op̕en͟ ̀t̀ags e҉x̵c̴̷e̶p̷t ͠X̶͢H̷̕͟T͡M̵L̕͝ ̶̷́s̨̕͜͜e̸̶l͘͘͟f̴-̧́ç͜o̵̧͢҉̨n͘͟͞t͜á͏ì̴͡n͝͏̷e̴͜ḑ ҉͢͝t̨̀a͞g͘͘s̶̨͘͟
        Осторожно, после неаккуратного прочтения ответа, можете открыть портал в ад.
          0
          Все-равно современное NLP похоже на поиск под фонарем: ищем там, где светло, а не там, где потеряли. Совершенно же очевидно, что человеческое понимание текстов способно придать смысл любому тексту, так один мой хороший знакомый «переводил» выражение «мэни таймз» как «время — деньги». ))

          Если мы вслушаемся в себя и попытаемся понять как мы понимаем речь и ЕЯ тексты, то окажется, что сначала возникает смысл, а уже потом его раскладывание в синтаксис. ПМСМ.
            0
            На самом деле, мы одновременно выделяем смысл, синтаксис и привычные конструкции. Можно считать, что у нас происходит итерационное улучшение понимания текста, когда мы по несколько кругов проходим одни и те стадии и улучшаем результат.

            И ИМХО, современное NLP бывает разным, скорее всего, действительно качественные NLP модели очень редко становятся общедоступными даже в виде публичного api, вроде гугл транслейта, поэтому сложно говорить о уровне самых совершенных закрытых NLP систем.
              0
              Да, конечно, одновременно. Просто есть сомнения, что тот «глубинный» синтаксис, которым пользуется мозг, совпадает с «академическим» синтаксисом, который используется в парсинге. Тут существует простая проверка: взять достаточно сложное предложение и разложить его в «академический» синтаксис — это, часто, не самая простая задача, особенно, если мы анализируем речь, а не литературный язык.
                0
                Просто для реальных задач не нужно использовать «академический» синтаксис, он имеет смысл для задачи разбора книги Пушкина, которая многократно вычитывалась и исправлялась редакторами. Тогда и человек разбирает «академически».

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

          Главная трудность в обработке естественного языка — многозначность, которая проявляется чаще, чем мы способны формализовать. Синтаксический анализ сейчас обычно делается при помощи машинного обучения, см. старый обзор от Choi et al. (2015).


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

            +1

            С проектом Spacy-ru не сравнивали?

              0
              Есть какая-то оценка того, что получилось? Какой-то скор (UAS/LAS) на синтагрусе, например? Очень не хватает понимания потенциала качества правилового подхода, честно говоря.

              В проекте Universal Dependencies давно доступна куча скоров, например

              Only users with full accounts can post comments. Log in, please.