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

Levenshtein Distance Calculation in MySQL and PHP

The Levenshtein distance is a popular metric for measuring the similarity between two strings. It finds applications in a variety of scenarios, particularly in spell checking and search engines. This article explores how to compute the Levenshtein distance between a given term and all terms in a MySQL database using PHP.

Original PHP Implementation

The original PHP code you provided queries the database to retrieve all terms and then performs a Levenshtein distance calculation on each term in PHP. This approach is inefficient as it requires multiple database queries.

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

Improved MySQL Query

To improve efficiency, you can utilize MySQL's built-in LEVENSHTEIN() function. This function calculates the Levenshtein distance between two strings, eliminating the need for PHP to perform these calculations.

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

This query retrieves all terms whose Levenshtein distance from the given term falls within a specified range (0-4 in this case). By executing this single query, you can obtain the desired results without the overhead of multiple database queries and PHP calculations.

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!