mysql - MySQL:如何有效地选择只有一个字符差异的字符串？

Question

在MySQL中，是否可以从与给定字符串只有一个字符差的表中选择所有字符串？
例如Iphone 5和Iphone 5s或Model x-1和Models x1

Answer 1

如果可以向MySQL添加一个用户函数，那么可以使用Levenshtein的距离。代码见this other question。
例如，您可以查询WHERE LEVENSHTEIN(description, 'iphone 5') <= 2。你会发现“iphone 5S”和“iphone 5”，这可能是一个优势。
否则，特定的案例很容易实现（例如，REGEX 'iphone.*'或类似的案例），但一般的案例将是一个噩梦。
表演
此版本被修改为接受第三个参数MAXCOST。当达到levenshtein子循环的maxcost时，搜索函数将简单地中止。排除病理性病例，并考虑到实际费用可能稍有降低（即排除12项费用可能包括12项费用的字符串，排除11项费用的字符串），这就减少了Levenshtein距离不合理的病例。你可能对那些案子不感兴趣。
因此，如果您想要距离小于3的字符串，可以使用WHERE levenshtein(string1, string2, 4) < 3。距离为3-4或以上的所有字符串现在将快速返回4，并被排除在外。
测试：

mysql> select BENCHMARK(1000,levenshtein('PIPPORIDICOLO','LUKASPERICOLO', 99));
+------------------------------------------------------------------+
| BENCHMARK(1000,levenshtein('PIPPORIDICOLO','LUKASPERICOLO', 99)) |
+------------------------------------------------------------------+
|                                                                0 |
+------------------------------------------------------------------+
1 row in set (2.50 sec)

mysql> select BENCHMARK(1000,levenshtein('PIPPORIDICOLO','LUKASPERICOLO', 3));
+-----------------------------------------------------------------+
| BENCHMARK(1000,levenshtein('PIPPORIDICOLO','LUKASPERICOLO', 3)) |
+-----------------------------------------------------------------+
|                                                               0 |
+-----------------------------------------------------------------+
1 row in set (0.08 sec)

在这里，每1000次评估的成本从2500毫秒减少到80毫秒。
这是修改后的代码。在定义新函数之前，必须删除旧函数，除非更改名称。

DELIMITER $$
CREATE FUNCTION levenshtein( s1 VARCHAR(255), s2 VARCHAR(255), maxcost INTEGER)
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(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 c > maxcost THEN
                 RETURN maxcost;
            END IF;
            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$$
DELIMITER ;