Entry

本日のメモ - 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.

Edit distance - Wikipedia, the free encyclopedia

一応,訳を当てておく。

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

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

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

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN