為mysql /模糊搜索實現Levenshtein距離？我希望能夠按照以下方式搜索一個表格，因為它可以獲得1個方差范圍內的所有內容。數據：奧布萊恩Smithe杜蘭Smuth皇Smoth岡瑟Smiht我已經研究過使用Levenshtein距離有沒有人知道如何實現它？
3 回答
慕姐8265434
TA貢獻1813條經驗 獲得超2個贊
上面給出的levenshtein <= 1的函數不正確 - 它給出了不正確的結果，例如“床”和“出價”。
我在第一個答案中修改了上面給出的“MySQL Levenshtein距離查詢”，以接受一個“限制”，這將加快它的速度?；旧?，如果你只關心Levenshtein <= 1，將極限設置為“2”，如果它是0或1，函數將返回精確的levenshtein距離; 如果精確的levenshtein距離為2或更大，則為2。
這個mod使它快15％到50％ - 搜索詞越長，優勢越大（因為算法可以提前保釋。）例如，搜索200,000個單詞以查找距離1的所有匹配項“傻笑”，原版在我的筆記本電腦上花了3分47秒，而“極限”版本需要1:39。當然，這些對于任何實時使用來說都太慢了。
碼：
DELIMITER $$CREATE FUNCTION levenshtein_limit_n( s1 VARCHAR(255), s2 VARCHAR(255), n INT) RETURNS INT DETERMINISTIC BEGIN DECLARE s1_len, s2_len, i, j, c, c_temp, cost, c_min INT; DECLARE s1_char CHAR; -- max strlen=255 DECLARE cv0, cv1 VARBINARY(256); SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0, c_min = 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 and c_min < n DO -- if actual levenshtein dist >= limit, don't bother computing it SET s1_char = SUBSTRING(s1, i, 1), c = i, c_min = 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; IF c < c_min THEN SET c_min = c; END IF; END WHILE; SET cv1 = cv0, i = i + 1; END WHILE; END IF; IF i <= s1_len THEN -- we didn't finish, limit exceeded SET c = c_min; -- actual distance is >= c_min (i.e., the smallest value in the last computed row of the matrix) END IF; RETURN c; END$$
侃侃爾雅
TA貢獻1801條經驗 獲得超16個贊
damerau-levenshtein距離的實現可以在這里找到： Damerau-Levenshtein算法：具有轉置 的Levenshtein對純Levenshtein距離的改進是考慮字符的交換。我在schnaader鏈接的評論中找到了它，謝謝！
添加回答
舉報
0/150
提交
取消