Algorithme de Jaro-Winkler

Version imprimable

Bonjour à tous,

Je suis en train de travailler sur des rapprochements de données par libellé.
Une des méthodes employée consiste à utiliser l'algorithme de Jaro-Winkler.

Vous n'êtes pas obligé de vous documenter sur cet algorithme pour le problème qui occupe actuellement mes pensées, c'est finalement un problème de transformation de données (voir les deux dernières fenêtres de code).

Depuis la version 10g, Oracle propose des fonctions builtins effectuant ce travail, ici celle qui m'interesse est utl_match.jaro_winkler :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 WITH L1 AS ( select 1 id1, 'DWAYNE' as nm1 from dual union all select 2 , 'DIXON' from dual union all select 3 , 'SUMMERZ' from dual union all select 4 , 'MARTHAAA' from dual union all select 5 , 'aeQehzqOaW' from dual union all select 6 , 'THE BARON' from dual ), L2 AS ( select 1 id2, 'DUANE' as nm2 from dual union all select 2 , 'DICKSONX' from dual union all select 3 , 'FZIPP SUMMERZ ' from dual union all select 4 , ' MARHTAAA' from dual union all select 5 , 'kJUFupdeJT' from dual union all select 6 , 'THE RACE IS ON' from dual ) select L1.nm1, L2.nm2, utl_match.jaro_winkler(L1.nm1, L2.nm2)*100 as jw, utl_match.jaro_winkler(L2.nm2, L1.nm1)*100 as jw2 from L1 inner join L2 on L2.id2 = L1.id1; NM1 NM2 JW JW2 --------------- ---------------- ---------------- ---------------- DWAYNE DUANE 84 84 DIXON DICKSONX 81.3333333333333 81.3333333333333 SUMMERZ FZIPP SUMMERZ 69.047619047619 78.5714285714286 MARTHAAA MARHTAAA 92.1296296296296 92.1296296296296 aeQehzqOaW kJUFupdeJT 40 40 THE BARON THE RACE IS ON 84.2063492063492 86.7063492063492
Néanmoins j'ai deux soucis avec ces fonctions.

D'une part le résultat ne me paraît pas toujours forcément cohérent.
D'après l'algorithme, l'ordre des arguments ne devraient pas avoir d'importance, hors ici on peut obtenir des résultats différents.

D'autre part, j'ai un soucis de performance. Comparer une ligne contre une table d'un million de lignes sans optimisation particulière prend une dizaine de secondes.
Si j'optimise en travaillant avec une IOT je tombe à l'ordre de la seconde.
Passer en mode ensembliste avec jointure de table fait par contre exploser les temps de traitement.

Je pourrai contourner par du PL/SQL, mais je me dis que c'est dommage.
L'algorithme n'est finalement pas si complexe que ça et pourquoi pas le réimplémenter en SQL, en jouant avec les IOT, les partitions et le parallélisme j'ai de bons espoirs pour les performances.

J'ai un exemple de ce que je veux faire et je sais ce que je veux obtenir.
J'ai quelques règles à implémenter mais voilà je butte complètement sur l'une d'entre elle.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 WITH T1 AS ( select 6 id1, 'A' nm1 from dual union all select 8 , 'A' from dual union all select 9 , 'B' from dual union all select 10 , 'A' from dual union all select 11 , 'A' from dual ), T2 AS ( select 0 id2, 'A' nm2 from dual union all select 1 , 'B' from dual union all select 2 , 'B' from dual union all select 3 , 'B' from dual union all select 4 , 'B' from dual union all select 5 , 'A' from dual union all select 6 , 'B' from dual union all select 7 , 'A' from dual union all select 8 , 'A' from dual union all select 9 , 'B' from dual union all select 10 , 'B' from dual union all select 11 , 'B' from dual union all select 12 , 'A' from dual union all select 13 , 'A' from dual ), M AS ( select T1.*, T2.*, case when T1.nm1 = T2.nm2 then 1 else 0 end as c1, -- Règle 1 case when T1.id1 between T2.id2 - 5 and T2.id2 + 5 then 1 else 0 end as c2 -- Règle 2 -- Règle 3 ??? from T1 cross join T2 ) select M.* from M order by M.id1 asc, M.id2 asc
Je fais volontairement un produit cartésien pour commencer, si je peux affiner par la suite je le ferai.
Mes trois règles sont :

