Geek asks and answers

Graph - How to use Tree Isomorphic to solve language pattern matching?

The Algorithm Development Guide says

Do you check if two trees are isomorphic? - There are faster algorithms for some special cases of graph isomorphism, such as trees and flat graphs. Perhaps the most important case is the detection of isomorphisms between trees, a problem that occurs when comparing language patterns and parsing applications. The parse tree is often used to describe the structure of the text; two parse trees will be isomorphic if the base pair of texts has the same structure.

I just want someone, please, give an example of how to use tree isomorphism to solve the language template matching problem. that is, how can I correlate the correspondence of the language template with the tree isomorphism problem?

Typically, how can I build a line or text like a tree and compare their identifiers?

thank

+5
source share
2 answers

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

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

English phrase "dog barks". can then be analyzed 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

- " ". , , . , , .

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

, , .

+4

, . (- ) , - , , , .

, .

( )

0

More articles:


All Articles