Identification de cellules aux textes voisins

**David Lemarquand** · 02/05/2018, 16h22

Bonjour à toutes et tous,

Comme vous pourrez le constater via mes "stats", ceci est mon premier message sur ce forum ! Compte tenu de mes compétences en VBA (et en développement de manière général), vous comprendrez très vite que mon passage ici sera très bref.. bien que ce langage me passionne.

Afin de ne pas passer pour un opportuniste, j'ai passé les deux derniers jours à croiser les différentes infos qui pourraient m'aider dans mon problème. J'ai conscience qu'il n'y a rien de pire qu'un novice qui n'a même pas cherché dans les topics préexistants les réponses à son banal problème. Mes copiés/collés de macro chopés sur le net sans même comprendre de quoi il ressort m'ont donné l'envie de comprendre - voire mieux d'écrire ma propre macro. (Mal?)heureusement, on ne s'improvise pas développeur en 2 jours.

Voici mon objectif :

Je possède une liste d'adresses dans une première colonne (environ 30000 lignes) ainsi qu'une deuxième (environ 10000 lignes). Pour les deux colonnes, les adresses s'écrivent sous le format classique. Par ex : 14, rue Saint-Michel 14000 CAEN.
Je veux pouvoir identifier les adresses de la deuxième colonne (B) qui se glissent dans la première (A). Néanmoins, les textes ne sont pas identiques et ne se font pas face à face. Si je reprends mon exemple précédent, on pourrait retrouver dans la colonne A à la ligne 1500 le "2 r st-michel 14000 CAEN" et dans la colonne B à la ligne 500 le "2 rue saint michel 14000 Caen".
Vous remarquez donc qu'il y a des différences dans la chaîne de caractère.

J'ai pensé à géocoder les adresses via les API Google et comparer les longitudes et latitudes, toutefois dans le cadre de mon travail le résultat ne serait pas satisfaisant. Je cherche à identifier des copropriétés qui peuvent intégrer plusieurs adresses. Si je géocode le 2-8 allée des acacias, il n'y aura qu'un point correspondant au 2 allées des acacias. Dans la colonne B qui est le résultat d'adresses déclarées, les habitants ne déclarent pas l'ensemble des adresses qui composent leur copro. C'est pourquoi il est important que les cellules aux chaines de caractères similaires/voisines s'identifient afin de laisser place à un travail manuel de vérification.

J'avais trouvé cette macro :

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
Sub Find_Matches()
    Dim CompareRange As Variant, x As Variant, y As Variant
    ' Set CompareRange equal to the range to which you will
    ' compare the selection.
    Set CompareRange = Range("C1:C5")
    ' NOTE: If the compare range is located on another workbook
    ' or worksheet, use the following syntax.
    ' Set CompareRange = Workbooks("Book2"). _
    '   Worksheets("Sheet2").Range("C1:C5")
    '
    ' Loop through each cell in the selection and compare it to
    ' each cell in CompareRange.
    For Each x In Selection
        For Each y In CompareRange
            If x = y Then x.Offset(0, 1) = x
        Next y
    Next x
End Sub

Avec un peu trop d'enthousiasme et d'optimisme, j'ai cru qu'il suffirait de rajouter une condition si x = "1, 2 ou 3 mots de y" ou encore x = "70% des caractères de y" alors on colorie la cellule active.

Je tiens à préciser que ces adresses couvrent toute la France. Aussi, il me semble que pour plus de facilité, il faudrait que j'isole par département (voire par ville) les adresses afin d'éviter les similarités entre toutes les rues récurrentes comme les "rue de la république" ou encore "rue jeanne d'arc" que l'on peut retrouver dans de nombreuses communes.

Ci-joint, une liste d'adresses si quelqu'un serait tenté de se pencher sur ce problème "difficile" selon un ami développeur ou encore ce que j'ai pu lire sur les problèmes concernant les chaînes de caractères. J'y ai intégré tous les cas possibles auxquels je pourrais faire face.