Les lettres doivent correspondre
L'écart de position entre les éléments est fixé à 5 pour cet exemple
Lorsqu'un couple est identifié avec ces deux règles dans les ordres ascendant id1 et id2, aucun de ces éléments ne doit être pris en compte par la suite

C'est bien évidement la dernière que j'ai du mal à implémenter.
J'ai essayé les fonctions analytiques, je suis persuadé qu'il s'agit de la bonne piste mais je ne trouve pas la solution.
J'ai également essayé avec model, mais là je n'ai pas le niveau requis.

A partir des données ci-dessus je veux obtenir les données suivantes :
Code:

1 2 3 4 5 6 ID1 NM1 ID2 NM2 6 A 5 A 8 A 7 A 9 B 4 B 10 A 8 A 11 A 12 A
J'ai réussi à détourner la dernière règle pour que dans certains cas ça fonctionne, mais cet à peu près est très loin de me satisfaire.

Voilà, si quelqu'un peut apporter des idées neuves qui fonctionnent j'en serai ravi et je pourrai avancer mes tests et écrire un article à ce sujet sur mon blog.

Bonjour,

Je ne suis pas sûr d'avoir tout compris à cette troisième règle.
Je verrai quelque chose comme ça :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
WITH T1 AS 
(
SELECT 6 id1, 'A' nm1 FROM dual union ALL
SELECT 8    , 'A'     FROM dual union ALL
SELECT 9    , 'B'     FROM dual union ALL
SELECT 10   , 'A'     FROM dual union ALL
SELECT 11   , 'A'     FROM dual
),   T2 AS
(
SELECT 0 id2, 'A' nm2 FROM dual union ALL
SELECT 1    , 'B'     FROM dual union ALL
SELECT 2    , 'B'     FROM dual union ALL
SELECT 3    , 'B'     FROM dual union ALL
SELECT 4    , 'B'     FROM dual union ALL
SELECT 5    , 'A'     FROM dual union ALL
SELECT 6    , 'B'     FROM dual union ALL
SELECT 7    , 'A'     FROM dual union ALL
SELECT 8    , 'A'     FROM dual union ALL
SELECT 9    , 'B'     FROM dual union ALL
SELECT 10   , 'B'     FROM dual union ALL
SELECT 11   , 'B'     FROM dual union ALL
SELECT 12   , 'A'     FROM dual union ALL
SELECT 13   , 'A'     FROM dual
), M AS
(
SELECT
    T1.*,
    T2.*,
    case
      when T1.nm1 = T2.nm2
      then 1 else 0
    end AS c1, -- Règle 1
    case
      when T1.id1 BETWEEN T2.id2 - 5
                      AND T2.id2 + 5
      then 1 else 0
    end AS c2, -- Règle 2
    coalesce(
    sum(case
           when T1.nm1 = T2.nm2
           then 1 else 0
        end 
		*
        case
           when T1.id1 BETWEEN T2.id2 - 5
                           AND T2.id2 + 5
           then 1 else 0
        end) 
    over(partition by T1.nm1,t2.nm2 order by T1.id1,T2.id2 ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING),0) as c3
FROM
    T1 CROSS JOIN T2
)
SELECT M.*
FROM M
ORDER BY
    M.id1 ASC,
    M.id2 ASC

Si c1 * c2 est différent de 0, alors les deux règles sont vérifiées.
Donc, imaginons pour c3 la somme de c1*c2 sur les lignes précédentes, groupé par nm1/nm2, ordonnés par id1/id2.
Si c3 est différent de 0, alors le couple nm1/nm2 est déjà pris en compte.
En espérant avoir bien saisi la problématique...

EDIT : Ajout du coalesce pour remplacer les valeurs NULL pour la première ligne de chaque couple.

Et non malheureusement je n'obtiens pas le résultat escompté.

Il faut imaginer qu'on parcourt les données comme le ferait un curseur PL/SQL.

Je prend le premier id1 de la table1 et je recherche le premier id2 de la table2 qui répond aux trois conditions : même lettre, distance comprise dans l'intervale et id2 jamais utilisé. Dès que j'ai un résultat je passe à l'id1 suivant.

Si je me limite dans mon exemple aux deux premiers caractères de la table1 (les id1 6 et 8).
Parmis les id2 qui respectent les deux premières règles j'en retrouve huit, trois pour id1 = 6 et cinq pour id1 = 8 :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 SELECT id1, nm1, id2, nm2 FROM M where c1 = 1 and c2 = 1 and id1 <= 8 ORDER BY M.id1 ASC, M.id2 ASC; ID1 NM1 ID2 NM2 ------- -------- ------- ------- 6 A 5 A 6 A 7 A 6 A 8 A 8 A 5 A 8 A 7 A 8 A 8 A 8 A 12 A 8 A 13 A
Mais parmis ces données la troisième règle stipule de prendre le premier id2 disponible (pas encore pris).

Ici, c'est donc le couple (6, 5) qui satisfait les trois règles pour id1 = 6.
Et pour id1 = 8, comme id2 = 5 a déjà été pris je prends le suivant c'est à dire le couple (8, 7).

Pour chaque id1 j'ai 0 ou 1 id2 correspondant, mais jamais plus.

15/07/2009, 21h58
NGasparotto

Citation:

Envoyé par Waldar

...Je suis en train de travailler sur des rapprochements de données par libellé....

SOUNDEX ?

Nicolas.

Citation:

Envoyé par Waldar

...A partir des données ci-dessus je veux obtenir les données suivantes :

Code:

1
2
3
4
5
6
ID1	NM1	ID2	NM2
6	A	5	A
8	A	7	A
9	B	4	B
10	A	8	A
11	A	12	A

...

Comme cela ?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
SQL> WITH T1 AS
  2  (
  3  SELECT 6 id1, 'A' nm1 FROM dual union ALL
  4  SELECT 8    , 'A'     FROM dual union ALL
  5  SELECT 9    , 'B'     FROM dual union ALL
  6  SELECT 10   , 'A'     FROM dual union ALL
  7  SELECT 11   , 'A'     FROM dual
  8  ),   T2 AS
  9  (
 10  SELECT 0 id2, 'A' nm2 FROM dual union ALL
 11  SELECT 1    , 'B'     FROM dual union ALL
 12  SELECT 2    , 'B'     FROM dual union ALL
 13  SELECT 3    , 'B'     FROM dual union ALL
 14  SELECT 4    , 'B'     FROM dual union ALL
 15  SELECT 5    , 'A'     FROM dual union ALL
 16  SELECT 6    , 'B'     FROM dual union ALL
 17  SELECT 7    , 'A'     FROM dual union ALL
 18  SELECT 8    , 'A'     FROM dual union ALL
 19  SELECT 9    , 'B'     FROM dual union ALL
 20  SELECT 10   , 'B'     FROM dual union ALL
 21  SELECT 11   , 'B'     FROM dual union ALL
 22  SELECT 12   , 'A'     FROM dual union ALL
 23  SELECT 13   , 'A'     FROM dual
 24  ), M as
 25  (
 26  SELECT T1.*,
 27         T2.*,
 28         row_number() over (partition by id1 order by id2) rn1,
 29         row_number() over (partition by id2 order by id1) rn2
 30  FROM T1, T2
 31  WHERE T1.id1 BETWEEN T2.id2 - 5 AND T2.id2 + 5 -- regle 2
 32  AND   T1.nm1=T2.nm2                            -- regle 1
 33  )
 34  select id1,nm1,id2,nm2
 35  from m
 36  where rn1=rn2                                  -- regle 3
 37  ORDER BY id1 ASC, id2 ASC;
 
       ID1 N        ID2 N
---------- - ---------- -
         6 A          5 A
         8 A          7 A
         9 B          4 B
        10 A          8 A
        11 A         12 A
 
SQL>

Autre declinaison similaire :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
...
), M as
(
SELECT T1.*,
       T2.*,
       decode(row_number() over (partition by id1 order by id2),
              row_number() over (partition by id2 order by id1),
              1) regle3                        -- regle 3
FROM T1, T2
WHERE T1.id1 BETWEEN T2.id2 - 5 AND T2.id2 + 5 -- regle 2
AND   T1.nm1=T2.nm2                            -- regle 1
)
select id1,nm1,id2,nm2
from m
where regle3=1                                 -- regle 3 (validation)
ORDER BY id1 ASC, id2 ASC;
 
  ID1 N        ID2 N
----- - ---------- -
    6 A          5 A
    8 A          7 A
    9 B          4 B
   10 A          8 A
   11 A         12 A

Nicolas.

Citation:

SOUNDEX ?

C'est certes un bon algorithme de reconnaissance mais étant binaire il est moins souple que l'algorithme Jaro-Winkler.
Ce dernier calcule un indice de similarité sur lequel on peut agir au moment de retourner les résultats.
Ce n'est pas le seul algorithme, ce n'est probablement pas le meilleur mais il donne d'excellents résultats lorsque l'indice de similarité est supérieur à 80%.

Citation:

WHERE rn1=rn2

Ca fait partie des solutions que j'ai essayées, et c'est une de celles qui me permet de me rapprocher le plus de la fonction initiale.
Je pensais que le test couvrait ce cas de figure mais pas en l'état, je n'ai pas été assez vigilant.

On peut le voir en modifiant l'écart de position de 5 à 1.
Modifier l'écart permet un test plus complet de la requête, voici les résultats attendus par écart :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 Ecart = 0 ID1 NM1 ID2 NM2 8 A 8 A 9 B 9 B Ecart = 1 ID1 NM1 ID2 NM2 6 A 5 A 8 A 7 A 9 B 9 B 11 A 12 A Ecart = 2 ID1 NM1 ID2 NM2 6 A 5 A 8 A 7 A 9 B 9 B 10 A 8 A 11 A 12 A Ecart = 3 ID1 NM1 ID2 NM2 6 A 5 A 8 A 7 A 9 B 6 B 10 A 8 A 11 A 12 A Ecart = 4 ID1 NM1 ID2 NM2 6 A 5 A 8 A 7 A 9 B 6 B 10 A 8 A 11 A 12 A Ecart = 5 ID1 NM1 ID2 NM2 6 A 5 A 8 A 7 A 9 B 4 B 10 A 8 A 11 A 12 A Ecart = 6 ID1 NM1 ID2 NM2 6 A 0 A 8 A 5 A 9 B 3 B 10 A 7 A 11 A 8 A Ecart = 7 ID1 NM1 ID2 NM2 6 A 0 A 8 A 5 A 9 B 2 B 10 A 7 A 11 A 8 A
Merci à vous deux pour vos entrées.

Bon, c'est vrai, certains ecarts posent probleme.
C'est donc un peu plus complique, alors voila un nouvel essai :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
SQL> WITH T1 AS
  2  (
  3  SELECT 6 id1, 'A' nm1 FROM dual union ALL
  4  SELECT 8    , 'A'     FROM dual union ALL
  5  SELECT 9    , 'B'     FROM dual union ALL
  6  SELECT 10   , 'A'     FROM dual union ALL
  7  SELECT 11   , 'A'     FROM dual
  8  ),   T2 AS
  9  (
 10  SELECT 0 id2, 'A' nm2 FROM dual union ALL
 11  SELECT 1    , 'B'     FROM dual union ALL
 12  SELECT 2    , 'B'     FROM dual union ALL
 13  SELECT 3    , 'B'     FROM dual union ALL
 14  SELECT 4    , 'B'     FROM dual union ALL
 15  SELECT 5    , 'A'     FROM dual union ALL
 16  SELECT 6    , 'B'     FROM dual union ALL
 17  SELECT 7    , 'A'     FROM dual union ALL
 18  SELECT 8    , 'A'     FROM dual union ALL
 19  SELECT 9    , 'B'     FROM dual union ALL
 20  SELECT 10   , 'B'     FROM dual union ALL
 21  SELECT 11   , 'B'     FROM dual union ALL
 22  SELECT 12   , 'A'     FROM dual union ALL
 23  SELECT 13   , 'A'     FROM dual
 24  ), ECART AS
 25  (
 26  select &ecart as ecart_valeur from dual
 27  ), T3 AS
 28  (
 29  select nm2, min(id2) min_id2, max(id2) max_id2
 30          from   T1,
 31                 T2,
 32                 ECART
 33          WHERE T1.id1 BETWEEN (T2.id2 - ecart_valeur) AND (T2.id2 + ecart_valeur)
 34          AND   T1.nm1=T2.nm2
 35          group by nm2
 36  ),M AS
 37  (
 38  SELECT T1.*,
 39         T2.*,row_number() over (partition BY id1 ORDER BY id2) rn1,
 40         row_number() over (partition BY id2 ORDER BY id1) rn2,
 41         min_id2,max_id2
 42  FROM   T1,
 43         T2,
 44         T3
 45  WHERE T2.id2 BETWEEN min_id2 AND max_id2
 46  AND   T1.nm1=T2.nm2
 47  AND   T1.nm1=T3.nm2
 48  )
 49  SELECT m.id1,nm1,id2,nm2
 50  FROM m, ecart
 51  WHERE id1 between (id2 - ecart_valeur) and (id2 + ecart_valeur)
 52  AND   decode(ecart_valeur,0,-1,rn1)=decode(ecart_valeur,0,-1,rn2)
 53  ORDER BY id1 ASC, id2 ASC;
