python -regex correspondant à une liste de mots

Question

J'ai un script python qui a probablement environ 100 lignes regex chaque ligne correspondant à certains mots.

Le script consomme évidemment jusqu'à 100% de CPU chaque fois qu'il est exécuté (je lui passe fondamentalement une phrase et il retournera tous les mots trouvés trouvés).

Je veux combiner en environ 4 ou 5 différents « compilé » parseurs tels que regex:

>>> words = ('hello', 'good\-bye', 'red', 'blue') 
>>> pattern = re.compile('(' + '|'.join(words) + ')', re.IGNORECASE) 

Combien de mots puis-je en toute sécurité dans ce domaine et serait-il une différence? À l'heure actuelle, si je lance une boucle sur un millier de phrases aléatoires, il en traite peut-être 10 par seconde, en cherchant à augmenter considérablement cette vitesse de manière à ce qu'elle fasse 500 secondes (si possible).

Aussi, est-il possible à une liste comme ceci?

>>> words = ('\d{4,4}\.\d{2,2}\.\d{2,2}', '\d{2,2}\s\d{2,2}\s\d{4,4}\.') 
>>> pattern = re.compile('(' + '|'.join(words) + ')', re.IGNORECASE) 
>>> print pattern.findall("Today is 2010 11 08) 

Answer 1

Votre algorithme ici est essentiellement O(N*M*L) (où N est la durée de la peine, M est le nombre de mots que vous recherchez, et L est le plus long mot que vous cherchez) pour chaque phrase . Utiliser une regex n'accélère pas plus que simplement utiliser find. La seule chose qu'il vous donne est la possibilité de faire correspondre les modèles comme votre deuxième exemple.

Si vous voulez juste trouver des mots, un Trie serait une bien meilleure approche. La mise en œuvre est vraiment facile, aussi:

TERMINAL = 'TERMINAL' # Marks the end of a word 

def build(*words, trie={}): 
    for word in words: 
     pointer = trie 
     for ch in word: 
      pt = pt.setdefault(ch, {TERMINAL:False}) 
     pt[TERMINAL] = True 
    return trie 

def find(input, trie): 
    results = [] 
    for i in range(len(input)): 
     pt = trie 
     for j in range(i, len(input)+1): 
      if pt[TERMINAL]: 
       results.append(input[i:j]) 
      if j >= len(input) or input[j] not in pt: 
       break 
      pt = pt[input[j]] 
    return results 

Ceci renvoie tous les mots de votre phrase qui sont dans le trie. Le temps d'exécution est O(N*L), ce qui signifie que vous pouvez ajouter autant de mots que vous voulez sans ralentir l'algorithme.