Modo efficiente per confrontare gli alberi del grafico di scena

Crea una pila di coppie di nodi per un confronto approfondito.

Definisci un identificatore che puoi usare per un confronto rapido, ad es. ID / nome / modello-percorso.

1. Confronta i root root, se corrispondono abbinarli allo stack.

2. Per ogni coppia nello stack:

2.1. Ordina i bambini in base all'identificatore scelto

2.2. Confronta i bambini in modo superficiale e aggiungi le corrispondenze allo stack.

Decidi se l'algoritmo deve essere terminato alla prima mancata corrispondenza o meno (a seconda dei risultati richiesti).

Se i tuoi nodi sono essi stessi sottoalberi (di parti più piccole), puoi applicare lo stesso algoritmo a loro.

Dipende piuttosto da cosa intendi per "confrontare", ma se puoi (efficacemente) serializzare i tuoi alberi (o almeno le loro proprietà a cui tieni) alle stringhe, allora " Levenshtein distance " (o qualche altro " modifica distanza " correlato oppure " metrica stringa ") tra una coppia di stringhe dovrebbe dirti qualcosa di utile sulle somiglianze tra di loro.

Puoi anche divertirti un po 'con le metriche di similarità basate sulla compressione: se le stringhe A e B comprimono a dimensione a e b, ma comprimendo il file C creato concatenando A e B comprime alla dimensione c, allora c / (a + b) ti dice qualcosa su quante informazioni duplicate ci fossero nei due file: il più vicino a 1.0, minore è il beneficio derivante dalla compressione dei file insieme e quindi meno simili sono (soggetto a caveat re dimensione del file e la finestra massima il tuo compressore funziona comunque). Pensa che questo tipo di approccio è usato da persone bioinformatiche ma con le sue radici teoriche dell'informazione dovrebbe essere più generalmente applicabile.