Comment calculer efficacement le pourcentage de similarité de chaînes dans MySQL ?

Comment calculer la similarité de chaînes dans MySQL

Pour déterminer la similarité entre deux chaînes stockées dans MySQL, envisagez d'utiliser un algorithme efficace comme la distance de Levenshtein. Cette approche calcule le nombre de modifications d'un seul caractère (ajouts, suppressions ou substitutions) nécessaires pour transformer une chaîne en une autre.

Implémentation à l'aide des fonctions MySQL

MySQL fournit une série de fonctions pour les chaînes. manipulation. Voici un exemple de fonction (levenshtein) qui calcule la distance de Levenshtein entre deux chaînes, s1 et s2 :

CREATE FUNCTION `levenshtein`(s1 text, s2 text) RETURNS int(11)
DETERMINISTIC
BEGIN
  # Initialize variables
  DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
  DECLARE s1_char CHAR;
  DECLARE cv0, cv1 text;
  SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2),
    cv1 = 0x00, j = 1, i = 1, c = 0;

  # Check for edge cases
  IF s1 = s2 THEN
    RETURN 0;
  ELSEIF s1_len = 0 THEN
    RETURN s2_len;
  ELSEIF s2_len = 0 THEN
    RETURN s1_len;
  ELSE
    # Main loop over s1 characters
    WHILE j <= s2_len DO
      SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
    END WHILE;

    WHILE i <= s1_len DO
      SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)),
        j = 1;

      # Inner loop over s2 characters
      WHILE j <= s2_len DO
        SET c = c + 1;
        IF s1_char = SUBSTRING(s2, j, 1) THEN
          SET cost = 0;
        ELSE
          SET cost = 1;
        END IF;

        SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
        IF c > c_temp THEN SET c = c_temp; END IF;
        SET c_temp = CONV(HEX(SUBSTRING(cv1, j + 1, 1)), 16, 10) + 1;
        IF c > c_temp THEN SET c = c_temp; END IF;
        SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
      END WHILE;

      SET cv1 = cv0, i = i + 1;
    END WHILE;
  END IF;

  # Return Levenshtein distance
  RETURN c;
END

Calcul du pourcentage de similarité

Avec la distance de Levenshtein calculée, vous pouvez calculer le pourcentage de similarité comme suit :

CREATE FUNCTION `levenshtein_ratio`(s1 text, s2 text) RETURNS int(11)
DETERMINISTIC
BEGIN
  DECLARE s1_len, s2_len, max_len INT;
  SET s1_len = LENGTH(s1), s2_len = LENGTH(s2);
  IF s1_len > s2_len THEN
    SET max_len = s1_len;
  ELSE
    SET max_len = s2_len;
  END IF;
  RETURN ROUND((1 - LEVENSHTEIN(s1, s2) / max_len) * 100);
END

Par exemple, si vous avez deux chaînes dans MySQL :

SET @a = "Welcome to Stack Overflow";
SET @b = "Hello to stack overflow";

Utilisation de la fonction levenshtein_ratio :

SELECT LEVENSHTEIN_RATIO(@a, @b);

Renverra une valeur représentant le pourcentage de similarité entre les deux chaînes, par exemple. 60 pour l'exemple fourni.

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!