Синтаксический анализ в NLTK
Здравствуйте. Это статья об синтаксическом анализе предложений, их представлении. Для разбора предложений будет использоваться пакет NLTK и язык программирования Python (версии 2.7).
Вступление
В моей предыдущей статье мы рассматривали морфологические анализаторы и их использование. Настоятельно рекомендую прочитать её, чтобы лучше понять данную статью. Также там рассматривается установка и настройка пакета NLTK.
Приступим
Что такое синтаксический анализ? Синтаксический анализ – это процесс, который определяет, принадлежит ли некоторая последовательность лексем языку, порождаемому грамматикой. Обычно представляется в виде дерева для удобства понимания.
Рассмотрим некоторые грамматические особенности английского языка:
- Неограниченные возможности
Например, интересной особенностью предложений есть то, что они могут вкладываться в большие предложения. Рассмотрим следующие предложения:- Usain Bolt broke the 100m record
- The Jamaica Observer reported that Usain Bolt broke the 100m record
- Andre said The Jamaica Observer reported that Usain Bolt broke the 100m record
- I think Andre said the Jamaica Observer reported that Usain Bolt broke the 100m record
Если заменить предыдущие предложения на символ S, то следующие предложения строятся за шаблонами Andre said S, I think S. Эти шаблоны и другие подобные (например, S but S или S when S) позволяют на основе одного предложения строить больше предложений.
С помощью подобных шаблонов построено огромное предложение в сказке «Винни-Пух» (Winnie the Pooh story by A.A. Milne, In which Piglet is Entirely Surrounded by Water):
You can imagine Piglet’s joy when at last the ship came in sight of him.] In after-years he liked to think that he had been in Very Great Danger during the Terrible Flood, but the only danger he had really been in was the last half-hour of his imprisonment, when Owl, who had just flown up, sat on a branch of his tree to comfort him, and told him a very long story about an aunt who had once laid a seagull’s egg by mistake, and the story went on and on, rather like this sentence, until Piglet who was listening out of his window without much hope, went to sleep quietly and naturally, slipping slowly out of the window towards the water until he was only hanging on by his toes, at which moment, luckily, a sudden loud squawk from Owl, which was really part of the story, being what his aunt said, woke the Piglet up and just gave him time to jerk himself back into safety and say, «How interesting, and did she?» when — well, you can imagine his joy when at last he saw the good ship, Brain of Pooh (Captain, C. Robin; 1st Mate, P. Bear) coming over the sea to rescue him.
While hunting in Africa, I shot an elephant in my pajamas. How an elephant got into my pajamas I’ll never know.
Двусмысленность можно рассмотреть с помощью программы. Подробно рассмотрим процесс создания грамматики и построения дерева немного ниже по статье. Сейчас просто посмотрим пример неоднозначности.
Сначала определим простую грамматику и построим дерево:
>>> grammar = nltk.parse_cfg(""" S -> NP VP PP -> P NP NP -> Det N | Det N PP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' N -> 'elephant' | 'pajamas' V -> 'shot' P -> 'in' """) >>> sent = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas'] >>> parser = nltk.ChartParser(grammar) >>> trees = parser.nbest_parse(sent) >>> for tree in trees: print tree (S (NP I) (VP (V shot) (NP (Det an) (N elephant) (PP (P in) (NP (Det my) (N pajamas)))))) (S (NP I) (VP (VP (V shot) (NP (Det an) (N elephant))) (PP (P in) (NP (Det my) (N pajamas))))) Контекстно-свободная грамматика
- Простая грамматика
Рассмотрим простейшую контекстно-свободную грамматику. Согласно определению, первым символом слева в первом правиле грамматики есть специальный символ S и все деревья должны иметь этот символ как корень.
В следующем листинге приводится пример определения грамматики и использование его для анализа предложения «Mary saw Bob»:
>>> grammar1 = nltk.parse_cfg(""" S -> NP VP VP -> V NP | V NP PP PP -> P NP V -> "saw" | "ate" | "walked" NP -> "John" | "Mary" | "Bob" | Det N | Det N PP Det -> "a" | "an" | "the" | "my" N -> "man" | "dog" | "cat" | "telescope" | "park" P -> "in" | "on" | "by" | "with" """) >>> sent = "Mary saw Bob".split() >>> rd_parser = nltk.RecursiveDescentParser(grammar1) >>> for tree in rd_parser.nbest_parse(sent): print tree (S (NP Mary) (VP (V saw) (NP Bob))) grammar2 = nltk.parse_cfg(""" S -> NP VP NP -> Det Nom | PropN Nom -> Adj Nom | N VP -> V Adj | V NP | V S | V NP PP PP -> P NP PropN -> 'Buster' | 'Chatterer' | 'Joe' Det -> 'the' | 'a' N -> 'bear' | 'squirrel' | 'tree' | 'fish' | 'log' Adj -> 'angry' | 'frightened' | 'little' | 'tall' V -> 'chased' | 'saw' | 'said' | 'thought' | 'was' | 'put' P -> 'on' """) Синтаксический анализ на основе контекстно-свободной грамматики
Синтаксический анализатор – это программа, которая обрабатывает входное предложение согласно правилам грамматики и строит одну или несколько синтаксических структур, которые отвечают этой грамматике.
Мы рассмотрим два простых алгоритма синтаксического анализа: алгоритм рекурсивного спуска (стратегия «сверху-вниз») и алгоритм перемещения-сворачивания (стратегия «снизу-вверх»).
Рассмотрим каждый подробнее:
- Алгоритм рекурсивного спуска.
Простейший алгоритм анализатора, интерпретирующий грамматику, как спецификацию для превращения элемента высшего уровня не несколько элементов уровня ниже. Например: задача – найти элемент S. Правило S -> NP VP позволяет анализатору заменить этот элемент на два других (сначала найти NP, потом VP). Каждый из этих элементов может быть преобразован в другие элементы на основе правил грамматики. Такой процесс будет продолжаться до тех пор, пока не будет поставлена задача заменить элемент на слово, например telescope. Тогда происходит сравнение этого слова со словом из входной последовательности и если устанавливается соответствие между этими словами, то алгоритм продолжает работу. Если нет, то анализатор возвращается на шаг назад и пытается рассмотреть другие варианты.
Алгоритм рекурсивного спуска осуществляется методом
nltk.RecursiveDescentParser(grammar)Этот метод может иметь ещё необязательный параметр trace. Если значение этого параметра больше нуля, то анализатор будет выводить на экран результаты всех шагов синтаксического анализа.
Давайте рассмотрим его работу. Будем разбирать предложение «Mary saw a dog». Сначала определим грамматику, а потом воспользуемся методом:
>>> import nltk >>> grammar = nltk.parse_cfg(""" S -> NP VP VP -> V NP | V NP PP PP -> P NP V -> "saw" | "ate" | "walked" NP -> "John" | "Mary" | "Bob" | Det N | Det N PP Det -> "a" | "an" | "the" | "my" N -> "man" | "dog" | "cat" | "telescope" | "park" P -> "in" | "on" | "by" | "with" """) >>> rd_parser = nltk.RecursiveDescentParser(grammar) >>> sent = 'Mary saw a dog'.split() >>> for t in rd_parser.nbest_parse(sent): print t (S (NP Mary) (VP (V saw) (NP (Det a) (N dog)))) Испытаем метод с определенным параметром trace=2. Полный вывод будет спрятан под спойлер, ибо сильно длинный:
>>> rd_parser = nltk.RecursiveDescentParser(grammar, trace=2) >>> sent = 'Mary saw a dog'.split() >>> for t in rd_parser.nbest_parse(sent): print t Parsing 'Mary saw a dog' [ * S ] E [ * NP VP ] E [ * 'John' VP ] E [ * 'Mary' VP ] M [ 'Mary' * VP ] E [ 'Mary' * V NP ] E [ 'Mary' * 'saw' NP ] M [ 'Mary' 'saw' * NP ] E [ 'Mary' 'saw' * 'John' ] E [ 'Mary' 'saw' * 'Mary' ] E [ 'Mary' 'saw' * 'Bob' ] E [ 'Mary' 'saw' * Det N ] E [ 'Mary' 'saw' * 'a' N ] M [ 'Mary' 'saw' 'a' * N ] E [ 'Mary' 'saw' 'a' * 'man' ] E [ 'Mary' 'saw' 'a' * 'dog' ] M [ 'Mary' 'saw' 'a' 'dog' ] + [ 'Mary' 'saw' 'a' 'dog' ] E [ 'Mary' 'saw' 'a' * 'cat' ] E [ 'Mary' 'saw' 'a' * 'telescope' ] E [ 'Mary' 'saw' 'a' * 'park' ] E [ 'Mary' 'saw' * 'an' N ] E [ 'Mary' 'saw' * 'the' N ] E [ 'Mary' 'saw' * 'my' N ] E [ 'Mary' 'saw' * Det N PP ] E [ 'Mary' 'saw' * 'a' N PP ] M [ 'Mary' 'saw' 'a' * N PP ] E [ 'Mary' 'saw' 'a' * 'man' PP ] E [ 'Mary' 'saw' 'a' * 'dog' PP ] M [ 'Mary' 'saw' 'a' 'dog' * PP ] E [ 'Mary' 'saw' 'a' 'dog' * P NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'in' NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'on' NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'by' NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'with' NP ] E [ 'Mary' 'saw' 'a' * 'cat' PP ] E [ 'Mary' 'saw' 'a' * 'telescope' PP ] E [ 'Mary' 'saw' 'a' * 'park' PP ] E [ 'Mary' 'saw' * 'an' N PP ] E [ 'Mary' 'saw' * 'the' N PP ] E [ 'Mary' 'saw' * 'my' N PP ] E [ 'Mary' * 'ate' NP ] E [ 'Mary' * 'walked' NP ] E [ 'Mary' * V NP PP ] E [ 'Mary' * 'saw' NP PP ] M [ 'Mary' 'saw' * NP PP ] E [ 'Mary' 'saw' * 'John' PP ] E [ 'Mary' 'saw' * 'Mary' PP ] E [ 'Mary' 'saw' * 'Bob' PP ] E [ 'Mary' 'saw' * Det N PP ] E [ 'Mary' 'saw' * 'a' N PP ] M [ 'Mary' 'saw' 'a' * N PP ] E [ 'Mary' 'saw' 'a' * 'man' PP ] E [ 'Mary' 'saw' 'a' * 'dog' PP ] M [ 'Mary' 'saw' 'a' 'dog' * PP ] E [ 'Mary' 'saw' 'a' 'dog' * P NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'in' NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'on' NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'by' NP ] E [ 'Mary' 'saw' 'a' 'dog' * 'with' NP ] E [ 'Mary' 'saw' 'a' * 'cat' PP ] E [ 'Mary' 'saw' 'a' * 'telescope' PP ] E [ 'Mary' 'saw' 'a' * 'park' PP ] E [ 'Mary' 'saw' * 'an' N PP ] E [ 'Mary' 'saw' * 'the' N PP ] E [ 'Mary' 'saw' * 'my' N PP ] E [ 'Mary' 'saw' * Det N PP PP ] E [ 'Mary' 'saw' * 'a' N PP PP ] M [ 'Mary' 'saw' 'a' * N PP PP ] E [ 'Mary' 'saw' 'a' * 'man' PP PP ] E [ 'Mary' 'saw' 'a' * 'dog' PP PP ] M [ 'Mary' 'saw' 'a' 'dog' * PP PP ] E [ 'Mary' 'saw' 'a' 'dog' * P NP PP ] E [ 'Mary' 'saw' 'a' 'dog' * 'in' NP PP ] E [ 'Mary' 'saw' 'a' 'dog' * 'on' NP PP ] E [ 'Mary' 'saw' 'a' 'dog' * 'by' NP PP ] E [ 'Mary' 'saw' 'a' 'dog' * 'with' NP PP ] E [ 'Mary' 'saw' 'a' * 'cat' PP PP ] E [ 'Mary' 'saw' 'a' * 'telescope' PP PP ] E [ 'Mary' 'saw' 'a' * 'park' PP PP ] E [ 'Mary' 'saw' * 'an' N PP PP ] E [ 'Mary' 'saw' * 'the' N PP PP ] E [ 'Mary' 'saw' * 'my' N PP PP ] E [ 'Mary' * 'ate' NP PP ] E [ 'Mary' * 'walked' NP PP ] E [ * 'Bob' VP ] E [ * Det N VP ] E [ * 'a' N VP ] E [ * 'an' N VP ] E [ * 'the' N VP ] E [ * 'my' N VP ] E [ * Det N PP VP ] E [ * 'a' N PP VP ] E [ * 'an' N PP VP ] E [ * 'the' N PP VP ] E [ * 'my' N PP VP ] (S (NP Mary) (VP (V saw) (NP (Det a) (N dog)))) >>> Анализатор рекурсивного спуска имеет три существенных недостатка:
- леворекурсивные правила вида NP -> NP PP приводят к бесконечному циклу;
- при анализе, много времени уходит на рассмотрение слов и структур, которые не соответствуют входному предложению (это видно в листинге с использованием параметра trace=2);
- процесс перебора с возвращением отбрасывает проанализированные составляющие, а потом снова обязан их строить.
В NLTK алгоритм перемещения-сворачивания реализован в методе
nltk.ShiftReduceParser(grammar)Давайте сразу же проверим его на знакомом предложении «Mary saw a dog» (грамматику будем использовать тоже из предыдущего примера):
>>> sr_parse = nltk.ShiftReduceParser(grammar) >>> sent = 'Mary saw a dog'.split() >>> print sr_parse.parse(sent) (S (NP Mary) (VP (V saw) (NP (Det a) (N dog)))) Анализатор перемещения-сворачивания может попадать в тупики, что не позволит получить любые результаты анализа, даже, если входное предложение не противоречит грамматике. Если такое происходит, то нету уже входных слов и стек содержит элементы, которые нельзя свернуть к S. Эти проблемы возникают в результате действий на предыдущих шагах.
Вывод
В данной статье мы рассмотрели синтаксический анализ предложений с помощью пакета NLTK. Также рассмотрели два алгоритма для синтаксического анализа: алгоритм перемещения-сворачивания и алгоритм рекурсивного спуска.
Спасибо за внимание.