Comparaison de chaînes de caractères

Introduction

Dans un précédent article nous avons vu comment on pouvait avec du NLP ou sans (en utilisant les « sacs de mots ») comparer des chaînes de caractères, ou plutôt des phrases. Je vous propose dans ce post d’aborder la comparaison de mots. La question que nous allons nous poser ici n’est pas tant sur le sens d’une phrase mais plutôt sur la ressemblance d’un mot par rapport à un autre.

Nous aborderons donc les différentes problématiques que nous rencontrons couramment quand on traite des chaînes de caractères. Des fautes de frappe, des fautes tout court, des abréviations, bref des erreurs diverses et variées qui nous empêchent de travailler correctement l’information. Très clairement nous utiliserons des algorithmes de distance (Levenshtein, Hamming, etc.) qui ont fait maintes fois preuve de leur efficacité. Puis nous irons un peu plus loin avec une librarie qui a pour le moins que l’on puisse dire un nom original : Fuzzywuzzy !

Comparaison à l’ancienne !

Pour commencer la première chose à faire lorsque l’on compare des chaînes de caractères c’est de retirer les éléments qui n’apportent pas de valeur à la chaîne elle même. C’est ce que l’on appelle le bruit. Imaginez en effet que dans mon système j’ai deux prénoms : « Ben oit. » et « benoît« . Il paraît évident pour un être humain que c’est le même prénom. Il parait tout aussi évident qu’une comparaison « basique » ne donnera pas le résultat escompté. Les majuscule, trémas, espaces et autres signes de ponctuation sont important mais nous empêchent de comparer nos chaînes.

Nous allons donc devoir les retirer ou les remplacer (comme le î en i, ou le B en b). De même nous allons choisir la casse (majuscule ou minuscule) afin de comparer les chaînes sur un même niveau.

Voici un exemple d’une fonction Python pour comparer ces deux chaînes :

noise_list = [".", ",", "?", "!", ";"]
def prepString(_str, _noise = True, _multiplespaces = True):
    # remove noise (punctuation) if asked (by default yes)
    if _noise:
        for car in noise_list:
            _str = _str.replace(car, "")
    # replace multiple spaces by ine in string if requested (default yes)
    if _multiplespaces:
        _str = re.sub("\s+", " ", _str).strip()
    return _str.strip().lower()

def compareString(Str1, Str2):
    return prepString(Str1) == prepString(Str2)

compareString("Ben  oit.,", "BEN oit")

True

Comparaison Hamming

L’objectif de cette comparaison est de compter les différences qu’il y a entre deux chaînes de caractères. Attention les chaînes comparées doivent être de même taille ce qui devient très vite un inconvénient.

def hamming_distance(string1, string2): 
    if (len(string1) != len (string2)):
        return -1
    # Start with a distance of zero, and count up
    distance = 0
    # Loop over the indices of the string
    L = len(string1)
    for i in range(L):
        # Add 1 to the distance if these two characters are not equal
        if string1[i] != string2[i]:
            distance += 1
    # Return the final count of differences
    return distance

hamming_distance("BINUIT", "BENOIT")

2

Nous avons bien deux différences entre BINUIT et BENOIT (le I à la place du E et le U à la place du O). Dans la réalité la comparaison Hamming (code hamming) est plutôt utilisée pour vérifier/corriger des erreurs dans les transmissions de données.

Comparaison Jaro-Winkler

Cette comparaison est beaucoup plus fine et va nous procurer un score qui nous donnera la distance entre les deux chaînes comparées. Cette mesure de distance est issue de la distance de Jaro qui est souvent utilisée pour les opérations de dédoublonnage.

Si s est la chaîne de caractère :

Cf. wikipédia

• |s_1| est la longueur de la chaîne de caractères s1 (idem pour S_2)
• m est le nombre de caractères
• t est le nombre de transpositions

Python a bien sur une librairie pour gérer cette formule : jaro-winkler

Installons la librairies via pip :

pip install jaro-winkler

Puis utilisons là :

import jaro
# Calcul classique jaro
jaro.jaro_metric("BINUIT", "BENOIT")

0.7777777777777777

# Distance Jaro avec ajustement Winkler
jaro.jaro_winkler_metric("BINUIT", "BENOIT")

0.7999999999999999

Le score renvoyé (entre 0 et 1) nous permet d’apprécier la similarité entre les deux chaînes.

Levenshtein

L’algorithme de Levenshtein nous renvoit deux métriques : la distance et le ratio.

• Distance : C’est la mesure du nombre minimum de modifications (insertions, suppressions ou substitutions) qu’il faut effectuer pour changer une séquence d’un mot en l’autre.
• Ratio : Similarité entre deux mots

import Levenshtein as lev
def levCalclulate(str1, str2):
    Distance = lev.distance(str1, str2)
    Ratio = lev.ratio(str1, str2)
    print("Levenshtein entre {0} et {1}".format(str1, str2))
    print("> Distance: {0}\n> Ratio: {1}\n".format(Distance, Ratio))

levCalclulate("Benoit", "Ben")
levCalclulate("Benoit", "Benoist")

Levenshtein entre Benoit et Ben
> Distance: 3
> Ratio: 0.6666666666666666

Levenshtein entre Benoit et Benoist
> Distance: 1
> Ratio: 0.9230769230769231

Fuzzywuzzy

Cette librairie permet d’aller plus loin que des comparaisons de type distance que nous avons vu jusque là. Elle permet de détecter des Lien & Appartenance, des inversions, etc.

Lien et appartenance (ratio)

Str1 = "Les scouts de France"
Str2 = "France"
Partial_Ratio = fuzz.partial_ratio(Str1.lower(),Str2.lower())
print(Partial_Ratio)

100

Inversions dans la chaîne (Token_Sort_Ratio)

Str1 = "Ceci est un test"
Str2 = "un test est ceci"
Ratio = fuzz.ratio(Str1.lower(),Str2.lower())
Partial_Ratio = fuzz.partial_ratio(Str1.lower(),Str2.lower())
Token_Sort_Ratio = fuzz.token_sort_ratio(Str1,Str2)
print(Ratio)
print(Partial_Ratio)
print(Token_Sort_Ratio)

50
50
100

Chaînes de taille différentes (Cf. token_set_ratio)

Str1 = "Ce soir on regarde un match France contre Angleterre"
Str2 = "France vs Angleterre"
Ratio = fuzz.ratio(Str1.lower(),Str2.lower())
Partial_Ratio = fuzz.partial_ratio(Str1.lower(),Str2.lower())
Token_Sort_Ratio = fuzz.token_sort_ratio(Str1,Str2)
Token_Set_Ratio = fuzz.token_set_ratio(Str1,Str2)
print(Ratio)
print(Partial_Ratio)
print(Token_Sort_Ratio)
print(Token_Set_Ratio)

50
70
53
92

Conclusion

Il est plutôt simple d’utiliser ces algorithmes en fait. La difficulté ne réside en effet pas dans l’utilisation mais plutôt dans le choix du bon algorithme. En effet il existe beaucoup d’algorithmes de comparaison de chaînes de caractères. Vous pouvez allez sur https://pypi.org/project/textdistance/ pour avoir un bref aperçu des algorithmes de distance. Il y en a beaucoup et chacun a ses spécificités et surtout sa spécialité. vous en trouverez qui sont spécialisés dans les chaînes courtes, longues, avec des nombres ou pas, etc.

En d’autres termes il vaut mieux bien se documenter et bien comprendre ces algorithmes avant des les mettre en oeuvre et pourquoi pas aussi de les combiner.

Les sources de cet articles sont sur Github.