レーベンシュタイン距離を使って電話でのイライラを解決する

電話で自分の苗字を伝えようとしても、電話相手に正しく伝わらないことがある。私が「松前です」と告げても、電話相手は「はい、増前さまですね」と間違って復唱しやがることがある。いずれ「夏前」とか「安前」とか「松苗」とか、いろいろ間違われるようになるかもしれない。このような不運な事故を回避するには、事前に間違えられやすい苗字を洗い出しておいて、ばっちり発音を練習しておく必要がある。

さて「松前」と似ている苗字を洗い出すにはどうすればよいだろうか。そんなとき使えそうなのが「レーベンシュタイン距離」である。

「レーベンシュタイン距離」とは、ある単語を、別の単語に書き換えるために必要な、文字の挿入／削除／置換操作の回数のことである。レーベンシュタイン距離を使えば、ある単語同士がどれくらい似ているか、ということが分かる。

レーベンシュタイン距離
http://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2

ということでレーベンシュタイン距離を求めるプログラムをRubyで書いてみた。

#leven_dist.rb
STR1 = ARGV[0]
STR2 = ARGV[1]

def execute(y, x)
  if(y == 0)
    STR2.slice(0,x).length
  elsif(x == 0)
    STR1.slice(0,y).length
  else
    r1 = execute(y-1, x) + 1
    r2 = execute(y, x-1) + 1
    r3 = execute(y-1, x-1)
    r3 += 1 if STR1.slice(0,y).reverse[0] != STR2.slice(0,x).reverse[0]
    [r1,r2,r3].min
  end
end

puts execute(STR1.length, STR2.length)

では早速、どんな苗字が「松前」に似ているのか、調べてみよう。

% ruby leven_dist.rb matsumae masumae  #松前と増前             
1
% ruby leven_dist.rb matsumae natsumae  #松前と夏前
1
% ruby leven_dist.rb matsumae matsunae  #松前と松苗               
1
% ruby leven_dist.rb matsumae yasumae   #松前と安前               
2
% ruby leven_dist.rb matsumae matsumoto  #松前と松本
3
% ruby leven_dist.rb matsumae matsui   #松前と松井              
3
% ruby leven_dist.rb matsumae yamada    #松前と山田               
6

似ていれば似ているほど、小さい数字が返ってくるということになる。増前、夏前、松苗あたりは、レーベンシュタイン距離は1なので、よっぽど似ているということだ。安前もそれなり。松本、松井あたりになってくると3とかなので、まず間違えられることはないだろう。松前と山田って。全然違うし。レーベンシュタイン距離６だし。

とかとか。まあこのプログラムで本当に苗字がうんぬんの問題が解決できるとは思わないが、ある単語とある単語がどれくらい似ているか、っていうことを客観的、機械的に求めることができる、ということがわかった。文書作成ソフトのスペルチェッカー機能などにおいて、実際にこんな感じの処理をしているっぽい。比較対象は単語とかじゃなくても、データ列とかでもいい訳なので、データの類似度の算出などにも多いに使える事だろう。

ちなみに、コードだけ見てもいまいち何をやっているのか分からないので、表を使って説明してみる。たとえば「hoge」と「foga」を比較する場合は、以下のような表を作って考えると分かり易い。

	_	h	ho	hog	hoge
_	0	1	2	3	4
f	1	1	2	3	4
fo	2	2	1	2	3
fog	3	3	2	1	2
foga	4	4	3	2	2

この表は、列の文字列と行の文字列のレーベンシュタイン距離を示した表である。
たとえば"_"（空文字）を"h"に変更するには、"h"をひとつ挿入すればよい。なので距離は1
"f" => "_" なら逆に、"f"をひとつ削除すればよいので、距離は1
"f" => "h" なら fをhに１回だけ置換すればいいので、距離は1
"fo" => "ho" なら fをhに置換して、"o"はそのままでいいので、距離は1
あるセルの距離は、(1)当該セルの左隣のセルの距離+1、(2)当該セルの上のセルの距離+1、(3)当該セルの左上のセルの距離(当該セルの文字列同士の末尾が同じでない場合は+1)の３つのうち、最小のものを選べば求める事ができる。
たとえば"hoge"と"foga"の距離を求めたい場合は、(1)fogaとhogの距離+1、(2)fogとhogeの距離+1、(3)fogとhogの距離+1、の３つのうち、最小のものが、fogeとfogaの距離になる。
そうすると、hogeとfogaの距離は2となる。hをfに置換、eをeに置換、で2、ということで、合ってます。
説明がむずかしい。。。

#追記：今回のコードでは再帰を使って距離を求めていますが、よく考えれば左から一行づつ計算して行けば再帰は不要だったな