運営しているサーバのサービスで、ある検索条件に対する結果を一覧で表示しているのですが、結果を全て表示するのではなく、なるべく似た結果を省いて表示したいという要望に駆られました。
例えば、あるタレントが出演しているDVDや番組を一覧表示するとして、全ての番組名を表示すると、同じ番組名の放送日が異なるものや、同じシリーズのＤＶＤで巻数が異なるものがたくさん表示されてしまいます。
そのため、こういうものを除外して、そのタレントが、どんな作品に出てきたかのサマリーを俯瞰できるような結果を返したいと思ったわけです。
そこで考えたのは、２つの文字列を比較して、類似度がある閾値より高ければ、同じ作品の巻数違いとか放送日違いだと見做せるのではないかということです。
そこで、２つの文字列の類似度を判定する方法を探したところ、あるんですね。世の中にはすごい人がいるものです。
良く知られた方法としては、以下の２つがあるとのことです。
どちらも、２つの文字列がどれだけ異なるかを距離(類似度)として表現しています。
方法が違えば、その結果も異なるのは当然のことで、その距離を算出する過程から、それぞれ得意な領域があります。
下記で述べた特徴は、私が少し試した結果、受けた印象ですので、利用する目的に基づいて、適切なアルゴリズムを選択されることをお勧めします。
レーベンシュタイン距離(LevenshteinDiatance)
編集距離とも呼ばれ、その言葉から想像できるように、文字の挿入や削除、置換によって、一つの文字列をもう一方の文字列に変形するのに必要な手順の最小回数から導かれます。
そのため、文字数も含めて、文字列同士の類似度が判定される傾向があると思います。
この距離の概念を考案したロシアの学者ウラジミール・レーベンシュタインにちなんで命名されたそうです。
ジャロ・ウィンクラー距離(Jaro-WinklerDiatance)
米国勢調査局で開発された方法で、2つの文字列の部分的な類似度を数値化していきます。
ある一定範囲内の文字列が交換可能かを判断するため、文字数の異なる文章でも、比較的人間の判断に近い類似度を出せるような感じがします。
Javaでの利用方法
私は、今回Javaで実験しましたので、Ｊａｖaでの利用方法を以下にメモしておこうと思います。
上記２つのアルゴリズムは、実は、Javaのテキストサーチに利用される、ApacheLuceneプロジェクトのライブラリに、どちらも含まれています。
ですから、このプロジェクトのjarを設定すれば、両方のアルゴリズムが試せてしまうというわけです。
なお、関数の戻り値はfloatで、0から1の値になります。「1に近いほど両文字列は似ている」ということです。
①ダウンロード
ここのプロジェクトページから、ライブラリをダウンロードします。
私は今回は、「lucene-3.6.1.zip 」をダウンロードしました。
②必要なjarをクラスパスに設定
上記２つの距離判定のためのクラスを利用するには、以下のjarをライブラリに設定する必要があります。
・lucene-core-3.6.1.jar
・lucene-analyzers-3.6.1.jar
・lucene-spellchecker-3.6.1.jar
③サンプルソース
では、実際に利用してみましょう。
といっても、それぞれのクラスをインスタンス化して、getDistance()のメソッドを呼ぶだけです。
こんなに簡単に利用できるなんて、素晴らしいプロジェクトですね。Lucene。
import org.apache.lucene.search.spell.JaroWinklerDistance;
import org.apache.lucene.search.spell.LevensteinDistance;
public class TestBatch {
public static void main(String[] arg) throws Exception {
String one = "今日の東京は非常に寒いです。でも、天気は快晴ですよ！";
String two = "今日の京都は非常に暑いです。";
//1に近いほど似ている
LevensteinDistance l_algo = new LevensteinDistance();
JaroWinklerDistance j_algo = new JaroWinklerDistance();
System.out.println("実行結果(LevensteinDistance)：" + l_algo.getDistance(one,two));
System.out.println("実行結果(JaroWinklerDistance)：" + j_algo.getDistance(one,two));
}
}いかがでしたでしょうか。
世の中には、文字列だけでなく、画像の比較もできる理論があるらしいので、近いうちにTryしてみたいと思います！