图形 - 我如何使用树同构来解决语言模式匹配问题？

Question

在《算法设计手册》中，它说：

“你正在测试两棵树是否同构吗？-对于图同构的某些特殊情况，例如树和平面图，存在更快的算法。也许最重要的情况是检测树之间的同构，这是语言模式匹配和解析应用程序中出现的问题。解析树通常用于描述文本的结构；如果基础文本对具有相同结构的两个解析树是同构的。”

我只希望有人能给我一个例子，说明如何使用树同构来解决语言模式匹配问题。即如何将语言模式匹配映射到树同构问题？

通常，我如何将字符串或文本构造为一棵树并比较它们的标识？

谢谢

- Jackson Tale

---

只是一个快速提示，如果你在这里没有得到满意的答案，那么这个问题可能适合 http://cstheory.stackexchange.com/。 - ChristopheD

Answer 1

以英语为例，有些英文句子可以用以下解析树表示:

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

英语短语"The dog barks."可以解析如下：

ARTICLE    NOUN      VERB
 /          /         /
The       dog       barks

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


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

另一个具有相同结构的句子是"A leaf falls."它的语法树看起来应该具有相同的形状，这意味着这两个语法树应该是同构的。也就是说，它们具有相同的逻辑结构，即使意义不同。

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

如果您忽略实际的物理单词，两个解析树也与表示为树的一般模式同构。

- Antti Huima

Answer 2

正如文本所示，解析树是关键概念。解析树以某种方式表示文本的结构，并且它在技术上是一棵树，因此您可以使用任何树算法来处理解析树。

解析树是一个有序的、根据某些形式语法表示字符串句法结构的树。

(维基百科关于解析树的文章)

- Przemysław Pietrzkiewicz