有没有办法在SQL数据库中搜索相似的单词（意思是不相同的单词）？

Question

有没有办法在MySQL数据库中搜索相似的单词（意思是不相同的单词）。例如：用户在数据库中搜索单词“abcd”，并在数据库中有一个单词“abd”，所以搜索引擎或程序询问用户“你的意思是[abd]？”，就像大多数搜索引擎中的网页？请注意，搜索词是不是现有字的一部分（不能用“像”）

Answer 1

看看Damerau-Levenshtein distance算法。它计算两个字符串之间的“距离”，并确定将一个字符串转换为另一个字符串需要多少步。两个琴弦越接近越少。

This文章显示了作为MySQL存储函数实现的算法。

该算法比LIKE或SOUNDEX好得多。

我相信Google使用众包的数据而不是算法。即如果用户输入abcd，点击后退按钮，然后立即搜索abd，然后在用户对结果不满意时建立两个搜索项之间的关系。一旦你有一个非常大的社区搜索，然后出现模式。

Answer 2

取决于它们相距多远，你可以看看同音也许..

http://dev.mysql.com/doc/refman/5.0/en/string-functions.html#function_soundex

Answer 3

退房Levenshtein_distance

Answer 4

另一种技术是在trigrams上创建索引。

Answer 5

由于戴夫·巴克的答案的链接是死的，这里是代码an archived version of the website：

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; 
     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 

要注意：

• 输入字符串的最大长度为255个字符。我相信你可以编辑该功能以支持更多需要的功能。

• 我已经用utf8_bin列上的国际字符对它进行了测试，它似乎可行，但我没有经常测试该功能。

• 我只在MySQL 5.0+上测试过它。不知道它如何在小于这个版本的版本上工作。

作为奖励我还创建了返回不同比例 （百分比）的辅助功能：相同的字符，这可不仅仅是一个直编辑距离更 有益的（想法来自这里）。

CREATE FUNCTION LEVENSHTEIN_RATIO (s1 VARCHAR(255), s2 VARCHAR(255)) 
    RETURNS INT 
    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