Obtenir un regex trie pour courir plus vite?

Question

J'ai un 50 bits regex que j'utilise pour séparer les phrases.

Voici le code correspondant:

import io 
import re 

with io.open('REGEXES.rx.txt', encoding='latin-1') as myfile: 
     regex = myfile.read() 


while True == True: 
    Password = input("Enter a phrase to be split: ") 

    Words = re.findall(regex, Password) 

    print(Words) 

Depuis la regex est si grand, cela prend toujours!

Voici le code que je suis en train maintenant, avec re.compile (TempRegex):

import io 
import re 

with io.open('REGEXES.rx.txt', encoding='latin-1') as myfile: 
     TempRegex = myfile.read() 

regex = re.compile(TempRegex) 

while True == True: 
    Password = input("Enter a phrase to be split: ") 

    Words = re.findall(regex, Password) 

    print(Words) 

Ce que je suis en train de faire est que je suis en train de vérifier si une expression est entrée une combinaison de noms. Par exemple, l'expression "johnsmith123" pour retourner ['john', 'smith', '123']. Le fichier regex a été créé par un outil à partir d'une liste de mots de tous les prénom et nom de Facebook. Je veux voir si une phrase entrée est une combinaison de mots de cette liste de mots essentiellement ... Si johns et mith sont des noms dans la liste, alors je voudrais que "johnsmith123" retourne ['john', 'smith', '123 ', 'John Smith'].

Answer 1

Je ne pense pas que regex soit la solution. Il me semble que tout ce que vous essayez de faire est de trouver une liste de toutes les sous-chaînes d'une chaîne donnée qui sont des noms.

Si l'entrée de l'utilisateur est un mot de passe ou une phrase secrète, cela implique une chaîne relativement courte. Il est facile de décomposer cette chaîne dans l'ensemble des sous-chaînes possibles, puis de tester cet ensemble par rapport à un autre ensemble contenant les noms.

Le nombre de sous-chaînes d'une chaîne de longueur n est n (n + 1)/2. En supposant que personne ne va entrer plus de 40 caractères, vous ne regardez que 820 sous-chaînes, dont beaucoup pourraient être éliminées comme étant trop courtes. Voici un code pour le faire:

def substrings(s, min_length=1): 
    for start in range(len(s)): 
     for length in range(min_length, len(s)-start+1): 
      yield s[start:start+length] 

Le problème est alors de charger les noms dans une structure de données appropriée. Votre expression régulière est de 50 Mo, mais compte tenu de l'extrait que vous avez montré dans un de vos commentaires, la quantité de données réelles va être beaucoup plus petite que cela en raison de la surcharge de la syntaxe regex.

Si vous venez d'utiliser des fichiers texte avec un nom par ligne, vous pouvez le faire:

names = set(word.strip().lower() for word in open('names.txt')) 

def substrings(s, min_length=1): 
    for start in range(len(s)): 
     for length in range(min_length, len(s)-start+1): 
      yield s[start:start+length] 

s = 'johnsmith123' 
print(sorted(names.intersection(substrings(s))) 

POUVAIT sortie:

 
['jo', 'john', 'johns', 'mi', 'smith'] 

Je doute qu'il y aura des problèmes de mémoire étant donné le risque faible ensemble de données, mais si vous trouvez qu'il n'y a pas assez de mémoire pour charger l'ensemble de données complet à la fois, vous pouvez regarder en utilisant sqlite3 avec une table simple pour stocker les noms. Ce sera plus lent à interroger, mais il tiendra dans la mémoire.

Une autre façon pourrait être d'utiliser le module shelve pour créer un dictionnaire persistant avec des noms comme clés.

Answer 2

Si vous le compilez, les motifs regex seront compilés dans un bytecode puis exécutés par un moteur correspondant. Si vous ne le compilez pas, il le chargera encore et encore pour la même regex à chaque fois qu'elle est appelée. C'est pourquoi compilé est beaucoup plus rapide si vous utilisez la même regex pour plusieurs enregistrements différents.

Answer 3

Le moteur d'expressions rationnelles de Python n'est pas une expression régulière puisqu'il inclut des fonctions telles que lookbehind, groupes de capture, références arrière et retours arrière pour correspondre à la branche la plus à gauche.

Si vous utilisez un moteur réel regex, vous obtiendrez presque toujours de meilleurs résultats si votre expression régulière ne nécessite pas ces fonctionnalités.

L'une des qualités les plus importantes d'une véritable expression régulière est qu'il toujours retourner un résultat en temps proportionnel à la longueur de l'entrée, sans utiliser une mémoire. J'en ai écrit un moi-même en utilisant un DFA implémenté en C (mais utilisable depuis python via cffi), qui aura des performances asymptotiques optimales, mais je n'ai pas essayé d'améliorations constantes comme la vectorisation et la génération d'assemblages. Je n'ai pas fait d'API utilisable en général, car je n'ai besoin de l'appeler qu'à partir de ma bibliothèque, mais cela ne devrait pas être trop difficile à comprendre à partir des exemples. (Notez que la recherche peut être implémentée comme correspondance avec .* à l'avance, puis revenir en arrière, mais pour mon but je préfère retourner un seul caractère comme un jeton d'erreur). Vous pouvez également envisager de créer le DFA hors ligne et de l'utiliser pour plusieurs exécutions de votre programme - mais c'est ce que fait flex alors cela ne servait à rien de le faire pour mon projet, alors peut-être l'utiliser si vous ' re confortable avec C? Bien sûr, vous auriez presque certainement besoin d'écrire un peu de code C personnalisé pour utiliser mon projet de toute façon ...