字符串相似度算法

相似度算法

Jaccard Similarity Coefficient、JaroWinkler 、Cosine Similarity、Levenshtein 距离编辑算法案例。

• Jaccard相似性系数衡量两个集合的相似程度，通过计算两个集合的交集大小除以并集大小得出。适用于处理文本、推荐系统、生物信息学等领域
• Cosine Similarity 余弦相似度用于度量两个向量之间的夹角余弦值，适用于文本相似性、信息检索和推荐系统等领域。它将向量投影到多维空间中，衡量它们的方向相似程度。
• Levenshtein 将一个字符串转换为另一个字符串所需的最小编辑操作数，包括插入、删除和替换。常用于拼写纠错、基因序列比对等领域。
• Jaro-Winkler距离衡量两个字符串的相似性，考虑字符匹配和位置，适用于姓名匹配、数据清洗等领域。

一、java实现

1.1 引入Maven依赖

 <dependency>
     <groupId>org.apache.commonsgroupId>
     <artifactId>commons-textartifactId>
     <version>1.10.0version>
 dependency>
1
2
3
4
5

1.2 Java测试类

import org.apache.commons.text.similarity.CosineDistance;
import org.apache.commons.text.similarity.JaccardDistance;
import org.apache.commons.text.similarity.JaroWinklerDistance;
import org.apache.commons.text.similarity.LevenshteinDistance;

public class EditDistanceTest {

    private Map<String, String> testData(){
        String goalName = "Dexter Morgan";
        HashMap<String, String> data = Maps.newHashMap();
        data.put("Jackson Morgan", goalName);
        data.put("Dex Morgan", goalName);
        data.put("Deter Morgan", goalName);
        data.put("Morgan", goalName);
        data.put("Morgan Dexter", goalName);
        data.put("MorganDexter", goalName);
        data.put("Dexter Morgan", goalName);
        data.put("DexterMorgan", goalName);
        data.put("DexterMorgan ", goalName);
        return data;
    }

