Intelligence artificielle: comparaison de deux mots

J’avais envie depuis quelques temps de me pencher sur l’intelligence artificielle et plus particulièrement sur la comparaison de deux mots.

Je me demandais comment un programme pouvait faire pour détecter les fautes d’orthographe. Par exemple, qua,d on tape sur un moteur de recherche « anagrame », il nous suggère « anagramme ». Comment est-ce possible en Python ?

Au menu sur cette page...

Intelligence artificielle et comparaison de deux mots: les débuts

Bien entendu, nous connaissons toutes et tous la comparaison directe de deux chaînes de caractères:

def compare(a , b):
    return a == b

>>> compare("toto" , "tata")
True

Bien entendu, cette méthode n’est pas du tout satisfaisante car c’est bien trop binaire… Nous devons imaginer une fonction qui admette une certaine tolérance en terme d’orthographe.

Intelligence artificielle et comparaison de deux mots: la distance de Jaro-Winkler

Parlons mathématiques… et munissons l’ensemble des mots d’une distance un peu spéciale: la distance de Jaro-Winkler.

Pour deux chaînes de caractères, on la définit ainsi:$$d(s_1,s_2)=\frac{1}{3}\left( \frac{m}{|s_1|}+\frac{m}{|s_2|}+\frac{m-t}{m} \right)$$ où:

$|s_k|$ représente le nombre de caractères de $s_k$;
$m$ représente le nombre de caractères commun aux deux chaînes;
$t$ représente le nombre de transpositions des caractères qui ne sont pas « à la bonne place ».

Je reprends ici l’exemple de wikipedia :

$s_1$ = « MARTHA »
$s_2$ = « MARHTA »
il y a 6 caractères communs aux deux chaînes donc $m=6$;
les deux chaînes donnent deux ensembles ordonnés : {M,A,R,T,H,A} et {M, A, R, H, T, A}. Les 3 premiers éléments coïncident, ainsi que les deux derniers. Seuls {T, H} et {H, T} ne coïncident pas, soit 1 transposition.

Je ne vais pas m’attarder sur cela car la page wikipedia donnent plusieurs exemples pour mieux comprendre, donc jetez-y un coup d’œil.

Jusqu’à présent, nous n’avons manipulé que la distance de Jaro. Winkler a ajouté à cette technique une autre chose:

La méthode introduite par Winkler utilise un coefficient de préfixe p qui favorise les chaînes commençant par un préfixe de longueur ℓ (avec ℓ ≤ 4).
Wikipedia

La distance de Jaro-Winkler est donc bien plus performante que celle de Jaro.

En Python, il existe un module qui nous permet d’obtenir cette distance: le module jaro. Pour l’installer avec PIP :

pip install jaro

Ainsi, pour connaître la distance entre « chaîne » et « chêne », on aura:

>>> a, b = "chêne", "chaîne"
>>> from jaro import jaro_winkler_metric
>>> jaro_winkler_metric(a , b)
0.8577777777777779
>>> c = "chienne"
>>> jaro_winkler_metric(a , c)
0.7657142857142858
>>> d = "chaînne"
>>> jaro_winkler_metric(str1,d)
0.9714285714285714

Donc d’après cette distance, « chaîne » est plus proche de « chêne » que de « chienne ».

