MySQL实现Levenshtein距离算法用于模糊搜索？

Question

MySQL实现Levenshtein距离算法用于模糊搜索？

mysqldatabasealgorithmsearchlevenshtein-distance

50

我希望能够按如下方式搜索表格，以获取所有在1个差异范围内的"smith"：

数据:

O'Brien
Smithe
Dolan
Smuth
Wong
Smoth
Gunther
Smiht

我已经研究了使用Levenshtein距离，但不知道如何实现，请问有谁知道吗？

- Andrew Clark

9个回答

8

有一个Levenshtein距离函数的mysql UDF实现

https://github.com/jmcejuela/Levenshtein-MySQL-UDF

它是用C实现的，比schnaader提到的“MySQL Levenshtein距离查询”性能更好。

- Hongzheng

这个速度对于实时搜索大约200,000条记录足够快吗？ - srayner

我不确定你所说的实时是什么意思。在一个测试盒子上，它有两个Intel(R) Xeon(R) CPU E5-2680 0 @ 2.70GHz的CPU和64G内存，以下查询在0.30秒内完成：'select min(levenshtein(country, 'GC')) from countries;'。countries表有一个2个字符的country列。表中包含1M行+。 - Hongzheng

@Hongzheng，这只是两个字母，请尝试使用更高的数字进行基准测试。 - talsibony

2

@talsibony 为什么不自己尝试一下呢？ - Pablo Pazos

6

上面给出的 levenshtein <= 1 的函数是不正确的--它对于 "bed" 和 "bid" 等输入会给出错误的结果。

我修改了上面给出的 "MySQL Levenshtein distance query" 函数，加入了一个 "limit" 参数以提高其速度。如果你只关心 Levenshtein <= 1，则将 limit 设置为 "2"，该函数将返回确切的 levenshtein 距离，如果它为 0 或 1；或者如果确切的 levenshtein 距离大于等于 2，则返回 2。

这个修改使得算法的速度提高了 15% 到 50%，搜索单词越长，优势越大（因为算法可以更早地退出）。例如，在针对 20 万个单词执行与单词 "giggle" 距离为 1 的所有匹配项的搜索时，原始函数在我的笔记本电脑上需要 3 分 47 秒，而带有 "limit" 参数的版本只需要 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$$

- stopthe

5

这里可以找到Damerau-Levenshtein距离的实现： Damerau-Levenshtein算法：带有置换的Levenshtein。相比纯Levenshtein距离，它考虑了字符交换。我在schnaader的链接评论中找到了它，谢谢！

- Ponk

不幸的是，这导致它变慢了10％。然而，我已经实现了字符串长度，他建议使用最大或更小的字符串，我已经实现了仅在字符串+/- 1长度上进行比较。 - Andrew Clark

4

如果您只想知道莱文斯坦距离是否最多为1，您可以使用以下MySQL函数。

CREATE FUNCTION `lv_leq_1` (
`s1` VARCHAR( 255 ) ,
`s2` VARCHAR( 255 )
) RETURNS TINYINT( 1 ) DETERMINISTIC
BEGIN
    DECLARE s1_len, s2_len, i INT;
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), i = 1;
    IF s1 = s2 THEN
        RETURN TRUE;
    ELSEIF ABS(s1_len - s2_len) > 1 THEN
        RETURN FALSE;
    ELSE
        WHILE SUBSTRING(s1,s1_len - i,1) = SUBSTRING(s2,s2_len - i,1) DO
            SET i = i + 1;
        END WHILE;
        RETURN SUBSTRING(s1,1,s1_len-i) = SUBSTRING(s2,1,s2_len-i) OR SUBSTRING(s1,1,s1_len-i) = SUBSTRING(s2,1,s2_len-i+1) OR SUBSTRING(s1,1,s1_len-i+1) = SUBSTRING(s2,1,s2_len-i);
    END IF;
END

这基本上是编辑距离（Levenshtein distance）递归描述中的单个步骤。如果距离最多为1，则该函数返回1，否则返回0。

