レーベンシュタイン距離を使用して、MySQL データベース内で類似した用語を効率的に見つけるにはどうすればよいですか?

レーベンシュタイン距離を使用した MySQL での類似用語の検索

レーベンシュタイン距離は、2 つの文字列間の類似性の尺度です。これは、データベース内で類似した用語を検索するために使用でき、オートコンプリートやスペル チェックなどのタスクに役立ちます。

MySQL で類似した用語を検索する 1 つの方法は、levenshtein() 関数を使用することです。この関数は 2 つの文字列を入力として受け取り、それらの間のレーベンシュタイン距離を返します。次の 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 以内にあるすべての用語のリストを返します。レーベンシュタイン距離の昇順に並べ替えられた入力用語。

以上がレーベンシュタイン距離を使用して、MySQL データベース内で類似した用語を効率的に見つけるにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。