par , 27/02/2015 à 07h37 (3947 Affichages)
On a quelque fois le problème suivant: on a une liste de noms saisis au clavier, et qui peut donc comporter des fautes de frappes.
Par exemple: ["Durand", "Meyer", "Dupond", "Dopon", "DUPON", "Nguyen", "Toto"]
Et je cherche si j'ai "Dupont" dans la liste. Par les méthodes habituelles (recherche exacte, wildcard, regex, ...), je ne trouve pas parce que s'il y a une faute de frappe (ou plusieurs?), elle peut être n'importe où: "Dupon"? "Dopond", "Tupond"...
Dans les modules livrés avec Python, il y une fonction qui fait ça très bien: SequenceMatcher (module difflib). Voyons l'utilisation basique:
1 2 3 4 5 6 7
| from difflib import SequenceMatcher
mots =["Durand", "Meyer", "Dupond", "Dopon", "DUPON", "Nguyen", "Toto"]
ratio = 0.8
resultat = [mot for mot in mots if SequenceMatcher(None, "Dupont", mot).ratio() >= ratio]
print(resultat)
['Dupond'] |
J'ai donc trouvé un nom "Dupond" qui pourrait être "Dupont" (merci Tintin...) avec une faute de frappe.
Vous voyez que j'ai utilisé un ratio=0.80. En changeant ce ratio, on va pouvoir accepter plus ou moins d'erreurs sur le mot recherché:
- Avec ratio = 1.0: je n'accepte que le mot exact. Je ne trouverais donc rien avec l'exemple ci-dessus.
- Avec ratio = 0.0: j'accepte tout, ce qui n'a, bien entendu, aucun intérêt!
D'après mon expérience, le ratio peut aller selon les besoins entre 0.5 et 0.9. Avec la liste ci-dessus, on trouverait:
ratio = 0.5 => ['Durand', 'Dupond', 'Dopon']
ratio = 0.6 => ['Dupond', 'Dopon']
ratio = 0.7 => ['Dupond', 'Dopon']
ratio = 0.8 => ['Dupond']
ratio = 0.9 => []
Mais je ne trouve pas "DUPON", parce que ce nom est en majuscule. Pour le trouver aussi (si c'est pertinent dans le contexte!), on va neutraliser la casse, c'est à dire ne comparer que les mots passés préalablement en majuscules. Et comme on est en français, on va même les passer en "majuscules non accentuées" avec la fonction suivante:
1 2 3 4 5 6 7 8 9 10
| import unicodedata
def majuscsa(chaine):
"""Convertit la chaine (unicode), en majuscules non accentuées
"""
# convertit en majuscule avec conservation des accents éventuels
chaine = chaine.upper()
# supprime les accents éventuels qui restent
chnorm = unicodedata.normalize('NFKD', chaine)
return "".join([car for car in chnorm if not unicodedata.combining(car)]) |
Et dans ce cas, on va créer une fonction qui va contenir notre SequenceMatcher et qui permettra d'accepter ou non la prise en compte de la casse:
1 2 3 4 5 6 7 8 9
| from difflib import SequenceMatcher
def simil(mot1, mot2, ratio, okmajusc=True):
"""compare les 2 mots, et retourne True si le tx de similitude >= ratio
si okmajusc=True, la comparaison est faite en majuscule sans accent
"""
if okmajusc:
mot1, mot2 = majuscsa(mot1), majuscsa(mot2)
return SequenceMatcher(None, mot1, mot2).ratio() >= ratio |
Avec ces 2 fonctions, et sans tenir compte de la casse, on trouveras:
ratio = 0.5 => ['Durand', 'Dupond', 'Dopon', 'DUPON']
ratio = 0.6 => ['Dupond', 'Dopon', 'DUPON']
ratio = 0.7 => ['Dupond', 'Dopon', 'DUPON']
ratio = 0.8 => ['Dupond', 'DUPON']
ratio = 0.9 => ['DUPON']
Et, cerise sur le gâteau, si on utilise une base de données relationnelle sqlite3 avec le pilote Python, on peut ajouter ces 2 fonctions Python pour pouvoir les utiliser directement dans les requêtes SQL! Avec une connexion ouverte cnx, on va faire simplement:
1 2 3 4 5
| # fonction 'simil' (similitude de 2 chaines)
cnx.create_function("simil", 3, simil)
# fonction 'majuscsa' (majuscule_sans_accent))
cnx.create_function("majuscsa", 1, majuscsa) |
J'utilise couramment ces fonctionnalités dans une base de données sqlite3 de plusieurs milliers d'articles, et ça m'est vraiment très utile!