Levenshtein 거리를 사용하여 MySQL 데이터베이스에서 유사한 용어를 어떻게 효율적으로 찾을 수 있습니까?

Levenshtein 거리를 사용하여 MySQL에서 유사 용어 찾기

Levenshtein 거리는 두 문자열 간의 유사성을 측정한 것입니다. 데이터베이스에서 유사한 용어를 찾는 데 사용할 수 있으며 이는 자동 완성 및 맞춤법 검사와 같은 작업에 유용할 수 있습니다.

MySQL에서 유사한 용어를 찾는 한 가지 방법은 levenshtein() 함수를 사용하는 것입니다. 이 함수는 두 개의 문자열을 입력으로 사용하고 두 문자열 사이의 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'];
    }
}

그러나 이 접근 방식은 데이터베이스에 많은 수의 용어가 있는 경우 비효율적일 수 있습니다. 각 용어에 대해 별도의 쿼리가 필요합니다. 효율성을 높이기 위해 단일 쿼리를 사용하여 입력 용어의 특정 Levenshtein 거리 내에 있는 모든 용어를 찾는 것이 가능합니다.

이를 위해서는 MySQL 함수를 사용하여 Levenshtein 거리를 계산해야 합니다. . 다음 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;

이 함수를 생성하면 단일 쿼리를 사용하여 데이터베이스에서 유사한 용어를 찾는 데 사용할 수 있습니다. 다음 쿼리는 단어 테이블에서 입력 용어로부터 Levenshtein 거리 4 내에 있는 모든 용어를 찾습니다.

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

이 쿼리는 입력 용어에서 Levenshtein 거리 4 내에 있는 모든 용어 목록을 반환합니다. Levenshtein 거리의 오름차순으로 정렬된 입력 용어입니다.

위 내용은 Levenshtein 거리를 사용하여 MySQL 데이터베이스에서 유사한 용어를 어떻게 효율적으로 찾을 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!