Mysql中搜索的需求非常常见, 但是搜索的要求不尽相同, 常见的是匹配(模糊)搜索:
LIKE语句 : 使用最多的模糊查询%/_模式: 基于模式的匹配方式REGEX正则 : 相对使用的较少
LOCATE/POSITION/POSITION/INSTR等函数
关于上述几种的使用方式这里不做赘述, 自行百度即可.
例如要搜索鞋子表内名称包含jordan的鞋名, SQL长这样:
-- 直接匹配
SELECT * FROM shoe WHERE NAME LIKE '%jordan%' LIMIT 10;
-- 直接匹配
但是以上的方式都要求输入的单词或词组必须准确是内容的一部分才可以进行搜索匹配, 如果用户输入错误的词组的词语应该怎么办呢? 比如用户输入成了jodan, 但是我们的结果只有jordan呢?, 这个时候就需要纠错搜索
纠错搜索
目前来说有以下几种做法:
贝叶斯根据评分进行查询, 有兴趣的可以自行了解
莱文斯坦距离(编辑距离/levenshtein)可以有效的查找可能相似的搜索值
levenshtein()函数
这里主要说一下levenshtein()函数, 但Mysql函数中不包含这个函数, 则需要自行创建, 根据 https://gist.github.com/Kovah/df90d336478a47d869b9683766cff718 提供的方式在Mysql中创建这个函数:
-- Levenshtein function
-- Source: https://openquery.com.au/blog/levenshtein-mysql-stored-function
-- Levenshtein reference: http://en.wikipedia.org/wiki/Levenshtein_distance
-- Arjen note: because the levenshtein value is encoded in a byte array, distance cannot exceed 255;
-- thus the maximum string length this implementation can handle is also limited to 255 characters.
DELIMITER $$
DROP FUNCTION IF EXISTS LEVENSHTEIN $$
CREATE FUNCTION LEVENSHTEIN(s1 VARCHAR(255) CHARACTER SET utf8, s2 VARCHAR(255) CHARACTER SET utf8)
RETURNS INT
DETERMINISTIC
BEGIN
DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
DECLARE s1_char CHAR CHARACTER SET utf8;
-- max strlen=255 for this function
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);
END IF;
WHILE (j <= s2_len) DO
SET cv1 = CONCAT(cv1, CHAR(j)),
j = j + 1;
END WHILE;
WHILE (i <= s1_len) DO
SET s1_char = SUBSTRING(s1, i, 1),
c = i,
cv0 = CHAR(i),
j = 1;
WHILE (j <= s2_len) DO
SET c = c + 1,
cost = IF(s1_char = SUBSTRING(s2, j, 1), 0, 1);
SET c_temp = ORD(SUBSTRING(cv1, j, 1)) + cost;
IF (c > c_temp) THEN
SET c = c_temp;
END IF;
SET c_temp = ORD(SUBSTRING(cv1, j+1, 1)) + 1;
IF (c > c_temp) THEN
SET c = c_temp;
END IF;
SET cv0 = CONCAT(cv0, CHAR(c)),
j = j + 1;
END WHILE;
SET cv1 = cv0,
i = i + 1;
END WHILE;
RETURN (c);
END $$
DELIMITER ;
测试是否运行正常
1
SELECT LEVENSHTEIN('jodan', 'jordan');
- 可以使用
BENCHMARK()来测试普通查询性能
1
SELECT BENCHMARK(10000, LEVENSHTEIN('jodan', 'jordan')); -- 万次1分钟左右
注意: LEVENSHTEIN()函数的计算时间很久, 在业务中使用要考虑数据量的大小, 如果您的数据库中字符串的长度都差不多, 就会很快, 如果长短不一, 跨度比较大, 则非常之慢
添加好函数后, 匹配的SQL可以写成这样
-- 根据匹配值倒序排列, 排除超过5(包含)位置的结果
SELECT * FROM shoe
WHERE LEVENSHTEIN ("jodan", name) < 5
ORDER BY -LEVENSHTEIN ("jodan", name) < 5 DESC
LIMIT 10
当通过LEVENSHTEIN()函数查询可能相似的值, 同时还可以增加Mysql发音纠错SOUNDEX()函数的方式
SELECT * FROM shoe
WHERE SOUNDEX( NAME ) LIKE SOUNDEX( "jodan" ) AND LEVENSHTEIN ("jodan", name)
ORDER BY -LEVENSHTEIN ("jodan", name) DESC
LIMIT 10
结论
因性能问题, 很显然LEVENSHTEIN()函数在大部分情况下并不适合对输入错误的词语进行纠错, 推荐使用机器学习或ES等专业的搜索工具进行优化
查阅:
- https://blog.csdn.net/csdn_0_001/article/details/79497228
- https://zh.wikipedia.org/wiki/%E8%90%8A%E6%96%87%E6%96%AF%E5%9D%A6%E8%B7%9D%E9%9B%A2
- https://lucidar.me/en/web-dev/levenshtein-distance-in-mysql/
- https://gist.github.com/Kovah/df90d336478a47d869b9683766cff718
- https://stackoverflow.com/questions/3438833/is-levenshtein-slow-in-mysql
- https://www.joe0.com/2019/06/13/how-to-search-mysql-for-similar-words-or-typos-by-leveraging-soundex-and-levenshtein-distance-algorithms/
