Méthodologie de la correction orthographique : Algorithme Soundex et distance de Levenshtein

• Avant toute chose, il faut un bon lexique, "à large ouverture" comme on dit dans le jargon linguistique : c'est-à-dire suffisamment varié pour tenir compte d'un grand nombre de corps de métiers et de parlers différents. La création de ce lexique est souvent réalisée à partir de corpus importants (base textuelle Frantext, sous-titres de films, grands quotidiens) en fonction du niveau de langue et de variété souhaité. De nombreuses études sont consacrées à ces problématiques (qui relèvent du TAL, le Traitement Automatique des Langues).

• La méthode Soundex consiste à chiffrer un terme sur 4 octets en tenant compte des caractéristiques phonétiques de la langue concernée. Cela permet de rapprocher des termes aux orthographes différentes par le biais de leur prononciation. Ex. éléfan > éléphant ; grau > gros, etc.

Procédure (tous les codes sont en Visual Basic)

1) Mise en majuscules (UCase ; nota : ne pas oublier le Ç)

2) Conservation de la lettre initiale (premierCar = Left(mot, 1) )

3) Remplacement des voyelles (A E I O U), ainsi que des consonnes H, W par 0, et suppression des éventuels blancs ou tirets:

4) Remplacement des consonnes restantes selon le tableau suivant (idem que précédemment):

5) Suppression des doublons consécutifs

6) Conservation des quatre premiers caractères de la chaîne. Si celle-ci est < 4, on complète le reste par des zéros