Merci beaucoup pour votre considération,

David.

**Menhir** · 02/05/2018, 16h35

Je pense que ton problème ne peut pas se résoudre avec un simple code VBA.

C'est ce qu'on appelle de la logique floue, un domaine réservé au cerveau humain ou à des algorithmes de haute volée difficilement transcriptibles en VBA. Le nombre de cas possibles est trop vaste et la frontière entre ce qui est "quasiment" identique et ce qui ne l'est pas est trop vague.

**David Lemarquand** · 02/05/2018, 16h46

Merci pour ta réponse.

Pensez-vous que le problème se simplifierait si j'enlevais le code postal et la commune ?

**Menhir** · 02/05/2018, 17h32

Je pense au contraire que le code postal et la commune sont les éléments sur lesquels ce type de recherche serait le plus "simple" à développer.
Quoi que... pour la commune, pas simple d'expliquer à VBA que "St jean des monts" et Saint-Jean-des-Monts" sont identiques.

**patricktoulon** · 02/05/2018, 17h49

re
Bonjour je rejoint un peu menhir sur ce coup la
cependant il existe des algo bazooka qui font une analise de similarité
le plus performant a ce jours a ma connaissance est celui ci

Code :

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

1
2
3
4
5
Sub test3()
chaine1 = "St-jean-des-monts"
chaine2 = "Saint-Jean-des-Monts"
MsgBox "chaine 1=" & chaine1 & vbCrLf & "chaine 2=" & chaine2 & vbCrLf & "resultat = " & similaire(chaine1, chaine2) & "%"
End Sub

Code :

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

1
2
3
4
5
Sub test4()
chaine1 = "St jean des monts"
chaine2 = "Saint-Jean-des-Monts"
MsgBox "chaine 1=" & chaine1 & vbCrLf & "chaine 2=" & chaine2 & vbCrLf & "resultat = " & similaire(chaine1, chaine2) & "%"
End Sub

Code :

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

1
2
3
4
5
Sub test5()
chaine1 = "St jean des monts"
chaine2 = "Saint-Jean-des-Mous"
MsgBox "chaine 1=" & chaine1 & vbCrLf & "chaine 2=" & chaine2 & vbCrLf & "resultat = " & similaire(chaine1, chaine2) & "%"
End Sub

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
Public Function similaire(ByVal s1 As String, ByVal s2 As String) As Double
'Calcul la similarité (de [0 à 1]) entre deux chaines d'après l'algorithme de Damerau-Levenshtein
'références : http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
'             http://mwh.geek.nz/2009/04/26/python-damerau-levenshtein-distance/
'             http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node2.html
'Remarques  : Préparer les chaines car les comparaisons sont binaires : UCase(), Trim(),...
'Philben v1.0 - Free to Use
   Const cFacteur As Long = &H100&, cMaxLen As Long = 256&   'Longueur maxi autorisée des chaines analysées
   Dim l1 As Long, l2 As Long, c1 As Long, c2 As Long
    Dim r() As Integer, rp() As Integer, rpp() As Integer, i As Integer, j As Integer
    Dim c As Integer, x As Integer, y As Integer, z As Integer, f1 As Integer, f2 As Integer
    Dim dls As String, ac1() As Byte, ac2() As Byte
    l1 = Len(s1): l2 = Len(s2)
    If l1 > 0 And l1 <= cMaxLen And l2 > 0 And l2 <= cMaxLen Then
       ac1 = s1: ac2 = s2   'conversion des chaines en tableaux de bytes
       'Initialise la ligne précédente (rp) de la matrice
      ReDim rp(0 To l2)
       For i = 0 To l2: rp(i) = i: Next i
       For i = 1 To l1
          'Initialise la ligne courante de la matrice
         ReDim r(0 To l2): r(0) = i
          'Calcul le CharCode du caractère courant de la chaine
         f1 = (i - 1) * 2: c1 = ac1(f1 + 1) * cFacteur + ac1(f1)
          For j = 1 To l2
             f2 = (j - 1) * 2: c2 = ac2(f2 + 1) * cFacteur + ac2(f2)
             c = -(c1 <> c2)   'Cout : True = -1 => c = 1
             'suppression, insertion, substitution
            x = rp(j) + 1: y = r(j - 1) + 1: z = rp(j - 1) + c
             If x < y Then
                If x < z Then r(j) = x Else r(j) = z
             Else
                If y < z Then r(j) = y Else r(j) = z
             End If
             'transposition
            If i > 1 And j > 1 And c = 1 Then
                If c1 = ac2(f2 - 1) * cFacteur + ac2(f2 - 2) And c2 = ac1(f1 - 1) * cFacteur + ac1(f1 - 2) Then
                   If r(j) > rpp(j - 2) + c Then r(j) = rpp(j - 2) + c
                End If
             End If
          Next j
          'Reculer d'un niveau la ligne précédente (rp) et courante (r)
         rpp = rp: rp = r
       Next i
       'Calcul la similarité via la distance entre les chaines r(l2)
      If l1 >= l2 Then dls = 1 - r(l2) / l1 Else dls = 1 - r(l2) / l2
    ElseIf l1 > cMaxLen Or l2 > cMaxLen Then
       dls = -1   'indique un dépassement de longueur de chaine
   ElseIf l1 = 0 And l2 = 0 Then
       dls = 1   'cas particulier
   End If
    similaire = dls * 100
