Pour une implémentation UDF de la Distance de Levenshtein algorithme que vous voudrez peut-être consulter "codejanitor.com :distance de Levenshtein en tant que fonction stockée MySQL " :
CREATE FUNCTION LEVENSHTEIN (s1 VARCHAR(255), s2 VARCHAR(255))
RETURNS INT
DETERMINISTIC
BEGIN
DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
DECLARE s1_char CHAR;
DECLARE cv0, cv1 VARBINARY(256);
SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;
IF s1 = s2 THEN
RETURN 0;
ELSEIF s1_len = 0 THEN
RETURN s2_len;
ELSEIF s2_len = 0 THEN
RETURN s1_len;
ELSE
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;
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 c;
END
Construisons maintenant un cas de test, en utilisant les données que vous avez fournies dans votre question :
CREATE TABLE table_a (name varchar(20));
CREATE TABLE table_b (name varchar(20));
INSERT INTO table_a VALUES('Olde School');
INSERT INTO table_a VALUES('New School');
INSERT INTO table_a VALUES('Other, C.S. School');
INSERT INTO table_a VALUES('Main School');
INSERT INTO table_a VALUES('Too Cool for School');
INSERT INTO table_b VALUES('Old School');
INSERT INTO table_b VALUES('New ES');
INSERT INTO table_b VALUES('Other School');
INSERT INTO table_b VALUES('Main School');
INSERT INTO table_b VALUES('Hardknocks School');
Ensuite :
SELECT *
FROM table_a a
LEFT JOIN table_b b ON (a.name = b.name);
Renvoie évidemment une correspondance où les noms d'école correspondent exactement :
+---------------------+-------------+
| name | name |
+---------------------+-------------+
| Olde School | NULL |
| New School | NULL |
| Other, C.S. School | NULL |
| Main School | Main School |
| Too Cool for School | NULL |
+---------------------+-------------+
5 rows in set (0.00 sec)
Maintenant, nous pouvons essayer d'utiliser le LEVENSHTEIN fonction pour renvoyer les noms d'écoles qui ont une modifier la distance
de 2 caractères ou moins :
SELECT *
FROM table_a a
LEFT JOIN table_b b ON (LEVENSHTEIN(a.name, b.name) <= 2);
+---------------------+-------------+
| name | name |
+---------------------+-------------+
| Olde School | Old School |
| New School | NULL |
| Other, C.S. School | NULL |
| Main School | Main School |
| Too Cool for School | NULL |
+---------------------+-------------+
5 rows in set (0.08 sec)
Utilise maintenant <= 3 comme seuil de distance d'édition :
SELECT *
FROM table_a a
LEFT JOIN table_b b ON (LEVENSHTEIN(a.name, b.name) <= 3);
Nous obtenons le résultat suivant :
+---------------------+--------------+
| name | name |
+---------------------+--------------+
| Olde School | Old School |
| Olde School | Other School |
| New School | Old School |
| Other, C.S. School | NULL |
| Main School | Main School |
| Too Cool for School | NULL |
+---------------------+--------------+
6 rows in set (0.06 sec)
Notez comment cette fois Olde School correspond également à Other School , et New School correspondant à Old School aussi bien. Il s'agit probablement de faux positifs, et cela montre que la définition du seuil est très importante pour éviter les correspondances incorrectes.
Une technique courante pour résoudre ce problème consiste à prendre en considération la longueur des cordes lors de l'application d'un seuil. En fait, le site qui J'ai cité pour cette implémentation
fournit également un LEVENSHTEIN_RATIO fonction qui renvoie le rapport (en pourcentage) de la différence d'édition en fonction de la longueur des chaînes.
