レーベンシュタイン距離で文字列の類似度を計算してみる

電子書籍のタイトルをAmazonAPIに投げて、その結果からISBNを取得しようとコードを書いてるんだけど、Amazonさんの検索結果上位だからといって、必ずしも検索したい文字列に最も近い語というわけではないみたい。きっと、色々良い感じの補正をかけているのでしょう。

ただ、自分のしたい事には不要なので、仕方がないので検索結果と検索クエリの類似度をとって求めて最もマッチするものを採用することにした。

文字列の類似度はレーベシュタイン距離(編集距離)というのを求めるのが一番手軽っぽい。どうでも良いですが、レーベシュタインってなんだかカッコイイ名前ですよね。「レーベシュタイン!」とか叫ぶともれなく必殺技な感じ。ほんと、どうでも良いですね。はい。

なぜかPHPは標準関数で持っていますが、javaでは良い感じのライブラリがなかったので、Scalaでにゃるっと書いてみました。と言っても、こちらのコードを激しく参考に、というかほとんど移植させてもらっただけですけど。

コードは下記の通り。まずテストから。

続いて実装コード。

Javaからの単純移植なんで特にScalaらしくないです。気が向いたら書き直します。テストコード見てもらえれば分かる通りマルチバイトでもちゃんと動作します。途中を文字列じゃなくて文字として扱ってるので、文字コードによっては変な動作するかもですが、そこは未検証。

自分の用途だと、全角と半角を統一するとかスペースを削るとかの前処理をした方が精度が良くなったので、実際に使うときはその前処理を入れる感じですかね。

とりあえず、久しぶりにアルゴリズム的なコードを調べたり書いたりしてちょっと楽しかった。たまには頭の体操のためにもこういうの書かないとなぁ。

 

参考:

Wikipedia - レーベンシュタイン距離
naoyaのはてなダイアリー - 編集距離 (Levenshtein Distance)
Javaで編集距離 - のらくら備忘録<