Optimisation de la correspondance d'expressions rationnelles pour une longue liste d'expressions

Question

Définition du problème: Avec un texte de longueur n caractères et une liste de termes (qui peuvent être des expressions régulières) de longueur t, trouvez et comptez toutes les occurrences de termes dans le texte.

Voici une implémentation naïve pour que:

class WordFrequency(TextAnalysis): 
    """Determines the frequency of words from a vocabulary in a given text""" 

    def __init__(self, vocabulary, text): 
     """ 
     :param vocabulary: contains the words (e.g. list) 
     :param text: the analysed text 
     """ 
     self.text = text 
     self.vocabulary = vocabulary 
     self.matches = {} 

    def run(self): 
     """ 
     :return: self for method chaining 
     """ 

     ltext = self.text.lower() 
     self.freq = {} # word -> absolute frequency 
     for word in self.vocabulary: 
      matches = re.findall(r'\b' + word + r'\b', ltext) 
      self.matches[word] = [match for match in matches] #.lstrip() for match in matches] 
      self.freq[word] = len(matches) 
     return self 

Maintenant, cela prend environ 6 secondes pour un texte d'environ longueur 35000 caractères et une liste de ca. 5000 termes, ce qui est trop lent. Il semble que la complexité temporelle de ceci est O(t * n) car pour chacun des termes t le texte doit être scanné une fois. Y a-t-il un bug de performance évident ici? Quelles sont les optimisations possibles et/ou de meilleurs algorithmes?

Answer 1

Cela peut être fait pour fonctionner dans n O (t * log (n)). J'ai actuellement deux implémentations de cette course dans la production

Mise en œuvre # 1:

Fait en Python pur. J'ai construit un arbre de recherche à partir du fichier de motif (plus petit), où chaque noeud de l'arbre est une lettre qui lie à un hachage des lettres suivantes possibles. Par exemple, vous avez trois modèles: chat, chien et esquive. L'arbre suivant est en cours de construction automatiquement en O (n):

{ 
    'c': {'a': {'t': 'cat'}}, 
    'd': {'d': {'g': {'e': 'dodge'}}, 
      'o': {'g': 'dog'}} 
} 

Vous pouvez maintenant le texte d'analyse et de rechercher tous les mots (ou chaque personnage) dans cet arbre de recherche dans O (log (n)).

Je ne supportais pas regex pour cette solution, bien que ce soit possible. L'inconvénient est que Python n'a pas de bonnes performances pour cela et l'arbre de hachage est inefficace dans la quantité de mémoire qu'il consomme. J'ai envisagé d'utiliser Pypy, de le réécrire en Perl ou C et de faire du multitraitement.

Mise en œuvre # 2:

Un outil bien connu appelé grep fait déjà tout ce qui précède. Il supporte les expressions régulières et peut accepter un fichier de motifs. Pour une raison quelconque, il n'aime pas les gros fichiers de modèles et ses performances se dégradent de façon exponentielle avec l'augmentation du fichier de signatures. Cela pourrait être parce que j'utilise regex fortement. J'ai fini par diviser le fichier de configuration en plusieurs tranches et les alimenter en grep dans des processus parallèles. Pour mes applications, grep fonctionne 10 fois plus vite. Remarque: définissez la variable d'environnement $ LANG sur '', car grep est gêné par une lenteur importante de la localisation.

Conclusion:

Construire un moteur ciblé en C serait idéal, mais en prenant un travail et largement disponible outil GPL peut vous faire économiser quelques mois votre vie.