Enter value for ecart: 0
old  26: select &ecart as ecart_valeur from dual
new  26: select 0 as ecart_valeur from dual
 
       ID1 N        ID2 N
---------- - ---------- -
         8 A          8 A
         9 B          9 B
 
Elapsed: 00:00:00.00
SQL> /
Enter value for ecart: 1
old  26: select &ecart as ecart_valeur from dual
new  26: select 1 as ecart_valeur from dual
 
       ID1 N        ID2 N
---------- - ---------- -
         6 A          5 A
         8 A          7 A
         9 B          9 B
        11 A         12 A
 
Elapsed: 00:00:00.00
SQL> /
Enter value for ecart: 2
old  26: select &ecart as ecart_valeur from dual
new  26: select 2 as ecart_valeur from dual
 
       ID1 N        ID2 N
---------- - ---------- -
         6 A          5 A
         8 A          7 A
         9 B          9 B
        10 A          8 A
        11 A         12 A
 
Elapsed: 00:00:00.00
SQL> /
Enter value for ecart: 3
old  26: select &ecart as ecart_valeur from dual
new  26: select 3 as ecart_valeur from dual
 
       ID1 N        ID2 N
---------- - ---------- -
         6 A          5 A
         8 A          7 A
         9 B          6 B
        10 A          8 A
        11 A         12 A
 
Elapsed: 00:00:00.00
SQL> /
Enter value for ecart: 4
old  26: select &ecart as ecart_valeur from dual
new  26: select 4 as ecart_valeur from dual
 
       ID1 N        ID2 N
---------- - ---------- -
         6 A          5 A
         8 A          7 A
         9 B          6 B
        10 A          8 A
        11 A         12 A
 
Elapsed: 00:00:00.00
SQL> /
Enter value for ecart: 5
old  26: select &ecart as ecart_valeur from dual
new  26: select 5 as ecart_valeur from dual
 
       ID1 N        ID2 N
---------- - ---------- -
         6 A          5 A
         8 A          7 A
         9 B          4 B
        10 A          8 A
        11 A         12 A
 
Elapsed: 00:00:00.00
SQL> /
Enter value for ecart: 6
old  26: select &ecart as ecart_valeur from dual
new  26: select 6 as ecart_valeur from dual
 
       ID1 N        ID2 N
---------- - ---------- -
         6 A          0 A
         8 A          5 A
         9 B          3 B
        10 A          7 A
        11 A          8 A
 
Elapsed: 00:00:00.00
SQL> /
Enter value for ecart: 7
old  26: select &ecart as ecart_valeur from dual
new  26: select 7 as ecart_valeur from dual
 
       ID1 N        ID2 N
---------- - ---------- -
         6 A          0 A
         8 A          5 A
         9 B          2 B
        10 A          7 A
        11 A          8 A
 
Elapsed: 00:00:00.00
SQL>

A moins que j'ai loupe un truc, les resultats obtenus sont ceux attendus.

Nicolas.

16/07/2009, 11h37
Waldar

Ca à l'air d'être ça, je n'avais pas pensé du tout à agir sur l'écart et appliquer mes règles après avoir fait les comptages.

Je fait quelques tests pour voir ce que donne l'algorithme.

Merci beaucoup !
16/07/2009, 11h45
NGasparotto

Deux points sur lesquels on peut toujours pinallier :
1. la vue T3, ca peut etre pas mal d'essayer de l'eviter, mais integrer sa logique dans M n'est pas si evident
2. l'exception de l'ecart 0...

Nicolas.
16/07/2009, 16h54
Waldar

Quelques nouvelles !

Avec votre algorithme de base j'obtiens de très bons résultats.
Je fais mes comparaison en comparant une valeur avec 100.000 autres valeurs.

Avant votre requête j'avais 90% d'égalité avec utl_match.jaro_winkler().
Avec votre requête je monte à 96%.

