有沒有辦法在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