エディットグラフでの最短経路探索

Java diff

diffっぽいもの - pocketberserkerの爆走ではプログラムを見せるだけで終了してしまったので、今回は最短経路探索についてお話します。
以下の図は、strengthとstringのエディットグラフに、編集距離(Edit Distance)を求める際に通った座標(以降ではノードと呼びます)と通った順番を付加したものです。

最短経路は最終ノードから逆順に道をたどればとれるのですが、プログラムにしようとすると編集距離を求めるアルゴリズムにいくつもの処理を加えなければならなくなり非常にめんど……わかりづらいです。
そこで今回の実装では、ノードを通る時にひとつ前に通ったノードを親ノードとして記憶することにしました。
つまり、以下のようにノードがつながっています。

プログラムではノード生成時にデータを放り込むだけです。
さて、最終ノードに到達した（ということにしておいてください）ので、ここから最短経路を求めます。
ここで重要なのは、ノードは本来ならば以下の3つのノードとしか接点がないことです。

  • 左隣のノード
  • 真上のノード
  • 左斜め上のノード

なので、これらの条件を満たさないノードは発見次第消去していきます。
たとえば、ノード12から見たノード11は条件を満たさないので消去し、親ノードをノード10に更新します。
下図をみるとわかるとおり、ノード11を消去したことにより紫線部分が消滅し、更新したノード10へとつながる線が新たに追加されます。

前回の実装では、条件を満たす場合は処理を行わず、どの条件も満たさない場合に「親ノードを親ノードの親ノードに書き換える」処理を行っています。

if(current.type == Node.Type.DELETE && parent.x == current.x && parent.y == current.y-1) {}
else if(current.type == Node.Type.ADD && parent.x == current.x-1 && parent.y == current.y) {}
else if(current.type == Node.Type.COMMON && parent.x == current.x-1 && parent.y == current.y-1) {}
else {
	current.prev = parent.prev;
	continue;
}

親ノードが条件を満たすノードだった場合は次のノードへと処理を移行します。
そういうわけで、この調子でほかのノードもどんどん見ていきましょう。
ノード5は条件を満たさないので消去します。この結果（左側の）紫線部分が消え、ノード6がノード4とつながります。

さらに、ノード4も条件を満たさないので消去します。この結果、水色線部分が消え、ノード6がノード3とつながります。

残りのノードは条件を満たすので、無事開始ノードまで到着します。
これで無事に、欲していた最短経路（下図水色線）を取得できました。

あまりきれいな実装ではないですが、編集距離導出アルゴリズム内をほとんどいじらずにコーディングできる利点があります（あと、単純に編集距離導出アルゴリズムの実行速度を求める場合は便利かも）。
欠点としては、消去すべきノードが大量にある場合は処理に時間がかかることでしょうか。

ちなみに先日掲載したソースコードは、昨日行われた機能追加による構造変更により3分の1が原形をとどめていません（特に列挙体関連）。
そしてなぜか通称O(ND)アルゴリズムの編集距離導出もこっそり実装していたり……

というわけで、簡単にざっくりとしたわけのわからないかもしれない自作最短経路探索の説明でした。