編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー

昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが

[kei2100]

文字列類似度

[suzukiMY]

『編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたもの』

[kitone]

帰納的に。Text::Levenshteinも。

[bluele]

Levenshtein Distance

[celt69cobra]

編集距離 (レーベンシュタイン距離, Levenshtein Distance)

[shrhdk]

編集距離

[rjbook]

素人にはわけわからないということはわかった(･д･)

[Untouchable]

なぜDPで解けるのかという事がとても分り易い説明。自分はDPを使うという事まで知った上で丸一日使って思い付けなかったｗ

[Nekomajin]

編集距離

[jinim8]

編集距離で並べ替えると良いのかも

[cancer6]

レーベンシュタイン距離　とか

[mooz]

Levenshtein 距離。

[tettsyun]

編集距離

[syou6162]

ん、これって系列アライメントっぽい感じか

[j0hn]

PHPラブな人が levenshtein関数の自慢をブコメでしてるかな、と思ってみに来たがそんなことしてるひとはいなかった……

[hiromark]

”説明は長いのに実装するとあっけないというのは DP でよくあることです”、にちょっと笑った。

[mamoruk]

Perl に加えて Python でも簡潔にコードを出して説明されていて、非常に参考になる解説の書き方。やっぱり擬似コードよりリアルコードのほうがいいよなぁ、と個人的には思う。

[Yuichirou]

講義テストで削除のときの漸化式が思いつかなかった記憶が。挿入が"play"―LD("appl", "play")手→"appl"―1手→"apple"に対して、削除は"play"―1手→"pla"―LD("apple", "pla")手→"apple"。操作のタイミングを逆に考えればよかったのかぁ。

[blankblank]

hogeとhgoeは２か