эффективный алгоритм сравнения деревьев и расстояния Левенштейна

20

Я недавно прочитал это краткое изложение проблем, связанных с выполнением различий между деревьями, и мне стало интересно узнать, каково состояние этой проблемы.

Кроме того, предположим, что между разрешенными операциями редактирования находится традиционный узел добавления / удаления, для редактирования содержимого добавляются расширенные операции копирования / перемещения поддерева, это облегчает или усложняет проблему (нахождения оптимальной разницы)?

lurscher
источник

Ответы:

16

Следующая статья описывает чуть более эффективный алгоритм, чем Чжан-Шаша, для вычисления расстояния редактирования дерева, а также доказательство того, что их алгоритм является оптимальным (в рамках определенного широкого класса алгоритмов):

Jeffε
источник
7

Полезный опрос по теме, немного устаревший:

Филипп Билле. Опрос по расстоянию редактирования дерева и связанным с ним проблемам . Теоретическая информатика, том 337, выпуски 1–3, страницы 217–239, 2005.

Недавняя статья об одной из версий проблемы:

Тацуя Акуцу и соавт. Точные алгоритмы вычисления дерева редактируют расстояние между неупорядоченными деревьями . Теоретическая информатика, том 412, выпуски 4–5, страницы 352–364, 2011.

Александр Тискин
источник