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

Question

在Algorithm Design Manual , 它说

Are you testing whether two trees are isomorphic? – Faster algorithms exist for certain special cases of graph isomorphism, such as trees and planar graphs. Perhaps the most important case is detecting isomorphisms among trees, a problem that arises in language pattern matching and parsing applications. A parse tree is often used to describe the structure of a text; two parse trees will be isomorphic if the underlying pair of texts have the same structure.

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

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

谢谢

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

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