Correlation de chaine de caracteres

Bonjour a tous,

Alors voila je me retrouve a devoir filer un coup de main a un membre de ma famille et a mettre de l'ordre dans ses fichiers clients qui sont une aberation. Il y a plusieurs feuilles CSV qui contiennent toutes des donnees et j'essaye de faire un tri dans tout ca. Bien entendu elles ont ete remplie n'importe comment .Il n'y a pas de format unique,certains clients sont dans plusieurs feuilles a la fois et toutes les informations ont ete saisie a la main avec un taux d'erreur important.
Voila pour la situation de depart.

Maintenant voila ma question. Je cherche a eviter les doublons. Malheureusement, je ne peux pas me permettre de faire uniquement un test sur le prenom/Nom de famille. En effet, vu comment les donnes ont ete rentre je peux tres bien avoir 3 entrees client differents de la maniere suivante:

Barry Hiland 6 Morgan Street
Barry+Helen Hiland 6 Morgan St
Barry Hilano 6 Mojan St

On peut voir que la deuxieme entree contient le prenom de la femme
la troisieme contient une faute d'orthographe dans le nom de famille ainsi que dans le nom de la rue
La premiere ligne contient 'Street' en entier alors que les deux autres ont l'abrege 'St'.

Or il s'agit du meme client. Je souhaite donc pouvoir mettre au point un test de correlation entre ces differentes chaines qui se ressemble pas mal quand meme, et donc le PC serait capable de voir qu'il s'agit de la meme personne.

J'avoue que ca ne me parait pas evident donc si qlq avait la moindre idee...

Julien

PS: Dsl pour les accents et fautes de frappe mais les qwerty...

Bonjour,

Ça, c'est un beau problème...

A mon avis, il ne faut pas chercher à faire ça d'un seul coup: en fonction des principaux types d'erreurs, il faut définir plusieurs étapes pour réduire progressivement le désordre des listes.

Il y a plusieurs étapes qui concerneront les lignes entières (une chaine par ligne), et plusieurs étapes qui concerneront les lignes déjà décomposées en champs (une liste de chaines par ligne).

Pour chaque étape, il me semble inévitable de recourir aux expressions régulières. C'est très puissant, mais ça ressemble souvent à une 'punition'...

Au minimum, on peut utiliser le module fnmatch (qui utilise les expressions régulières en interne), construit pour permettre les recherches de noms de fichiers avec:
'?'=n'importe quel caractère,
'*'=n'importe quel groupe de caractères éventuellement vide
[xyz]=liste des caractères possibles pour une position
[!xyz]=liste des caractères interdits pour une position

Pour utiliser le module fnmatch dans la recherche de chaines normales, il ne faut pas utiliser la fonction fnmatch qui normalise les chemins des disques, mais fnmatchcase.

Voilà un exemple:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 from fnmatch import fnmatchcase as trouve L = ["Barry Hiland 6 Morgan Street", "Barry+Helen Hiland 6 Morgan St", "Barry Hilano 6 Mojan St"] motif = "Barry*Hilan[do]*St*" for ligne in L: if trouve(ligne,motif): print ligne Barry Hiland 6 Morgan Street Barry+Helen Hiland 6 Morgan St Barry Hilano 6 Mojan St
A voir aussi s'il est nécessaire de neutraliser la casse (majuscule/minuscule), voire, mais c'est plus compliqué, les caractères accentués et autres signes diacritiques ('ç', ...).

Bon courage!

Tyrtamos

Hello,
Merci tyrtamos, ca pourrai etre une solution. mais j'avais envisage les choses sous cet angle la:

Pour deux chaine : chaine_1,chaine_2 on calcul un 'coeff de correlation'
Si coefficient de corellation>90% -> c'est la meme chaine
Si 60%<coefficient de corellation<90% -> On demande a l'utilisateur de chosir si c'est la meme chaine ou pas
Si coefficient de corellation<60% -> la chaine est differente>

Bien entendu mes bornes 60% et 90% sont la a titre d'example.

Maintenant il reste a trouver comment comment trouver une corellation.
Voici un exemple auque j'ai pense, mais c'est pas performant :mouarf:
En gros on calcul la lettre moyenne de la chaine
Code:

1 2 3 4 5 6 7 8 9 chaine=[chaine_1,chaine_2] moyenne=[] for element in chaine: for c in element : total=total+ord(c) moyenne.append(total/len(chaine_1)) coeff=moyenne[1]-moyenne[0]
Enfin bon ca c'est un peu simplet comme idee. je me demande si il n'y a pas des algo connu performant...

bonjour,

les moteurs de recherche sur le web savent faire ceci puisqu'en rentrant une requête mal orthographiée ils arrivent tout de même à trouver la bonne page :)

je ne sais pas la techno qui est en jeu, mais peut être que le module reverand pourrait t'aider (c'est un classificateur bayésien)

à mon avis, si tu veux quelque chose de robuste, je te conseille de rechercher sur le net plutôt que de recoder :)

Salut,