Et quand on compare « chaînne » (avec une faute de frappe » à « chaîne », la distance et proche de 1… Pas mal !

Intelligence artificielle et comparaison de deux mots: distance de Levenshtein

La distance de Levenshtein est une autre distance possible pour comparer deux mots.

Je passe les détails de sa définition (disponibles sur la page de wikipedia) et vais directement aborder le côté Python.

En effet, il existe fort heureusement un module qui nous permet de la calculer directement: le module éponyme.

pip install Levenshtein

from jaro import jaro_winkler_metric
from Levenshtein import distance, ratio

str1 = "urluberlu"
str2 = "urlubrelu"

print ( jaro_winkler_metric(str1 , str2) )
print ( 'Distance : {} ; ratio : {}' . format(distance(str1,str2) , ratio(str1,str2)) )

0.9777777777777777
Distance : 2 ; ratio : 0.8888888888888888

J’ai voulu ici comparer les résultats obtenus avec les deux distances : Jaro-Winkler d’une part, et Levenshtein d’autre part.

La distance de Jaro-Winkler entre les deux chaînes est très proche de 1, bien plus que le ration donné par Levenshtein. Notez ici que la distance de Levenshtein est une réelle distance dans le sens où plus elle est éloignée de 0, plus cela signifie que les deux chaînes sont éloignées l’une de l’autre. Ici, le couple (distance , ratio) nous conforte dans notre prise de décision: si la distance est éloignée de 0 et si le ration est éloignée de 1, on peut prendre la décision de conclure que les deux chaînes n’ont rien à voir l’une avec l’autre.

from jaro import jaro_winkler_metric
from Levenshtein import distance, ratio

str1 = "drosophile"
str2 = "mouche"

print ( 'Distance de Jaro-Winkler : {}' . format(jaro_winkler_metric(str1 , str2)) )
print ( 'Distance : {} ; ratio : {}' . format(distance(str1,str2) , ratio(str1,str2)) )

Distance de Jaro-Winkler : 0.6
Distance : 7 ; ratio : 0.375

Intelligence artificielle et comparaison de deux mots: d’autres distances

Il existe bien plus de distances que les deux cités dans cet article

Le module Python textdistance en contient plus de 30.

Parmi ces distances, on retrouve celle de Jaro-Winkler et celle de Levenshtein, mais il y en a deux autres assez intéressantes: les distances phonétiques RMA et Editex.

pip install textdistance

Un premier exemple

from textdistance import mra, editex, hamming, levenshtein, jaro_winkler

str1 = "philosofie"
str2 = "philosophie"

print ( 'Distance de Jaro-Winkler : {}' . format(jaro_winkler(str1 , str2)) )
print ( 'Distance de Levenshtein : {}' . format(levenshtein(str1,str2)) )
print ( 'Distance de Hamming : {}' . format(hamming(str1,str2)) )
print ( 'Distance phonétique MRA : {}' . format( mra.distance(str1,str2) ))
print ( 'Distance phonétique Editex : {}' . format( editex.distance(str1,str2) ))

Distance de Jaro-Winkler : 0.9436363636363637
Distance de Levenshtein : 2
Distance de Hamming : 4
Distance phonétique MRA : 2
Distance phonétique Editex : 3

Un deuxième exemple

from textdistance import mra, editex, hamming, levenshtein, jaro_winkler

str1 = "filosofi"
str2 = "philosophie"

print ( 'Distance de Jaro-Winkler : {}' . format(jaro_winkler(str1 , str2)) )
print ( 'Distance de Levenshtein : {}' . format(levenshtein(str1,str2)) )
print ( 'Distance de Hamming : {}' . format(hamming(str1,str2)) )
print ( 'Distance phonétique MRA : {}' . format( mra.distance(str1,str2) ))
print ( 'Distance phonétique Editex : {}' . format( editex.distance(str1,str2) ))

Distance de Jaro-Winkler : 0.7651515151515151
Distance de Levenshtein : 5
Distance de Hamming : 11
Distance phonétique MRA : 6
Distance phonétique Editex : 7

La comparaison phonétique en français semble ne pas trop bien fonctionner par rapport à l’anglais :

Un troisième exemple (anglais)

from textdistance import mra, editex, hamming, levenshtein, jaro_winkler

str1 = "engine"
str2 = "ingeane"

print ( 'Distance de Jaro-Winkler : {}' . format(jaro_winkler(str1 , str2)) )
print ( 'Distance de Levenshtein : {}' . format(levenshtein(str1,str2)) )
print ( 'Distance de Hamming : {}' . format(hamming(str1,str2)) )
print ( 'Distance phonétique MRA : {}' . format( mra.distance(str1,str2) ))
print ( 'Distance phonétique Editex : {}' . format( editex.distance(str1,str2) ))

Distance de Jaro-Winkler : 0.6626984126984127
Distance de Levenshtein : 3
Distance de Hamming : 5
Distance phonétique MRA : 1
Distance phonétique Editex : 3

Ici, là où la distance de Jaro-Winkler est relativement éloignée de 1, la distance MRA est proche de 0, contrairement aux exemples français. Hasard des mots ?…