End Function

reste l'utilisateur de retenir le pourcentage valide pour accepter la similarité

**Transitoire** · 02/05/2018, 18h52

Bonsoir,
Je vais mêler ma médiocrité.
Bien qu'en apparence le plus sur, le code postal ne l'est pas réellement. En effet, la ville de Cannes par exemple de code 06400 et 06150 pour Cannes la bocca dispose en fait d'une trentaine de CP, que l'on retrouve certes rarement, mais? Nice en a minimum une centaine. Pareil pour la ville, mais je partage l'avis de menhir, ce sont vraisemblablement les critères de recherche de masse les plus sur.
Super Patrick ton intervention, je vais devoir ressortir mes Doliprane

Cordialement

**David Lemarquand** · 02/05/2018, 18h58

Moi qui pensait jeter une bouteille à la mer, vos réponses me font chaud au coeur et je m'étonne toujours de la solidarité qu'il existe dans ce domaine. C'est excellent et ça me motive à prendre un peu de temps pour m'initier.

Avec l'aide d'un ami je vais essayer de mettre en application ta fonction Patrick et je vais réfléchir à tout ça. Je vous retiens au courant des avancées.

Encore merci!

**eriiic** · 02/05/2018, 19h11

Bonjour,

comme la logique floue a été évoquée, MS a développé un addin pour ce type de problème.
Performant, et rapide en plus (il n'est pas en vba).
Une présentation : http://www.emarketeur.fr/ressources/...-vieux-vlookup
L'addin : https://www.microsoft.com/en-us/down....aspx?id=15011
Dans le temps tu trouvais une mini-doc sur cette page, elle n'y est plus. Je la met en PJ.
eric

**patricktoulon** · 03/05/2018, 10h31

re
@eric fuzy logic utilise le meme algorymtme ecrit en un autre language que l'ago que j'ai cité
petite demo d'utilsation
Nom : demo3.gif
Affichages : 208
Taille : 437,6 Ko

Nom : demo3.gif
Affichages : 208
Taille : 437,6 Ko

Invité · 03/05/2018, 11h29

Bonjour

Quelques infos complémentaires qui peuvent t'intéresser dans ce blog :

https://blog.developpez.com/philben/...nes_de_caracte

Il s'agit de l'algorithme que ta fourni patricktoulon.

Je l'utilise dans une base Access pour une recherche du même type que la tienne, et donc j'en ai déduis qu'avec un ration de 0.61 on arrive à avoir quelque chose de pas mal.

Un ration trop grand te fais perdre certaines similarités et un ratio trop faible te donne des résultats erronés.

Philippe

**patricktoulon** · 03/05/2018, 11h43

bonjour philippe JOCHMAN
oui c'est ce que je disais
reste seul a l'utilsateur de determiner le % acceptable
pour ma part j'ai ajouter un test simple en plus
car en effet si on prend l'indice le plus grand on a des surprises
exemple
chaine de base ="impasse du ponnant 83450 le pont du las"
chaine atester1="impasse du ponant le pont du las "
chaineatester2="impasse du ponnint 83100 le pont du los"
il est evident que c'est la chaine 1 qui est la plus proche pourtant en prenant l'indice le plus fort on a la 2
mon test supplementaire consiste a spliter les deux chaines(base/les deux possibilité ) et boucle et test de la presence du mot exact

apres honnetement la 2 il peut s'agir de fautes d'orthographe alors la on est dans une autre considération et il n'y a pas d'autre solution que la reflexion humaine

apres plus grave encore et c'est la que l'algo atteint ses limites
exemple
chaine de base ="impasse du ponnant 83450 le pont du las"
chaine atester1="impasse du ponant le pont du las 83450"
chaineatester2="impasse du ponnint 83100 le pont du los"

la encore c'est la 2 qui aura l'indice le plus fort avec l'algo
donc en ce qui concerne les adresse,mails,ou toutes autres expression pouvant etre exprimer dans un ordre différent mon ajout fait la part des choses et ajoute le pourcentage

Invité · 03/05/2018, 11h49

Patrick,

En effet, dés fois on a des résultats surprenants.

Philippe

**eriiic** · 03/05/2018, 12h23

@eric fuzy logic utilise le meme algorymtme ecrit en un autre language que l'ago que j'ai cité

Je connais la distance de Levenstein, tu fais une affirmation erronée sans avoir fait un seul contrôle.
Voir plutôt ici : https://fr.wikipedia.org/wiki/Indice...nce_de_Jaccard

Et combien même le principe serait le même, le fait d'avoir été développé dans un autre langage le rendrait incomparablement plus rapide.
On parle quand même de 30000 chaines à comparer à 10000 autres, pas de qq dizaines ou centaines.
Chacun connait les performances de vba dès qu'il s'agit de strings, ça rame terriblement...

Sans parler de la simplicité de mise en oeuvre. Juste installer et utiliser l'interface.
Et éventuellement désactiver le complément quand on en a plus besoin si on ne veut pas le charger inutilement.
eric

**eriiic** · 03/05/2018, 12h55

PS : par curiosité je lui ai fait faire tes 2 tests.
Pour les 2 il a bien ressorti la 1ère chaine

**patricktoulon** · 03/05/2018, 13h04

re
bon j'ai voulu l'installer pour l'essayer
et je ne peux pas il me demande d'installer VSTO..... et malheureusement ce composant est incompatible avec les supplements que m'a ajoute visual studio 2017
donc pour moi j'en resterais la

tant pis

**eriiic** · 03/05/2018, 13h11

Dommage, il est très intéressant à découvrir.
Il a un coté 'magique'

**patricktoulon** · 03/05/2018, 13h21

je testerais sur mon pc cobaie

**eriiic** · 03/05/2018, 13h55

Pour t'éviter de tourner un moment en rond comme moi la 1ère fois, il faut mettre les 2 plages en Tableaux.
Et sélectionner la 1ère cellule où doivent apparaitre les résultats avant de cliquer sur Go. Sinon elle écrase tout

**David Lemarquand** · 03/05/2018, 14h34

Encore une fois merci pour vos réponses.
Il va me falloir pas mal de temps pour tester vos différentes pistes! Avec mon bagage actuel, je ne saisis pas toutes vos idées... mais j'ai bon espoir! vous semblez plutôt optimistes finalement!

Identification de cellules aux textes voisins

Macros et VBA Excel

Discussions similaires

Partager

Partager