algoritmo diff eficiente para árvores e distância de Levenshtein

Recentemente, li este resumo dos problemas envolvidos na diferenciação entre árvores e isso me interessou em saber qual é o estado da arte para esse problema.

Além disso, suponha que entre as operações de edição permitidas esteja o nó tradicional de adição / exclusão, edite o conteúdo e adicione as operações estendidas da subárvore de copiar / mover, isso facilita ou dificulta o problema (de encontrar uma comparação ótima)?

O artigo a seguir descreve um algoritmo um pouco mais eficiente que o Zhang-Shasha para calcular a distância de edição em árvore, juntamente com uma prova de que o algoritmo é ideal (dentro de uma certa classe ampla de algoritmos):

• Erik Demaine, Shay Mozes, Benjamin Rossman e Oren Weimann. Um algoritmo de decomposição ideal para a distância de edição em árvore . ACM Transactions on Algorithms , 6 (1), 2009.

Uma pesquisa útil sobre o tema, um pouco desatualizada:

Philip Bille. Uma pesquisa na árvore edita distâncias e problemas relacionados . Teoria da Computação, Volume 337, Edições 1–3, Páginas 217–239, 2005.

Um artigo recente sobre uma das versões do problema:

Tatsuya Akutsu et al. Algoritmos exatos para calcular a distância de edição em árvore entre árvores não ordenadas . Theoretical Computer Science, Volume 412, Edições 4-5, Páginas 352-364, 2011.