tyrtamos

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:

Code PYTHON :

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

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:

Code PYTHON :

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

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:

Code PYTHON :

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

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:

Code PYTHON :

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

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!