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