Как мне манипулировать деревьями разбора? - PullRequest
Новая
       60

Как мне манипулировать деревьями разбора?

15 голосов
/ 12 сентября 2010

Я играл с деревьями парсинга естественного языка и манипулировал ими различными способами.Я использовал инструменты Стэнфорда Tregex и Tsurgeon, но код беспорядок и не вписывается в мою в основном среду Python (эти инструменты Java и не идеальны для настройки).Я хотел бы иметь набор инструментов, который позволит легко взломать, когда мне нужно больше функциональности.Существуют ли какие-либо другие инструменты, которые хорошо подходят для сопоставления с образцом на деревьях, а затем для манипулирования этими сопоставленными ветвями?

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

(ROOT
  (S
    (NP
      (NP (NNP Bank))
      (PP (IN of)
        (NP (NNP America))))
    (VP (VBD used)
      (S
        (VP (TO to)
          (VP (VB be)
            (VP (VBN called)
              (NP
                (NP (NNP Bank))
                (PP (IN of)
                  (NP (NNP Italy)))))))))))

и (это упрощенный пример):

  1. Найдите любой узел с меткой NP, у которого есть первый дочерний элемент с меткой NP и некоторый потомок с именем «Банк», а второй дочерний элемент сметка PP.
  2. Если это совпадает, возьмите все дочерние элементы узла PP и переместите их в конец дочерних элементов сопоставляемого NP.

Например, возьмите эту частьдерева: 

(NP
  (NP (NNP Bank))
  (PP (IN of)
    (NP (NNP America))))

и превратить его в это: 

(NP
  (NP (NNP Bank) (IN of) (NP (NNP America))))

Поскольку мои входные деревья являются S-выражениями, я рассмотрел использование Lisp (встроенного в мою программу Python), ноя так долго писал что-то существенное на Лиспе, что понятия не имею, с чего начать.

Что было бы хорошим способом описать шаблоны?Какой будет хороший способ описать манипуляции?Какой хороший способ думать об этой проблеме?

Ответы [ 3 ]

11 голосов
/ 19 сентября 2010

Красота в глазах смотрящего.Но вы никогда не скажете , как код Tregex или Tsurgeon - беспорядок.Похоже, что вы не можете иметь дело с Java или большей абстракцией, и поэтому вы ищете что-то конкретное, написанное на Python.

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

Tree t = Tree.valueOf("(ROOT (S (NP (NP (NNP Bank)) (PP (IN of) (NP (NNP America)))) (VP (VBD used) (S (VP (TO to) (VP (VB be) (VP (VBN called) (NP (NP (NNP Bank)) (PP (IN of) (NP (NNP Italy)))))))))))");
TregexPattern pat = TregexPattern.compile("NP <1 (NP << Bank) <2 PP=remove");
TsurgeonPattern surgery = Tsurgeon.parseOperation("excise remove remove");
Tsurgeon.processPattern(pat, surgery, t).pennPrint();

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

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

8 голосов
/ 12 сентября 2010

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

Вот пример процедурного сопоставления с использованием Common Lisp. В Лиспе есть сопоставители, которые работают над структурами списков, которые можно использовать вместо них. Использование сопоставителя списков упростит пример (см. Мой другой ответ для примера использования сопоставителя шаблонов).

Код: 

(defun node-children (node)
  (rest node))

(defun node-name (node)
  (second node))

(defun node-type (node)
  (first node))


(defun treemap (tree matcher transformer)
  (cond ((null tree) nil)
        ((consp tree)
         (if (funcall matcher tree)
             (funcall transformer tree)
           (cons (node-type tree)
                 (mapcar (lambda (child)
                           (treemap child matcher transformer))
                         (node-children tree)))))
        (t tree))))

Пример: 

(defvar *tree*
  '(ROOT
    (S
     (NP
      (NP (NNP Bank))
      (PP (IN of)
          (NP (NNP America))))
     (VP (VBD used)
         (S
          (VP (TO to)
              (VP (VB be)
                  (VP (VBN called)
                      (NP
                       (NP (NNP Bank))
                       (PP (IN of)
                           (NP (NNP Italy))))))))))))



(defun example ()
  (pprint
   (treemap *tree*
            (lambda (node)
              (and (= (length (node-children node)) 2)
                   (eq (node-type (first (node-children node))) 'np)
                   (some (lambda (node)
                           (eq (node-name node) 'bank))
                         (children (first (node-children node))))
                   (eq (first (second (node-children node))) 'pp)))
            (lambda (node)
              (list (node-type node)
                    (append (first (node-children node))
                            (node-children (second (node-children node)))))))))

Запуск примера: 

CL-USER 75 > (example)

(ROOT
 (S
  (NP
   (NP (NNP BANK) (IN OF) (NP (NNP AMERICA))))
  (VP
   (VBD USED)
   (S
    (VP
     (TO TO)
     (VP
      (VB BE)
      (VP
       (VBN CALLED)
       (NP
        (NP
         (NNP BANK)
         (IN OF)
         (NP (NNP ITALY)))))))))))
5 голосов
/ 19 сентября 2010

Вот вторая версия в Common Lisp. На этот раз я использую шаблон .

Я использую функцию, которая сопоставляет шаблон с данными Lisp. PMATCH: MATCH - это расширенная версия сопоставления с образцом, найденная в книге Winston / Horn, Lisp, 3rd Edition. Доступны аналогичные функции сопоставления с образцом.

Данные такие же, как в моем другом ответе.

Функция отображения дерева изменена для использования сопоставителя шаблонов. Функция PMATCH: MATCH возвращает T или связанный список привязок, если сопоставление прошло успешно. Возвращает NIL, если совпадение не было успешным. PMATCH: INSTANTIATE-PATTERN принимает шаблон и набор привязок. Возвращает новую структуру списка, в которой переменные шаблона заменяются привязками. 

(defun treemapp (tree pattern transformer)
  (cond ((null tree) nil)
        ((consp tree)
         (let ((bindings (pmatch:match pattern tree)))
           (if bindings
               (pmatch:instantiate-pattern transformer bindings)
             (cons (node-type tree)
                   (mapcar (lambda (child)
                             (treemapp child pattern transformer))
                           (node-children tree))))))
        (t tree)))

В примере теперь используются шаблоны.

Шаблон представляет собой структуру списка. Символ # соответствует одному элементу и создает привязку для символа. Символ $ соответствует списку элементов и создает привязку для символа.

Трансформатор - это шаблон, который будет создан с привязками. 

(defun example1 ()
  (pprint (treemapp *tree*
                    '(NP (NP (#?type bank)) (PP #$children))
                    '(NP (NP (#?type bank) #$children)))))

Запуск этого кода возвращает тот же результат, что и в моем другом ответе.

...