文字列類似度アルゴリズム(距離アルゴリズムの編集)

距離アルゴリズムを編集

クライテリア

原理

公式

例

実現

後記

前言
2つの文字列の類似度を比較して,通常は編集距離アルゴリズムを用いて実現した.下記は常用文字列の類似度の計算方法です.文字列の類似度の測定方法はいくつかあります.
原理
最小編集距離の原理は、2つの文字列を比較し、1つの文字列を削除し、置換し、指定された文字列の数に変換して、2つの文字列の直接の類似度を決定することです.
数式

（    ）/ Math.max(str.length, str.length)  =     

例
文字列1:bsada文字列2:asqa
文字列2を文字列1にしたいですが、ステップは以下の通りです.bsada->asda->asqaはここで3段階操作します.ですから、類似度は3/5=0.6です.もちろん、あなたもこのようにbsada->asada->asqda->asqd->asqaを操作してもいいです.
したがって、このアルゴリズムの核心は最小の操作回数を求めています.実はマトリックスで表してもいいです.
b
s
a.
d
a.
0
1
2
3
4
5
a.
1
1
2
2
3
4
s
2
2
1
2
3
4
q
3
3
2
2
3
4
a.
4
4
3
2
3
3
表を分析すると、最小距離のルールは以下の通りです.

二二文字が等しい場合、左上の数字

をとります.

二二文字が等しくなければとり、左、左上の最小数に

を加えます.
実現する

    /**
     *         
     *             ，
     *           str1  
     *
     * @param str1    1
     * @param str2    2
     * @return    
     */
    public static BigDecimal getLevenshteinDistance(String str1, String str2) {
        char[] char1 = str1.toCharArray();
        char[] char2 = str2.toCharArray();
        int[] distance = new int[str1.length() + 1];
        int[] nextDistance = new int[distance.length];
        distance[0] = 0;
        //distance    
        for (int i = 1; i < distance.length; i++) distance[i] = i;
        //         ,    
        for (int i = 0; i < char2.length; i++) {
            nextDistance[0] = i + 1;

            for (int j = 0; j < char1.length; j++) {
                int val;
                if(char2[i] == char1[j]) { //       ,       
                    val = distance[j];
                } else { //      ，    ,  ,         + 1
                    int slash = distance[j] + 1;
                    int left = distance[j + 1] + 1;
                    val = Math.min(slash, left);
                    val = Math.min(val, nextDistance[j] + 1);
                }

                nextDistance[j + 1] = val;
            }

            System.arraycopy(nextDistance, 0, distance, 0, distance.length);
        }

        return BigDecimal.valueOf(1d).subtract(BigDecimal.valueOf((double) nextDistance[nextDistance.length - 1]/Math.max(str1.length(), str2.length())));
    }

後記
編集距離アルゴリズムは確かにある程度で2つの文字列の類似度を検出することができますが、文字順序に無関心なマッチングには不適切かもしれません.たとえばabcd->dcbaはこのアルゴリズムで計算した結果、0です.