    @Test
    public void testEditDistance(){

        for (Map.Entry<String, String> entry : testData().entrySet()) {

            //最后得分越高说明相似度越大, 0分表示没有任何相似度，1分则代表完全匹配
            System.out.printf("JaroWinklerDistance [%s],[%s]相似度 ===> [%s]%n", entry.getKey(), entry.getValue(),  (1-new JaroWinklerDistance().apply(entry.getKey(), entry.getValue())));

            //余弦相似度用于度量两个向量之间的夹角余弦值，适用于文本相似性、信息检索和推荐系统等领域。它将向量投影到多维空间中，衡量它们的方向相似程度。
            System.out.printf("CosineDistance 余弦相似度[%s],[%s]相似度 ===> [%s]%n", entry.getKey(), entry.getValue(),  (1- new CosineDistance().apply(entry.getKey(), entry.getValue())));

            //Jaccard相似性系数衡量两个集合的相似程度，通过计算两个集合的交集大小除以并集大小得出。适用于处理文本、推荐系统、生物信息学等领域。
            System.out.printf("JaccardDistance 杰卡德系数[%s],[%s]相似度 ===> [%s]%n", entry.getKey(), entry.getValue(),   (1-new JaccardDistance().apply(entry.getKey(), entry.getValue())));

            //两个字串之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
            Integer editLen = new LevenshteinDistance().apply(entry.getKey(), entry.getValue());
            System.out.printf("LevenshteinDistance 莱文斯坦距离[%s],[%s]相似度 ===> [%s]%n%n", entry.getKey(), entry.getValue(),    1 - (double)editLen / Math.max(entry.getKey().length() , entry.getValue().length()));
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

运行结果

JaroWinklerDistance [Dex Morgan],[Dexter Morgan]相似度 ===> [0.8994871794871795]
CosineDistance 余弦相似度[Dex Morgan],[Dexter Morgan]相似度 ===> [0.4999999999999999]
JaccardDistance 杰卡德系数[Dex Morgan],[Dexter Morgan]相似度 ===> [0.9090909090909091]
LevenshteinDistance 莱文斯坦距离[Dex Morgan],[Dexter Morgan]相似度 ===> [0.7692307692307692]

JaroWinklerDistance [Deter Morgan],[Dexter Morgan]相似度 ===> [0.9794871794871796]
CosineDistance 余弦相似度[Deter Morgan],[Dexter Morgan]相似度 ===> [0.4999999999999999]
JaccardDistance 杰卡德系数[Deter Morgan],[Dexter Morgan]相似度 ===> [0.9090909090909091]
LevenshteinDistance 莱文斯坦距离[Deter Morgan],[Dexter Morgan]相似度 ===> [0.9230769230769231]

JaroWinklerDistance [Morgan],[Dexter Morgan]相似度 ===> [0.4145299145299146]
CosineDistance 余弦相似度[Morgan],[Dexter Morgan]相似度 ===> [0.7071067811865475]
JaccardDistance 杰卡德系数[Morgan],[Dexter Morgan]相似度 ===> [0.5454545454545454]
LevenshteinDistance 莱文斯坦距离[Morgan],[Dexter Morgan]相似度 ===> [0.46153846153846156]

JaroWinklerDistance [DexterMorgan],[Dexter Morgan]相似度 ===> [0.9846153846153847]
CosineDistance 余弦相似度[DexterMorgan],[Dexter Morgan]相似度 ===> [0.0]
JaccardDistance 杰卡德系数[DexterMorgan],[Dexter Morgan]相似度 ===> [0.9090909090909091]
LevenshteinDistance 莱文斯坦距离[DexterMorgan],[Dexter Morgan]相似度 ===> [0.9230769230769231]

JaroWinklerDistance [Jackson Morgan],[Dexter Morgan]相似度 ===> [0.5128205128205128]
CosineDistance 余弦相似度[Jackson Morgan],[Dexter Morgan]相似度 ===> [0.4999999999999999]
JaccardDistance 杰卡德系数[Jackson Morgan],[Dexter Morgan]相似度 ===> [0.4666666666666667]
LevenshteinDistance 莱文斯坦距离[Jackson Morgan],[Dexter Morgan]相似度 ===> [0.5]

JaroWinklerDistance [DexterMorgan ],[Dexter Morgan]相似度 ===> [0.9692307692307692]
CosineDistance 余弦相似度[DexterMorgan ],[Dexter Morgan]相似度 ===> [0.0]
JaccardDistance 杰卡德系数[DexterMorgan ],[Dexter Morgan]相似度 ===> [1.0]
LevenshteinDistance 莱文斯坦距离[DexterMorgan ],[Dexter Morgan]相似度 ===> [0.8461538461538461]

JaroWinklerDistance [Dexter Morgan],[Dexter Morgan]相似度 ===> [1.0]
CosineDistance 余弦相似度[Dexter Morgan],[Dexter Morgan]相似度 ===> [0.9999999999999998]
JaccardDistance 杰卡德系数[Dexter Morgan],[Dexter Morgan]相似度 ===> [1.0]
LevenshteinDistance 莱文斯坦距离[Dexter Morgan],[Dexter Morgan]相似度 ===> [1.0]

JaroWinklerDistance [MorganDexter],[Dexter Morgan]相似度 ===> [0.38247863247863245]
CosineDistance 余弦相似度[MorganDexter],[Dexter Morgan]相似度 ===> [0.0]
JaccardDistance 杰卡德系数[MorganDexter],[Dexter Morgan]相似度 ===> [0.9090909090909091]
LevenshteinDistance 莱文斯坦距离[MorganDexter],[Dexter Morgan]相似度 ===> [0.0]

JaroWinklerDistance [Morgan Dexter],[Dexter Morgan]相似度 ===> [0.41346153846153855]
CosineDistance 余弦相似度[Morgan Dexter],[Dexter Morgan]相似度 ===> [0.9999999999999998]
JaccardDistance 杰卡德系数[Morgan Dexter],[Dexter Morgan]相似度 ===> [1.0]
LevenshteinDistance 莱文斯坦距离[Morgan Dexter],[Dexter Morgan]相似度 ===> [0.07692307692307687]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

二、MySQL实现

2.1 Levenshtein(莱文斯坦距离)算法实现

自定义levenshtein函数

CREATE FUNCTION `levenshtein`(s1 varchar(255), s2 varchar(255)) RETURNS int(11)
    DETERMINISTIC
BEGIN
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
    DECLARE s1_char CHAR;
    DECLARE cv0, cv1 text;
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;
    IF s1 = s2 THEN
        RETURN 0;
    ELSEIF s1_len = 0 THEN
        RETURN s2_len;
    ELSEIF s2_len = 0 THEN
        RETURN s1_len;
    ELSE
        WHILE j <= s2_len
            DO
                SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
            END WHILE;
        WHILE i <= s1_len
            DO
                SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1;
                WHILE j <= s2_len
                    DO
                        SET c = c + 1;
                        IF s1_char = SUBSTRING(s2, j, 1) THEN
                            SET cost = 0;
                        ELSE
                            SET cost = 1;
                        END IF;
                        SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
                        IF c > c_temp THEN SET c = c_temp; END IF;
                        SET c_temp = CONV(HEX(SUBSTRING(cv1, j + 1, 1)), 16, 10) + 1;
                        IF c > c_temp THEN
                            SET c = c_temp;
                        END IF;
                        SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
                    END WHILE;
                SET cv1 = cv0, i = i + 1;
            END WHILE;
    END IF;
    RETURN c;
END
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

自定义levenshtein_ratio百分比函数

CREATE FUNCTION `levenshtein_ratio`(s1 varchar(255), s2 varchar(255)) RETURNS int(11)
    DETERMINISTIC
BEGIN
    DECLARE s1_len, s2_len, max_len INT;
    SET s1_len = LENGTH(s1), s2_len = LENGTH(s2);
    IF s1_len > s2_len THEN
        SET max_len = s1_len;
    ELSE
        SET max_len = s2_len;
    END IF;
    RETURN ROUND((1 - LEVENSHTEIN(s1, s2) / max_len) * 100);
END
1
2
3
4
5
6
7
8
9
10
11
12

使用方式（查询lastname是 jackson的 top10， 按照相似度倒排）

select levenshtein_ratio('jackson', last_name), last_name, first_name, full_name
from t_list_detail
where levenshtein_ratio('jackson', last_name) >= 40
order by levenshtein_ratio('jackson', last_name) desc
limit 10;
1
2
3
4
5

三、扩展：100余种相似性算法