本日のメモ - diff(1) のアルゴリズムとエディット距離についての参考サイト

2008/03/16

ちょっと diff(1) のアルゴリズムを調べる用事があったので,エディット距離(edit distance)について調べ物……。diff(1) のアルゴリズム自体については,津田さんが説明してくださっているんですけれど,あたしゃそれ以前に,そもそも LCS(Longest Common Subsequence)と SED(Shortest Edit Distance)がどんなもんなのか,知らんかったのでした。

で,英語版の Wikipedia を見たところ,それっぽい説明があったのでメモ。てか,そろそろ専門書を読んだ方がいいかなぁ。

In information theory and computer science, the edit distance between two strings of characters is the number of operations required to transform one of them into the other.

一応,訳を当てておく。

情報理論およびコンピュータサイエンスにおいて,2文字列間のエディット距離とは,一方の文字列を他方の文字列に変換するのに必要な操作の数をいう。

「操作」というのは,具体的には「追加」「削除」「置換」のこと。ここで,元の文字列を全部削除して,変換先の文字列を全部追加すれば,一方の文字列を他方の文字列に変換したことになるわけですけれど,操作の数が多すぎる(コストがかかる)。diff(1) の問題にしてみたら,差分を取ったことにならない(上書きと同じになる)ので,最小エディット距離(SED)が問題になる……と。つまるところ,できるだけ操作の数を減らして(変更しなくていいところは変更しない),変換した時の操作が diff(1) の結果と等しくなるわけですね。なるほど。

あとは SED を求めるアルゴリズム……と。参考サイトをメモ。日本語での説明はあまりないんだなぁ……。

Site Navigation
SNS Accounts (@aian)

普段はここら辺に住んでいます.