Hatena::ブログ(Diary)

Alone Like a Rhinoceros Horn

2011-03-05

2つの文字列の編集距離を求める

unite-outline で使おうと思ったけど、ボツになったので貼っとく。

Wikipedia に載っていた擬似コードをほぼそのまま Vim script に落とし込んだだけです (^^;

レーベンシュタイン距離といわれるもので、2つの文字列がどの程度異なっているかを、文字列1を文字列2へと変形させるのに必要な手順の最小回数として求めます。帰納的なアルゴリズムになっていて、実装は意外にもシンプル。

参考
トラックバック - http://d.hatena.ne.jp/h1mesuke/20110305/p1