Structure lexicale. Reconnaissance approximative.
Une partie intégrale et essentielle de l'ingénierie linguistique est le stockage et le transfert d'énormes quantités d'information textuelle, souvent critique et protégée, et qui est soumise en permanence aux procédures de recherche et analyse. Ceci a plusieurs implications.
"Distance" entre les entités textuelles
La similitude entre les mots ou phrases est souvent conventionnelle, basée sur notre compréhension des textes. Puisque l'analyse sémantique est très onéreuse, on cherchera des critères facilement formalisables et implémentables. La mesure standard dans la théorie d'information est la distance de Hamming, qui compte le nombre de bits/caractères altérés dans un signal.
Ceci s'avère peu utile dans le TAL. Les "distances sémantiques" structurelles sont nombreuses (1 mois de cours...), nous allons parler d'une technique concrère, bien formalisée et utile.
L'utilité d'une telle mesure est, par exemple, de corriger automatiquement un mot qui est immédiatemment corrigible (distance très petite avec un mot connu, et pas trop de variantes), et la reconnaissance d'une faute, si on trouve un mot correct "pas trop loin". Sinon, on considère le mot comme inconnu.
Distance de Levenshtein - Damerau
Cette mesure nous informe combien d'opérations élémentaires MINIMUM : l'ajout, le remplacement, ou la suppression d'une lettre, ou l'échange entre deux lettres voisines – est nécessaire, afin de transformer un mot en son voisin. Par exemple, la distance vue comme ça entre "université" et "niversitéu" est 2, tandis que la comparaison caractère par caractère donne le résultat moins joyeux : aucune des 10 lettres ne correspond...
On l'appelle parfois "la distance d'édition". Elle peut nous aider à proposer des corrections à un mot légèrement erroné, si on connaît les mots corrects voisins. Elle a été introduite par Владимир Иосифович Левенштейн en 1965 et ne parlait pas de transpositions (échanges), seulement des additions, suppressions et substitutions. Frederick Damerau a ajouté aux opérations de Levenshtein la tranpsosition de deux caractères, et a affirmé que ces quatre cas couvrent plus de 80% d'erreurs humaines lors de l'écriture d'un mot.
i=n1=len(s1)-1; j=n2=len(s2)-1
def rec(i,j):
if i==-1: return j+1
if j==-1: return i+1
if s1[i]==s2[j]: return rec(i-1,j-1)
return 1+min(rec(i-1,j-1),rec(i,j-1),rec(i-1,j))
i,j > 0). Le noyau devient une procédure interne.
def vfd(s1,s2):
n1=len(s1)-1; n2=len(s2)-1
def rec(i,j):
if i==-1: return j+1
if j==-1: return i+1
if s1[i]==s2[j]: return rec(i-1,j-1)
lev = 1+min(rec(i-1,j-1),rec(i,j-1),rec(i-1,j))
if s1[i]==s2[j-1] and s1[i-1]==s2[j]: # transp.
return min(lev,1+rec(i-2,j-2))
return lev
return rec(n1,n2)
Le problème principal avec cette solution est son inefficacité à cause de l'évaluation répétitive des mêmes données, on appelle plusieurs fois la fonction avec les mêmes paramètres (la "calamité Fibonacci" pour ceux qui savent de quoi je parle...)
La solution traditionnelle est l'usage d'une matrice rectangulaire afin de stocker statiquement les résultats des appels. Mais nous utiliserons un dictionnaire de mémoïsation où on sauvegarde les paramètres et les résultats déjà vus, et donc, récupérés immédiatement.
def vfd1(s1,s2):
n1=len(s1)-1; n2=len(s2)-1; mem={}
for i in range(-1,n1+1):mem[(i,-1)]=i+1 # optimization
for j in range(-1,n2+1):mem[(-1,j)]=j+1
def rec(i,j):
t=(i,j) # abréviation, peu importe.
if t in mem: return mem[t]
if s1[i]==s2[j]:
r=rec(i-1,j-1); mem[t]=r; return r
lev = 1+min(rec(i-1,j-1),rec(i,j-1),rec(i-1,j))
if i>0 and j>0:
if s1[i]==s2[j-1] and s1[i-1]==s2[j]:
r=min(lev,1+rec(i-2,j-2))
mem[t]=r; return r
mem[t]=lev; return lev
return rec(n1,n2)
Les boucles for en bleu optimisent mem et remplacent :
if i==-1: mem[t]=j+1; return j+1 if j==-1: mem[t]=i+1; return i+1L'application de ce calcul dépend du problème. Supposons que la correction ortho nous intéresse. Alors si pour chaque mot qui n'est pas trouvé dans le vocabulaire on calcule la distance L-D, et on choisit les mots où elle est petite pour les suggestions, ce serait extrêmement coûteux, irréalisable. On peut modifier l'algorithme de manière à ce que le calcul est abandonné dès que la distance minimale dépasse un seuil, disons 2, mais ceci n'est pas facile. Norvig propose simplement de prendre le mot erroné, et d'exploiter le raisonnement de Levenshtein-Damerau pour engendrer tous les mots à distance 1. Le programme ci-dessous doit être facile à comprendre
alphabet = 'abcdefghijklmnopqrstuvwxyzàâæçéèêëîïôœùûüÿ'
def edits1(w):
splits = [(w[:i], w[i:]) for i in range(len(w) + 1)]
dels = [a + b[1:] for a, b in splits if b]
transp = [a + b[1] + b[0] + b[2:] for a, b in splits
if len(b)>1]
repl = [a + c + b[1:] for a, b in splits
for c in alphabet if b]
insr = [a + c + b for a, b in splits
for c in alphabet]
return set(dels + transp + repl + insr)
Alors sorted(list(edits1('mots'))) produit une liste de 378 mots...
['amots', 'aots', 'bmots', 'bots', 'cmots', 'cots', 'dmots', ..., 'motsy', 'motsz', 'motsà', 'motsâ', 'motsæ', 'motsç',... 'mîots', 'mîts', 'mïots', 'mïts', 'môots', 'môts', 'mùots', 'ûots', 'ümots', 'üots', 'ÿmots', 'ÿots', 'œmots', 'œots']et on peut vérifier leur présence dans le dictionnaire de mots connus. On peut aussi appliquer les distorsions aux éléments de cet ensemble, et ainsi localiser les mots à distance 2. Ensuite on peut proposer des corrections ; il serait souhaitable d'avoir un dictionnaire qui contient les fréquences des mots, ainsi on pourra suggérer les corrections plus probables. Bien sûr, il n'est pas rationnel d'engendrer d'abord l'ensemble complet des mots distants de 2, et vérifier ensuite leur présence ; il faut le faire incrémentalement, afin d'économiser la mémoire. Plusieurs variantes ont vu le jour. Par exemple, on stocke dans le dictionnaire les mots distordus (marqués comme tels ; pour ne pas exploser le dictionnaire : seulement les supressions des caractères), etc. Aussi, on utilise des techniques considérablement plus élaborées, par ex. des structures de données probabililistes connues comme les filtres de Bloom, avec plusieurs fonctions simultanées de hachage. Un devoir de l'année dernière a été consacré à un correcteur orthographique. Il est évident que vous avez à votre disposition des dizaines de solutions implémentées dans tous les langages, et styles. Lisez l'article de Norvig (utilisé dans mon cours). Peut-être, sans copier quoi que ce soit de cet article, je vous demanderai de tester/implémenter quelques idées algorithmiques très limitées... (Peut-être vous travillerez sur les filtres de Bloom – extrêmement faciles à réaliser ; peut-être sur les arbres BK [Burkhard-Keller].)
|
|
|