graph - ¿Cómo uso Tree Isomorphic para resolver el emparejamiento de patrones de lenguaje?

Question

En Algorithm Design Manual, se dice

¿Está probando si dos árboles son isomorfos? - Existen algoritmos más rápidos para ciertos casos especiales de isomorfismo gráfico, como árboles y gráficos planos. Tal vez el caso más importante es la detección de isomorfismos entre árboles, un problema que surge en la coincidencia de patrones de lenguaje y las aplicaciones de análisis. Un árbol de análisis se usa a menudo para describir la estructura de un texto; dos árboles de análisis serán isomorfos si el par de textos subyacente tiene la misma estructura.

Solo deseo a alguien por favor dame un ejemplo de cómo usar el isomorfismo de árbol para resolver un problema de coincidencia de patrón de idioma. es decir, ¿cómo puedo asignar la coincidencia de patrones de lenguaje a un problema de isomorfismo de árbol?

Normalmente, ¿cómo construyo una cadena o texto como árbol y comparo sus identidades?

Gracias

Answer 1

El uso de Inglés como un ejemplo, la idea es que algunas frases en inglés pueden ser representados por las siguientes árboles de análisis sintáctico:

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

La frase Inglés "El el perro ladra." luego se puede analizar de la siguiente manera

ARTICLE NOUN  VERB 
/  /  /
The  dog  barks 

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


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

Otra oración con la misma estructura es "A leaf falls". Su árbol de análisis tendría la misma forma, lo que significa que los dos árboles de análisis serían isomorfos. Es decir, tienen la misma estructura lógica que una oración, aunque el significado sea diferente.

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

Tanto Árboles analizadores son también isomorfo al patrón general, también representado como un árbol, si se ignoran las palabras físicas reales.

Answer 2

Como se indica en el texto, árbol de análisis sintáctico es el concepto clave aquí. Un árbol de análisis representa (de alguna manera) la estructura de un texto, y es técnicamente un árbol, por lo que puede trabajar con los árboles de análisis utilizando cualquier algoritmo de árbol que desee.

Parse tree es un árbol ordenado y enraizado que representa la estructura sintáctica de una cuerda según una gramática formal.

(artículo de Wikipedia sobre Parse trees)