Из-за того, что я испортил домашнее задание друга по компьютерной лингвистике, я не смог получить синтаксическое дерево, которое ожидал, и решил глубже изучить этот алгоритм.
Отличный способ понять алгоритм - это реализовать его. Оказалось, что программа Python, распространяемая с домашним заданием, была размещена на GitHub, поэтому я раздвоил ее и начал взламывать. Вы можете увидеть измененный код здесь.
В зависимости от ваших предварительных знаний нижеследующее может быть плохо объяснено, скучно базовым или и то, и другое.
Давай начнем.
Алгоритм
Путем синтаксического анализа мы добавляем структуру к списку «слов» для построения дерева с использованием грамматики, которая представляет собой список правил. Есть два вида правил:
- Узел может быть словом. Например. «Слон» - это существительное:
N -> 'elephant'. - Узел может состоять из двух узлов ². Например. предложение может состоять из существительного и глагольного словосочетания:
S -> NP VP.
Первый тип правил применяется к отдельным словам для создания узлов из одного слова, затем правила второго типа применяются для создания узлов, охватывающих 2 слова, 3 слова… и затем все предложение.
Чтобы использовать алгоритм для синтаксического анализа, необходимо отслеживать узлы, используемые для создания более высокого узла. «Иногда это делается с помощью второй таблицы B[n,n,r] так называемых обратных указателей». ³ Но мы используем Python, выразительный язык, и использование индексов кажется примитивным. Почему бы вместо этого не передать дочерний узел в качестве аргументов? Что может быть лучше указателей, чем ссылки ⁴ на объекты?
Итак, я написал узел, который будет просто переносить символ и его дочерние элементы. Это мало чем отличается от того, как типы суммы (также известные как помеченные объединения) являются тегом и некоторыми аргументами.
type vp = | VP0 of v * np | VP1 of vp * pp
Код OCaml выше, определение грамматики ниже. Не сильно отличается, если немного прищуриться.
VP -> V NP VP -> VP PP
Вернемся к ошибке, которая ее запустила, исходная реализация правильно проанализировала две возможности, но забыла иметь дело с двусмысленностью в корне деревьев.
В моей реализации неоднозначности любых узлов, будь то в корне или в ветвях, представлены и обрабатываются одинаково. А поскольку узел не разветвляется на несколько вариантов⁵, простая рекурсия помогает распечатать дерево.
Да, я изобретаю колесо, код, который я написал, был лучше написан раньше ». Но я получил удовольствие, оценивая связи между предметами, которые я изучал.
Наконец, два забавных дерева разбора для читателей на кантонском диалекте. : D
➜ CYK-Parser git:(master) ✗ python3 Parser.py grammar.txt '兒子 生 性 病 母 倍 感 安慰' Using /Users/phisgr/CYK-Parser/grammar.txt as path for the grammar and 兒子 生 性 病 母 倍 感 安慰 as sentence. The given sentence is contained in the language produced by the given grammar! Possible parse(s): [NewsHeadline [S [NP '兒子'] [VP [V '生'] [NP '性']]] [S [NP [Adj '病'] [N '母']] [VP [Adv '倍'] [VP [V '感'] [AP '安慰']]]]] [NewsHeadline [S [NP '兒子'] [VP [V '生'] [NP [Adj '性'] [N '病']]]] [S [NP '母'] [VP [Adv '倍'] [VP [V '感'] [AP '安慰']]]]]
[1] Так я научился программировать.
[2] Правила с 3 дочерними узлами, такими как NP -> Det N PP, могут быть преобразованы в 2 правила, NP -> NP0 PP и NP0 -> Det N, для использования в алгоритме.
Правила с одним дочерним узлом, например VP -> V, могут обрабатываться путем копирования правил, которые создают V . Например. V -> ‘shot’ скопировано в VP -> ‘shot’.
[3] https://en.wikipedia.org/wiki/CYK_algorithm#Generating_a_parse_tree
[4] Поскольку узлы используются как неизменяемые, семантика передачи по значению также подходит.
[5] Узел разветвляется на один или два дочерних узла, но не на несколько возможностей. Множественные возможности представлены списком узлов.
