graph - How do I use Tree Isomorphic to solve language pattern matching?

Question

In Algorithm Design Manual, it says

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.

I just wish someone please give me an example that how to use Tree Isomorphism to solve language pattern matching problem. i.e., how can I map language pattern matching to a tree isomorphism problem?

Normally, how do I construct a string or text as a tree and compare their identities?

Thanks

Answer 1

Using English as an example, the idea is that some English sentences can be represented by the following parse trees:

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

The English phrase "The dog barks." can then be parsed as follows

ARTICLE    NOUN      VERB
 /          /         /
The       dog       barks

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


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

Another sentence with the same structure is "A leaf falls." Its parse tree would look to have the same shape, which means that the two parse trees would be isomorphic. That is, they have the same logical structure as a sentence even though the meaning is different.

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

Both parse trees are also isomorphic to the general pattern, also represented as a tree, if you ignore the actual physical words.

Answer 2

As indicated in the text, parse tree is the key concept here. A parse tree represents (is some way) the structure of a text, and it is technically a tree, so you can work with the parse trees using any tree algorithms you like.

Parse tree is an ordered, rooted tree that represents the syntactic structure of a string according to some formal grammar.

( Wikipedia article on Parse trees)