Comment puis-je trouver efficacement des termes similaires dans une base de données MySQL en utilisant la distance de Levenshtein ?

Recherche de termes similaires dans MySQL à l'aide de la distance de Levenshtein

La distance de Levenshtein est une mesure de la similitude entre deux chaînes. Il peut être utilisé pour rechercher des termes similaires dans une base de données, ce qui peut être utile pour des tâches telles que la saisie semi-automatique et la vérification orthographique.

Une façon de trouver des termes similaires dans MySQL consiste à utiliser la fonction levenshtein(). Cette fonction prend deux chaînes en entrée et renvoie la distance de Levenshtein entre elles. Le code PHP suivant montre comment utiliser la fonction levenshtein() pour rechercher des termes similaires dans une 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'];
    }
}

Cependant, cette approche peut s'avérer inefficace s'il y a un grand nombre de termes dans la base de données, comme cela nécessite une requête distincte pour chaque terme. Pour améliorer l'efficacité, il est possible d'utiliser une seule requête pour trouver tous les termes qui se trouvent dans une certaine distance de Levenshtein du terme d'entrée.

Pour ce faire, vous devez utiliser une fonction MySQL pour calculer la distance de Levenshtein . La fonction MySQL suivante peut être utilisée :

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;

Une fois que vous avez créé cette fonction, vous pouvez l'utiliser pour rechercher des termes similaires dans une base de données à l'aide d'une seule requête. La requête suivante recherche tous les termes de la table de mots qui se trouvent à une distance de Levenshtein de 4 du terme d'entrée :

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

Cette requête renverra une liste de tous les termes qui se trouvent à une distance de Levenshtein de 4 de le terme d'entrée, trié par ordre croissant de distance de Levenshtein.

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!