【MySQL】Levenshtein编辑距离 自定义函数实现

在 上张贴 由 Hydra发表回复

Levenshtein Distance 编辑距离算法，也称字符串相似度算法。
计算从一个字符串，编辑成另一个字符串，需要的最少步骤。
例如“你好”和“你好啊”，需要加一个“啊”字，所以编辑距离为1。
该函数可以计算字段之间的相似度。

以下levenshtein为编辑距离函数，levenshtein_ratio为相似度（差距/字符串长度）百分比函数。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
--设置全局创建函数无条件信任
SET global log_bin_trust_function_creators=1;

--修改MySQL分隔符
delimiter $$

--创建levenshtein函数
CREATE FUNCTION levenshtein( s1 VARCHAR(255), s2 VARCHAR(255) )
RETURNS INT
deterministic
BEGIN
DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
DECLARE s1_char CHAR;
DECLARE cv0, cv1 varbinary(256);
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;
$$

--创建levenshtein_ratio函数
CREATE FUNCTION levenshtein_ratio( s1 VARCHAR(255), s2 VARCHAR(255) )
RETURNS INT
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;
$$

--还原MySQL分隔符
delimiter ;

 

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
--另一种实现
delimiter $$

CREATE FUNCTION similar_rate (s1 VARCHAR(255),s2 VARCHAR(255)) RETURNS FLOAT
BEGIN
DECLARE l1 INT DEFAULT 0;
DECLARE l2 INT DEFAULT 0;
DECLARE i INT DEFAULT 0;
DECLARE _ss VARCHAR(2) ;
DECLARE j INT DEFAULT 0;
DECLARE SUM INT DEFAULT 0;
SET l1=CHAR_LENGTH(s1);
SET l2=CHAR_LENGTH(s2);
IF l1=0 THEN RETURN 0;
END IF;
IF l2=0 THEN RETURN 0;
END IF;
SET i=0;
SET SUM=0;
myloop1:loop
SET i=i+1;
IF i>l1 THEN leave myloop1;
END IF;
SET _ss=substr(s1,i,1);
SET j=0;
myloop2:loop
SET j=j+1; IF j>l2 THEN
leave myloop2;
END IF;
IF _ss=substr(s2,j,1) THEN
SET SUM=SUM+1;
END IF;
END loop myloop2;
END loop myloop1;
RETURN SUM/l2;
END;

delimiter ;