Bagaimanakah saya boleh mencari istilah serupa dengan cekap dalam pangkalan data MySQL menggunakan jarak Levenshtein?

Mencari Istilah Serupa dalam MySQL Menggunakan Jarak Levenshtein

Jarak Levenshtein ialah ukuran persamaan antara dua rentetan. Ia boleh digunakan untuk mencari istilah yang serupa dalam pangkalan data, yang boleh berguna untuk tugas seperti autolengkap dan semakan ejaan.

Salah satu cara untuk mencari istilah serupa dalam MySQL ialah menggunakan fungsi levenshtein(). Fungsi ini mengambil dua rentetan sebagai input dan mengembalikan jarak Levenshtein antara mereka. Kod PHP berikut menunjukkan cara menggunakan fungsi levenshtein() untuk mencari istilah yang serupa dalam pangkalan data:

$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'];
    }
}

Walau bagaimanapun, pendekatan ini boleh menjadi tidak cekap jika terdapat sejumlah besar istilah dalam pangkalan data, seperti ia memerlukan pertanyaan berasingan untuk setiap istilah. Untuk meningkatkan kecekapan, adalah mungkin untuk menggunakan pertanyaan tunggal untuk mencari semua istilah yang berada dalam jarak Levenshtein tertentu bagi istilah input.

Untuk melakukan ini, anda perlu menggunakan fungsi MySQL untuk mengira jarak Levenshtein . Fungsi MySQL berikut boleh digunakan:

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;

Setelah anda mencipta fungsi ini, anda boleh menggunakannya untuk mencari istilah yang serupa dalam pangkalan data menggunakan satu pertanyaan. Pertanyaan berikut mencari semua istilah dalam jadual perkataan yang berada dalam jarak Levenshtein 4 daripada istilah input:

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

Pertanyaan ini akan mengembalikan senarai semua istilah yang berada dalam jarak Levenshtein 4 dari istilah input, diisih dalam tertib menaik jarak Levenshtein.

Atas ialah kandungan terperinci Bagaimanakah saya boleh mencari istilah serupa dengan cekap dalam pangkalan data MySQL menggunakan jarak Levenshtein?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!