Wie berechnet man die Levenshtein-Distanz effizient in MySQL und PHP?

Levenshtein-Distanzberechnung in MySQL und PHP

Die Levenshtein-Distanz ist eine beliebte Metrik zur Messung der Ähnlichkeit zwischen zwei Zeichenfolgen. Es findet in einer Vielzahl von Szenarien Anwendung, insbesondere bei der Rechtschreibprüfung und in Suchmaschinen. In diesem Artikel wird erläutert, wie Sie mit PHP den Levenshtein-Abstand zwischen einem bestimmten Begriff und allen Begriffen in einer MySQL-Datenbank berechnen.

Ursprüngliche PHP-Implementierung

Der ursprüngliche PHP-Code, den Sie bereitgestellt haben fragt die Datenbank ab, um alle Begriffe abzurufen, und führt dann eine Levenshtein-Distanzberechnung für jeden Begriff in PHP durch. Dieser Ansatz ist ineffizient, da er mehrere Datenbankabfragen erfordert.

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

Verbesserte MySQL-Abfrage

Um die Effizienz zu verbessern, können Sie die integrierte LEVENSHTEIN()-Funktion von MySQL nutzen . Diese Funktion berechnet den Levenshtein-Abstand zwischen zwei Zeichenfolgen, sodass PHP diese Berechnungen nicht mehr durchführen muss.

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

Diese Abfrage ruft alle Begriffe ab, deren Levenshtein-Abstand vom angegebenen Begriff in einen angegebenen Bereich (0-4) fällt in diesem Fall). Durch die Ausführung dieser einzelnen Abfrage können Sie die gewünschten Ergebnisse ohne den Aufwand mehrerer Datenbankabfragen und PHP-Berechnungen erhalten.

Das obige ist der detaillierte Inhalt vonWie berechnet man die Levenshtein-Distanz effizient in MySQL und PHP?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!