SED

メモ。

"あいうか"という文字列を編集して"あいうえおあお"という文字列を作った場合について。

まず、下のような格子を作る。

　　　あ　い　う　え　お　あ　お (変更後の文字列)
　┌─┬─┬─┬─┬─┬─┬─┐
　│　│　│　│　│　│　│　│
あ├─┼─┼─┼─┼─┼─┼─┤
　│　│　│　│　│　│　│　│
い├─┼─┼─┼─┼─┼─┼─┤
　│　│　│　│　│　│　│　│
う├─┼─┼─┼─┼─┼─┼─┤
　│　│　│　│　│　│　│　│
か└─┴─┴─┴─┴─┴─┴─┘
(変更前の文字列)

さらに、頂点座標を振っておく。

　　     あ　い　う　え　お　あ　お
(0,0)┌─┬─┬─┬─┬─┬─┬─┐(0,7)
   　│　│　│　│　│　│　│　│
   あ├─┼─┼─┼─┼─┼─┼─┤
   　│　│　│　│　│　│　│　│
   い├─┼─┼─┼─┼─┼─┼─┤
　   │　│　│　│　│　│　│　│
   う├─┼─┼─┼─┼─┼─┼─┤
　   │　│　│　│　│　│　│　│
   か└─┴─┴─┴─┴─┴─┴─┘
(4,0)                            (4,7)

すべてのi, jに対し、変更前のi番目の要素と変更後のj番目の要素が等しい場合、(i, j) -> (i + 1, j + 1)に対角線を引く。

　　     あ　い　う　え　お　あ　お
(0,0)┌─┬─┬─┬─┬─┬─┬─┐(0,7)
   　│＼│　│　│　│　│＼│　│
   あ├─┼─┼─┼─┼─┼─┼─┤
   　│　│＼│　│　│　│　│　│
   い├─┼─┼─┼─┼─┼─┼─┤
　   │　│　│＼│　│　│　│　│
   う├─┼─┼─┼─┼─┼─┼─┤
　   │　│　│　│　│　│　│　│
   か└─┴─┴─┴─┴─┴─┴─┘
(4,0)                            (4,7)

diagonals: {(0, 0), (0, 5), (1, 1), (2, 2)} // あ, あ, い, う

すべてのkに対し、(i, k) -> (i + 1, k + 1) となるような対角線が存在しない i が存在する場合、変更前のi番目の要素を削除する。

　　     あ　い　う　え　お　あ　お
     ┌─┬─┬─┬─┬─┬─┬─┐
   　│＼│　│　│　│　│＼│　│
   あ├─┼─┼─┼─┼─┼─┼─┤
   　│　│＼│　│　│　│　│　│
   い├─┼─┼─┼─┼─┼─┼─┤
　   │　│　│＼│　│　│　│　│
   う└─┴─┴─┴─┴─┴─┴─┘

diagonals: {(0, 0), (0, 5), (1, 1), (2, 2)} // あ, あ, い, う
remove: {3} // え

同様に、すべてのkに対し、(k, i) -> (k + 1, i + 1) となるような対角線が存在しない i が存在する場合、変更後のi番目の要素を削除する。

　　     あ　い　う　あ
     ┌─┬─┬─┬─┐
   　│＼│　│　│＼│
   あ├─┼─┼─┼─┤
   　│　│＼│　│　│
   い├─┼─┼─┼─┤
　   │　│　│＼│　│
   う└─┴─┴─┴─┘

diagonals: {(0, 0), (0, 5), (1, 1), (2, 2)} // あ, あ, い, う
remove: {3} // え
insert: {3, 4, 6} // え, お, お

各頂点をグラフのノードとし、左上のノードから右下のノードへ辿り着くための最短経路を探す。ただし、縦棒=1点, 横棒=1点, 対角線=[0,1)点とする。

　　     あ　い　う　あ
     ○─○─○─○─○
   　│＼│　│　│＼│
   あ○─○─○─○─○
   　│　│＼│　│　│
   い○─○─○─○─○
　   │　│　│＼│　│
   う○─○─○─○─○

diagonals: {(0, 0), (0, 5), (1, 1), (2, 2)} // あ, あ, い, う
remove: {3} // え
insert: {3, 4, 6} // え, お, お

通常の最短経路問題として解け、たぶん下のようになる。

　　     あ　い　う　あ
     ○
   　　＼
   あ　　○
   　　　　＼
   い　　　　○
　   　　　　　＼
   う　　　　　　○─○

distance: 1
diagonals: {(0, 0), (1, 1), (2, 2)} // あ, い, う
remove: {3} // え
insert: {3, 4, 6} // え, お, お

下に移動することを挿入、右に移動することを削除、斜めに移動することを保持とすると、左上から右下への最短経路は、変更前のテキストから変更後のテキストへの最小エディット方法に等しい。ただし、最短経路の計算の際にいくつか行と列を削除しているので、それを復元する必要がある。

　　     あ　い　う　え　お　あ　お
     ○
   　　＼
   あ　　○
   　　　　＼
   い　　　　○
　   　　　　　＼
   う　　　　　　○
     　　　　　　┃
   か　　　　　　●━●━●─○━●
distance: 5

結果として、最小エディット距離は5となる。これは、先ほどの1に|remove|(=1)と|insert|(=3)を足した数に等しい。

diffっぽく書くとこうなる。

 あ
 い
 う
-か
+え
+お
+あ
+お