Как я могу использовать Tree Isomorphic для решения сопоставления с образцом языка?

Question

В Руководстве по разработке алгоритмов говорится:

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

Я просто хочу, чтобы кто-нибудь дал мне пример того, как использовать древовидный изоморфизм для решения проблемы сопоставления языковых шаблонов то есть, как я могу сопоставить образец языка, соответствующий проблеме изоморфизма дерева?

Обычно, как мне построить строку или текст в виде дерева и сравнить их идентичности?

Спасибо

Answer 1

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

        SENTENCE               SENTENCE
       /        \             /        \
  PROPER NOUN  VERB      COMMON NOUN  VERB
      /                    /    \
     NAME                ARTICLE NOUN

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

ARTICLE    NOUN      VERB
 /          /         /
The       dog       barks

    COMMON NOUN
     /      \
ARTICLE    NOUN      VERB
 /          /         /
The       dog       barks


            SENTENCE
             /     \
    COMMON NOUN     \
     /      \        \
ARTICLE    NOUN      VERB
 /          /         /
The       dog       barks

Другое предложение с такой же структурой - "Лист падает". Его дерево разбора будет выглядеть одинаково, что означает, что два дерева разбора будут изоморфными. То есть они имеют ту же логическую структуру, что и предложение, хотя значение иное.

            SENTENCE
             /     \
    COMMON NOUN     \
     /      \        \
ARTICLE    NOUN      VERB
 /          /         /
A         leaf      falls

Оба дерева разбора также изоморфны общему шаблону, также представленному в виде дерева, если вы игнорируете реальные физические слова.

Answer 2

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

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

(Статья в Википедии о разборе деревьев)