JAVAで文字列の類似度スコアを算出する #Java

apache lucene を使えばすぐできる。一行でできる。
レーベンシュタイン距離法とJaroWinkler距離法がある（他にもあるが）。

レーベンシュタイン距離法

何回編集すればいいか＝距離となる。
『BitCoin Core』を『BitCoin Cash』に置き換える場合

１回目：『BitCoin C[a]re』
２回目：『BitCoin Ca[s]e』
３回目：『BitCoin Cas[h]』

なので、距離は『３』となる。

文字数はこの場合は、１２文字。１２文字中９文字は編集不要なので
スコアは９／１２＝３／４＝０．７５で７５点とする。

※ 比較する文字列の文字数が異なる場合は
より文字数が多いほうをベースとしてスコアを計算する。

一般的には、スペルチェックや剽窃のチェックに使いやすいと言われる。

JaroWinkler距離法

同じく類似度を測定するが
例する一定の範囲内に置換できる文字が存在するか、という感じで類似度を算出する。

加えて、接頭語がどれくらい一致するかも類似度を算出する際に考慮される。

『1234567890』と『0004567890』の場合、スコアは８０点くらい
『1234567890』と『1234567111』の場合、スコアは９４点くらい

一般的には、スペルミスのチェック等に効果的だと言われている

実装

Luceneに頼るのみ。Mavenで。

pom.xml

        <dependency>
            <artifactId>lucene-core</artifactId>
            <groupId>org.apache.lucene</groupId>
            <version>5.1.0</version>
        </dependency>
        <dependency>
            <artifactId>lucene-analyzers</artifactId>
            <groupId>org.apache.lucene</groupId>
            <version>3.6.1</version>
        </dependency>
        <dependency>
            <artifactId>lucene-spellchecker</artifactId>
            <groupId>org.apache.lucene</groupId>
            <version>3.6.1</version>
        </dependency>

sample

import org.apache.lucene.search.spell.JaroWinklerDistance;
import org.apache.lucene.search.spell.LevensteinDistance;

/**
 * 文字列の類似スコアを算出するサンプル
 * @author ryutaro_hakozaki
 */
public class ExecStringSimilaritySample {

    public static void main(String argv[]){

        System.out.println(
                "レーベンシュタイン距離で『BitCoin Core』と『BitCoin Cash』を比較したスコア == " 
                        + getSimilarScoreByLevenshteinDistance("BitCoin Core", "BitCoin Cash"));

        System.out.println(
                "ジャロ・ウィンクラー距離で『BitCoin Core』と『BitCoin Cash』を比較したスコア == " 
                        + getSimilarScoreByJaroWinklerDistance("BitCoin Core", "BitCoin Cash"));


    }

    /**
     * レーベンシュタイン距離で文字列の類似度を判定
     * @param s1
     * @param s2
     * @return 
     */
    private static int getSimilarScoreByLevenshteinDistance(String s1, String s2){

        // 入力チェックは割愛
        LevensteinDistance dis =  new LevensteinDistance();
        return (int) (dis.getDistance(s1, s2) * 100);
    }

    /**
     * ジャロ・ウィンクラー距離で文字列の類似度を判定
     * @param s1
     * @param s2
     * @return 
     */
    private static int getSimilarScoreByJaroWinklerDistance(String s1, String s2){

        // 入力チェックは割愛
        JaroWinklerDistance dis =  new JaroWinklerDistance();
        return (int) (dis.getDistance(s1, s2) * 100);
    }

}

実行結果

レーベンシュタイン距離で『BitCoin Core』と『BitCoin Cash』を比較したスコア == 75
ジャロ・ウィンクラー距離で『BitCoin Core』と『BitCoin Cash』を比較したスコア == 95