Malheureusement dans ces 4% restants j'ai bien des erreurs.

En remontant le dernier between dans la vue M, je n'ai plus que 0.5% de différence avec la fonction builtin (un peu plus de 500 lignes).

Je ne les ai pas toute regardées mais j'ai fait un peu de picking et pour le moment c'est la fonction Oracle qui est en tort.

Côté performance, la requête a quand même beaucoup grossie, j'arrive autour des 150 lignes de sql.

Sans aucune optimisation particulière, je calcule mes 100.000 lignes
en 9 secondes versus 4 secondes pour la fonction builtin.

Je vais donc commencer à travailler sur cet aspet-là maintenant que les résultats me paraissent cohérents !

Encore merci, je vous tiendrai informé de mes trouvailles.
16/07/2009, 17h10
NGasparotto

Citation:

En remontant le dernier between dans la vue M

Je comprends pas tres bien, je viens d'essayer et ca marche pas, mauvais resultat ne serait-ce que pour ecart=1. Les row_number() s'en trouve en peu perturbes.

Citation:

je calcule mes 100.000 lignes en 9 secondes

Je ne connais l'objectif, mais je trouve que c'est vraiment honnete.

Nicolas.

Oui exact, ce n'est pas juste non plus, pourtant j'avais de meilleurs résultats, mais c'était sur des données générées au hasard donc ça ne veut peut-être rien dire.

Damnit.

Avec ce jeu de donnée suivant et un écart à 4 il me manque une ligne :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
WITH T1 AS
(
SELECT 1 id1, 'k' nm1 FROM dual union ALL
SELECT 2    , 'J'     FROM dual union ALL
SELECT 3    , 'U'     FROM dual union ALL
SELECT 4    , 'F'     FROM dual union ALL
SELECT 5    , 'u'     FROM dual union ALL
SELECT 6    , 'p'     FROM dual union ALL
SELECT 7    , 'd'     FROM dual union ALL
SELECT 8    , 'e'     FROM dual union ALL
SELECT 9    , 'J'     FROM dual union ALL
SELECT 10   , 'T'     FROM dual
),   T2 AS
(
SELECT 1 id2, 'b' nm2 FROM dual union ALL
SELECT 2    , 'J'     FROM dual union ALL
SELECT 3    , 'h'     FROM dual union ALL
SELECT 4    , 'J'     FROM dual union ALL
SELECT 5    , 'x'     FROM dual union ALL
SELECT 6    , 'r'     FROM dual union ALL
SELECT 7    , 'v'     FROM dual union ALL
SELECT 8    , 'J'     FROM dual union ALL
SELECT 9    , 'V'     FROM dual union ALL
SELECT 10   , 'h'     FROM dual
), ECART AS 
(
SELECT &ecart AS ecart_valeur FROM dual
), T3 AS
(
SELECT nm2, min(id2) min_id2, max(id2) max_id2
FROM   T1,
T2,
ECART
WHERE T1.id1 BETWEEN (T2.id2 - ecart_valeur) AND (T2.id2 + ecart_valeur)
AND   T1.nm1=T2.nm2
GROUP BY nm2
),M AS
(
SELECT
    T1.*,
    T2.*,
    row_number() over (partition BY id1 ORDER BY id2) rn1,
    row_number() over (partition BY id2 ORDER BY id1) rn2,
    min_id2,
    max_id2
FROM
    T1,
    T2,
    T3
WHERE T2.id2 BETWEEN T3.min_id2 AND T3.max_id2
AND   T1.nm1=T2.nm2
AND   T1.nm1=T3.nm2
)
SELECT
    m.id1,
    m.nm1,
    m.id2,
    m.nm2
FROM
    m,
    ecart
WHERE id1 BETWEEN (m.id2 - ecart_valeur) AND (m.id2 + ecart_valeur)
  AND decode(ecart_valeur,0,-1,m.rn1) = decode(ecart_valeur,0,-1,m.rn2);
 
ID1	NM1	ID2	NM2
2	J	2	J
 
Attendu :
ID1	NM1	ID2	NM2
2	J	2	J
9	J	8	J

