Zhang と Shasha によるアルゴリズムを実装して、2 つのツリー間の最小編集距離を計算しました。すべてがうまく機能しており、現在の実行時間に非常に満足しています。
ここで、変更/削除/挿入されたノードを強調表示する差分も生成したいと思います。彼らの論文によると、計算された距離をもたらすマッピングを求めるのは非常に自然なことであり、このプレゼンテーションの最後のスライドによると、最後の森林距離テーブルと樹木距離テーブルからマッピングを簡単に抽出できるようです。残念ながら、私はまだ正確なルールを把握できていません。
追加の説明をいただければ幸いです。どうもありがとう！
わかりました、私はついに自分でそれを理解しました。それぞれ m ノードと n ノードを持つ 2 つのツリーのノードに最適なマッピングを生成するには、フォレスト テーブルでバックトラックを行う必要があります。
(m, n) 森林距離テーブルの (m, n) で始まる各フィールド (x, y) について、次の操作を行います。 フィールド (x', y') と編集を合計して最小値が得られた場合/ コストを削除 / 挿入し、マッピングを書き留めて、現在の森林距離テーブルのフィールド (x', y') に移動します。一方、現在の森林距離テーブルのフィールド (x', y') と樹木距離テーブルのフィールド (tx, ty) を合計して最小値が得られた場合は、フィールド (x' , y') を現在のフォレスト距離テーブルから AND して、ツリー (tx, ty) に対応するフォレスト テーブルからフィールド (tx, ty) に変換します。両方のフォレスト テーブルで個別にバックトラックを続行し、両方からマッピングを収集する必要があります。