« そんなの関係ない♪ | メイン | 知的な距離感 »

2007年08月23日

レーベンシュタイン距離

※技術メモ

単語間や文章間の文字面の近さをあらわす。
ある単語からある単語へ変換する場合、何回、「挿入」「削除」「置換」を繰り返すと実現できるかという考え方を元にしている。
たとえば、puzzle⇒pzzlの場合、「u」の削除で1カウント、「e」の削除で1カウントなので、レーベンシュタイン距離は２。

レーベンシュタイン距離を求める手法としては、ＤＰマッチングがある。

レーベンシュタイン距離を求めるPHPの関数もあり。

ＩＢＭのページの解説がわかりやすい。

http://www-06.ibm.com/jp/developerworks/java/041217/j_j-jazzy.html

ちなみに、同じ文字数からなる単語同士を比べる場合には、「置換」の数を比べるハミング距離を見る。

投稿者 zackie : 2007年08月23日 02:41

trackback2.gif

このエントリーのトラックバックURL:
http://www.zackie.biz/blog/mt-tb.cgi/1425

comment2.gif





以上の情報を保存しますか?

※保存すると次回コメントする際に、名前、メールアドレス、ＵＲＬを書き込む手間が省けます

(HTMLタグを使うことができます)

スパムコメント対策です。
お手数ですが、画像に表示された文字列をテキストボックスに入力してください。:

※コメントをご投稿いただいた後、反映されるまでに若干の時間を要する場合がございます。ご了承ください。