C'est parce que le deuxième J de "bJhJxrvJVh" est sélectionné par le min/max, mais il n'est pas compté car il est effectivement trop loin du deuxième J de "kJUFupdeJT".
Mais il est compté dans le row_number(), c'est pourquoi j'ai pensé à remonter la condition justement pour le modifier, mais effectivement du coup "AABAA" et "ABBBBABAABBBAA" ne correspondent plus comme ils devraient.

Y'a peut-etre plus simple.... m'enfin, nouvel essai :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
WITH T1 AS
(
SELECT 1 id1, 'k' nm1 FROM dual union ALL
SELECT 2    , 'J'     FROM dual union ALL
SELECT 3    , 'U'     FROM dual union ALL
SELECT 4    , 'F'     FROM dual union ALL
SELECT 5    , 'u'     FROM dual union ALL
SELECT 6    , 'p'     FROM dual union ALL
SELECT 7    , 'd'     FROM dual union ALL
SELECT 8    , 'e'     FROM dual union ALL
SELECT 9    , 'J'     FROM dual union ALL
SELECT 10   , 'T'     FROM dual
),   T2 AS
(
SELECT 1 id2, 'b' nm2 FROM dual union ALL
SELECT 2    , 'J'     FROM dual union ALL
SELECT 3    , 'h'     FROM dual union ALL
SELECT 4    , 'J'     FROM dual union ALL
SELECT 5    , 'x'     FROM dual union ALL
SELECT 6    , 'r'     FROM dual union ALL
SELECT 7    , 'v'     FROM dual union ALL
SELECT 8    , 'J'     FROM dual union ALL
SELECT 9    , 'V'     FROM dual union ALL
SELECT 10   , 'h'     FROM dual
), T11 AS
(
select t1.*, count(*) over (partition by nm1) ct from t1
), ECART AS 
(
SELECT &ecart AS ecart_valeur FROM dual
), T3 AS
(
SELECT nm2, min(id2) min_id2, max(id2) max_id2
FROM   T11,
T2,
ECART
WHERE T11.id1 BETWEEN (T2.id2 - ecart_valeur) AND (T2.id2 + ecart_valeur)
AND   T11.nm1=T2.nm2
GROUP BY nm2
),M AS
(
SELECT
    T11.*,
    T2.*,
    least(row_number() over (partition BY id1 ORDER BY id2), ct) rn1,
    row_number() over (partition BY id2 ORDER BY id1) rn2,
    min_id2,
    max_id2
FROM
    T11,
    T2,
    T3
WHERE T2.id2 BETWEEN T3.min_id2 AND T3.max_id2
AND   T11.nm1=T2.nm2
AND   T11.nm1=T3.nm2
)
SELECT id1,nm1,min(id2) id2,min(nm2) nm2
FROM
    m,
    ecart
WHERE id1 BETWEEN (m.id2 - ecart_valeur) AND (m.id2 + ecart_valeur)
 AND decode(ecart_valeur,0,-1,m.rn1) = decode(ecart_valeur,0,-1,m.rn2)
group by id1,nm1
order by id1,id2;

Apres tests, tous les resultats sont ceux escomptes avec les differents jeux de donnees que tu as fourni.

Nicolas.

17/07/2009, 13h46
Waldar

Ca m'a l'air parfait, j'ai lancé un peu plus de tests pour le moment je n'ai pas trouvé de problème !

Merci encore.

J'ai pu en rentrant de congé retravailler rapidement sur ce sujet.
Malheureusement avec ce jeu de données et un écart à 4 il me manque le premier "L" (id1 = 2 match avec id2 = 6) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
WITH T1 AS
(
SELECT 1 id1, 'L' nm1 FROM dual union ALL
SELECT 2    , 'L'     FROM dual union ALL
SELECT 3    , 'E'     FROM dual union ALL
SELECT 4    , 'w'     FROM dual union ALL
SELECT 5    , 'U'     FROM dual union ALL
SELECT 6    , 'd'     FROM dual union ALL
SELECT 7    , 'S'     FROM dual union ALL
SELECT 8    , 'C'     FROM dual union ALL
SELECT 9    , 'v'     FROM dual union ALL
SELECT 10   , 'f'     FROM dual
),   T2 AS
(
SELECT 1 id2, 'd' nm2 FROM dual union ALL
SELECT 2    , 'J'     FROM dual union ALL
SELECT 3    , 'o'     FROM dual union ALL
SELECT 4    , 'h'     FROM dual union ALL
SELECT 5    , 'A'     FROM dual union ALL
SELECT 6    , 'L'     FROM dual union ALL
SELECT 7    , 'C'     FROM dual union ALL
SELECT 8    , 'v'     FROM dual union ALL
SELECT 9    , 'I'     FROM dual union ALL
SELECT 10   , 'T'     FROM dual
)

