Discussion :

[Waldar]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

1. Les lettres doivent correspondre
2. L'écart de position entre les éléments est fixé à 5 pour cet exemple
3. 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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Snipah]

Bonjour,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Waldar]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[NGasparotto]

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

SOUNDEX ?

Nicolas.

[NGasparotto]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Waldar]

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%.

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[NGasparotto]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[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 !

[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.