algoritma diff efisien untuk pohon dan jarak Levenshtein

Saya baru-baru ini membaca ringkasan masalah yang terlibat dengan melakukan perbedaan di antara pohon-pohon dan itu membuat saya tertarik untuk belajar apa yang paling canggih untuk masalah ini.

Juga, anggaplah bahwa di antara operasi edit yang diizinkan adalah simpul tambah / hapus tradisional, edit konten yang Anda tambahkan operasi perluasan salin / geser subtree, apakah ini membuat masalah (menemukan diff optimal) lebih mudah atau lebih sulit?

Makalah berikut ini menjelaskan algoritma yang sedikit lebih efisien daripada Zhang-Shasha untuk menghitung jarak sunting pohon, bersama dengan bukti bahwa algoritma mereka optimal (dalam kelas algoritma tertentu):

• Erik Demaine, Shay Mozes, Benjamin Rossman, dan Oren Weimann. Algoritma Dekomposisi Optimal untuk Jarak Edit Pohon . Transaksi ACM tentang Algoritma , 6 (1), 2009.

Survei bermanfaat tentang topik ini, sedikit kedaluwarsa:

Philip Bille. Sebuah survei pada jarak edit pohon dan masalah terkait . Ilmu Komputer Teoritis, Volume 337, Masalah 1–3, Halaman 217–239, 2005.

Makalah terbaru tentang salah satu versi masalah:

Tatsuya Akutsu et al. Algoritma yang tepat untuk menghitung jarak edit pohon antara pohon yang tidak berurutan . Ilmu Komputer Teoritis, Volume 412, Masalah 4–5, Halaman 352–364, 2011.