grafico - Come si usa Albero Isomorphic per risolvere il pattern matching lingua?

Question

In Algorithm Design Manual, si dice

Si sta testando se due alberi sono isomorfi? - Esistono algoritmi più veloci per alcuni casi speciali di isomorfismo grafico, come alberi e grafici planari. Forse il caso più importante rileva isomorfismi tra alberi, un problema che si pone nel modello linguaggio corrispondenza e parsing applicazioni. Un albero di analisi viene spesso utilizzato per descrivere la struttura di un testo; due alberi di analisi saranno isomorfi se la coppia di testi sottostante ha la stessa struttura.

Spero solo che qualcuno mi dia un esempio di come utilizzare l'Isomorfismo degli alberi per risolvere il problema di corrispondenza dei modelli linguistici. cioè, come posso mappare la corrispondenza del modello linguistico con un problema di isomorfismo dell'albero?

Normalmente, come faccio a costruire una stringa di testo o come un albero e confrontare la loro identità?

Grazie

Answer 1

Usando l'inglese come esempio, l'idea è che alcune frasi in inglese possono essere rappresentati dalle seguenti alberi di analisi:

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

La frase inglese "The il cane abbaia." può quindi essere analizzato come segue

ARTICLE NOUN  VERB 
/  /  /
The  dog  barks 

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


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

Un'altra frase con la stessa struttura è "Una foglia cade". Il suo albero di analisi sembrerebbe avere la stessa forma, il che significa che i due alberi di analisi sarebbero isomorfi. Cioè, hanno la stessa struttura logica di una frase anche se il significato è diverso.

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

Entrambi analizzare gli alberi sono anche isomorfo al modello generale, anche rappresentato come un albero, se si ignorano le parole fisici reali.

Answer 2

Come indicato nel testo, albero parse è il concetto chiave qui. Un albero sintattico rappresenta (è in qualche modo) la struttura di un testo, ed è tecnicamente un albero, in modo da poter lavorare con gli alberi di analisi utilizzando qualsiasi algoritmo di alberi che ti piace.

Parse tree è un albero ordinato e radicato che rappresenta la struttura sintattica di una stringa secondo una grammatica formale.

(articolo di Wikipedia su Parse trees)