編集距離のプログラミング
2つの任意の文字列について、編集グラフを作成し、そのグラフに対して最短経路の計算を行って最良解と編集距離を得るためのプログラムを作成できます。最短経路全般の検出方法については、私の記事「Network Know-How: Finding Shortest Paths」を参照ください。今回の編集グラフは最短経路の検出に都合のよい特殊な構造を備えているので、それを利用してプログラムを作成します。
基本的な考え方は、左上隅の開始ノードからグラフ内のすべてのノードへの最短経路を計算することです。リンクはすべて右と下（斜めの場合はその両方）に向かうので、左上隅を起点として右方向と下方向に進む距離を計算します。
最初に、左上隅のノードに距離0を割り当てます。このノードからそれ自体への経路は0だからです。次に、左端の列の各ノードに1、2、3という順序で値を割り当てます。これらのノードへの経路は、次にくる文字を変換後の文字列に追加する操作に対応します。図1では、「t」ノードのコストが1、「u」ノードのコストが2という具合になります。
同様に、グラフの最上部の行の各ノードに1、2、3という順序で値を割り当てます。これらの経路は、元の文字列から文字を削除する操作に対応します。これで、グラフ内を進みながら他の値を記録できるようになります。
2列目の上から下に並んでいる各ノードについて考えてみましょう。各ノードに到達するために取り得る経路は3つあります。
1つ目は、上のノードから到達する経路です。この移動は文字列に新しい文字を1つ追加する操作に対応するので、このノードに到達するためのコストは、上のノードに到達するときにかかったコストより1大きくなります。
2つ目は、左のノードから到達する経路です。この移動は元の文字列から文字を1つ削除する操作に対応するので、このノードに到達するためのコストは、左のノードに到達するときにかかったコストより1大きくなります。
3つ目は、斜めのリンクに沿って到達する経路です。斜めのリンクのコストは0なので、コストは左上のノードに到達するときにかかったコストと同じになります。
このノードに到達する最良のコストを見つけるために、アルゴリズムはこれら3つの経路をすべて検討し、最良の経路を選択します。アルゴリズムはこのノードの新しい距離を記録し、最良の経路を示すように求められた場合に備えて、それがどのノードからの経路かを記録します。
図2に示すStringEditDistanceプログラムでは、このアルゴリズムを使っています。表示される結果は図1の青色の経路と同じになっている点に注目してください。つまり、「pa」を削除し、「tu」を追加し、「s」を削除しています。
