文字列の類似度を示す指標として、Levenshtein Distance (別名 Edit Distance。以下LDと略す)という考え方が使われている。ソースとなる文字列(s)とターゲット(t)があるとして、LDは、sをtに変換する過程で必要な文字の削除、挿入、置換の総和である。

sとtのLDをLD(s,t)と書くとして、たとえば、 LD(”test”, “tent”) = 1 LD(”test”, “past”) = 2

上記のページには、各種プログラミング言語でのLDの実装の例が紹介されている。その中には Objective-C、SQLなどもみられる。このうち、Objective-Cでの実装は、NSStringのカテゴリーとして、LDを計算する関数を実装しているので、非常に簡単に使える。

NSString *s, *t,

[s comareWithString: t];

実際にこの関数をテスト用のDBシステムに実装してみた。検索ワードが入力されるたびに、検索語とのLDが計算され、transient attributeとして保持される仕組みを作った。ユーザが指定した閾値以下のLDを持つ単語がテーブル上に表示される。

英仏、仏英、独英辞書がインポートされたテスト用のDBで試してみたところ、例えば、英語の”current” に似た言葉として、フランス語の quarante (40) crainte (恐れ)などが、また “announce”には anana (パイナップル)と面白い例がいくつかみられた。

まだ単純にLDを計算しているだけなので、すべての発音記号の違いを等価に扱っている。発音記号”列”の違いとしては小さいものの、実際の発音は大きく異なるという場合が頻繁にみられた。前回の記事にも書いたように、発音記号を似通った音のカテゴリーに分けてLDを計算する際に考慮に入れる等のアルゴリズムの実装が今後の課題になる。

(徳井)