Frédéric Brouard a mis en ligne un excellent article, L'art des Soundex, dans lequel il présente à la fois l'algorithme Soundex (adapté à l'anglais) ainsi qu'un algorithme Soundex2 (adapté au français) dont il est l'auteur. J'ai donc transcris ce code Soundex2 en Visual Basic et je l'ai adapté à Sanzéreur. Le résultat est effectivement plus probant que la francisation qu'on trouve par ailleurs.

Articles sur ce sujet : Soundex - Wikipédia - Understanding Classic SoundEx Algorithms - Search Names & Phrases Based on Phonetic Similarity (w/source code) - NARA and Daitch-Mokotoff Soundex

• Distance de Levenshtein

Il s'agit d'une valeur exprimant le nombre de caractères pour passer d'une chaîne à une autre. D'une certaine manière, cette valeur ou "distance" mesure la similitude entre deux termes (pratique pour les recherches généalogiques, ou dans des bases de données importantes quand on n'est plus très sûr de l'orthographe d'un nom). Il est donc intéressant ensuite de la formuler en pourcentage. On la trouve facilement sur Internet écrite en PHP, Turbo Pascal, C#, etc. Mais beaucoup moins en Visual Basic. Voici donc le code (récupéré sur planet-source-code.com)

Private Function LevenshteinDistance(argStr1 As String, argStr2 As String) As Long
Dim m As Long, n As Long
Dim editMatrix() As Long, i As Long, j As Long, cost As Long
Dim str1_i As String, str2_j As String
Dim p() As Long, q() As Long, r As Long
Dim x As Long, y As Long

n = Len(argStr1)
m = Len(argStr2)

'If (n = 0) Or (m = 0) Then Exit Function
ReDim editMatrix(n, m) As Long

For i = 0 To n
editMatrix(i, 0) = i
Next

For j = 0 To m
editMatrix(0, j) = j
Next

For i = 1 To n
str1_i = Mid$(argStr1, i, 1)
For j = 1 To m
str2_j = Mid$(argStr2, j, 1)
If str1_i = str2_j Then
cost = 0
Else
cost = 1
End If

editMatrix(i, j) = min3(editMatrix(i - 1, j) + 1, editMatrix(i, j - 1) + 1, editMatrix(i - 1, j - 1) + cost)
Next j
Next i

LevenshteinDistance = editMatrix(n, m)
Erase editMatrix
End Function

Une application concrète est proposée sur vbfrance.com.

Article Wikipédia : Distance de Levenshtein.

Nota : Le moteur de correction orthographique de Sanzéreur est une version française et améliorée du logiciel A Comprehensive Spell Checker Revisited par Rde de Planet Source Code. La francisation a consisté en la création d'une nouvelle base Access à partir d'un fichier texte (provenances diverses dont Christophe Pelletier, OpenOffice, ABU). Car la méthode Soundex, pour être intéressante, oblige à constituer une base avec les mots ET leur code Soundex associé (plus rapide!). Les améliorations ont porté sur "une discrimination" automatique par la distance Livenshtein. En effet le logiciel anglais n'ajuste pas cette distance en fonction du nombre de suggestions.

• La correction orthographique fera probablement l'objet d'autres recherches.

En effet une première implémentation empirique, basée sur les probabilités des erreurs, avait fonctionné parfaitement, avec des résultats très proches de ceux de MS Word. Les règles étaient notamment les suivantes:

- problème d'accents ou de cédille : éstimer, merçi

- caractère supplémentaire : esssai

- caractère manquant : apeler

- caractère incongru (faute de frappe): visi8on

- inversion de deux caractères (frappe rapide) : docn pour donc

En dernier recours, le moteur orthographique recherchait le caractère erroné puis parcourant le lexique à la recherche d'un terme comportant la formule : left(mot_initial, position_du_caractere_erroné - 1) And right(mot_initial, position_du_caractere_erroné +1). Cela fonctionnait bien, mais avec une lacune importante : le moteur travaillait en supposant une seule faute par mot. Or chacun sait qu'il est très facile de faire plusieurs fautes par mots !

Par contre, cette méthodologie ne pouvait en aucun cas faire face aux problèmes orthographiques dus à la phonétique. Voir à ce sujet l'excellent diaporama de Jean Véronis (prof. à l'Univ. de Provence) sur la correction orthographique.

Autre problème : les fautes grammaticales ne sont toujours pas prises en compte : un maux (pour mot), le mon (pour mont). Cela suppose une désambiguïsation lexicale (sens d'un mot en contexte) qui dépasse le cadre d'un correcteur orthographique pour entrer dans le domaine du traitement automatique d'une langue et de l'analyse grammaticale en contexte. Bien que très ambitieuses, ces problématiques sont à l'étude. Ne travaillant qu'à titre individuel, il est bien évident que je serai forcé de me restreindre à définir un certain nombre de règles (accords, homographes et homophones, ponctuation, etc).

Les statistiques seront à ce titre intéressantes. J'imagine que les erreurs les plus courantes concernent l'infinitif : *il n'a pas terminer, *je vais mangé ; l'accord des participes avec l'auxiliaire avoir :*les roses que tu m'as donné ; les usages les plus courants : *malgré que (bien que la nouvelle orthographe semble l'avoir admis!), *la terre toute entière; les emplois difficiles ou ambigus tous/tout, aucun/aucuns ; leur/leurs; ou encore l'absence d'accents sur les majuscules.

Le Bréviaire d'Orthographe Française sera donc le bienvenu dans l'aide grammaticale...

Il faudra également suivre de près le projet de correcteur grammatical libre pour le français pour OpenOffice, initié par inDesko :

cf. Analyse et conception d'un correcteur grammatical libre pour le français, par Myriam Lechelt (stage de Master)

Analyse morphologique : lexiques morphologiques DICO, LEFFF, Morphalou

• DELAF : Dictionnaire électronique des formes fléchies du français (Université de Marne-la-Vallée) :

+ de 700 000 entrées, env. 40Mo

• DICO : ABU : + de 300 000 entrées (env. 10 Mo, format TXT)

• Le lexique des formes fléchis du français (LEFFF voir aussi ici) : 404 634 entrées (env. 40 Mo, format TXT)

• Lexique morphologique ouvert du français (MORPHALOU) : 540 000 entrées, format XML, env. 70Mo

Ces quatre lexiques morphologiques sont des mines d'or !

DICO a été implémenté dans la partie contextuelle , pour les analyses sommaires et rapides, tandis que le DELAF, du fait de sa qualité et de son étendue, a fait l'objet d'un traitement minutieux, et est consultable via le menu contextuel (en cas de recherche infructueuse), et via le menu Outils > Analyser une forme.

• Dictionnaire des synonymes : c'est celui d'OpenOffice.org, disponible ici. Il contient d'après mes calculs un peu plus de 41 000 entrées

• Dictionnaire d'Emile Littré : Le dictionnaire Littré (1873, 2e éd. 1872-1877) est tiré du XML Littré réalisé par François Gannaz : il contient 78 423 entrées et 293 009 citations. Un grand merci et d'avoir réalisé ce travail, et de me l'avoir communiqué ! Ce fichier est sous licence GPL.