Peut-être que difflib.SequenceMatcher (http://docs.python.org/library/diffl...atcher-objects) et notamment la méthode ratio() peuvent suffire ?

tiens je connaissais pas ce module, c'est sympa. Je me suis amusé à essayer:

Code:

1
2
3
4
5
6
7
8
9
10
>>> from difflib import SequenceMatcher as Matcher
>>> s = Matcher(None, "Barry Hilano", "Barry Hiland")
>>> s.ratio()
0.91666666666666663
>>> s = Matcher(None, "Barry Hilano", "Hilary Barno")
>>> s.ratio()
0.5
>>> s = Matcher(None, "Barry Hiland 6 Morgan Street", "Barry Hilano 6 Mojan St")
>>> s.ratio()
0.82352941176470584

je pense que c'est ça qu'il te faut :p

Hu ! Perso, je me suis un peu amusé, aujourd’hui (j’avais du temps à perdre :mrgreen: )

Attention, accrochez-vous :D

J’ai choisi une approche par étape, en commençant par grouper selon les addresses, puis selon les noms… Je ne connaiisais pas non plus le module difflib, donc j’ai utilisé les regex…

Le code m’a l’air assez efficace, même si une partie des dites regex pourraient sans doute être remplacées par un calcul de match, fondamentalement ça ne change pas grand chose… Mais surtout, il est assez spécialisé, et (relatievemnt) facile à étendre pour prendre en compte de manière optimale des cas particuliers (comme ces fameux “Barry+Helen”).

Donc :

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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
import re
 
lines = ["Barry Hiland 6 Morgan Street",
         "Bill Gates 666 HellL and av",
         "Linus Torvald 6 Heaven street",
         "Barry+Helen Hiland 6 Morgan St",
         "Helen+Barry Hiland 6 Morgan St",
         "Halbert Einstain 6 Morran St",
         "Barry Hilano 6 Mojan St",
         "Bil&Melinda Gattes 666 Hel Lannd Avenue",
         "Barhy Hilant 6 Molan St",
         "Linux Thorwald 6 Heaven St",
         "Barry Hilano 6 Mojan Street",
         "Hellen&Barry Hiland 6 Moran St",
         "Albert Einstein 6 Moran St",
         "Bill Gates 666 Hell Land Av",
         "Melindo+Billou Gates 666 Hell Land av"]
 
streets = [{"Street", "street", "St", "st"}, {"Avenue", "avenue", "Av", "av"}]
spouse_links = {"+", "&"}
 
def print_groups(groups, nr):
    if nr:
        print("Pass nr ", nr, ":")
    for grp in groups:
        print("    ", "; ".join([str(l) for l in grp]))
    print("\n")
 
def generate_regex(word, max_diverge, prepend=""):
    """
    Generates all regex patterns matching all words diverging of the given max_diverge number of
    letters from given word…
    Note: “diverging” here also implies removed/added letters.
    """
    if max_diverge == 0:
        return [prepend+re.escape(word)]
    ret = []
    for i in range(len(word)):
        # One or more letters (depends on max_diverge) were replaced, removed or added…
        ret += ["".join([prepend, w]) \
                for w in generate_regex(word[i+1:], max_diverge-1, re.escape(word[:i])+".{0,2}")]
    return ret
 
def optimize_groups(groups):
    """
    Basically, given a list of sets, it returns a list of sets such that:
    * No returned set intersect with any other one.
    * Biggest given sets are preserved in priority.
    This version is slightly customized for the lines stuff…
    """
    lmap = dict([(grp[0][0], grp[0]) for grp in groups])
    for grp in groups:
        for grp2 in groups:
            if grp == grp2:
                continue
            if grp[1].isdisjoint(grp2[1]):
                continue
            if len(grp[1]) > len(grp2[1]):
                grp2[1] -= grp[1]
            else:
                grp[1] -= grp2[1]
    # Remove empty groups.
    groups = [grp for grp in groups if grp[1]]
    return [[lmap[l] for l in grp[1]] for grp in groups]
 
def merge(lines, streets, spouse_links, max_diverge = 2):
    # First, split names and address parts. We just search the number index…
    # Note that we keep the number, as we implies only lines with matching number should be further
    # tested…
    reg = re.compile(r"(\d+)")
    lines = [(l, reg.split(l, maxsplit = 1)) for l in lines]
    # Now, make a first grouping based on number.
    tmp = {}
    for l in lines:
        if l[1][1] not in tmp:
            tmp[l[1][1]] = [l]
        else:
            tmp[l[1][1]].append(l)
    groups = tmp.values()
    print_groups(groups, 1)
    tgrps = []
 
    # We further refine groups based on the remaining address part, assuming that the same address
    # will always have the same number of words…
    for grp in groups:
        # Always keep org lines!
        addr = [(l[0], l[1][0], l[1][2].split()) for l in grp]
        tmp = {}
        for l in addr:
            ln = len(l[2])
            if ln not in tmp:
                tmp[ln] = [l]
            else:
                tmp[ln].append(l)
        tgrps += tmp.values()
    groups = tgrps
    print_groups(groups, 2)
    tgrps = []
 
    # We can further refine groups using the trailing word of the address.
    for grp in groups:
        for addr_set in streets:
            tgrp = []
            for l in grp:
                if l[2][-1] in addr_set:
                    del l[2][-1]  # No more needed…
                    tgrp.append(l)
            if tgrp:
                tgrps.append(tgrp)
    groups = tgrps
    print_groups(groups, 3)
    tgrps = []
 
    # So far, we have (in tmp3) groups with same number, same number of words in
    # address, and same last address word (Street/St/etc., Avenue/Av/etc., …).
    # Now, the tricky part… For each line of a given group, we must check it against all
    # other lines of the group…
    # XXX We must avoid a sort of derivation: l1 might match l2, which mitght match l3, which
    #     however does not match l1…
    #     To avoid such problems, we:
    #     * Check all lines against all other lines, which gives us groups of lines similar to
    #       each singular line.
    #     * Keep biggest of intersecting groups, recursively…
    for grp in groups:
        # As sets does not support lists (non-hashable)…
        tmp = [{l[0]} for l in grp]
        for i, l in enumerate(grp):
            reg = []
            for w in l[2]:
                treg = generate_regex(w, max_diverge)
                # Join all elements in a single regex.
#                print("".join(["(?:", ")|(?:".join(treg), ")"]))
                reg.append(re.compile("".join(["^", "|".join(treg), "$"])))
            for l2 in grp:
                if l2[0] == l[0]:
                    continue
                match = True
                for j, w in enumerate(l2[2]):
                    if not reg[j].match(w):
                        match = False
                        break
                if match:
                    tmp[i].add(l2[0])
#        print(optimize_groups([[l, tmp[i]] for i, l in enumerate(grp)]))
        tgrps += optimize_groups([[l, tmp[i]] for i, l in enumerate(grp)])
    groups = tgrps
    print_groups(groups, 4)
    tgrps = []
 
    # Now, we have used addresses as much as we could, let’s finish with checks on names (there
    # might be several clients living at the same place…).
    # First, the count-based refining…
    for grp in groups:
        # Let’s get rid of last address parts, and split name part…
        grp = [(l[0], l[1].split()) for l in grp]
        tmp = {}
        for l in grp:
            ln = len(l[1])
            if ln not in tmp:
                tmp[ln] = [l]
            else:
                tmp[ln].append(l)
        tgrps += tmp.values()
    groups = tgrps
    print_groups(groups, 5)
    tgrps = []
 
    # And now, the regex-based refining.
    # Its globally the same process as previous step, but we must take into account the optionnal
    # spouse stuff…
    # Compute spouse links regex part here, as it is constant…
    reg_sps_lnk = "".join(["(?:", "|".join([re.escape(el) for el in spouse_links]), ")"])
#    print(reg_sps_lnk)
    for grp in groups:
        tmp = [{l[0]} for l in grp]
        for i, l in enumerate(grp):
            reg = []
            for w in l[1]:
                # The spouse special case.
                # XXX Note that this code assume both spouses are the same client
                #     I.e. in A+B, all A+B, B&A, A, B, (as well as their divergences) etc.,
                #     will be taken as the same…
                # XXX Note also you might have A+B+C, or A&B&C&D forms, etc.
                # XXX It will also match things like A+A+B+A… But I don’t think really is a problem…
                is_spouse = False
                for spouse_lnk in spouse_links:
                    if spouse_lnk in w:
                        is_spouse = True
                        names = w.split(spouse_lnk)
                        treg = []
                        for name in names:
                            tr = generate_regex(name, max_diverge)
                            # Join all elements in a single regex.
                            treg.append("".join(["(?:", "|".join(tr), ")"]))
                        # Make all those elements into a single, big, fat, horribly switched regex!
                        treg = "".join(["(?:", "|".join(treg), ")"])
                        treg = "".join(["^", treg, "(?:", reg_sps_lnk, treg, ")*$"])
                        reg.append(re.compile(treg))
                        break
                if not is_spouse:
                    treg = generate_regex(w, max_diverge)
                    # Join all elements in a single regex.
                    reg.append(re.compile("".join(["^(?:", "|".join(treg), ")$"])))
            for l2 in grp:
                if l2[0] == l[0]:
                    continue
                match = True
                for j, w in enumerate(l2[1]):
#                    print(l[1][j], "versus", w, ":", reg[j].match(w), "\n")
                    if not reg[j].match(w):
                        match = False
                        break
                if match:
                    tmp[i].add(l2[0])
#        print(optimize_groups([[l, tmp[i]] for i, l in enumerate(grp)]))
        tgrps += optimize_groups([[l, tmp[i]] for i, l in enumerate(grp)])
    groups = tgrps
    print_groups(groups, 6)
 
    return [[l[0] for l in grp] for grp in groups]
 
groups = merge(lines, streets, spouse_links)
print("Final results:")
print_groups(groups, 0)

…ce qui produit :

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
Pass nr  1 :
     ('Bill Gates 666 HellL and av', ['Bill Gates ', '666', ' HellL and av']); ('Bil&Melinda Gattes 666 Hel Lannd Avenue', ['Bil&Melinda Gattes ', '666', ' Hel Lannd Avenue']); ('Bill Gates 666 Hell Land Av', ['Bill Gates ', '666', ' Hell Land Av']); ('Melindo+Billou Gates 666 Hell Land av', ['Melindo+Billou Gates ', '666', ' Hell Land av'])
     ('Barry Hiland 6 Morgan Street', ['Barry Hiland ', '6', ' Morgan Street']); ('Linus Torvald 6 Heaven street', ['Linus Torvald ', '6', ' Heaven street']); ('Barry+Helen Hiland 6 Morgan St', ['Barry+Helen Hiland ', '6', ' Morgan St']); ('Helen+Barry Hiland 6 Morgan St', ['Helen+Barry Hiland ', '6', ' Morgan St']); ('Halbert Einstain 6 Morran St', ['Halbert Einstain ', '6', ' Morran St']); ('Barry Hilano 6 Mojan St', ['Barry Hilano ', '6', ' Mojan St']); ('Barhy Hilant 6 Molan St', ['Barhy Hilant ', '6', ' Molan St']); ('Linux Thorwald 6 Heaven St', ['Linux Thorwald ', '6', ' Heaven St']); ('Barry Hilano 6 Mojan Street', ['Barry Hilano ', '6', ' Mojan Street']); ('Hellen&Barry Hiland 6 Moran St', ['Hellen&Barry Hiland ', '6', ' Moran St']); ('Albert Einstein 6 Moran St', ['Albert Einstein ', '6', ' Moran St'])
 
 
Pass nr  2 :
     ('Bill Gates 666 HellL and av', 'Bill Gates ', ['HellL', 'and', 'av']); ('Bil&Melinda Gattes 666 Hel Lannd Avenue', 'Bil&Melinda Gattes ', ['Hel', 'Lannd', 'Avenue']); ('Bill Gates 666 Hell Land Av', 'Bill Gates ', ['Hell', 'Land', 'Av']); ('Melindo+Billou Gates 666 Hell Land av', 'Melindo+Billou Gates ', ['Hell', 'Land', 'av'])
     ('Barry Hiland 6 Morgan Street', 'Barry Hiland ', ['Morgan', 'Street']); ('Linus Torvald 6 Heaven street', 'Linus Torvald ', ['Heaven', 'street']); ('Barry+Helen Hiland 6 Morgan St', 'Barry+Helen Hiland ', ['Morgan', 'St']); ('Helen+Barry Hiland 6 Morgan St', 'Helen+Barry Hiland ', ['Morgan', 'St']); ('Halbert Einstain 6 Morran St', 'Halbert Einstain ', ['Morran', 'St']); ('Barry Hilano 6 Mojan St', 'Barry Hilano ', ['Mojan', 'St']); ('Barhy Hilant 6 Molan St', 'Barhy Hilant ', ['Molan', 'St']); ('Linux Thorwald 6 Heaven St', 'Linux Thorwald ', ['Heaven', 'St']); ('Barry Hilano 6 Mojan Street', 'Barry Hilano ', ['Mojan', 'Street']); ('Hellen&Barry Hiland 6 Moran St', 'Hellen&Barry Hiland ', ['Moran', 'St']); ('Albert Einstein 6 Moran St', 'Albert Einstein ', ['Moran', 'St'])
 
 
Pass nr  3 :
     ('Bill Gates 666 HellL and av', 'Bill Gates ', ['HellL', 'and']); ('Bil&Melinda Gattes 666 Hel Lannd Avenue', 'Bil&Melinda Gattes ', ['Hel', 'Lannd']); ('Bill Gates 666 Hell Land Av', 'Bill Gates ', ['Hell', 'Land']); ('Melindo+Billou Gates 666 Hell Land av', 'Melindo+Billou Gates ', ['Hell', 'Land'])
     ('Barry Hiland 6 Morgan Street', 'Barry Hiland ', ['Morgan']); ('Linus Torvald 6 Heaven street', 'Linus Torvald ', ['Heaven']); ('Barry+Helen Hiland 6 Morgan St', 'Barry+Helen Hiland ', ['Morgan']); ('Helen+Barry Hiland 6 Morgan St', 'Helen+Barry Hiland ', ['Morgan']); ('Halbert Einstain 6 Morran St', 'Halbert Einstain ', ['Morran']); ('Barry Hilano 6 Mojan St', 'Barry Hilano ', ['Mojan']); ('Barhy Hilant 6 Molan St', 'Barhy Hilant ', ['Molan']); ('Linux Thorwald 6 Heaven St', 'Linux Thorwald ', ['Heaven']); ('Barry Hilano 6 Mojan Street', 'Barry Hilano ', ['Mojan']); ('Hellen&Barry Hiland 6 Moran St', 'Hellen&Barry Hiland ', ['Moran']); ('Albert Einstein 6 Moran St', 'Albert Einstein ', ['Moran'])
 
 
Pass nr  4 :
     ('Bil&Melinda Gattes 666 Hel Lannd Avenue', 'Bil&Melinda Gattes ', ['Hel', 'Lannd']); ('Bill Gates 666 HellL and av', 'Bill Gates ', ['HellL', 'and']); ('Melindo+Billou Gates 666 Hell Land av', 'Melindo+Billou Gates ', ['Hell', 'Land']); ('Bill Gates 666 Hell Land Av', 'Bill Gates ', ['Hell', 'Land'])
     ('Linus Torvald 6 Heaven street', 'Linus Torvald ', ['Heaven']); ('Linux Thorwald 6 Heaven St', 'Linux Thorwald ', ['Heaven'])
     ('Helen+Barry Hiland 6 Morgan St', 'Helen+Barry Hiland ', ['Morgan']); ('Halbert Einstain 6 Morran St', 'Halbert Einstain ', ['Morran']); ('Barry Hilano 6 Mojan Street', 'Barry Hilano ', ['Mojan']); ('Barry Hilano 6 Mojan St', 'Barry Hilano ', ['Mojan']); ('Barry+Helen Hiland 6 Morgan St', 'Barry+Helen Hiland ', ['Morgan']); ('Barhy Hilant 6 Molan St', 'Barhy Hilant ', ['Molan']); ('Barry Hiland 6 Morgan Street', 'Barry Hiland ', ['Morgan']); ('Hellen&Barry Hiland 6 Moran St', 'Hellen&Barry Hiland ', ['Moran']); ('Albert Einstein 6 Moran St', 'Albert Einstein ', ['Moran'])
 
 
Pass nr  5 :
     ('Bil&Melinda Gattes 666 Hel Lannd Avenue', ['Bil&Melinda', 'Gattes']); ('Bill Gates 666 HellL and av', ['Bill', 'Gates']); ('Melindo+Billou Gates 666 Hell Land av', ['Melindo+Billou', 'Gates']); ('Bill Gates 666 Hell Land Av', ['Bill', 'Gates'])
     ('Linus Torvald 6 Heaven street', ['Linus', 'Torvald']); ('Linux Thorwald 6 Heaven St', ['Linux', 'Thorwald'])
     ('Helen+Barry Hiland 6 Morgan St', ['Helen+Barry', 'Hiland']); ('Halbert Einstain 6 Morran St', ['Halbert', 'Einstain']); ('Barry Hilano 6 Mojan Street', ['Barry', 'Hilano']); ('Barry Hilano 6 Mojan St', ['Barry', 'Hilano']); ('Barry+Helen Hiland 6 Morgan St', ['Barry+Helen', 'Hiland']); ('Barhy Hilant 6 Molan St', ['Barhy', 'Hilant']); ('Barry Hiland 6 Morgan Street', ['Barry', 'Hiland']); ('Hellen&Barry Hiland 6 Moran St', ['Hellen&Barry', 'Hiland']); ('Albert Einstein 6 Moran St', ['Albert', 'Einstein'])
 
 
Pass nr  6 :
     ('Bil&Melinda Gattes 666 Hel Lannd Avenue', ['Bil&Melinda', 'Gattes'])
     ('Bill Gates 666 HellL and av', ['Bill', 'Gates']); ('Melindo+Billou Gates 666 Hell Land av', ['Melindo+Billou', 'Gates']); ('Bill Gates 666 Hell Land Av', ['Bill', 'Gates'])
     ('Linus Torvald 6 Heaven street', ['Linus', 'Torvald']); ('Linux Thorwald 6 Heaven St', ['Linux', 'Thorwald'])
     ('Helen+Barry Hiland 6 Morgan St', ['Helen+Barry', 'Hiland']); ('Barry Hilano 6 Mojan Street', ['Barry', 'Hilano']); ('Barry Hilano 6 Mojan St', ['Barry', 'Hilano']); ('Barry+Helen Hiland 6 Morgan St', ['Barry+Helen', 'Hiland']); ('Barhy Hilant 6 Molan St', ['Barhy', 'Hilant']); ('Barry Hiland 6 Morgan Street', ['Barry', 'Hiland']); ('Hellen&Barry Hiland 6 Moran St', ['Hellen&Barry', 'Hiland'])
     ('Halbert Einstain 6 Morran St', ['Halbert', 'Einstain']); ('Albert Einstein 6 Moran St', ['Albert', 'Einstein'])
 
 
Final results:
     Bil&Melinda Gattes 666 Hel Lannd Avenue
     Bill Gates 666 HellL and av; Melindo+Billou Gates 666 Hell Land av; Bill Gates 666 Hell Land Av
     Linus Torvald 6 Heaven street; Linux Thorwald 6 Heaven St
     Helen+Barry Hiland 6 Morgan St; Barry Hilano 6 Mojan Street; Barry Hilano 6 Mojan St; Barry+Helen Hiland 6 Morgan St; Barhy Hilant 6 Molan St; Barry Hiland 6 Morgan Street; Hellen&Barry Hiland 6 Moran St
     Halbert Einstain 6 Morran St; Albert Einstein 6 Moran St

Le résultat n’est pas parfait, mais déjà pas mal… Attention à la valeur de max_diverge, elle peut très vitre produire des faux positifs ! De toute façon, un contrôle rapide du résultat “à la main” me semble quoi qu’il arrive indispensable…

En passant à difflib (toujours avec des “comparaisons” au mot-à-mot) :

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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
import re
from difflib import SequenceMatcher as Matcher
 
lines = ["Barry Hiland 6 Morgan Street",
         "Bill Gates 666 HellL and av",
         "Linus Torvald 6 Heaven street",
         "Barry+Helen Hiland 6 Morgan St",
         "Helen+Barry Hiland 6 Morgan St",
         "Halbert Einstain 6 Morran St",
         "Barry Hilano 6 Mojan St",
         "Bil&Melinda Gattes 666 Hel Lannd Avenue",
         "Barhy Hilant 6 Molan St",
         "Linux Thorwald 6 Heaven St",
         "Barry Hilano 6 Mojan Street",
         "Hellen&Barry Hiland 6 Moran St",
         "Albert Einstein 6 Moran St",
         "Bill Gates 666 Hell Land Av",
         "Melindo+Billou Gates 666 Hell Land av"]
 
streets = [{"Street", "street", "St", "st"}, {"Avenue", "avenue", "Av", "av"}]
spouse_links = {"+", "&"}
 
def print_groups(groups, nr):
    if nr:
        print("Pass nr ", nr, ":")
    for grp in groups:
        print("    ", "; ".join([str(l) for l in grp]))
    print("\n")
 
def optimize_groups(groups):
    """
    Basically, given a list of sets, it returns a list of sets such that:
    * No returned set intersect with any other one.
    * Biggest given sets are preserved in priority.
    This version is slightly customized for the lines stuff…
    """
    lmap = dict([(grp[0][0], grp[0]) for grp in groups])
    for grp in groups:
        for grp2 in groups:
            if grp == grp2:
                continue
            if grp[1].isdisjoint(grp2[1]):
                continue
            if len(grp[1]) > len(grp2[1]):
                grp2[1] -= grp[1]
            else:
                grp[1] -= grp2[1]
    # Remove empty groups.
    groups = [grp for grp in groups if grp[1]]
    return [[lmap[l] for l in grp[1]] for grp in groups]
 
def merge(lines, streets, spouse_links, threshold = 0.9):
    # First, split names and address parts. We just search the number index…
    # Note that we keep the number, as we implies only lines with matching number should be further
    # tested…
    reg = re.compile(r"(\d+)")
    lines = [(l, reg.split(l, maxsplit = 1)) for l in lines]
    # Now, make a first grouping based on number.
    # Note: If you have entries without street number, just create a group for them…
    tmp = {}
    for l in lines:
        if l[1][1] not in tmp:
            tmp[l[1][1]] = [l]
        else:
            tmp[l[1][1]].append(l)
    groups = tmp.values()
    print_groups(groups, 1)
    tgrps = []
 
    # We further refine groups based on the remaining address part, assuming that the same address
    # will always have the same number of words…
    for grp in groups:
        # Always keep org lines!
        addr = [(l[0], l[1][0], l[1][2].split()) for l in grp]
        tmp = {}
        for l in addr:
            ln = len(l[2])
            if ln not in tmp:
                tmp[ln] = [l]
            else:
                tmp[ln].append(l)
        tgrps += tmp.values()
    groups = tgrps
    print_groups(groups, 2)
    tgrps = []
 
    # We can further refine groups using the trailing word of the address.
    # XXX We assume all lines end with Street, St, Avenue, Av, etc. Not hard to add a case for
    #     peculiar lines, though…
    for grp in groups:
        for addr_set in streets:
            tgrp = []
            for l in grp:
                if l[2][-1] in addr_set:
                    del l[2][-1]  # No more needed…
                    tgrp.append(l)
            if tgrp:
                tgrps.append(tgrp)
    groups = tgrps
    print_groups(groups, 3)
    tgrps = []
 
    # So far, we have (in tmp3) groups with same number, same number of words in
    # address, and same last address word (Street/St/etc., Avenue/Av/etc., …).
    # Now, the tricky part… For each line of a given group, we must check it against all
    # other lines of the group…
    # XXX We must avoid a sort of derivation: l1 might match l2, which mitght match l3, which
    #     however does not match l1…
    #     To avoid such problems, we:
    #     * Check all lines against all other lines, which gives us groups of lines similar to
    #       each singular line.
    #     * Keep biggest of intersecting groups, recursively…
    for grp in groups:
        # As sets does not support lists (non-hashable)…
        tmp = [{l[0]} for l in grp]
        for i, l in enumerate(grp):
            for l2 in grp:
                if l2[0] == l[0]:
                    continue
                match = True
                for j, w in enumerate(l[2]):
                    if Matcher(None, w, l2[2][j]).ratio() < threshold:
                        match = False
                        break
                if match:
                    tmp[i].add(l2[0])
#        print(optimize_groups([[l, tmp[i]] for i, l in enumerate(grp)]))
        tgrps += optimize_groups([[l, tmp[i]] for i, l in enumerate(grp)])
    groups = tgrps
    print_groups(groups, 4)
    tgrps = []
 
    # Now, we have used addresses as much as we could, let’s finish with checks on names (there
    # might be several clients living at the same place…).
    # First, the count-based refining…
    for grp in groups:
        # Let’s get rid of last address parts, and split name part…
        grp = [(l[0], l[1].split()) for l in grp]
        tmp = {}
        for l in grp:
            ln = len(l[1])
            if ln not in tmp:
                tmp[ln] = [l]
            else:
                tmp[ln].append(l)
        tgrps += tmp.values()
    groups = tgrps
    print_groups(groups, 5)
    tgrps = []
 
    # And now, the regex-based refining.
    # Its globally the same process as previous step, but we must take into account the optionnal
    # spouse stuff…
    for grp in groups:
        tmp = [{l[0]} for l in grp]
        for i, l in enumerate(grp):
            for l2 in grp:
                if l2[0] == l[0]:
                    continue
                match = True
                for j, w in enumerate(l[1]):
                    wn = [w]
                    wn2 = [l2[1][j]]
                    for spouse_lnk in spouse_links:
                        if spouse_lnk in w:
                            wn = w.split(spouse_lnk)
                            break
                    for spouse_lnk in spouse_links:
                        if spouse_lnk in l2[1][j]:
                            wn2 = l2[1][j].split(spouse_lnk)
                            break
                    tmatch = False
                    for w in wn:
                        for w2 in wn2:
                            if Matcher(None, w, w2).ratio() > threshold:
                                tmatch = True
                                break
                        if tmatch:
                            break
                    if not tmatch:
                        match = False
                        break
                if match:
                    tmp[i].add(l2[0])
#        print(optimize_groups([[l, tmp[i]] for i, l in enumerate(grp)]))
        tgrps += optimize_groups([[l, tmp[i]] for i, l in enumerate(grp)])
    groups = tgrps
    print_groups(groups, 6)
 
    return [[l[0] for l in grp] for grp in groups]
 
groups = merge(lines, streets, spouse_links)
print("Final results:")
print_groups(groups, 0)

…il faut descendre vers un threshold global de 0.8 pour obtenir des resultats à peine correctes :

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
Pass nr  1 :
     ('Bill Gates 666 HellL and av', ['Bill Gates ', '666', ' HellL and av']); ('Bil&Melinda Gattes 666 Hel Lannd Avenue', ['Bil&Melinda Gattes ', '666', ' Hel Lannd Avenue']); ('Bill Gates 666 Hell Land Av', ['Bill Gates ', '666', ' Hell Land Av']); ('Melindo+Billou Gates 666 Hell Land av', ['Melindo+Billou Gates ', '666', ' Hell Land av'])
     ('Barry Hiland 6 Morgan Street', ['Barry Hiland ', '6', ' Morgan Street']); ('Linus Torvald 6 Heaven street', ['Linus Torvald ', '6', ' Heaven street']); ('Barry+Helen Hiland 6 Morgan St', ['Barry+Helen Hiland ', '6', ' Morgan St']); ('Helen+Barry Hiland 6 Morgan St', ['Helen+Barry Hiland ', '6', ' Morgan St']); ('Halbert Einstain 6 Morran St', ['Halbert Einstain ', '6', ' Morran St']); ('Barry Hilano 6 Mojan St', ['Barry Hilano ', '6', ' Mojan St']); ('Barhy Hilant 6 Molan St', ['Barhy Hilant ', '6', ' Molan St']); ('Linux Thorwald 6 Heaven St', ['Linux Thorwald ', '6', ' Heaven St']); ('Barry Hilano 6 Mojan Street', ['Barry Hilano ', '6', ' Mojan Street']); ('Hellen&Barry Hiland 6 Moran St', ['Hellen&Barry Hiland ', '6', ' Moran St']); ('Albert Einstein 6 Moran St', ['Albert Einstein ', '6', ' Moran St'])
 
 
Pass nr  2 :
     ('Bill Gates 666 HellL and av', 'Bill Gates ', ['HellL', 'and', 'av']); ('Bil&Melinda Gattes 666 Hel Lannd Avenue', 'Bil&Melinda Gattes ', ['Hel', 'Lannd', 'Avenue']); ('Bill Gates 666 Hell Land Av', 'Bill Gates ', ['Hell', 'Land', 'Av']); ('Melindo+Billou Gates 666 Hell Land av', 'Melindo+Billou Gates ', ['Hell', 'Land', 'av'])
     ('Barry Hiland 6 Morgan Street', 'Barry Hiland ', ['Morgan', 'Street']); ('Linus Torvald 6 Heaven street', 'Linus Torvald ', ['Heaven', 'street']); ('Barry+Helen Hiland 6 Morgan St', 'Barry+Helen Hiland ', ['Morgan', 'St']); ('Helen+Barry Hiland 6 Morgan St', 'Helen+Barry Hiland ', ['Morgan', 'St']); ('Halbert Einstain 6 Morran St', 'Halbert Einstain ', ['Morran', 'St']); ('Barry Hilano 6 Mojan St', 'Barry Hilano ', ['Mojan', 'St']); ('Barhy Hilant 6 Molan St', 'Barhy Hilant ', ['Molan', 'St']); ('Linux Thorwald 6 Heaven St', 'Linux Thorwald ', ['Heaven', 'St']); ('Barry Hilano 6 Mojan Street', 'Barry Hilano ', ['Mojan', 'Street']); ('Hellen&Barry Hiland 6 Moran St', 'Hellen&Barry Hiland ', ['Moran', 'St']); ('Albert Einstein 6 Moran St', 'Albert Einstein ', ['Moran', 'St'])
 
 
Pass nr  3 :
     ('Bill Gates 666 HellL and av', 'Bill Gates ', ['HellL', 'and']); ('Bil&Melinda Gattes 666 Hel Lannd Avenue', 'Bil&Melinda Gattes ', ['Hel', 'Lannd']); ('Bill Gates 666 Hell Land Av', 'Bill Gates ', ['Hell', 'Land']); ('Melindo+Billou Gates 666 Hell Land av', 'Melindo+Billou Gates ', ['Hell', 'Land'])
     ('Barry Hiland 6 Morgan Street', 'Barry Hiland ', ['Morgan']); ('Linus Torvald 6 Heaven street', 'Linus Torvald ', ['Heaven']); ('Barry+Helen Hiland 6 Morgan St', 'Barry+Helen Hiland ', ['Morgan']); ('Helen+Barry Hiland 6 Morgan St', 'Helen+Barry Hiland ', ['Morgan']); ('Halbert Einstain 6 Morran St', 'Halbert Einstain ', ['Morran']); ('Barry Hilano 6 Mojan St', 'Barry Hilano ', ['Mojan']); ('Barhy Hilant 6 Molan St', 'Barhy Hilant ', ['Molan']); ('Linux Thorwald 6 Heaven St', 'Linux Thorwald ', ['Heaven']); ('Barry Hilano 6 Mojan Street', 'Barry Hilano ', ['Mojan']); ('Hellen&Barry Hiland 6 Moran St', 'Hellen&Barry Hiland ', ['Moran']); ('Albert Einstein 6 Moran St', 'Albert Einstein ', ['Moran'])
 
 
Pass nr  4 :
     ('Bil&Melinda Gattes 666 Hel Lannd Avenue', 'Bil&Melinda Gattes ', ['Hel', 'Lannd']); ('Bill Gates 666 HellL and av', 'Bill Gates ', ['HellL', 'and']); ('Melindo+Billou Gates 666 Hell Land av', 'Melindo+Billou Gates ', ['Hell', 'Land']); ('Bill Gates 666 Hell Land Av', 'Bill Gates ', ['Hell', 'Land'])
     ('Linus Torvald 6 Heaven street', 'Linus Torvald ', ['Heaven']); ('Linux Thorwald 6 Heaven St', 'Linux Thorwald ', ['Heaven'])
     ('Helen+Barry Hiland 6 Morgan St', 'Helen+Barry Hiland ', ['Morgan']); ('Halbert Einstain 6 Morran St', 'Halbert Einstain ', ['Morran']); ('Barry Hilano 6 Mojan Street', 'Barry Hilano ', ['Mojan']); ('Barry Hilano 6 Mojan St', 'Barry Hilano ', ['Mojan']); ('Barry+Helen Hiland 6 Morgan St', 'Barry+Helen Hiland ', ['Morgan']); ('Barhy Hilant 6 Molan St', 'Barhy Hilant ', ['Molan']); ('Barry Hiland 6 Morgan Street', 'Barry Hiland ', ['Morgan']); ('Hellen&Barry Hiland 6 Moran St', 'Hellen&Barry Hiland ', ['Moran']); ('Albert Einstein 6 Moran St', 'Albert Einstein ', ['Moran'])
 
 
Pass nr  5 :
     ('Bil&Melinda Gattes 666 Hel Lannd Avenue', ['Bil&Melinda', 'Gattes']); ('Bill Gates 666 HellL and av', ['Bill', 'Gates']); ('Melindo+Billou Gates 666 Hell Land av', ['Melindo+Billou', 'Gates']); ('Bill Gates 666 Hell Land Av', ['Bill', 'Gates'])
     ('Linus Torvald 6 Heaven street', ['Linus', 'Torvald']); ('Linux Thorwald 6 Heaven St', ['Linux', 'Thorwald'])
     ('Helen+Barry Hiland 6 Morgan St', ['Helen+Barry', 'Hiland']); ('Halbert Einstain 6 Morran St', ['Halbert', 'Einstain']); ('Barry Hilano 6 Mojan Street', ['Barry', 'Hilano']); ('Barry Hilano 6 Mojan St', ['Barry', 'Hilano']); ('Barry+Helen Hiland 6 Morgan St', ['Barry+Helen', 'Hiland']); ('Barhy Hilant 6 Molan St', ['Barhy', 'Hilant']); ('Barry Hiland 6 Morgan Street', ['Barry', 'Hiland']); ('Hellen&Barry Hiland 6 Moran St', ['Hellen&Barry', 'Hiland']); ('Albert Einstein 6 Moran St', ['Albert', 'Einstein'])
 
 
Pass nr  6 :
     ('Melindo+Billou Gates 666 Hell Land av', ['Melindo+Billou', 'Gates']); ('Bill Gates 666 HellL and av', ['Bill', 'Gates']); ('Bil&Melinda Gattes 666 Hel Lannd Avenue', ['Bil&Melinda', 'Gattes']); ('Bill Gates 666 Hell Land Av', ['Bill', 'Gates'])
     ('Linus Torvald 6 Heaven street', ['Linus', 'Torvald'])
     ('Linux Thorwald 6 Heaven St', ['Linux', 'Thorwald'])
     ('Halbert Einstain 6 Morran St', ['Halbert', 'Einstain'])
     ('Barhy Hilant 6 Molan St', ['Barhy', 'Hilant'])
     ('Helen+Barry Hiland 6 Morgan St', ['Helen+Barry', 'Hiland']); ('Barry Hilano 6 Mojan Street', ['Barry', 'Hilano']); ('Barry Hilano 6 Mojan St', ['Barry', 'Hilano']); ('Barry+Helen Hiland 6 Morgan St', ['Barry+Helen', 'Hiland']); ('Barry Hiland 6 Morgan Street', ['Barry', 'Hiland']); ('Hellen&Barry Hiland 6 Moran St', ['Hellen&Barry', 'Hiland'])
     ('Albert Einstein 6 Moran St', ['Albert', 'Einstein'])
 
 
Final results:
     Melindo+Billou Gates 666 Hell Land av; Bill Gates 666 HellL and av; Bil&Melinda Gattes 666 Hel Lannd Avenue; Bill Gates 666 Hell Land Av
     Linus Torvald 6 Heaven street
     Linux Thorwald 6 Heaven St
     Halbert Einstain 6 Morran St
     Barhy Hilant 6 Molan St
     Helen+Barry Hiland 6 Morgan St; Barry Hilano 6 Mojan Street; Barry Hilano 6 Mojan St; Barry+Helen Hiland 6 Morgan St; Barry Hiland 6 Morgan Street; Hellen&Barry Hiland 6 Moran St
     Albert Einstein 6 Moran St

…alors qu’avec un threshold de 0.75, c’est parfait (sur cette liste-test, en tout cas…) :

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
Pass nr  1 :
     ('Bill Gates 666 HellL and av', ['Bill Gates ', '666', ' HellL and av']); ('Bil&Melinda Gattes 666 Hel Lannd Avenue', ['Bil&Melinda Gattes ', '666', ' Hel Lannd Avenue']); ('Bill Gates 666 Hell Land Av', ['Bill Gates ', '666', ' Hell Land Av']); ('Melindo+Billou Gates 666 Hell Land av', ['Melindo+Billou Gates ', '666', ' Hell Land av'])
     ('Barry Hiland 6 Morgan Street', ['Barry Hiland ', '6', ' Morgan Street']); ('Linus Torvald 6 Heaven street', ['Linus Torvald ', '6', ' Heaven street']); ('Barry+Helen Hiland 6 Morgan St', ['Barry+Helen Hiland ', '6', ' Morgan St']); ('Helen+Barry Hiland 6 Morgan St', ['Helen+Barry Hiland ', '6', ' Morgan St']); ('Halbert Einstain 6 Morran St', ['Halbert Einstain ', '6', ' Morran St']); ('Barry Hilano 6 Mojan St', ['Barry Hilano ', '6', ' Mojan St']); ('Barhy Hilant 6 Molan St', ['Barhy Hilant ', '6', ' Molan St']); ('Linux Thorwald 6 Heaven St', ['Linux Thorwald ', '6', ' Heaven St']); ('Barry Hilano 6 Mojan Street', ['Barry Hilano ', '6', ' Mojan Street']); ('Hellen&Barry Hiland 6 Moran St', ['Hellen&Barry Hiland ', '6', ' Moran St']); ('Albert Einstein 6 Moran St', ['Albert Einstein ', '6', ' Moran St'])
 
 
Pass nr  2 :
     ('Bill Gates 666 HellL and av', 'Bill Gates ', ['HellL', 'and', 'av']); ('Bil&Melinda Gattes 666 Hel Lannd Avenue', 'Bil&Melinda Gattes ', ['Hel', 'Lannd', 'Avenue']); ('Bill Gates 666 Hell Land Av', 'Bill Gates ', ['Hell', 'Land', 'Av']); ('Melindo+Billou Gates 666 Hell Land av', 'Melindo+Billou Gates ', ['Hell', 'Land', 'av'])
     ('Barry Hiland 6 Morgan Street', 'Barry Hiland ', ['Morgan', 'Street']); ('Linus Torvald 6 Heaven street', 'Linus Torvald ', ['Heaven', 'street']); ('Barry+Helen Hiland 6 Morgan St', 'Barry+Helen Hiland ', ['Morgan', 'St']); ('Helen+Barry Hiland 6 Morgan St', 'Helen+Barry Hiland ', ['Morgan', 'St']); ('Halbert Einstain 6 Morran St', 'Halbert Einstain ', ['Morran', 'St']); ('Barry Hilano 6 Mojan St', 'Barry Hilano ', ['Mojan', 'St']); ('Barhy Hilant 6 Molan St', 'Barhy Hilant ', ['Molan', 'St']); ('Linux Thorwald 6 Heaven St', 'Linux Thorwald ', ['Heaven', 'St']); ('Barry Hilano 6 Mojan Street', 'Barry Hilano ', ['Mojan', 'Street']); ('Hellen&Barry Hiland 6 Moran St', 'Hellen&Barry Hiland ', ['Moran', 'St']); ('Albert Einstein 6 Moran St', 'Albert Einstein ', ['Moran', 'St'])
 
 
Pass nr  3 :
     ('Bill Gates 666 HellL and av', 'Bill Gates ', ['HellL', 'and']); ('Bil&Melinda Gattes 666 Hel Lannd Avenue', 'Bil&Melinda Gattes ', ['Hel', 'Lannd']); ('Bill Gates 666 Hell Land Av', 'Bill Gates ', ['Hell', 'Land']); ('Melindo+Billou Gates 666 Hell Land av', 'Melindo+Billou Gates ', ['Hell', 'Land'])
     ('Barry Hiland 6 Morgan Street', 'Barry Hiland ', ['Morgan']); ('Linus Torvald 6 Heaven street', 'Linus Torvald ', ['Heaven']); ('Barry+Helen Hiland 6 Morgan St', 'Barry+Helen Hiland ', ['Morgan']); ('Helen+Barry Hiland 6 Morgan St', 'Helen+Barry Hiland ', ['Morgan']); ('Halbert Einstain 6 Morran St', 'Halbert Einstain ', ['Morran']); ('Barry Hilano 6 Mojan St', 'Barry Hilano ', ['Mojan']); ('Barhy Hilant 6 Molan St', 'Barhy Hilant ', ['Molan']); ('Linux Thorwald 6 Heaven St', 'Linux Thorwald ', ['Heaven']); ('Barry Hilano 6 Mojan Street', 'Barry Hilano ', ['Mojan']); ('Hellen&Barry Hiland 6 Moran St', 'Hellen&Barry Hiland ', ['Moran']); ('Albert Einstein 6 Moran St', 'Albert Einstein ', ['Moran'])
 
 
Pass nr  4 :
     ('Bil&Melinda Gattes 666 Hel Lannd Avenue', 'Bil&Melinda Gattes ', ['Hel', 'Lannd']); ('Bill Gates 666 HellL and av', 'Bill Gates ', ['HellL', 'and']); ('Melindo+Billou Gates 666 Hell Land av', 'Melindo+Billou Gates ', ['Hell', 'Land']); ('Bill Gates 666 Hell Land Av', 'Bill Gates ', ['Hell', 'Land'])
     ('Linus Torvald 6 Heaven street', 'Linus Torvald ', ['Heaven']); ('Linux Thorwald 6 Heaven St', 'Linux Thorwald ', ['Heaven'])
     ('Helen+Barry Hiland 6 Morgan St', 'Helen+Barry Hiland ', ['Morgan']); ('Halbert Einstain 6 Morran St', 'Halbert Einstain ', ['Morran']); ('Barry Hilano 6 Mojan Street', 'Barry Hilano ', ['Mojan']); ('Barry Hilano 6 Mojan St', 'Barry Hilano ', ['Mojan']); ('Barry+Helen Hiland 6 Morgan St', 'Barry+Helen Hiland ', ['Morgan']); ('Barhy Hilant 6 Molan St', 'Barhy Hilant ', ['Molan']); ('Barry Hiland 6 Morgan Street', 'Barry Hiland ', ['Morgan']); ('Hellen&Barry Hiland 6 Moran St', 'Hellen&Barry Hiland ', ['Moran']); ('Albert Einstein 6 Moran St', 'Albert Einstein ', ['Moran'])
 
 
Pass nr  5 :
     ('Bil&Melinda Gattes 666 Hel Lannd Avenue', ['Bil&Melinda', 'Gattes']); ('Bill Gates 666 HellL and av', ['Bill', 'Gates']); ('Melindo+Billou Gates 666 Hell Land av', ['Melindo+Billou', 'Gates']); ('Bill Gates 666 Hell Land Av', ['Bill', 'Gates'])
     ('Linus Torvald 6 Heaven street', ['Linus', 'Torvald']); ('Linux Thorwald 6 Heaven St', ['Linux', 'Thorwald'])
     ('Helen+Barry Hiland 6 Morgan St', ['Helen+Barry', 'Hiland']); ('Halbert Einstain 6 Morran St', ['Halbert', 'Einstain']); ('Barry Hilano 6 Mojan Street', ['Barry', 'Hilano']); ('Barry Hilano 6 Mojan St', ['Barry', 'Hilano']); ('Barry+Helen Hiland 6 Morgan St', ['Barry+Helen', 'Hiland']); ('Barhy Hilant 6 Molan St', ['Barhy', 'Hilant']); ('Barry Hiland 6 Morgan Street', ['Barry', 'Hiland']); ('Hellen&Barry Hiland 6 Moran St', ['Hellen&Barry', 'Hiland']); ('Albert Einstein 6 Moran St', ['Albert', 'Einstein'])
 
 
Pass nr  6 :
     ('Melindo+Billou Gates 666 Hell Land av', ['Melindo+Billou', 'Gates']); ('Bill Gates 666 Hell Land Av', ['Bill', 'Gates']); ('Bil&Melinda Gattes 666 Hel Lannd Avenue', ['Bil&Melinda', 'Gattes']); ('Bill Gates 666 HellL and av', ['Bill', 'Gates'])
     ('Linus Torvald 6 Heaven street', ['Linus', 'Torvald']); ('Linux Thorwald 6 Heaven St', ['Linux', 'Thorwald'])
     ('Helen+Barry Hiland 6 Morgan St', ['Helen+Barry', 'Hiland']); ('Barry Hilano 6 Mojan Street', ['Barry', 'Hilano']); ('Barry Hilano 6 Mojan St', ['Barry', 'Hilano']); ('Barry+Helen Hiland 6 Morgan St', ['Barry+Helen', 'Hiland']); ('Barhy Hilant 6 Molan St', ['Barhy', 'Hilant']); ('Barry Hiland 6 Morgan Street', ['Barry', 'Hiland']); ('Hellen&Barry Hiland 6 Moran St', ['Hellen&Barry', 'Hiland'])
     ('Halbert Einstain 6 Morran St', ['Halbert', 'Einstain']); ('Albert Einstein 6 Moran St', ['Albert', 'Einstein'])
 
 
Final results:
     Melindo+Billou Gates 666 Hell Land av; Bill Gates 666 Hell Land Av; Bil&Melinda Gattes 666 Hel Lannd Avenue; Bill Gates 666 HellL and av
     Linus Torvald 6 Heaven street; Linux Thorwald 6 Heaven St
     Helen+Barry Hiland 6 Morgan St; Barry Hilano 6 Mojan Street; Barry Hilano 6 Mojan St; Barry+Helen Hiland 6 Morgan St; Barhy Hilant 6 Molan St; Barry Hiland 6 Morgan Street; Hellen&Barry Hiland 6 Moran St
     Halbert Einstain 6 Morran St; Albert Einstein 6 Moran St

Intéressant, s’pas ? :D

Mais encore une fois, un contrôle manuel du résultat me semble indispensable (comme avec les anti-spam, en fait…).

[EDIT] : J’ai oublié de préciser que ce code est valable pour python3.2, il faudrait l’adapter un peu pour qu’il tourne sous python2.x ;)

Hello a tous, et bien c'est exactement ce que je cherchais.
La bibliotheque difflib.SequenceMatcher c'est vraiment cool :)
Merciiiiiiii:mouarf: