Здравствуйте. Это небольшое продолжение предыдущей статьи, где рассматривались основы синтаксического анализа с помощью пакета Natural Language Toolkit (сокращенно, NLTK). Как и в прошлой статье, в этой я буду сопровождать примеры кодом на языке Python (версии 2.7).

Вступление

В предыдущей статье мы рассматривали синтаксические анализаторы и виды грамматик. Настоятельно рекомендую её прочитать, если Вы этого не сделали. Также можно почитать первую статью, где мы устанавливаем и настраиваем пакет NLTK.

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

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

Динамическое программирование позволяет при синтаксическом анализе предложения "I shot an elephant in my pajamas", которое, мы, кстати, уже рассматривали, строить "PP in my pajamas" всего один раз. Результат сохраняется в специальную таблицу WFST (well-formed substring table или же «таблица закономерностей подстрочек») и с этой же таблицы можно брать при необходимости составляющие для построения NP или VP.

Приступим

Well-Formed Substring Tables

Рассмотрим предложение «I shot an elephant in my pajamas» как входные данные. Данное предложение можно представить в виде, который показан на рисунке. Такая структура называется Chart Data Structure.

В WFST записываются позиции слов путем заполнения ячеек треугольной матрицы, в которой по вертикали записываются начальные позиции подстрок, а по горизонтали – конечные позиции (таким образом, слову shot будет отвечать клетка с координатами (1, 2)). Для упрощения такого представления, допускается, что каждому слову соответствует только одна уникальная лексическая категория (тег морфологических характеристик) и именно она хранится в ячейке матрицы (например, в ячейке (1, 2) содержится V).

Тег для слова shot из списка text можно найти на основе грамматики:

>>> 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'
 """)
>>> text = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas']
>>> grammar.productions(rhs=text[1])
[V -> 'shot']

Для построения WFST создается матрица размерностью (n-1) на (n-1). В Python матрица строиться как список списков. В следующем листинге мы создадим несколько методов для построения, заполнения и отображения таблицы WFST. С помощью метода init_wfst() заполняется только главная диагональ, где присутствуют теги всех слов предложения. Метод display() создан для отображения результатов на экран в удобно читаемом виде.

def init_wfst(tokens, grammar):
    numtokens = len(tokens)
    wfst = [[None for i in range(numtokens+1)] for j in range(numtokens+1)]
    for i in range(numtokens):
        productions = grammar.productions(rhs=tokens[i])
        wfst[i][i+1] = productions[0].lhs()
    return wfst

def display(wfst, tokens):
    print '\nWFST ' + ' '.join([("%-4d" % i) for i in range(1, len(wfst))])
    for i in range(len(wfst)-1):
        print "%d   " % i,
        for j in range(1, len(wfst)):
            print "%-4s" % (wfst[i][j] or '.'),
        print

Сразу же и проверим работу методов. Кстати, будем использовать грамматику, описанную в предыдущем примере.

>>> tokens = "I shot an elephant in my pajamas".split()
>>> wfst0 = init_wfst(tokens, grammar)
>>> display(wfst0, tokens)

WFST 1    2    3    4    5    6    7   
0    NP   .    .    .    .    .    .   
1    .    V    .    .    .    .    .   
2    .    .    Det  .    .    .    .   
3    .    .    .    N    .    .    .   
4    .    .    .    .    P    .    .   
5    .    .    .    .    .    Det  .   
6    .    .    .    .    .    .    N

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

def complete_wfst(wfst, tokens, grammar, trace=False):
    index = dict((p.rhs(), p.lhs()) for p in grammar.productions())
    numtokens = len(tokens)
    for span in range(2, numtokens+1):
        for start in range(numtokens+1-span):
            end = start + span
            for mid in range(start+1, end):
                nt1, nt2 = wfst[start][mid], wfst[mid][end]
                if nt1 and nt2 and (nt1,nt2) in index:
                    wfst[start][end] = index[(nt1,nt2)]
                    if trace:
                        print "[%s] %3s [%s] %3s [%s] ==> [%s] %3s [%s]" % \
                        (start, nt1, mid, nt2, end, start, index[(nt1,nt2)], end)
    return wfst

Проверим работу:

>>> wfst1 = complete_wfst(wfst0, tokens, grammar)
>>> display(wfst1, tokens)

WFST 1    2    3    4    5    6    7   
0    NP   .    .    S    .    .    S   
1    .    V    .    VP   .    .    VP  
2    .    .    Det  NP   .    .    .   
3    .    .    .    N    .    .    .   
4    .    .    .    .    P    .    PP  
5    .    .    .    .    .    Det  NP  
6    .    .    .    .    .    .    N

Давайте посмотрим на подробный вывод метода complete_wfst:

>>> wfst1 = complete_wfst(wfst0, tokens, grammar, trace=True)
[2] Det [3]   N [4] ==> [2]  NP [4]
[5] Det [6]   N [7] ==> [5]  NP [7]
[1]   V [2]  NP [4] ==> [1]  VP [4]
[4]   P [5]  NP [7] ==> [4]  PP [7]
[0]  NP [1]  VP [4] ==> [0]   S [4]
[1]  VP [4]  PP [7] ==> [1]  VP [7]
[0]  NP [1]  VP [7] ==> [0]   S [7]

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

Кстати, заполненную таблицу WFST можно представить в виде Chart Data Structure:

Программа построения WFST – это простой chart parser, который имеет несколько недостатков:

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

Зависимости и грамматика зависимостей

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

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

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

Каждая из дуг на рисунке помеченная типом отношений которые установлены между основным и зависимым словом. Например, I это SBJ (подлежащее), shot (основное слово предложения), in — NMOD (модификатор существительного elephant). В грамматике зависимостей связи между членами предложения могут быть представлены с помощью типов зависимостей.

Рассмотрим построение грамматики зависимостей без указания типа зависимостей:

>>> grammar = nltk.parse_dependency_grammar("""
 'shot' -> 'I' | 'elephant' | 'in'
 'elephant' -> 'an' | 'in'
 'in' -> 'pajamas'
 'pajamas' -> 'my'
 """)
>>> print groucho_dep_grammar
Dependency grammar with 7 productions
  'shot' -> 'I'
  'shot' -> 'elephant'
  'shot' -> 'in'
  'elephant' -> 'an'
  'elephant' -> 'in'
  'in' -> 'pajamas'
  'pajamas' -> 'my'
>>>

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

>>> pdp = nltk.ProjectiveDependencyParser(grammar)
>>> sent = 'I shot an elephant in my pajamas'.split()
>>> trees = pdp.parse(sent)
>>> for tree in trees:
     print tree

(shot I (elephant an (in (pajamas my))))
(shot I (elephant an) (in (pajamas my)))

Вывод

Конечно, эти анализаторы несколько сложнее тех, что рассматривались ранее. Зато они дают новые возможности синтаксического анализа.

Спасибо за внимание.

Ссылки

Синтаксический анализ в NLTK. Продолжение