edit distanceと和文入力 - tomoemonの日記

先生から渡された論文のタイトルは「The greedy algorithm for edit distance with moves」。これでどんな内容かわかった人はきっとすごい人です。うちの研究室はAIBOだけじゃなく文字列のアルゴリズムも研究対象なのでこういうものもストライクゾーンなのです。

edit distanceは僕も初めて聞く用語なので調べてみましたが、日本語ではそのまま編集距離となるそうです。すなわちSという文字列とTという文字列がどれだけ近いかどうかを測るための尺度。別の言い方をするとどれだけの操作でSをTにすることができるかという単位ですね。

編集距離はレーベンシュタイン距離とも言われるようで詳しいことは以下に。
レーベンシュタイン距離 - Wikipedia

ここでいう「編集」とは通常以下の3つが用いられるそうです。

挿入：文字を挿入する
欠失：文字を削除する
置換：別の文字に置き換える

例えばSとTを以下のように定義すると編集距離はいくらになるでしょうか。
S = worldcup
T = robocup

Sのw,r,lを置換してそれぞれr,b,oにしたあとdを削除すると良さそうです。Wikipediaに載っていたアルゴリズムでPythonコードを書いてみてそれぞれの文字を突っ込んでみると編集距離は4となりました。

さてさて、この編集距離ですけど以前和文入力のタイピングソフトを作ろうとしていたときに悩んでいたことそのままの題材なのです。Sを入力した文字列、Tが正解の文字列と考えたときに二つの文字列を比較してどれだけ違いがあるかを調べる方法についていろいろ悩んだ記憶があります。

毎パソ和文系のソフトもこうやって間違いを計算しているのでしょうか。しかし、下のコードそのままだと置換（誤字）、挿入（脱字）、欠失（余字）がそれぞれ何個あるのかはわかりません。ちゃんと見てないだけで実は少し手を加えれば簡単にわかったりするのかもしれませんのであとで調べてみましょう。

というわけでedit distanceについてはある程度わかったのですが、論文のタイトルのwith movesがまだよくわかってません。しかも、その問題はNP-Hardであるとか書いてて、今度はNP-困難ってなんだっけ・・・以下略。

おまけ：レーベンシュタイン距離を求めるPythonコード

def levenshtein(str1,str2):
  d = []
  for i in range(len(str1)+1):
    d.append([0 for j in range(len(str2)+1)])
  
  for i in range(len(str1)+1):
    d[i][0] = i
  for i in range(len(str2)+1):
    d[0][i] = i
  
  for i1 in range(len(str1)):
    for i2 in range(len(str2)):
      if str1[i1] == str2[i2]:
        cost = 0
      else:
        cost = 1
      
      d[i1+1][i2+1] = min([d[i1  ][i2+1] + 1,\
                           d[i1+1][i2  ] + 1,\
                           d[i1  ][i2  ] + cost])
  return d[len(str1)-1][len(str2)-1]