IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

SQL Oracle Discussion :

Algorithme de Jaro-Winkler


Sujet :

SQL Oracle

  1. #1
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Sr. Specialist Solutions Architect @Databricks
    Inscrit en
    Septembre 2008
    Messages
    8 454
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Sr. Specialist Solutions Architect @Databricks
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 8 454
    Par défaut Algorithme de Jaro-Winkler
    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.

  2. #2
    Membre émérite
    Profil pro
    Inscrit en
    Août 2008
    Messages
    861
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2008
    Messages : 861
    Par défaut
    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.

  3. #3
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Sr. Specialist Solutions Architect @Databricks
    Inscrit en
    Septembre 2008
    Messages
    8 454
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Sr. Specialist Solutions Architect @Databricks
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 8 454
    Par défaut
    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.

  4. #4
    Membre chevronné Avatar de NGasparotto
    Inscrit en
    Janvier 2007
    Messages
    421
    Détails du profil
    Informations forums :
    Inscription : Janvier 2007
    Messages : 421
    Par défaut
    Citation Envoyé par Waldar Voir le message
    ...Je suis en train de travailler sur des rapprochements de données par libellé....
    SOUNDEX ?

    Nicolas.

  5. #5
    Membre chevronné Avatar de NGasparotto
    Inscrit en
    Janvier 2007
    Messages
    421
    Détails du profil
    Informations forums :
    Inscription : Janvier 2007
    Messages : 421
    Par défaut
    Citation Envoyé par Waldar Voir le message
    ...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.

  6. #6
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Sr. Specialist Solutions Architect @Databricks
    Inscrit en
    Septembre 2008
    Messages
    8 454
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Sr. Specialist Solutions Architect @Databricks
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 8 454
    Par défaut
    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.

  7. #7
    Membre chevronné Avatar de NGasparotto
    Inscrit en
    Janvier 2007
    Messages
    421
    Détails du profil
    Informations forums :
    Inscription : Janvier 2007
    Messages : 421
    Par défaut
    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.

  8. #8
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Sr. Specialist Solutions Architect @Databricks
    Inscrit en
    Septembre 2008
    Messages
    8 454
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Sr. Specialist Solutions Architect @Databricks
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 8 454
    Par défaut
    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 !

  9. #9
    Membre chevronné Avatar de NGasparotto
    Inscrit en
    Janvier 2007
    Messages
    421
    Détails du profil
    Informations forums :
    Inscription : Janvier 2007
    Messages : 421
    Par défaut
    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.

  10. #10
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Sr. Specialist Solutions Architect @Databricks
    Inscrit en
    Septembre 2008
    Messages
    8 454
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Sr. Specialist Solutions Architect @Databricks
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 8 454
    Par défaut
    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.

  11. #11
    Membre chevronné Avatar de NGasparotto
    Inscrit en
    Janvier 2007
    Messages
    421
    Détails du profil
    Informations forums :
    Inscription : Janvier 2007
    Messages : 421
    Par défaut
    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.

    je calcule mes 100.000 lignes en 9 secondes
    Je ne connais l'objectif, mais je trouve que c'est vraiment honnete.

    Nicolas.

  12. #12
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Sr. Specialist Solutions Architect @Databricks
    Inscrit en
    Septembre 2008
    Messages
    8 454
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Sr. Specialist Solutions Architect @Databricks
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 8 454
    Par défaut
    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 : 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
    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.

  13. #13
    Membre chevronné Avatar de NGasparotto
    Inscrit en
    Janvier 2007
    Messages
    421
    Détails du profil
    Informations forums :
    Inscription : Janvier 2007
    Messages : 421
    Par défaut
    Y'a peut-etre plus simple.... m'enfin, 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
    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.

  14. #14
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Sr. Specialist Solutions Architect @Databricks
    Inscrit en
    Septembre 2008
    Messages
    8 454
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Sr. Specialist Solutions Architect @Databricks
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 8 454
    Par défaut
    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.

  15. #15
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Sr. Specialist Solutions Architect @Databricks
    Inscrit en
    Septembre 2008
    Messages
    8 454
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Sr. Specialist Solutions Architect @Databricks
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 8 454
    Par défaut
    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 : 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
    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 !

  16. #16
    Membre chevronné Avatar de NGasparotto
    Inscrit en
    Janvier 2007
    Messages
    421
    Détails du profil
    Informations forums :
    Inscription : Janvier 2007
    Messages : 421
    Par défaut
    Citation Envoyé par Waldar Voir le message
    ...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.

  17. #17
    Membre Expert Avatar de pacmann
    Homme Profil pro
    Consulté Oracle
    Inscrit en
    Juin 2004
    Messages
    1 626
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Consulté Oracle
    Secteur : Distribution

    Informations forums :
    Inscription : Juin 2004
    Messages : 1 626
    Par défaut
    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...

  18. #18
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Sr. Specialist Solutions Architect @Databricks
    Inscrit en
    Septembre 2008
    Messages
    8 454
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Sr. Specialist Solutions Architect @Databricks
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 8 454
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.

  19. #19
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Sr. Specialist Solutions Architect @Databricks
    Inscrit en
    Septembre 2008
    Messages
    8 454
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Sr. Specialist Solutions Architect @Databricks
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 8 454
    Par défaut
    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) !

  20. #20
    Membre éclairé
    Inscrit en
    Juillet 2006
    Messages
    76
    Détails du profil
    Informations forums :
    Inscription : Juillet 2006
    Messages : 76
    Par défaut
    I can't wait for part2 !

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 0
    Dernier message: 08/05/2015, 20h29
  2. Algorithme de randomisation ... ( Hasard ...? )
    Par Anonymous dans le forum Assembleur
    Réponses: 8
    Dernier message: 06/09/2002, 14h25
  3. recherches des cours ou des explications sur les algorithmes
    Par Marcus2211 dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 19/05/2002, 22h18
  4. Recherche de documentation complète en algorithmes
    Par Anonymous dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 29/03/2002, 12h09
  5. Algorithme génétique
    Par Stephane.P_(dis Postef) dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 15/03/2002, 17h14

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo