Outils pour utilisateurs

Outils du site


mots_similaires

Trouver des mots similaires dans une liste avec SequenceMatcher

J'ai 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:

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:

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:

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:

# 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!

Amusez-vous bien!

mots_similaires.txt · Dernière modification: 2015/02/27 08:30 par tyrtamos

Outils de la page