diff2 つの有向非巡回グラフ (DAG)を処理できるアルゴリズムを探しています。つまり、最初の DAG で一連の削除と挿入を生成して 2 番目の DAG を生成するアルゴリズムが必要です。
100% 確信があるわけではありませんが、最長の共通サブシーケンスを DAG に適用できると思います。結果として得られる編集シーケンスの長さはあまり気にせず (十分に短い限り)、アルゴリズムの実行時間の方が気になります。
問題の 1 つは、単一のルート ノードを除いて、どの頂点にもラベルが付けられていないことです。ルート ノードは、インエッジがゼロの唯一のノードでもあります。グラフのエッジにはラベルが付けられ、グラフの「データ」はルートからリーフへのパスによって表されます。これは に似ていtrieますが、ツリーではなく有向グラフを使用します。directed acyclic word graph実際、私のグラフはデータ構造に非常に似ています。
例を次に示します。
DAG1
DAG2
DAG 2 を取得するには、頂点をルートから別の頂点にラベル「b」で追加するだけです。その頂点から、DAG 1 の最後の 'ac' 頂点へのエッジと、ラベルが 'd' である新しい頂点へのエッジがあります。その最後の頂点から、DAG 1 の 'ac' 頂点への別のエッジがあります。DAG 形式で diff へのリンクを投稿したいのですが、2 つ以上のリンクを投稿することはできません。
ありがとう、これが十分に読みやすいことを願っています。