5

在算法设计手册中，它说

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

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

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

谢谢

4

2 回答 2

4

以英语为例，想法是一些英语句子可以用以下解析树表示：

        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

另一个具有相同结构的句子是“一片叶子落下”。它的解析树看起来具有相同的形状，这意味着两个解析树将是同构的。也就是说，即使含义不同，它们也具有与句子相同的逻辑结构。

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

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

于 2012-05-08T05:09:35.163 回答
0

如文中所述，解析树是这里的关键概念。解析树代表（以某种方式）文本的结构，从技术上讲，它是一棵树，因此您可以使用任何您喜欢的树算法来处理解析树。

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

（关于解析树的维基百科文章）

于 2012-05-07T21:48:02.967 回答