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.