Il va falloir que je me replonge dans l'algo.
Que c'est parfois compliqué de faire du PL/SQL relativement simple en pur SQL !

24/08/2009, 17h01
NGasparotto

Citation:

Envoyé par Waldar

...Que c'est parfois compliqué de faire du PL/SQL relativement simple en pur SQL !

Si c'est si simple en PL/SQL, alors pourquoi ne pas faire une petite PIPELINED function prenant en entree ton ecart comme parametre ?
Ce n'est pas parce que c'est du PL/SQL :
1. que c'est une horreur, parfois c'est meme bien plus comprehensible notemment pour la maintenance
2. que c'est plus lent, en effet, dans certaine condition de calcul complexe, le PL/SQL s'avere tout autant voire plus rapide que du SQL...

A mediter, non ?

Nicolas.
24/08/2009, 17h44
pacmann

Salut !

Tout à fait d'accord, NGasparotto.

Par contre, il reste un avantage indéniable pour le SQL dans ces cas : c'est plus sportif et plus drôle ! ;)

Courage Waldar, nous sommes avec toi...

Tout-à-fait, je prends ces arguments complètement en considération.

J'ai fait un petit benchmark de référence, qui concerne la recherche d'un mot court de 5 caractères dans une table de 150.000 lignes avec des mots qui peuvent faire jusqu'à 255 caractères.

Avec une requête écrite relativement bizarrement pour améliorer les performances, j'ai un temps de référence de 12 secondes avec la fonction Oracle utl_match.jaro_winkler.

Avec la fonction PL/SQL (de base ou parallel_enable mais pas pipelined) je tourne à 20 secondes.

Avec le bloc SQL que vous m'avez grandement aidé à écrire (qui donc contient une coquille pas simple à débusquer) je tourne à 57 secondes.

Avec la requête écrite normalement utilisant utl_match.jaro_winkler je tourne à 135 secondes et j'ai parfois (mais pas toujours) des ORA-03113: End of communication file.

La fonction Oracle malheureusement ne me paraît pas complètement juste, les deux résultats devraient être identiques :
Code:

1 2 3 4 5 6 7 select w1, w2, utl_match.jaro_winkler(w1, w2) as utl_jw1, utl_match.jaro_winkler(w2, w1) as utl_jw2 from (select 'THE BARON' as w1, 'THE RACE IS ON' as w2 from dual); W1 W2 UTL_JW1 UTL_JW2 THE BARON THE RACE IS ON 0.842063492063492 0.867063492063492
La fonction PL/SQL à ce jour est incomplète, je vais essayer de la terminer.
La partie Jaro est disponible ici, c'est la partie Winkler qui reste à coder :
http://forums.devshed.com/software-d...thm-62100.html

Le bloc SQL est un peu faux et surtout il s'est énormément complexifié par rapport à ce que je pensais écrire (avec une voire deux sous-requêtes, là j'en suis à sept), ce qui évidement rend son utilisation beaucoup moins aisée et moins rapide que les premiers tests que j'avais obtenus.

Donc rien de parfait pour le moment sur ce sujet.
Il faut toujours que je compile tout ça pour en faire un joli post, néanmoins je vous remercie déjà pour vos nombreuses et très utiles réponses.

Mais effectivement c'est vers le PL/SQL que la solution semble s'orienter.

02/09/2009, 03h46
Waldar

Pour ceux qui sont intéressés par cet algorithme, j'ai publié une première entrée en anglais sur mon blog, sur ce que j'ai pu tirer de la fonction fournie par Oracle dans utl_match et diverses zones d'ombres rencontrées ici ou là.

C'est un peu dense et relativement long (plus long que ce que j'ai l'habitude de publier), mais j'essaye d'être complet :
http://www.waldar.org/blog/200909/ja...acle-utl_match

Les anglophones / anglophiles, surtout n'hésitez pas à me corriger.

Plus tard dans le mois, il y aura au moins une deuxième partie (je ne me suis pas encore décidé quant au fait d'en rédiger deux ou trois) !
02/09/2009, 11h42
boutade80

I can't wait for part2 !