wydajny algorytm różnicowy dla drzew i odległości Levenshteina

Niedawno przeczytałem to podsumowanie zagadnień związanych z różnicowaniem między drzewami i zainteresowało mnie poznanie najnowocześniejszych rozwiązań tego problemu.

Załóżmy również, że między dozwolonymi operacjami edycji jest tradycyjny węzeł dodawania / usuwania, edytuj zawartość, którą dodajesz rozszerzonymi operacjami poddrzewa kopiuj / przenieś, czy to sprawia, że ​​problem (znalezienie optymalnej różnicy) jest łatwiejszy czy trudniejszy?

Poniższy artykuł opisuje nieco bardziej wydajny algorytm obliczania odległości edycji drzewa niż Zhang-Shasha, wraz z dowodem, że ich algorytm jest optymalny (w ramach pewnej szerokiej klasy algorytmów):

• Erik Demaine, Shay Mozes, Benjamin Rossman i Oren Weimann. Algorytm optymalnego rozkładu dla odległości edycji drzewa . Transakcje ACM na algorytmach , 6 (1), 2009.

Przydatna ankieta na ten temat, nieco nieaktualna:

Philip Bille. Ankieta na temat odległości edycji drzewa i powiązanych problemów . Theoretical Computer Science, tom 337, numery 1–3, strony 217–239, 2005.

Ostatni artykuł na temat jednej z wersji problemu:

Tatsuya Akutsu i in. Dokładne algorytmy do obliczania odległości edycji drzewa między nieuporządkowanymi drzewami . Theoretical Computer Science, tom 412, wydania 4–5, strony 352–364, 2011.