TLDR
L'utilisation de cette méthode (avec recherche) si vous voulez la solution la plus rapide. Pour un jeu de données similaires à l'OP, c'est environ 2000 fois plus rapide que l'on a accepté la réponse.
Si vous insistez sur l'utilisation d'une expression régulière pour la recherche, l'utilisation de cette trie-en fonction de la version, qui est toujours 1000 fois plus rapide qu'un regex de l'union.
La théorie de l'
Si vos phrases ne sont pas faramineux des chaînes, il est probablement possible de traiter beaucoup plus de 50 par seconde.
Si vous enregistrez tous les interdits mots dans un ensemble, il va être très rapide pour vérifier si un mot est inclus dans cet ensemble.
Le Pack de la logique dans une fonction, de donner à cette fonction comme argument d' re.sub et vous avez terminé!
Code
import re
with open('/usr/share/dict/american-english') as wordbook:
banned_words = set(word.strip().lower() for word in wordbook)
def delete_banned_words(matchobj):
word = matchobj.group(0)
if word.lower() in banned_words:
return ""
else:
return word
sentences = ["I'm eric. Welcome here!", "Another boring sentence.",
"GiraffeElephantBoat", "sfgsdg sdwerha aswertwe"] * 250000
word_pattern = re.compile('\w+')
for sentence in sentences:
sentence = word_pattern.sub(delete_banned_words, sentence)
Converti phrases sont:
' . !
.
GiraffeElephantBoat
sfgsdg sdwerha aswertwe
Notez que:
- la recherche est insensible à la casse (grâce à l'
lower())
- le remplacement d'un mot avec
"" pourrait laisser deux espaces (comme dans votre code)
- Avec python3,
\w+ correspond à des caractères accentués (par exemple, "ångström").
- Tout non-caractère de mot (tab, espace, retour à la ligne, marques, ...) restera intacte.
Performance
Il y a un million de phrases, banned_words a près de 100000 mots et le script s'exécute en moins de 7s.
En comparaison, Liteye de réponse nécessaires 160s pour 10 mille phrases.
Avec n étant le total de la quantité de mots et d' m le montant de l'interdit des mots, des OP et des Liteye du code O(n*m).
En comparaison, mon code doit s'exécuter en O(n+m). Considérant qu'il ya beaucoup plus de phrases que d'interdire des mots, l'algorithme devient O(n).
Regex union test
Quelle est la complexité d'un regex de recherche avec un '\b(word1|word2|...|wordN)\b' modèle? Est-il O(N) ou O(1)?
Il est assez difficile de saisir la façon dont le moteur de regex fonctionne, nous allons donc écrire un test simple.
Ce code extrait 10**i aléatoire de mots anglais dans une liste. Il crée le correspondant de la regex de l'union, et des tests avec des mots différents :
- l'un est clairement pas un mot (il commence par
#)
- l'un est le premier mot dans la liste
- l'un est le dernier mot dans la liste
- on ressemble à un mot, mais n'est-ce pas
import re
import timeit
import random
with open('/usr/share/dict/american-english') as wordbook:
english_words = [word.strip().lower() for word in wordbook]
random.shuffle(english_words)
print("First 10 words :")
print(english_words[:10])
test_words = [
("Surely not a word", "#surely_NöTäWORD_so_regex_engine_can_return_fast"),
("First word", english_words[0]),
("Last word", english_words[-1]),
("Almost a word", "couldbeaword")
]
def find(word):
def fun():
return union.match(word)
return fun
for exp in range(1, 6):
print("\nUnion of %d words" % 10**exp)
union = re.compile(r"\b(%s)\b" % '|'.join(english_words[:10**exp]))
for description, test_word in test_words:
time = timeit.timeit(find(test_word), number=1000) * 1000
print(" %-17s : %.1fms" % (description, time))
C'sorties:
First 10 words :
["geritol's", "sunstroke's", 'fib', 'fergus', 'charms', 'canning', 'supervisor', 'fallaciously', "heritage's", 'pastime']
Union of 10 words
Surely not a word : 0.7ms
First word : 0.8ms
Last word : 0.7ms
Almost a word : 0.7ms
Union of 100 words
Surely not a word : 0.7ms
First word : 1.1ms
Last word : 1.2ms
Almost a word : 1.2ms
Union of 1000 words
Surely not a word : 0.7ms
First word : 0.8ms
Last word : 9.6ms
Almost a word : 10.1ms
Union of 10000 words
Surely not a word : 1.4ms
First word : 1.8ms
Last word : 96.3ms
Almost a word : 116.6ms
Union of 100000 words
Surely not a word : 0.7ms
First word : 0.8ms
Last word : 1227.1ms
Almost a word : 1404.1ms
Donc il semble que la recherche d'un mot avec un '\b(word1|word2|...|wordN)\b' modèle a:
-
O(1) dans le meilleur des cas
-
O(n/2) moyenne de cas, qui est encore O(n)
-
O(n) pire des cas
Ces résultats sont cohérents avec une simple boucle de recherche.
Beaucoup plus rapide, alternative à une regex de l'union est de créer de l' expression régulière pattern à partir d'un trie.
