Partage
  • Partager sur Facebook
  • Partager sur Twitter

Arrêter une fonction au bout d'un certain temps

    17 juin 2021 à 16:48:02

    Bonjour bonjour, 

    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...


    • Partager sur Facebook
    • Partager sur Twitter
      17 juin 2021 à 17:34:09

      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.

      -
      Edité par Nephthys 17 juin 2021 à 17:38:05

      • Partager sur Facebook
      • Partager sur Twitter
        18 juin 2021 à 3:43:01

        @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)
        • Partager sur Facebook
        • Partager sur Twitter

        Le Tout est souvent plus grand que la somme de ses parties.

          18 juin 2021 à 10:33:16

          Bonjour,


          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

          • Partager sur Facebook
          • Partager sur Twitter
            18 juin 2021 à 14:36:59

            ValentinSimao1 a écrit:

            Bonjour,


            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.

            N'hésite pas en cas de questions !

            -
            Edité par Nephthys 18 juin 2021 à 14:42:47

            • Partager sur Facebook
            • Partager sur Twitter
              18 juin 2021 à 15:38:42

              {"chien":1, "chat":1, "cheval":1} ...

              Sinon y a set() et frozenset().

              • Partager sur Facebook
              • Partager sur Twitter

              "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

                18 juin 2021 à 16:48:52

                josmiley a écrit:

                {"chien":1, "chat":1, "cheval":1} ...

                Sinon y a set() et frozenset().


                Au final les (frozen)set sont implémentés via des tables de hashage donc ça revient au même ... même si ta solution est syntaxiquement plus propre.

                Pour l'OP 

                d = frozenset([1 for i in range(max_elem)])



                -
                Edité par Nephthys 18 juin 2021 à 16:49:58

                • Partager sur Facebook
                • Partager sur Twitter
                  18 juin 2021 à 17:39:55

                  Les set prennent sûrement moins de place que les dict, non?
                  Si on a beaucoup de mots, ça peut faire une différence.
                  • Partager sur Facebook
                  • Partager sur Twitter

                  Le Tout est souvent plus grand que la somme de ses parties.

                    19 juin 2021 à 0:08:27

                    PierrotLeFou a écrit:

                    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.
                    • Partager sur Facebook
                    • Partager sur Twitter
                      23 juin 2021 à 17:08:53

                      Re bonjour

                      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...

                      • Partager sur Facebook
                      • Partager sur Twitter
                        23 juin 2021 à 20:35:42

                        Bonjour,

                        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()

                        Résultats :

                        22740 mots chargés depuis le dictionnaire !
                        
                        Distance d'édition: 0
                        	antérieur: {'antérieur'} (0.0s)
                        	anteérieure: X (0.0s)
                        	anterieure: X (0.0s)
                        	antrieure: X (0.0s)
                        	anticommunise: X (0.0s)
                        	lkqsdjfklmjf: X (0.0s)
                        
                        Distance d'édition: 1
                        	antérieur: {'intérieur', 'antérieure', 'antérieur', 'antérieurs'} (0.0010037422180175781s)
                        	anteérieure: {'antérieure'} (0.0s)
                        	anterieure: {'antérieure'} (0.0s)
                        	antrieure: {'antérieure'} (0.000995635986328125s)
                        	anticommunise: {'anticommuniste', 'anticommunisme'} (0.0s)
                        	lkqsdjfklmjf: X (0.0s)
                        
                        Distance d'édition: 2
                        	antérieur: {'inférieur', 'antérieure', 'intérieurs', 'intérieur', 'antérieures', 'intérieure', 'antérieur', 'antérieurs', 'extérieur'} (0.04099249839782715s)
                        	anteérieure: {'antérieures', 'intérieure', 'antérieure', 'antérieur', 'antérieurs'} (0.02800750732421875s)
                        	anterieure: {'antérieures', 'intérieure', 'antérieure', 'antérieurs', 'antérieur'} (0.027000904083251953s)
                        	antrieure: {'antérieures', 'intérieure', 'antérieure', 'antérieurs', 'antérieur'} (0.024976730346679688s)
                        	anticommunise: {'anticommuniste', 'anticommunisme'} (0.05198192596435547s)
                        	lkqsdjfklmjf: X (0.012007474899291992s)
                        
                        Distance d'édition: 3
                        	antérieur: {'ultérieure', 'inférieurs', 'inférieure', 'antérieures', 'antérieurs', 'antérieur', 'ingénieur', 'inférieur', 'antérieure', 'intérieurs', 'entériner', 'postérieur', 'intérieures', 'intérieur', 'extérieurs', 'intérieure', 'altérer', 'extérieur', 'supérieur', 'extérieure'} (3.460164785385132s)
                        	anteérieure: {'ultérieure', 'antérieure', 'intérieurs', 'inférieure', 'intérieures', 'intérieur', 'antérieures', 'intérieure', 'antérieur', 'antérieurs', 'extérieure'} (2.6634585857391357s)
                        	anterieure: {'ultérieure', 'antérieure', 'intérieurs', 'inférieure', 'intérieures', 'intérieur', 'antérieures', 'intérieure', 'antérieurs', 'antérieur', 'extérieure'} (2.942943811416626s)
                        	antrieure: {'ultérieure', 'inférieure', 'antérieures', 'prieure', 'antérieurs', 'antérieur', 'attribuer', 'attribuée', 'antique', 'antérieure', 'intérieurs', 'intérieures', 'intérieur', 'attribue', 'intérieure', 'intrigue', 'intriguer', 'extérieure'} (2.6129987239837646s)
                        	anticommunise: {'anticommuniste', 'anticommunisme'} (4.828001260757446s)
                        	lkqsdjfklmjf: X (1.2000396251678467s)




                        -
                        Edité par Nephthys 24 juin 2021 à 10:41:43

                        • Partager sur Facebook
                        • Partager sur Twitter

                        Arrêter une fonction au bout d'un certain temps

                        × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                        • Editeur
                        • Markdown