由于此函数未完全计算出编辑距离，因此速度更快。

您还可以修改此函数，使其通过递归调用自身，返回true，如果编辑距离最多为2或3。如果MySQL不支持递归调用，则可以复制此函数的略微修改版本两次，并调用它们。但是，您不应使用递归函数来计算精确的编辑距离。

- AbcAeffchen

你的意思是至少1个吗？ - Mark Fisher

@MarkFisher 不是，如果距离小于或等于1，则返回1（true）。 - AbcAeffchen

4

根据Chella的回答和Ryan Ginstrom的文章，模糊搜索可以如下实现：

DELIMITER $$
CREATE FUNCTION fuzzy_substring( 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;
    -- 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;
    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(0))), 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;
    SET j = 1;
    WHILE j <= s2_len DO
        SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10);
        IF c > c_temp THEN
            SET c = c_temp;
        END IF;
        SET j = j + 1;
    END WHILE;
    RETURN c;
END$$
DELIMITER ;

- D. Savina

3

您可以使用此函数：

CREATE FUNCTION `levenshtein`(s1 text, s2 text) 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

若要将其作为XX%获取，请使用此函数：

CREATE FUNCTION `levenshtein_ratio`(s1 text, s2 text) 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

- Alaa

抱歉问一个新手问题，但是当我将这个复制到一个文本文件“leven”，然后运行“. leven”时，我从MySQL 5中得到多个错误：

ERROR 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your MySQL server... near ''at line 4

. - max

3

我正在基于Levenshtein或Damerau-Levenshtein（可能是后者）为多个索引文本的搜索设置，这是基于Gonzalo Navarro和Ricardo Baeza-yates的论文：链接文本。

在构建后缀数组（参见维基百科）之后，如果您对最多有k个不匹配项的字符串感兴趣，则将搜索字符串分成k + 1个部分；其中至少一个必须完整。通过在后缀数组上进行二进制搜索来查找子字符串，然后对每个匹配片段周围的补丁应用距离函数。

- Hugh

0

我有一个特殊的k距离搜索案例，在安装了MySQL中的Damerau-Levenshtein UDF之后发现查询时间太长。我想出了以下解决方案：

我有一个非常严格的搜索空间（9个字符字符串，限制为数字值）。

创建一个新表格（或将列附加到目标表格），其中包含目标字段中每个字符位置的列。例如，我的VARCHAR（9）最终变成了9个TINYINT列+1个与我的主表匹配的Id列（为每个列添加索引）。我添加了触发器，以确保这些新列在更新主表时始终得到更新。

要执行k距离查询，请使用以下谓词：

(Column1=s[0]) + (Column2=s[1]) + (Column3=s[2]) + (Column4=s[3]) + ... >= m

其中s是您的搜索字符串，m是所需匹配字符的数量（或在我的情况下，m = 9-d，其中d是我想返回的最大距离）。

经过测试，我发现对于超过一百万行的查询，平均需要4.6秒的时间才能返回匹配的ID，但是现在只需要不到一秒钟的时间。另一个查询用于返回主表中匹配行的数据同样只需要不到一秒钟的时间。（将这两个查询合并为子查询或连接操作会导致执行时间显著延长，我不确定原因在哪里。）

虽然这不是Damerau-Levenshtein算法（不能考虑替换），但对于我的目的已经足够了。

虽然这种解决方案可能无法很好地适应更大（长度）的搜索空间，但对于这种限制性情况，它非常有效。

- greg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Arachnid · Accepted Answer

为了有效地使用Levenshtein距离进行搜索，您需要一个高效的、专门的索引，例如bk-tree。不幸的是，我所知道的没有任何数据库系统，包括MySQL，都实现了bk-tree索引。如果您要进行全文搜索而不仅仅是每行一个单词，情况就更加复杂了。一时之间，我想不出有任何方法可以对全文进行索引，并且允许基于Levenshtein距离进行搜索。