Comment calculer efficacement la distance de Levenshtein dans MySQL et PHP ?

Calcul de la distance de Levenshtein dans MySQL et PHP

La distance de Levenshtein est une métrique populaire pour mesurer la similarité entre deux chaînes. Il trouve des applications dans une variété de scénarios, notamment dans la vérification orthographique et les moteurs de recherche. Cet article explique comment calculer la distance de Levenshtein entre un terme donné et tous les termes d'une base de données MySQL à l'aide de PHP.

Implémentation PHP originale

Le code PHP original que vous avez fourni interroge la base de données pour récupérer tous les termes puis effectue un calcul de distance de Levenshtein sur chaque terme en PHP. Cette approche est inefficace car elle nécessite plusieurs requêtes de base de données.

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

Requête MySQL améliorée

Pour améliorer l'efficacité, vous pouvez utiliser la fonction LEVENSHTEIN() intégrée de MySQL. . Cette fonction calcule la distance de Levenshtein entre deux chaînes, éliminant ainsi la nécessité pour PHP d'effectuer ces calculs.

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

Cette requête récupère tous les termes dont la distance de Levenshtein par rapport au terme donné se situe dans une plage spécifiée (0-4 dans ce cas). En exécutant cette requête unique, vous pouvez obtenir les résultats souhaités sans la surcharge de plusieurs requêtes de base de données et calculs PHP.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!