48

我希望能够在如下表中搜索 smith 以获得它在 1 个方差内的所有内容。

数据：

奥布莱恩
史密斯
多兰
斯穆斯
黄
斯莫斯
冈瑟
史密斯

我已经研究过使用 Levenshtein distance 有人知道如何用它来实现吗？

4

9 回答 9

12

为了使用 levenshtein 距离进行高效搜索，您需要一个高效的专用索引，例如bk-tree。不幸的是，我所知道的任何数据库系统，包括 MySQL，都没有实现 bk-tree 索引。如果您正在寻找全文搜索，而不是每行只有一个词，这会更加复杂。顺便说一句，我想不出任何方式可以以允许基于 levenshtein 距离进行搜索的方式进行全文索引。

于 2009-03-13T11:17:17.667 回答
8

Levenshtein Distance函数有一个mysql UDF实现

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

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

于 2013-11-12T03:38:07.207 回答
5

可以在此处找到 damerau-levenshtein 距离的实现： Damerau-Levenshtein algorithm: Levenshtein with transpositions 对纯 Levenshtein 距离的改进是考虑了字符的交换。我在 schnaader 链接的评论中找到了它，谢谢！

于 2009-03-13T11:48:34.707 回答
5

上面为 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$$
于 2014-08-03T19:21:33.917 回答
3

根据 Gonzalo Navarro 和 Ricardo Baeza-yates 的论文，我正在设置基于 Levenshtein 或 Damerau-Levenshtein（可能是后者）的搜索，以对索引文本进行多次搜索：链接文本

建立后缀数组后（见维基百科），如果您对与搜索字符串最多有 k 个不匹配的字符串感兴趣，请将搜索字符串分解为 k+1 个；其中至少有一个必须完好无损。通过对后缀数组的二进制搜索找到子字符串，然后将距离函数应用于每个匹配片段周围的补丁。

于 2009-05-02T23:43:23.707 回答
3

你可以使用这个功能

创建函数`levenshtein`（s1文本，s2文本）返回int（11）
    确定性
开始
    声明 s1_len、s2_len、i、j、c、c_temp、成本 INT；
    声明 s1_char CHAR；
    声明 cv0、cv1 文本；
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;
    如果 s1 = s2 那么
      返回 0；
    ELSEIF s1_len = 0 那么
      返回 s2_len;
    ELSEIF s2_len = 0 那么
      返回 s1_len;
    别的
      当 j <= s2_len 做
        SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
      结束；
      当我 <= s1_len 做
        SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1;
        当 j <= s2_len 做
          设置 c = c + 1;
          如果 s1_char = SUBSTRING(s2, j, 1) 那么  
            设置成本 = 0；其他设置成本 = 1；
          万一;
          SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + 成本；
          如果 c > c_temp 那么设置 c = c_temp; 万一;
            SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
            如果 c > c_temp 那么  
              设置 c = c_temp;  
            万一;
            SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
        结束；
        设置 cv1 = cv0, i = i + 1;
      结束；
    万一;
    返回 c;
  结尾

并将其作为 XX% 使用此功能

创建函数`levenshtein_ratio`（s1文本，s2文本）返回int（11）
    确定性
开始
    声明 s1_len、s2_len、max_len INT；
    设置 s1_len = 长度（s1），s2_len = 长度（s2）；
    如果 s1_len > s2_len 那么  
      设置 max_len = s1_len;  
    别的  
      设置 max_len = s2_len;  
    万一;
    返回回合（（1 - LEVENSHTEIN（s1，s2）/ max_len）* 100）；
  结尾
于 2011-04-29T21:04:31.047 回答
2

如果只想知道 levenshtein-distance 是否最多为 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 距离的递归描述中的一个步骤。如果距离最多为 1，则该函数返回 1，否则返回 0。

由于此函数不完全计算 levenshtein 距离，因此它要快得多。

您还可以修改此函数，使其true在 levenshtein-distance 最多为 2 或 3 时返回，方法是递归地调用它。如果 MySQL 不支持递归调用，您可以将该函数的稍微修改的版本复制两次并调用它们。但是您不应该使用递归函数来计算精确的 levenshtein 距离。

于 2014-07-01T12:50:23.073 回答
1

根据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 ;
于 2017-05-10T13:15:16.717 回答
0

I had a specialized case of k-distance searching and after installing the Damerau-Levenshtein UDF in MySQL found that the query was taking too long. I came up with the following solution:

  • I have a very restrictive search space (9 character string limited to numeric values).

Create a new table (or append columns to your target table) with columns for each character position in your target field. ie. My VARCHAR(9) ended up as 9 TINYINT columns + 1 Id column that matches my main table (add indexes for each column). I added triggers to ensure that these new columns always get updated when my main table gets updated.

To perform a k-distance query use the following predicate:

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

where s is your search string and m is the required number of matching characters (or m = 9 - d in my case where d is the maximum distance I want returned).

After testing I found that a query over 1 million rows that was taking 4.6 seconds on average was returning matching ids in less than a second. A second query to return the data for the matching rows in my main table similarly took under a second. (Combining these two queries as a subquery or join resulted in significantly longer execution times and I'm not sure why.)

Though this is not Damerau-Levenshtein (doesn't account for substitution) it suffices for my purposes.

Though this solution probably doesn't scale well for a larger (length) search space it worked for this restrictive case very well.

于 2012-04-16T04:39:26.960 回答