Puisque le cours restant traitera les moteurs de recherche, l'indexation, etc., en TP encore devant nous, nous traiterons d'autres sujets, souvent déjà mentionnés. Donc une bonne partie de ces feuilles contiendra un complément du cours.
ATTENTION !! Nous avions seulement 8 séances de cours (12 heures), mais nous continuerons à travailler à 8h15, lundi, jusqu'à 12h00, comme auparavant ; ce seront 3 heures de TP. Ainsi nous terminerons le semestre plus tôt ! La fin su semestre sera consacré – si vous voulez ; je peux proposer d'autres choses... – à votre dernier devoir maison.
Si votre devoir actuel (les grammaires) vous pose des problèmes, posez des questions, et travaillez dessus, mais faites d'abord l'exercice 1.
La recherche des mots similaires, approximatifs, est très importante dans au moins deux contextes différents :
Vous trouverez plusieurs définitions de telles distances, certaines, d'intérêt théorique indiscutable, comme la distance de Hamming, n'est pas utile dans le contexte qui nous intéresse. (Pour les "codes correcteurs" qui corrigent des signaux bruités, si).
La distance de Levenshtein (Vladimir Levenshtein (Владимир Иосифович Левенштейн), 1965), appelée parfois la "distance d'édition" mesure le nombre d'opérations primitives à effectuer, afin de transformer un mot en un autre. Les opérations primitives sont: ajout d'un caractère, effacement d'un caractère, et remplacemt d'un caractère par un autre. Frederick Damerau a ajouté encore une opération : la transposition de deux caractères adjacents. Selon le modèle d'origine, ceci a besoin de deux opérations, non pas une, mais c'est une faute fréquente, il est donc judicieux de la distinguer.
(D'ailleurs, à titre de digression : la portée de ces concepts ne se réduit pas au traitement du texte, mais trouve des applications dans l'analyse des variations génétiques dans les séquences d'ADN).
Il s'agit de nombre minimal d'opérations de modification. Par exemple, la distance vue comme la quantité de travail d'édition entre "université" et "niversitéu" est 2, tandis que la comparaison caractère par caractère (la non-correspondance) donne le résultat moins joyeux : aucune des 10 lettres ne correspond... Le calcul de la distance de Levenshtein ou celle de Damerau–Levenshtein a été publiée dans plusieurs variantes. Pour nous la compréhension est plus importante que l'efficacité, mais cette dernière ne sera pas oubliée.
Notre algorithme est un peu différent de ceux typiquement publiés. Tous commencent par l'allocation d'une matrice indexée par despositions des lettres de deux mots, et il vous faudra plusieurs minutes afin de comprendre comment cela marche. Dans notre formulation ceci doit être immédiat.
Notre code utilise la récursivité de manière assez intense, et le programme devient très court. Supposons que s1, s2 soient les deux chaînes (variables globales dans le programme ci-dessous). Voici la procédure qui calcule leur distance de Levenshtein (sans transpositions).
Initialement 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.
# ou : if s1[i-1:i+1] == s2[j]+s2[j-1]:
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 même "calamité" qui fait exploser la complexité de la fonction de Fibonacci...)
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+1
BTW., Si vous vous posez la question : "si cette mémoïsation est si efficace et importante, pourquoi elle n'est pas disponible en standard??
La réponse est : elle l'est. Testez ce module :
from functools import *
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
Cependant, afin que l'on puisse stocker dans le cache les arguments et le résultat de la fonction, il faut que ces données soient hashables, et ceci n'est pas universel. De plus, des algorithmes utilisant des appels répétitifs ne sont pas courants non plus. Donc, la mémoïsation n'est pas le pain quotidien des programmeurs, et le dispositif se trouve dans un module optionnel, non pas dans la librairie built-in.
Exercice 1.
Écrivez un correcteur d'orthographe minimaliste, une fonction qui accepte un mot (chaîne), et qui trouve dans votre dictionnaire, par ex. dans la liste de mots récupérée depuis le fichier liste_mots tous les mots dont la distance L-D est inférieure à 3 (donc, 0, 1 ou 2). D'abord on cherche la correspondence exacte, si c'est le cas, le mot n'est pas mémorisé, et la fonction ne fait rien, le mot est correct. Sinon, le programme affiche toutes les corrections possibles du mot entré. Cette liste ne doit pas être trop longue. On a la possibilité d'optimiser l'algorithme de Levenshtein de manière à ce qu'il s'arrête quand on sait que la distance dépassera sûrement un certain seuil, mais vous n'allez pas travailler dessus.
Puisque vous aurez besoin de plusieurs tests, je vous conseille de lire le fichier avec les mots, qui a presqque 2M, 130000 mots... en faire une liste ou un set, et de stocker cette séquence dans un fichier binaire, purifié (sans fréquences) grâce au module pickle.
Lisez la documentation, exploitez pickle.dump et pickle.load. Si besoin, posez des questions, mais faites-le ! La sérialisation des données Python peut être très utile.
Exercice 2.
Si vous êtes fatigués avec votre devoir maison, tant pis, cet exercice n'est pas pour vous. Mais si vous avez encore des forces et un minimum d'ambition : essayez de résoudre cet exercice avec les DCG Prolog. La grammaire peut être considérablement plus élégante qu'en NLTK, même si sa syntaxe deviendra plus verbose. Mais vous pourrez traiter des nombres quelconques comme atomes, sans les charcuter en caractères individuels.
Exercice 3.
Je ne sais pas si j'arrive à présenter le sujet en cours... Faites le codage de tries présenté dans mes notes de cours. Testez le programme sur les données suggérées : les mots dans le fichier liste_mots de moins de 7 lettres, qui commencent par "ta".