I. Préambule▲
Les méthodes de rapprochement de données que nous allons voir se basent sur des fonctions qui mesurent le rapprochement ou l'éloignement de deux chaines de caractères.
Ces méthodes sont destinées à trouver la bonne valeur dans une table référençant des valeurs exactes à partir de données incorrectes ou imprécises. Elles s'avèrent souvent utiles à la construction de certaines solutions d'informatique décisionnelle afin de qualifier les données lors de la phase de migration (cadre de l'ETL, ou ELT).
II. Distance de Levenshtein▲
La distance de Levenshtein doit son nom à Vladimir Levenshtein qui l'a définie en 1965.
On appelle distance de Levenshtein entre deux mots source et cible le coût minimal pour aller de source à cible en effectuant des opérations élémentaires telles que :
- substitution d'un caractère ;
- ajout dans d'un caractère ;
- suppression d'un caractère.
En associant à chacune des opérations un poids, on trouve le coût par sommation des poids des différentes opérations.
La distance de Levenshtein opère généralement sur des données de type chaine de caractères, mais on peut l'employer sur toutes chaines de symboles et en particulier sur des données binaires.
L'algorithme présenté, d'une forte complexité (m x n opérations), peut être écrit de manière simplifiée à l'aide d'une matrice que nous élaborerons à l'aide d'une table. Cela n'en reste pas moins un algorithme couteux…
C'est pourquoi nous allons voir une première implémentation basique de cette fonction, ainsi qu'une implémentation particulière limitant la profondeur de calcul afin de donner des résultats plus rapidement.
Notons d'ores et déjà qu'il n'y a pas une seule implémentation de la distance de Levenshtein, mais toute une famille d'algorithmes qui considèrent ou non telle ou telle opération et qui valuent les différents poids en fonction du problème à traiter.
Par exemple en SQL on peut considérer que :
- si le type de données est CHAR et que la substitution est valuée à 1 alors l'ajout comme la suppression d'un caractère peut être valué à 3 du fait du décalage nécessaire dans la chaine ;
- en revanche, si le type de données est VARCHAR et que la substitution est valuée à 1 alors l'ajout peut être valué à 9 du fait de la nécessité d'agrandir l'espace de stockage pour ce faire, mais pour la suppression cette valuation peut rester à 4, car il n'est pas nécessaire de réajuster l'espace de stockage, mais juste de modifier la valeur du paramètre qui spécifie la longueur réelle de la donnée stockée.
Bref tout dépend du point de vue dans lequel on se place.
III. L'Implémentation du Levenshtein « standard »▲
Dans nos exemples nous avons considéré que toutes les opérations de l'algorithme de Levenshtein devaient être valuées à 1.
Par exemple pour aller du mot DEPORTA au mot PORTEURS, il nous faut six opérations unitaires :
|
1 |
suppression du D |
EPORTA |
|---|---|---|
|
2 |
suppression du E |
PORTA |
|
3 |
modification du A en E |
PORTE |
|
4 |
ajout du U |
PORTEU |
|
5 |
ajout du R |
PORTEUR |
|
6 |
ajout du S |
PORTEURS |
Voici une première implémentation de l'algorithme en Transact SQL :
CREATE FUNCTION F_DISTANCE_LEVENSHTEIN (@SOURCE VARCHAR(8000),
@CIBLE VARCHAR(8000))
RETURNS INT AS
BEGIN
-- gestion des effets de bord
-- null en entrée
IF @SOURCE IS NULL OR @CIBLE IS NULL
RETURN NULL
-- identique
IF @SOURCE = @CIBLE
RETURN 0
DECLARE @LN_SOURCE INT
DECLARE @LN_CIBLE INT
SET @LN_SOURCE = LEN(@SOURCE) + 1
SET @LN_CIBLE = LEN(@CIBLE) + 1
-- chaine vide avec chaine pleine
IF @LN_SOURCE= 1 OR @LN_CIBLE = 1
BEGIN
RETURN @LN_SOURCE + @LN_CIBLE - 2
END
DECLARE @MATRICE TABLE(ID Int, Valeur INT)
DECLARE @i INT
DECLARE @j INT
DECLARE @tmp Int
DECLARE @v1 Int
DECLARE @v2 Int
DECLARE @v3 Int
DECLARE @Vmin Int
DECLARE @COUT INT
/* Initialisation de la MATRICE */
SET @i = 0
WHILE (@i < @LN_SOURCE*@LN_CIBLE)
BEGIN
INSERT INTO @MATRICE VALUES (@i, 0)
SET @i = @i + 1
END
/* Initialisation de la premiere ligne */
SET @i = 0
WHILE (@i < @LN_SOURCE)
BEGIN
SET @tmp = 0
UPDATE @MATRICE SET Valeur = @i
WHERE ID = @tmp
SET @i = @i + 1
END
/* initialisation de la premiere colonne */
SET @i = 0
WHILE @i < @LN_CIBLE
BEGIN
SET @tmp = @i * @LN_SOURCE
UPDATE @MATRICE SET Valeur = @i
WHERE ID = @tmp
SET @i = @i + 1
END
/* On compare les deux chaines */
SET @i = 1
WHILE @i <@LN_SOURCE /* Colonne */
BEGIN
SET @j = 1
WHILE @j < @LN_CIBLE /* Ligne */
BEGIN
/* On regarde si les caractères correspondent */
IF SUBSTRING(@SOURCE, @i, 1) = SUBSTRING(@CIBLE, @j, 1)
/* EGALITE */
SET @COUT = 0
ELSE
/* SUBSTITUTION, INSERTION */
SET @COUT = 1
/* Lecture de la case de gauche */
SELECT @v1 = Valeur+1
FROM @MATRICE
WHERE ID = @j * @LN_SOURCE + @i - 1
/* Lecture de la case d au-dessus */
SELECT @v2 = Valeur+1
FROM @MATRICE
WHERE ID = (@j-1) * @LN_SOURCE + @i
/* Lecture de la case de diagonale gauche haute */
SELECT @v3 = @COUT+ Valeur
FROM @MATRICE
WHERE ID = (@j-1) * @LN_SOURCE + @i-1
/* On prend la valeur la plus petite et on l'insere dans la case actuelle */
IF @V1 <= @V2 AND @V1 <= @V3
SET @Vmin =@V1
ELSE
IF @V2 <= @V3
SET @Vmin = @V2
ELSE
SET @Vmin = @V3
SET @tmp = @j * @LN_SOURCE + @i
UPDATE @MATRICE
SET Valeur = @Vmin
WHERE ID = @tmp
SET @j = @j +1
END
SET @i = @i +1
END
/* On retourne le cout de la transformation */
SELECT @tmp = Valeur
FROM @MATRICE
WHERE ID = (@LN_CIBLE-1) * @LN_SOURCE + @LN_SOURCE-1
RETURN @tmp
END
GOPour en tester les effets, voici le jeu d'essais que je vous propose :
soit une table de vêtements contenant une colonne couleur et la table des couleurs cibles comportant les couleurs de référence. Nous allons utiliser la fonction pour tenter de trouver la valeur de la couleur de référence de chaque vêtement, la plus proche de celle saisie par des opérateurs insouciants…
CREATE TABLE T_VETEMENT_VTM
(VTM_DESCRIPTION VARCHAR(16),
VTM_COULEUR VARCHAR(32))
GO
INSERT INTO T_VETEMENT_VTM VALUES ('Pantalon1', 'Rouge')
INSERT INTO T_VETEMENT_VTM VALUES ('Robe2', 'Vert d''eau')
INSERT INTO T_VETEMENT_VTM VALUES ('Robe3', 'Viol.')
INSERT INTO T_VETEMENT_VTM VALUES ('Pull4', 'Jaune paille')
INSERT INTO T_VETEMENT_VTM VALUES ('Robe5', 'Verte')
INSERT INTO T_VETEMENT_VTM VALUES ('Pantalon6', 'Gris bleu')
INSERT INTO T_VETEMENT_VTM VALUES ('Pantalon7', 'Vert')
INSERT INTO T_VETEMENT_VTM VALUES ('Robe8', 'Rouge')
INSERT INTO T_VETEMENT_VTM VALUES ('Pull9', 'blanc')
INSERT INTO T_VETEMENT_VTM VALUES ('Robe10', 'Blanche')
INSERT INTO T_VETEMENT_VTM VALUES ('Pantalon11', 'Gris souris')
INSERT INTO T_VETEMENT_VTM VALUES ('Robe12', 'rose')
INSERT INTO T_VETEMENT_VTM VALUES ('Pull13', 'bleue')
INSERT INTO T_VETEMENT_VTM VALUES ('Pantalon14', 'Rouge brique')
INSERT INTO T_VETEMENT_VTM VALUES ('Pull15', 'Marron')
INSERT INTO T_VETEMENT_VTM VALUES ('Chemise16', 'Vrt')
INSERT INTO T_VETEMENT_VTM VALUES ('Chemise17', 'Blenc')
GO
CREATE TABLE T_REF_COULEUR_RCL
(RCL_COULEUR VARCHAR(16))
GO
INSERT INTO T_REF_COULEUR_RCL VALUES ('Noir')
INSERT INTO T_REF_COULEUR_RCL VALUES ('Blanc')
INSERT INTO T_REF_COULEUR_RCL VALUES ('Vert')
INSERT INTO T_REF_COULEUR_RCL VALUES ('Jaune')
INSERT INTO T_REF_COULEUR_RCL VALUES ('Bleu')
INSERT INTO T_REF_COULEUR_RCL VALUES ('Rouge')
INSERT INTO T_REF_COULEUR_RCL VALUES ('Rose')
INSERT INTO T_REF_COULEUR_RCL VALUES ('Violet')
INSERT INTO T_REF_COULEUR_RCL VALUES ('Noir')
INSERT INTO T_REF_COULEUR_RCL VALUES ('Gris')
INSERT INTO T_REF_COULEUR_RCL VALUES ('Marron')
GOLa requête suivante va nous donner une approche de la solution :
SELECT VTM_DESCRIPTION, VTM_COULEUR, RCL_COULEUR,
dbo.F_DISTANCE_LEVENSHTEIN(VTM_COULEUR, RCL_COULEUR) AS DL
FROM T_VETEMENT_VTM V
CROSS JOIN T_REF_COULEUR_RCL C
WHERE dbo.F_DISTANCE_LEVENSHTEIN(VTM_COULEUR, RCL_COULEUR)
= (SELECT MIN(dbo.F_DISTANCE_LEVENSHTEIN(VTM_COULEUR, RCL_COULEUR))
FROM T_VETEMENT_VTM
CROSS JOIN T_REF_COULEUR_RCL
WHERE VTM_DESCRIPTION = V.VTM_DESCRIPTION)
ORDER BY 1, 4 ASCVTM_DESCRIPTION VTM_COULEUR RCL_COULEUR DL
---------------- -------------------------------- ---------------- -----------
Chemise16 Vrt Vert 1
Chemise17 Blenc Blanc 1
Pantalon1 Rouge Rouge 0
Pantalon11 Gris souris Gris 1
Pantalon14 Rouge brique Vert 3
Pantalon14 Rouge brique Jaune 3
Pantalon14 Rouge brique Bleu 3
Pantalon14 Rouge brique Rouge 3
Pantalon14 Rouge brique Rose 3
Pantalon6 Gris bleu Bleu 0
Pantalon7 Vert Vert 0
Pull13 bleue Bleu 1
Pull15 Marron Marron 0
Pull4 Jaune paille Bleu 2
Pull9 blanc Blanc 0
Robe10 Blanche Blanc 2
Robe12 rose Rose 0
Robe2 Vert d'eau Vert 3
Robe2 Vert d'eau Jaune 3
Robe2 Vert d'eau Bleu 3
Robe3 Viol. Violet 2
Robe5 Verte Vert 1
Robe8 Rouge Rouge 0Mais le gros inconvénient de cette méthode, c'est qu'avec si peu de données, la combinatoire est telle que la masse des calculs nécessite déjà trois secondes de calculs sur un PC haut de gamme. C'est bien évidemment inexploitable en production avec de grosses masses d'informations.
IV. Un Levenshtein « limité »▲
L'idée est alors de limiter la profondeur de scrutation. En observant les résultats, nous nous apercevons que les bonnes approches l'ont été avec une distance de Levenshtein comprise entre 0 et 2. À 3 nous avons déjà le pantalon14 et la robe2 qui nous offrent trop de correspondances.
Nous pouvons introduire dans le code cette limitation en modifiant l'algorithme comme suit :
CREATE FUNCTION F_DISTANCE_LEVENSHTEIN_LIMITE (@SOURCE VARCHAR(8000),
@CIBLE VARCHAR(8000),
@LIMITE INT)
RETURNS INT AS
BEGIN
-- gestion des effets de bord
-- null en entrée
IF @SOURCE IS NULL OR @CIBLE IS NULL OR @LIMITE IS NULL
RETURN NULL
-- limite de 0 et différent !
IF @LIMITE = 0 AND @SOURCE <> @CIBLE RETURN NULL
-- limite inférieure à zéro :
IF @LIMITE < 0 RETURN NULL
-- identique
IF @SOURCE = @CIBLE
RETURN 0
DECLARE @LN_SOURCE INT
DECLARE @LN_CIBLE INT
SET @LN_SOURCE = LEN(@SOURCE) + 1
SET @LN_CIBLE = LEN(@CIBLE) + 1
-- chaine vide avec chaine pleine
IF @LN_SOURCE= 1 OR @LN_CIBLE = 1
BEGIN
RETURN @LN_SOURCE + @LN_CIBLE - 2
END
DECLARE @MATRICE TABLE(ID Int, Valeur INT)
DECLARE @i INT
DECLARE @j INT
DECLARE @tmp Int
DECLARE @v1 Int
DECLARE @v2 Int
DECLARE @v3 Int
DECLARE @Vmin Int
DECLARE @COUT INT/* Initialisation de la MATRICE */
SET @i = 0
WHILE (@i < @LN_SOURCE*@LN_CIBLE)
BEGIN
INSERT INTO @MATRICE VALUES (@i, 0)
SET @i = @i + 1
END
/* Initialisation de la premiere ligne */
SET @i = 0
WHILE (@i < @LN_SOURCE)
BEGIN
SET @tmp = 0
UPDATE @MATRICE SET Valeur = @i
WHERE ID = @tmp
SET @i = @i + 1
END
/* initialisation de la premiere colonne */
SET @i = 0
WHILE @i < @LN_CIBLE
BEGIN
SET @tmp = @i * @LN_SOURCE
UPDATE @MATRICE SET Valeur = @i
WHERE ID = @tmp
SET @i = @i + 1
END
/* On compare les deux chaines */
SET @i = 1
WHILE @i <@LN_SOURCE /* Colonne */
BEGIN
SET @j = 1
WHILE @j < @LN_CIBLE /* Ligne */
BEGIN
/* On regarde si les caractères correspondent */
IF SUBSTRING(@SOURCE, @i, 1) = SUBSTRING(@CIBLE, @j, 1)
/* EGALITE */
SET @COUT = 0
ELSE
/* SUBSTITUTION, INSERTION */
SET @COUT = 1
/* Lecture de la case de gauche */
SELECT @v1 = Valeur+1
FROM @MATRICE
WHERE ID = @j * @LN_SOURCE + @i - 1
/* Lecture de la case d au-dessus */
SELECT @v2 = Valeur+1
FROM @MATRICE
WHERE ID = (@j-1) * @LN_SOURCE + @i
/* Lecture de la case de diagonale gauche haute */
SELECT @v3 = @COUT+ Valeur
FROM @MATRICE
WHERE ID = (@j-1) * @LN_SOURCE + @i-1
/* On prend la valeur la plus petite et on l'insere dans la case actuelle */
IF @V1 <= @V2 AND @V1 <= @V3
SET @Vmin =@V1
ELSE
IF @V2 <= @V3
SET @Vmin = @V2
ELSE
SET @Vmin = @V3
SET @tmp = @j * @LN_SOURCE + @i
UPDATE @MATRICE
SET Valeur = @Vmin
WHERE ID = @tmp
-- si la limite est dépassée, on retourne NULL !
IF EXISTS(SELECT *
FROM @MATRICE
WHERE ID = (@LN_CIBLE-1) * @LN_SOURCE + @LN_SOURCE-1
AND Valeur > @LIMITE)
RETURN NULL
SET @j = @j +1
END
SET @i = @i +1
END
/* On retourne le cout de la transformation */
SELECT @tmp = Valeur
FROM @MATRICE
WHERE ID = (@LN_CIBLE-1) * @LN_SOURCE + @LN_SOURCE-1
RETURN @tmp
ENDDans notre cas, en utilisant une limite de 2, nous obtenons une réponse déjà plus consistante :
-- les meilleures approches avec une limite de 2
SELECT VTM_DESCRIPTION, VTM_COULEUR, RCL_COULEUR,
dbo.F_DISTANCE_LEVENSHTEIN(VTM_COULEUR, RCL_COULEUR) AS DL
FROM T_VETEMENT_VTM V
CROSS JOIN T_REF_COULEUR_RCL C
WHERE dbo.F_DISTANCE_LEVENSHTEIN_LIMITE(VTM_COULEUR, RCL_COULEUR, 2)
= (SELECT MIN(dbo.F_DISTANCE_LEVENSHTEIN_LIMITE(VTM_COULEUR,
RCL_COULEUR, 2))
FROM T_VETEMENT_VTM
CROSS JOIN T_REF_COULEUR_RCL
WHERE VTM_DESCRIPTION = V.VTM_DESCRIPTION)
ORDER BY 1, 4 ASC
VTM_DESCRIPTION VTM_COULEUR RCL_COULEUR DL
---------------- -------------------------------- ---------------- -----------
Chemise16 Vrt Vert 1
Chemise17 Blenc Blanc 1
Pantalon1 Rouge Rouge 0
Pantalon11 Gris souris Gris 1
Pantalon6 Gris bleu Bleu 0
Pantalon7 Vert Vert 0
Pull13 bleue Bleu 1
Pull15 Marron Marron 0
Pull4 Jaune paille Bleu 2
Pull9 blanc Blanc 0
Robe10 Blanche Blanc 2
Robe12 rose Rose 0
Robe3 Viol. Violet 2
Robe5 Verte Vert 1
Robe8 Rouge Rouge 0Vous noterez cependant qu'il existe toujours des dissemblances. Par exemple le Pantalon6 gris bleu a été trouvé plutôt bleu que gris… Quant au Pull4 il a été trouvé bleu alors qu'il est jaune paille. En fait la distance de Levenshtein se révèle très peu crédible quand les occurrences ont des longueurs très différentes.
Il y a divers moyens de corriger cela.
- D'abord en valuant fortement les insertions et suppressions et faiblement les substitutions.
- Ensuite en prenant en compte la différence de longueur et en pondérant le résultat du Levenshtein.
- Enfin en utilisant d'autres mesures telles que la différence de HAMMING.
Je vous laisse travailler à modifier savamment l'algorithme de ce Levenshtein. Quant à moi, je vais vous présenter la différence de HAMMING…
V. Différence de Hamming▲
C'est tout simplement le nombre de symboles différents d'une chaine à l'autre… Il suffit de lire séquentiellement les deux chaines en comparant chaque lettre à la position n dans les deux mots. Si la lettre est identique on compte 1.
La différence ce Hamming peut être codée comme suit en Transact SQL :
CREATE FUNCTION F_DIFFERENCE_HAMMING (@SOURCE VARCHAR(8000),
@CIBLE VARCHAR(8000))
RETURNS INT
AS
BEGIN
IF @SOURCE IS NULL OR @CIBLE IS NULL RETURN NULL
IF @SOURCE = '' OR @CIBLE = '' RETURN LEN(@SOURCE) + LEN(@CIBLE)
DECLARE @COUNT INT
DECLARE @I INT, @L INT
SET @I = 1
SET @L = LEN(@SOURCE)
IF LEN(@CIBLE) > @L
SET @L = LEN(@CIBLE)
SET @COUNT = 0
WHILE @I <= @L
BEGIN
IF @I > LEN(@SOURCE)
BEGIN
SET @COUNT = @COUNT + LEN(@CIBLE) - LEN(@SOURCE) + 1
BREAK
END
IF @I > LEN(@CIBLE)
BEGIN
SET @COUNT = @COUNT + LEN(@SOURCE) - LEN(@CIBLE) + 1
BREAK
END
IF SUBSTRING(@SOURCE, @I, 1) <> SUBSTRING(@CIBLE, @I, 1)
SET @COUNT = @COUNT + 1
SET @I = @I + 1
END
RETURN @COUNT
END
GOCet algorithme est peu couteux, car linéaire et donne quelques bons résultats :
-- les meilleures approches par Hamming
SELECT VTM_DESCRIPTION, VTM_COULEUR, RCL_COULEUR,
dbo.F_DIFFERENCE_HAMMING(VTM_COULEUR, RCL_COULEUR) AS DL
FROM T_VETEMENT_VTM V
CROSS JOIN T_REF_COULEUR_RCL C
WHERE dbo.F_DIFFERENCE_HAMMING(VTM_COULEUR, RCL_COULEUR)
= (SELECT MIN(dbo.F_DIFFERENCE_HAMMING(VTM_COULEUR, RCL_COULEUR))
FROM T_VETEMENT_VTM
CROSS JOIN T_REF_COULEUR_RCL
WHERE VTM_DESCRIPTION = V.VTM_DESCRIPTION)
ORDER BY 1, 4 ASC
VTM_DESCRIPTION VTM_COULEUR RCL_COULEUR DL
---------------- -------------------------------- ---------------- -----------
Chemise16 Vrt Vert 4
Chemise16 Vrt Gris 4
Chemise17 Blenc Blanc 1
Pantalon1 Rouge Rouge 0
Pantalon11 Gris souris Gris 8
Pantalon14 Rouge brique Rouge 8
Pantalon6 Gris bleu Gris 6
Pantalon7 Vert Vert 0
Pull13 bleue Bleu 2
Pull15 Marron Marron 0
Pull4 Jaune paille Jaune 8
Pull9 blanc Blanc 0
Robe10 Blanche Blanc 3
Robe12 rose Rose 0
Robe2 Vert d'eau Vert 7
Robe3 Viol. Violet 3
Robe5 Verte Vert 2
Robe8 Rouge Rouge 0Mais notre Chemise16 est vue verte et gris tandis que la Pantalon6 est vu spécifiquement gris…
Pouvons-nous encore améliorer notre score ?
J'ai pensé à travailler sur une approche plus directe, notamment en passant, non pas par la différence, mais par le rapprochement direct des lettres. J'ai appelé cet algorithme INFERENCE BASIQUE.
VI. Inférence basique▲
Algorithme de Frédéric Brouard.
Il s'agit ni plus ni moins de comparer les lettres d'une chaine à une autre en avançant toujours dans le même sens :
- on avance lettre par lettre dans le mot cible ;
- on se positionne à la première lettre dans le mot source ;
- si une lettre est trouvée dans le mot source on compte 1 et on reste positionné à cette lettre dans le mot source ;
- la comparaison n'étant pas commutative, on recommence en inversant cible et source ;
- on renvoie alors le meilleur des deux comptages.
C'est un algorithme moins couteux que Levenshtein, mais un peu plus que Hamming.
Il peut d'ailleurs être optimisé par le fait que la scrutation inverse n'est pas nécessaire si le comptage renvoie 0 à la première passe (aucune lettre commune).
Exemple
Soit à comparer par inférence basique les mots ANNANAS et BANANE.
Première passe :
B A N A N E
A N N A N A SCette première passe donne 3 symboles communs.
Seconde passe :
A N N A N A S
B A N A N EElle donne 4 symboles communs.
L'inférence directe donne donc 4.
Voici le code de cette fonction :
CREATE FUNCTION F_INFERENCE_BASIQUE (@SOURCE VARCHAR(8000),
@CIBLE VARCHAR(8000))
RETURNS INT
AS
BEGIN
IF @SOURCE IS NULL OR @CIBLE IS NULL RETURN NULL
IF @SOURCE = '' OR @CIBLE = '' RETURN 0
DECLARE @COUNT1 INT, @COUNT2 INT
DECLARE @I INT, @J INT, @L INT
DECLARE @C CHAR(1)
SET @COUNT1 = 0
SET @COUNT2 = 0
SET @I = 1
SET @J = 1
SET @L = LEN(@SOURCE)
-- première passe source vers cible
WHILE @I <= @L
BEGIN
SET @C = SUBSTRING(@SOURCE, @I, 1)
IF CHARINDEX(@C, @CIBLE, @J) > 0
BEGIN
SET @COUNT1 = @COUNT1 + 1
SET @J = CHARINDEX(@C, @CIBLE, @J) + 1
SET @I = @I + 1
CONTINUE
END
SET @I = @I + 1
END
IF @COUNT1 = 0 RETURN 0
SET @I = 1
SET @J = 1
SET @L = LEN(@CIBLE)
-- seconde passe cible vers source
WHILE @I <= @L
BEGIN
SET @C = SUBSTRING(@CIBLE, @I, 1)
IF CHARINDEX(@C, @SOURCE, @J) > 0
BEGIN
SET @COUNT2 = @COUNT2 + 1
SET @J = CHARINDEX(@C, @SOURCE, @J) + 1
SET @I = @I + 1
CONTINUE
END
SET @I = @I + 1
END
-- le meilleur comptage
IF @COUNT1 < @COUNT2
SET @COUNT1 = @COUNT2
RETURN @COUNT1
END
GOSur notre exemple, les résultats sont éloquents :
VTM_DESCRIPTION VTM_COULEUR RCL_COULEUR IB
---------------- -------------------------------- ---------------- -----------
Chemise16 Vrt Vert 3
Chemise17 Blenc Blanc 4
Pantalon1 Rouge Rouge 5
Pantalon11 Gris souris Gris 4
Pantalon14 Rouge brique Rouge 5
Pantalon6 Gris bleu Bleu 4
Pantalon6 Gris bleu Gris 4
Pantalon7 Vert Vert 4
Pull13 bleue Bleu 4
Pull15 Marron Marron 6
Pull4 Jaune paille Jaune 5
Pull9 blanc Blanc 5
Robe10 Blanche Blanc 5
Robe12 rose Rose 4
Robe2 Vert d'eau Vert 4
Robe3 Viol. Violet 4
Robe5 Verte Vert 4
Robe8 Rouge Rouge 5La seule occurrence à ne pas avoir été tranchée est le Pantalon6 gris bleu ! C'est effectivement la seule occurrence indécidable par le simple fait d'une machine…
VII. Comparaison des temps de calcul▲
Les temps de calcul de ces différents algorithmes pour notre jeu d'essai s'établissent comme suit (les requêtes ont été lancées sans la clause ORDER BY) :
|
méthode |
Temps UC (ms) |
Temps coulé (ms) |
|---|---|---|
|
Levenshtein |
10 375 |
10 959 |
|
Levenshtein limité à 2 |
11 562 |
11 984 |
|
Hamming |
407 |
447 |
|
Inférence basique |
797 |
830 |
On s'aperçoit finalement que le Levenshtein limité ne donne pas de résultats franchement probants et que le test de limitation s'avère finalement plus couteux que sa version « libre ».
On constate que le coût de l'inférence basique est moins du double de celui de la différence de Hamming. Mais compte tenu de sa meilleure performance en matière de rapprochement de motifs il s'avère payant dans bien des cas…
VIII. De plus amples informations vous sont nécessaires ?▲
Venez en discuter sur le forum public français de Microsoft SQL Server :
news:msnews.microsoft.com/microsoft.public.fr.sqlserver
Ou sur le forum SQL Server de developpez.com :
https://www.developpez.net/forums/f49/bases-donnees/ms-sql-server/