MySQL选择匹配字符串的最大长度

Question

我需要返回所有文本结果（如果有的话），它们共享搜索字符串常用的最大长度左边界的有限子字符串。

鉴于“的StackOverflow”的搜索中包含

"Stack", 
"Sta", 
"StackOv", 
"StackOverthrow", 
"StackOverSlow", 
"StackFlow", 
"Soverflow", 
"StackOverCrow", 
"StackOverSlow", 
etc. 

查询将返回“StackOverthrow”，因为它包含匹配字符的最大数量，以及StackOverSlow和StackOverCrow在一个独特的结果的表列组。 目前，我正在做一些效率低下的事情，首先是对第一个字符进行LIKE搜索，继续重复和扩展搜索字符串，直到找不到任何内容，并保持最后的好结果。

即

select names from table where name like 'XX%'; 


"S" ->Results 
"St"->Results 
. . 
"StackOver"->Results 
"StackOverf"-> No results (Last result returning items beginning with StackOver etc as being the correct answer) 

我知道这种做法是极其低效的，任何人都可以提供一个单一查询来实现这个结果？我知道我可以一次搜索所有组合，并筛选代码中最长的结果，但是，我认为数据库应该更好。

编辑1：注意上面的例子有点简化。 DB中绝大多数的数据是在2到10个字符之间，最常见的匹配长度约为3个字符。表中有超过10万条记录。

编辑2：道歉，我需要澄清可能有多个正确的结果，并且结果可能包含需要删除的重复项。目前我选择不同的方法效率低下很容易。

Answer 1

随着name索引，下面应该是非常高性能：

SELECT DISTINCT name 
FROM myTable 
WHERE name LIKE CASE 
    WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'S%') THEN '%' 
    WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'St%') THEN 'S%' 
    WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'Sta%') THEN 'St%' 
    WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'Stac%') THEN 'Sta%' 
    WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'Stack%') THEN 'Stac%' 
    WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackO%') THEN 'Stack%' 
    WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackOv%') THEN 'StackO%' 
    WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackOve%') THEN 'StackOv%' 
    WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackOver%') THEN 'StackOve%' 
    WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackOverf%') THEN 'StackOver%' 
    WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackOverfl%') THEN 'StackOverf%' 
    WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackOverflo%') THEN 'StackOverfl%' 
    WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackOverflow%') THEN 'StackOverflo%' 
    ELSE 'StackOverflow%' 
END 

见它sqlfiddle。

Answer 2

不知道为什么你会看最小的第一个。我会做相反的事情......先尝试最长的精确匹配，如果找不到，则一次倒退1个字符，直到找到一个。

Answer 3

您可以在创建Levenshtein Distance存储函数后执行查询。这可以为您获得最佳匹配结果。

这不是我的代码。我从here得到这个。它似乎在sqlfiddle上测试得很好。然后

CREATE FUNCTION levenshtein(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(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; 

你的查询可以是这个样子：

SELECT names, levenshtein(`names`, 'StackOverflow') as dist 
FROM mytable 
ORDER BY dist; 

下面是这个样子了上sqlfiddle。

结果看起来像这样具有最低距离为最接近的匹配：

NAMES   DIST 
StackOverthrow 3 
StackFlow  4 
Soverflow  4 
StackOv   6 
Stack   8 
Sta    10