如何使用 Levenshtein 距離在 MySQL 資料庫中有效地找到相似術語？

使用編輯距離在 MySQL 中找出相似術語

編輯距離是兩個字串之間相似性的量測。它可用於在資料庫中尋找相似術語，這對於自動完成和拼字檢查等任務非常有用。

在 MySQL 中尋找類似術語的一種方法是使用 levenshtein() 函數。該函數將兩個字串作為輸入並傳回它們之間的編輯距離。以下PHP 程式碼示範如何使用levenshtein() 函數在資料庫中尋找類似術語：

$word = strtolower($_GET['term']);

$lev = 0;

$q = mysql_query("SELECT `term` FROM `words`");
while($r = mysql_fetch_assoc($q)) 
{ 
    $r['term'] = strtolower($r['term']); 

    $lev = levenshtein($word, $r['term']);

    if($lev >= 0 && $lev < 5)
    {
        $word = $r['term'];
    }
}

但是，如果資料庫中存在大量術語，則此方法可能效率低下，例如它需要對每個術語進行單獨的查詢。為了提高效率，可以使用單一查詢來尋找與輸入術語在一定編輯距離內的所有術語。

為此，您需要使用 MySQL 函數來計算編輯距離。可以使用以下 MySQL 函數：

CREATE FUNCTION levenshtein(s1 VARCHAR(255), s2 VARCHAR(255)) RETURNS INT
BEGIN
  DECLARE s1_len INT, s2_len INT, i INT, j INT, c INT, d INT;
  SET s1_len = LENGTH(s1), s2_len = LENGTH(s2), i = 0, j = 0, c = 0, d = 0;
  IF s1_len = 0 THEN RETURN s2_len;
  ELSEIF s2_len = 0 THEN RETURN s1_len;
  END IF;
 
  DECLARE cost_matrix INT[][] DEFAULT (SELECT * FROM (
    SELECT a.i_col, b.j_row, IF(a.i_col = 0, b.j_row, IF(b.j_row = 0, a.i_col, IF(SUBSTR(s1, a.i_col, 1) = SUBSTR(s2, b.j_row, 1), 0, 1))) AS cost
    FROM (
      SELECT 1 AS i_col
      UNION ALL
      SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9 UNION ALL SELECT 10 UNION ALL SELECT 11 UNION ALL SELECT 12 UNION ALL SELECT 13 UNION ALL SELECT 14 UNION ALL SELECT 15
    ) AS a
    CROSS JOIN
    (
      SELECT 1 AS j_row
      UNION ALL
      SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9 UNION ALL SELECT 10 UNION ALL SELECT 11 UNION ALL SELECT 12 UNION ALL SELECT 13 UNION ALL SELECT 14 UNION ALL SELECT 15
    ) AS b
  ) AS subquery);
 
  WHILE i < s1_len DO
    SET i = i + 1;
    SET cost_matrix[i][0] = i;
  END WHILE;
 
  WHILE j < s2_len DO
    SET j = j + 1;
    SET cost_matrix[0][j] = j;
  END WHILE;
 
  WHILE i <= s1_len DO
    WHILE j <= s2_len DO
      IF SUBSTR(s1, i, 1) = SUBSTR(s2, j, 1) THEN
        SET c = 0;
      ELSE
        SET c = 1;
      END IF;
      SET d = cost_matrix[i-1][j] + 1;
      IF j > 0 THEN
        SET d = LEAST(d, cost_matrix[i][j-1] + 1);
      END IF;
      IF i > 0 THEN
        SET d = LEAST(d, cost_matrix[i-1][j-1] + c);
      END IF;
 
      SET cost_matrix[i][j] = d;
      SET j = j + 1;
    END WHILE;
    SET j = 0;
    SET i = i + 1;
  END WHILE;
 
  RETURN cost_matrix[s1_len][s2_len];
END;

建立此函數後，您可以使用它透過單一查詢在資料庫中尋找類似術語。以下查詢查找單字表中與輸入術語的編輯距離在4 以內的所有術語：

$word = mysql_real_escape_string($word);
mysql_qery("SELECT `term` FROM `words` WHERE levenshtein('$word', `term`) BETWEEN 0 AND 4");

此查詢將返回與輸入術語的編輯距離在4 以內的所有術語的列表輸入項，按編輯距離升序排序。

以上是如何使用 Levenshtein 距離在 MySQL 資料庫中有效地找到相似術語？的詳細內容。更多資訊請關注PHP中文網其他相關文章！