graph - 如何使用Tree Isomorphic来解决语言模式匹配问题？

Question

在算法设计手册中,它说

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

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

通常,如何将字符串或文本构造为树并比较它们的身份？

谢谢

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

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