Дерево редактирования Расстояние: Как я могу получить оптимальное отображение?

Question

Я внедрил algorithm by Zhang and Shasha для вычисления минимального расстояния редактирования между двумя деревьями. Все работает нормально, и я очень доволен текущим временем работы.

Теперь я хотел бы также создать diff, который выделяет измененные/удаленные/вставленные узлы. Согласно их статье, очень естественно просить сопоставление, которое дало вычисленное расстояние, и, согласно последним слайдам this presentation, кажется, что отображение можно легко извлечь из последней таблицы расстояния леса и таблицы расстояний деревьев. К сожалению, я пока не смог определить точные правила.

Любое дополнительное описание было бы высоко оценено. Большое спасибо!

Answer 1

Хорошо, я, наконец, понял это самостоятельно. Чтобы создать оптимальное сопоставление для узлов двух деревьев, с узлами m и n соответственно, вам нужно выполнить некоторую обратную трассировку в таблицах леса.

Для каждого поля (x, y), начиная с (m, n) таблицы расстояний леса (m, n), сделайте следующее: если минимум был получен путем суммирования поля (x ', y') и затраты на редактирование/удаление/вставку, затем запишите отображение и перейдите в поле (x ', y') текущей таблицы расстояний леса. С другой стороны, если минимум был получен путем суммирования поля (x ', y') из текущей таблицы расстояния леса и поля (tx, ty) из таблицы расстояний деревьев, затем перейдите в поле (x ' , y ') из текущей таблицы расстояний леса AND в поле (tx, ty) из таблицы леса, соответствующей дереву (tx, ty). Теперь вам нужно продолжать обратную трассировку в обеих таблицах леса отдельно и собирать сопоставления из обоих.