Wie kann ich mithilfe der Levenshtein-Distanz effizient ähnliche Begriffe in einer MySQL-Datenbank finden?

Ähnliche Begriffe in MySQL mithilfe der Levenshtein-Distanz finden

Die Levenshtein-Distanz ist ein Maß für die Ähnlichkeit zwischen zwei Zeichenfolgen. Es kann verwendet werden, um ähnliche Begriffe in einer Datenbank zu finden, was für Aufgaben wie Autovervollständigung und Rechtschreibprüfung nützlich sein kann.

Eine Möglichkeit, ähnliche Begriffe in MySQL zu finden, ist die Verwendung der Funktion levenshtein(). Diese Funktion verwendet zwei Zeichenfolgen als Eingabe und gibt den Levenshtein-Abstand zwischen ihnen zurück. Der folgende PHP-Code zeigt, wie die Funktion levenshtein() verwendet wird, um ähnliche Begriffe in einer Datenbank zu finden:

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

Dieser Ansatz kann jedoch ineffizient sein, wenn die Datenbank eine große Anzahl von Begriffen enthält, z es erfordert eine separate Abfrage für jeden Begriff. Um die Effizienz zu verbessern, ist es möglich, mit einer einzigen Abfrage alle Begriffe zu finden, die innerhalb eines bestimmten Levenshtein-Abstands vom Eingabebegriff liegen.

Dazu müssen Sie eine MySQL-Funktion verwenden, um den Levenshtein-Abstand zu berechnen . Die folgende MySQL-Funktion kann verwendet werden:

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;

Sobald Sie diese Funktion erstellt haben, können Sie sie verwenden, um mit einer einzigen Abfrage ähnliche Begriffe in einer Datenbank zu finden. Die folgende Abfrage findet alle Begriffe in der Worttabelle, die innerhalb eines Levenshtein-Abstands von 4 vom Eingabebegriff liegen:

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

Diese Abfrage gibt eine Liste aller Begriffe zurück, die innerhalb eines Levenshtein-Abstands von 4 liegen der Eingabebegriff, sortiert in aufsteigender Reihenfolge der Levenshtein-Entfernung.

Das obige ist der detaillierte Inhalt vonWie kann ich mithilfe der Levenshtein-Distanz effizient ähnliche Begriffe in einer MySQL-Datenbank finden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!