Pour mon travail, je dois faire un bout de code qui corrige des mots français si jamais il y a des erreurs dans ce mots. Cependant, comme je travaille avec un très long texte, il y a beaucoup de mots à corriger, et cela prend un temps un peu plus long pour certains (parfois, 4 à 5 secondes, sauf qu'il y a plusieurs millions de mots...). Je voudrais rendre mon programme plus rapide, et pour cela, il faudrait que j'arrive à limiter ce temps à 1s maximum par correction de mot. Je mets un tout petit bout de code pour montrer:
def correction(dataframe):
stockage=[]
for ligne in dataframe:
sentence = ligne.lower().replace("."," ").replace(","," ").replace("'"," ").split()
phrase=""
for mot in sentence:
phrase+=spell.correction(mot)+" "
stockage.append(phrase)
return stockage
Je voudrais ajouter un contrôle du temps qui fait que, si la fonction spell.correction(mot) prend plus de 1s, on arrête cet appel et on passe au mot suivant dans sentence (sachant que spell.correction est une fonction native de spellchecker). Il faudrait un contrôle du temp qui se fait en même temps que cette appel de fonction, mais je ne parviens pas à trouver quoi faire...
J'espère que mes explications/mon problème ne sont pas trop brouillons...
Merci par avance, ça me bloque vraiment de ne pas trouver comment faire...
Y'a deux problèmes : 1) ton algorithme est mauvais 2) celui de spell-checker aussi. Mélangez les deux, ça fait des chocapics.
Le premier problème c'est que tu dois vérifier pour chaque mot s'il est est bon ou pas. Selon comment tu le fais ça peut prendre du temps. Par exemple, faire "mot" in [liste] est globalement mauvais et peut prendre un temps infini si la liste de mot est longue et si ton texte est long. Premier problème.
Second problème, l'algorithme de Norvig est mauvais car il épelle toutes les permutations possibles d'un mot. Donc pour chaque mot, beaucoup de variantes fausses possibles. La solution est d'utiliser une structure de données adéquate, ici je conseille un arbre n-aire. Ca permet de stocker beaucoup de mots avec une complexité en espace réduite, et ça permet de vérifier en autant lettres qu'il y en a dans le mot si celui existe. Par exemple, pour vérifier si "ici" existe dans l'arbre, visiter trois noeuds suffit. Vérifier que "ici" existe dans une liste, c'est regarder au moins les n mots avant "ici" dans la liste, donc certainement plus que 3. Imagine si tu cherches si "zèbre" existe. Voir ici pour les arbres n-aire https://tatianashavrina.github.io/2018/08/30/spellcheck/
Ensuite, pour générer les corrections il suffit de parcourir l'arbre n-aire en générant les erreurs dès que tu changes de noeud et en essayant de parcourir le reste de l'arbre. Deux solutions se présentent, soit il ne te reste plus d'erreur à générer (nombre à définir en amont) et tu n'es pas à la fin d'un mot, dans ce cas tu arrêtes la recherche, tu remontes d'un noeud et tu génères l'erreur suivante. Soit, tu as pu générer ton erreur, et dans ce cas tu essayes de parcourir le reste de l'arbre. Si on y arrive pas, c'est que le mot avec erreur qu'on a généré n'est pas un vrai mot, donc pas une solution de correction possible. Selon ton niveau, ça peut être technique, ça implique de la récursivité et du backtracking.
@Nephthys: Le backtracking est en général facilité, voire invisible, avec la récursivité. Je simplifie: définir fonction(noeud): si correct: retourner vrai sélectionner les sous-noeuds éligibles pour chaque sous-noeud: si fonction(sous-noeud): retourner vrai fin si fin pour retourner faux fin fonction fonction(racine)
Le Tout est souvent plus grand que la somme de ses parties.
Merci Nephthys pour tous tes conseils, mais cela me soulève plusieurs autres questions.
Pour ce que tu dis en premier problème, il y a d'autres moyens de parcourir une liste de mot hormis une boucle for? Car de base, je stockais toutes les phrases dans une dataframe, puis je faisais un split de chaque élément de la dataframe pour parcourir mot par mot chacune des phrases et corriger les phrases mots par mots. Ou est ce que même cette approche n'est pas conseillé selon toi, car elle serait trop gourmande ?
Pour ce que tu dis dans le second problème, j'ai regardé le lien que tu as mis, mais je ne sais pas si c'est plutôt le premier ou le second exemple qui me serait le plus approprié au vue de ce que tu as décrit ensuite (1. Trie ou 2. Bk-trees). Pour moi, tu conseilles de prendre le 1.Trie en exemple, mais je ne comprends pas comment on peut être certain que le mot en question existe? Ou alors il faut lui importer un dictionnaire d'avance? Je vais réétudier le lien et le github correspondant, mais n'ayant pas un niveau foufou en anglais, j'espère pouvoir te solliciter à nouveau, je ne voudrais pas passer à côté de quelque chose, et surtout, m'améliorer en programmation python... Merci beaucoup Nephthys, j'espère que tu pourras encore me consacrer de ton temps
Merci Nephthys pour tous tes conseils, mais cela me soulève plusieurs autres questions.
Pour ce que tu dis en premier problème, il y a d'autres moyens de parcourir une liste de mot hormis une boucle for? Car de base, je stockais toutes les phrases dans une dataframe, puis je faisais un split de chaque élément de la dataframe pour parcourir mot par mot chacune des phrases et corriger les phrases mots par mots. Ou est ce que même cette approche n'est pas conseillé selon toi, car elle serait trop gourmande ?
Pour ce que tu dis dans le second problème, j'ai regardé le lien que tu as mis, mais je ne sais pas si c'est plutôt le premier ou le second exemple qui me serait le plus approprié au vue de ce que tu as décrit ensuite (1. Trie ou 2. Bk-trees). Pour moi, tu conseilles de prendre le 1.Trie en exemple, mais je ne comprends pas comment on peut être certain que le mot en question existe? Ou alors il faut lui importer un dictionnaire d'avance? Je vais réétudier le lien et le github correspondant, mais n'ayant pas un niveau foufou en anglais, j'espère pouvoir te solliciter à nouveau, je ne voudrais pas passer à côté de quelque chose, et surtout, m'améliorer en programmation python... Merci beaucoup Nephthys, j'espère que tu pourras encore me consacrer de ton temps
Pour le premier point, plutôt que d'utiliser une liste, la première chose que tu pourrais faire serait d'utiliser un dictionnaire. Là j'imagine que tu dois avoir une liste de mots qui existent du type ["chien", "chat", "cheval"] et à chaque fois, tu compares chacun des mots de la phrase pour savoir s'il existe genre
liste_de_mot_qui_existent = ['il', 'le', 'chocolat', 'cheval']
for mot in phrase:
if mot not in liste_de_mot_qui_existent:
mot = spellchecker(mot)
(en tout cas c'est ce que j'ai compris que tu faisais). Tu peux dans ce cas transformer ta liste en dictionaire {"chien":1, "chat":1, "cheval":1}. Ici, on se fiche des valeurs, ce qui nous intéresse c'est juste les clefs. La vérification de la présence/absence d'une clef se fait en temps constant O(1), alors que ce n'est pas le cas pour la vérification de la présence/absence d'un mot dans une liste qui est en O(n). Si tu veux te donner une idée de la différence entre une liste et un dictionnaire, essaye de faire tourner ce code
import time
def test_in(it, max_elem):
start = time.time()
for i in range(max_elem):
_ = i in it
end = time.time()
return end-start
def main():
max_elem = 100000
l = [i for i in range(max_elem)]
d = {i:1 for i in range(max_elem)}
print("Temps de recherche de {} élements dans un dictionnaire: {}s".format(max_elem, test_in(d, max_elem)))
print("Temps de recherche de {} élements dans une liste : {}s".format(max_elem, test_in(l, max_elem)))
main()
J'obtiens ça chez moi par exemple
Temps de recherche de 100000 élements dans un dictionnaire: 0.004982948303222656
Temps de recherche de 100000 élements dans une liste : 44.25153350830078
Déjà, je pense qu'une fois ceci fait tu devrais constater d'énormes améliorations.
Pour le Trie (et je parle bien de Trie), je pense qu'il y a déjà des implémentations qui doivent exister, mais c'est un bon exercice à faire soi-même La présence absence d'un mot est en général une propriété du noeud qui a un attribut genre self.fin_mot = True. Sinon, une autre solution consiste à ajouter un caractère spécial à chaque fin de mot "#" et si tu es sur un nom avec comme label # alors c'est que le mot que tu as parcouru existe (en suppansant qu'il ne te reste plus de lettres à parcourir). Effectviment, il faut avant peupler le Trie avec l'ensemble des mots d'une liste de mots.
Les set prennent sûrement moins de place que les dict, non? Si on a beaucoup de mots, ça peut faire une différence.
D'après ce que j'ai lu, les set étaient originellement implémentés comme des dict avec des valeurs inutiles (comme ce que je proposais) puis ont été optimisés ensuite. A priori, ça prend un tout petit peut moins de place (si ta valeur est un int, tu économises l'espace en mémoire que prend ton int). Ca reste assez marginal tout de même.
Je ne suis pas parvenu à faire ce que tu conseillais @Nephthys ... Je ne suis pas à l'aise avec l'arbre n aire...
Ce que j'ai fais pour le moment: j'ai fait un arbre n aire en utilisant la bibliothèque datrie, et j'ai rempli un arbre en utilisant un fichier contenant 23 000 mots français, de la façon suivante:
fichier2 = open('C:/Users/vsimao/Downloads/liste_francais.txt','r',encoding='UTF-8')
dictionnaire = {ligne.replace('\n',''):1 for ligne in fichier2}
for ligne in fichier2:
mot=ligne.replace("\n","")
mot=mot.lower()
trie[mot]=len(mot)
De là, j'ai essayé de fabriquer un correcteur, en utilisant de la récursivité, mais je ne suis pas fière de ce que j'ai fait... Car je n'ai pas réussi à faire ce que tu disais, en parcourant les arbres n aire comme tu as dit...
def distance(s, t):
if s == "":
return len(t)
if t == "":
return len(s)
if s[-1] == t[-1]:
cost = 0
else:
cost = 1
res = min([distance(s[:-1], t)+1,
distance(s, t[:-1])+1,
distance(s[:-1], t[:-1]) + cost])
return res
def corriger2(mot):
if len(sorted(trie.keys(mot),key=len))>0:
correction = sorted(trie.keys(mot),key=len)[0]
if len(correction) == len(mot)+1:
return(correction)
liste=[]
for candidate in dictionnaire:
if (len(candidate)==len(mot) or len(candidate)==len(mot)+1 or len(candidate)==len(mot)-1) and distance(candidate[0:5],mot[0:5])<2:
print(candidate)
if distance(candidate,mot)<2:
liste.append(candidate)
if len(liste)==1:
return liste[0]
else:
return mot
Je ne suis pas du tout satisfait, car ta méthode de parcourir les noeuds me semblaient très belle et séduisante, mais je n'arrive pas à les parcourir... Mon petit outil que j'ai fais est un peu lent, par exemple pour corriger "anterieure" en "antérieure", cela prend plusieurs minutes...
J'ai fait ce code à la va vite mais ça devrait répondre à tes besoins. Les performances sont OK pour une distance d'édition de de 2, dès qu'on passe à 3 beaucoup de mots deviennent possibles, donc le temps de les retrouver tous ça prendre plus de temps ...
import time
END = '#'
ALPHABET = "aàbcdeéèfghijklmnoôpqrstuùvwxyz"
def dict_to_trie(fp):
with open(fp, 'r') as in_file:
words = [line.strip() for line in in_file]
print("{} mots chargés depuis le dictionnaire !".format(len(words)))
return make_trie(*words)
def make_trie(*words):
"""https://stackoverflow.com/questions/11015320/how-to-create-a-trie-in-python"""
root = dict()
for word in words:
current_dict = root
for letter in word:
current_dict = current_dict.setdefault(letter, {})
current_dict[END] = word
return root
def in_trie(trie, word):
for letter in word:
if letter in trie.keys():
trie = trie[letter]
else:
return False
if END in trie.keys():
return True
return False
def find_closest(trie, edit_dist, word):
# Plus d'éditions possible: on regarde si on est sur une fin de mot
if word == "" and edit_dist == 0:
if END in trie.keys():
return set([trie[END]])
return set()
corrections = set()
# Editions possible
if edit_dist > 0:
# Suppression (s'il reste encore des lettres)
if len(word) > 0:
updated_word = word[1:]
corrections.update(find_closest(trie, edit_dist - 1, updated_word))
# Transposition (s'il reste encore assez de lettres)
if len(word) >=2:
updated_word = word[1] + word[0] + word[2:]
corrections.update(find_closest(trie, edit_dist - 1, updated_word))
for c in ALPHABET:
# Insertion
updated_word = c + word
corrections.update(find_closest(trie, edit_dist - 1, updated_word))
# Remplacement
updated_word = c + word[1:]
corrections.update(find_closest(trie, edit_dist - 1, updated_word))
# On 'consomme' le mot normalement (s'il reste des lettres à consommer)
if len(word) > 0:
letter, updated_word = word[0], word[1:]
if letter in trie.keys():
corrections.update(find_closest(trie[letter], edit_dist, updated_word))
return corrections
def main():
trie = dict_to_trie("liste_francais.txt")
for edit_dist in range(0,4):
print("\nDistance d'édition: {}".format(edit_dist))
for test_word in ["antérieur", "anteérieure", "anterieure", "antrieure", "anticommunise", "lkqsdjfklmjf"]:
start = time.time()
results = find_closest(trie, edit_dist, test_word)
end = time.time()-start
if len(results) != 0:
print("\t{}: {} ({}s)".format(test_word, results, end))
else:
print("\t{}: X ({}s)".format(test_word, end))
if __name__ == '__main__':
main()
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.