J'utilise Python 3.5.2

J'ai deux listes

• une liste d'environ 750 000 "phrases" (longues chaînes)
• une liste d'environ 20 000 "mots" que je voudrais supprimer de mes 750 000 phrases

Donc, je dois parcourir 750 000 phrases et effectuer environ 20 000 remplacements, mais UNIQUEMENT si mes mots sont en fait des «mots» et ne font pas partie d'une plus grande chaîne de caractères.

Je fais cela en pré-compilant mes mots afin qu'ils soient flanqués du \bmétacaractère

compiled_words = [re.compile(r'\b' + word + r'\b') for word in my20000words]

Puis je boucle mes «phrases»

import re

for sentence in sentences:
  for word in compiled_words:
    sentence = re.sub(word, "", sentence)
  # put sentence into a growing list

Cette boucle imbriquée traite environ 50 phrases par seconde , ce qui est bien, mais cela prend encore plusieurs heures pour traiter toutes mes phrases.

• Existe-t-il un moyen d'utiliser la str.replaceméthode (qui, je pense, est plus rapide), tout en exigeant que les remplacements ne se produisent qu'aux limites des mots ?

• Sinon, existe-t-il un moyen d'accélérer la re.subméthode? J'ai déjà légèrement amélioré la vitesse en sautant re.subsi la longueur de mon mot est> à la longueur de ma phrase, mais ce n'est pas vraiment une amélioration.

Merci pour vos suggestions.

Une chose que vous pouvez essayer est de compiler un seul modèle comme "\b(word1|word2|word3)\b".

Étant donné reque la correspondance réelle repose sur le code C, les économies peuvent être considérables.

Comme @pvg l'a souligné dans les commentaires, il bénéficie également de la correspondance en un seul passage.

Si vos mots ne sont pas des expressions régulières, la réponse d'Eric est plus rapide.

TLDR

Utilisez cette méthode (avec recherche d'ensemble) si vous voulez la solution la plus rapide. Pour un ensemble de données similaire aux PO, c'est environ 2000 fois plus rapide que la réponse acceptée.

Si vous insistez pour utiliser une expression régulière pour la recherche, utilisez cette version basée sur trie , qui est toujours 1000 fois plus rapide qu'une union d'expression régulière.

Théorie

Si vos phrases ne sont pas des chaînes énormes, il est probablement possible d'en traiter beaucoup plus de 50 par seconde.

Si vous enregistrez tous les mots interdits dans un ensemble, il sera très rapide de vérifier si un autre mot est inclus dans cet ensemble.

Emballez la logique dans une fonction, donnez cette fonction comme argument re.subet 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)

Les phrases converties sont:

' .  !
  .
GiraffeElephantBoat
sfgsdg sdwerha aswertwe

Notez que:

• la recherche est insensible à la casse (grâce à lower())
• le remplacement d'un mot par ""peut laisser deux espaces (comme dans votre code)
• Avec python3, \w+correspond également aux caractères accentués (par exemple "ångström").
• Tout caractère non-mot (tabulation, espace, nouvelle ligne, marques, ...) restera intact.

Performance

Il y a un million de phrases, banned_wordsprès de 100 000 mots et le script s'exécute en moins de 7 secondes.

En comparaison, la réponse de Liteye avait besoin de 160s pour 10 mille phrases.

Avec nla quantité totale de mots et mla quantité de mots interdits, les codes OP et Liteye le sont O(n*m).

En comparaison, mon code devrait fonctionner O(n+m). Considérant qu'il y a beaucoup plus de phrases que de mots interdits, l'algorithme devient O(n).

Test d'union regex

Quelle est la complexité d'une recherche regex avec un '\b(word1|word2|...|wordN)\b'modèle? Est-ce O(N)ou O(1)?

Il est assez difficile de comprendre le fonctionnement du moteur regex, alors écrivons un test simple.

Ce code extrait 10**ides mots anglais aléatoires dans une liste. Il crée l'union regex correspondante et la teste avec différents mots:

• on n'est clairement pas un mot (ça commence par #)
• l'un est le premier mot de la liste
• l'un est le dernier mot de la liste
• on ressemble à un mot mais ne l'est 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))

Il sort:

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

Il semble donc que la recherche d'un seul mot avec un '\b(word1|word2|...|wordN)\b'motif ait:

• O(1) meilleur cas
• O(n/2) cas moyen, qui est toujours O(n)
• O(n) pire cas

Ces résultats sont cohérents avec une simple recherche en boucle.

Un beaucoup plus rapide alternative à un syndicat regex est de créer le modèle regex à partir d' une structure arborescente .

TLDR

Utilisez cette méthode si vous voulez la solution basée sur les regex la plus rapide. Pour un ensemble de données similaire aux OP, c'est environ 1000 fois plus rapide que la réponse acceptée.

Si vous ne vous souciez pas des expressions régulières, utilisez cette version basée sur des ensembles , qui est 2000 fois plus rapide qu'une union regex.

Optimisé Regex avec Trie

Une approche simple d'union Regex devient lente avec de nombreux mots interdits, car le moteur de regex ne fait pas un très bon travail d'optimisation du modèle.

Il est possible de créer un Trie avec tous les mots interdits et d'écrire le regex correspondant. Le trie ou l'expression régulière qui en résulte ne sont pas vraiment lisibles par l'homme, mais ils permettent une recherche et une correspondance très rapides.

Exemple

['foobar', 'foobah', 'fooxar', 'foozap', 'fooza']

La liste est convertie en un trie:

{
    'f': {
        'o': {
            'o': {
                'x': {
                    'a': {
                        'r': {
                            '': 1
                        }
                    }
                },
                'b': {
                    'a': {
                        'r': {
                            '': 1
                        },
                        'h': {
                            '': 1
                        }
                    }
                },
                'z': {
                    'a': {
                        '': 1,
                        'p': {
                            '': 1
                        }
                    }
                }
            }
        }
    }
}

Et puis à ce modèle regex:

r"\bfoo(?:ba[hr]|xar|zap?)\b"

L'énorme avantage est que pour tester si les zoocorrespondances, le moteur d'expression régulière n'a besoin que de comparer le premier caractère (il ne correspond pas), au lieu d' essayer les 5 mots . C'est un prétraitement excessif pour 5 mots, mais il montre des résultats prometteurs pour plusieurs milliers de mots.

Notez que (?:)les groupes non capturants sont utilisés car:

• foobar|bazcorrespondrait foobarou baz, mais pasfoobaz
• foo(bar|baz)enregistrerait les informations inutiles dans un groupe de capture .

Code

Voici un résumé légèrement modifié , que nous pouvons utiliser comme trie.pybibliothèque:

import re


class Trie():
    """Regex::Trie in Python. Creates a Trie out of a list of words. The trie can be exported to a Regex pattern.
    The corresponding Regex should match much faster than a simple Regex union."""

    def __init__(self):
        self.data = {}

    def add(self, word):
        ref = self.data
        for char in word:
            ref[char] = char in ref and ref[char] or {}
            ref = ref[char]
        ref[''] = 1

    def dump(self):
        return self.data

    def quote(self, char):
        return re.escape(char)

    def _pattern(self, pData):
        data = pData
        if "" in data and len(data.keys()) == 1:
            return None

        alt = []
        cc = []
        q = 0
        for char in sorted(data.keys()):
            if isinstance(data[char], dict):
                try:
                    recurse = self._pattern(data[char])
                    alt.append(self.quote(char) + recurse)
                except:
                    cc.append(self.quote(char))
            else:
                q = 1
        cconly = not len(alt) > 0

        if len(cc) > 0:
            if len(cc) == 1:
                alt.append(cc[0])
            else:
                alt.append('[' + ''.join(cc) + ']')

        if len(alt) == 1:
            result = alt[0]
        else:
            result = "(?:" + "|".join(alt) + ")"

        if q:
            if cconly:
                result += "?"
            else:
                result = "(?:%s)?" % result
        return result

    def pattern(self):
        return self._pattern(self.dump())

Tester

Voici un petit test (le même que celui-ci ):

# Encoding: utf-8
import re
import timeit
import random
from trie import Trie

with open('/usr/share/dict/american-english') as wordbook:
    banned_words = [word.strip().lower() for word in wordbook]
    random.shuffle(banned_words)

test_words = [
    ("Surely not a word", "#surely_NöTäWORD_so_regex_engine_can_return_fast"),
    ("First word", banned_words[0]),
    ("Last word", banned_words[-1]),
    ("Almost a word", "couldbeaword")
]

def trie_regex_from_words(words):
    trie = Trie()
    for word in words:
        trie.add(word)
    return re.compile(r"\b" + trie.pattern() + r"\b", re.IGNORECASE)

def find(word):
    def fun():
        return union.match(word)
    return fun

for exp in range(1, 6):
    print("\nTrieRegex of %d words" % 10**exp)
    union = trie_regex_from_words(banned_words[:10**exp])
    for description, test_word in test_words:
        time = timeit.timeit(find(test_word), number=1000) * 1000
        print("  %s : %.1fms" % (description, time))

Il sort:

TrieRegex of 10 words
  Surely not a word : 0.3ms
  First word : 0.4ms
  Last word : 0.5ms
  Almost a word : 0.5ms

TrieRegex of 100 words
  Surely not a word : 0.3ms
  First word : 0.5ms
  Last word : 0.9ms
  Almost a word : 0.6ms

TrieRegex of 1000 words
  Surely not a word : 0.3ms
  First word : 0.7ms
  Last word : 0.9ms
  Almost a word : 1.1ms

TrieRegex of 10000 words
  Surely not a word : 0.1ms
  First word : 1.0ms
  Last word : 1.2ms
  Almost a word : 1.2ms

TrieRegex of 100000 words
  Surely not a word : 0.3ms
  First word : 1.2ms
  Last word : 0.9ms
  Almost a word : 1.6ms

Pour plus d'informations, l'expression régulière commence comme ceci:

(?: a (?: (?: \ 's | a (?: \' s | chen | liyah (?: \ 's)? | r (?: dvark (?: (?: \' s | s ))? | on)) | b (?: \ 's | a (?: c (?: us (?: (?: \' s | es))? | [ik]) | ft | lone (? : (?: \ 's | s))? | ndon (? :( ?: ed | ing | ment (?: \' s)? | s))? | s (?: e (? :( ?: ment (?: \ 's)? | [ds]))? | h (? :( ?: e [ds] | ing))? | ing) | t (?: e (? :( ?: ment ( ?: \ 's)? | [ds]))? | ing | toir (?: (?: \' s | s))?)) | b (?: as (?: id)? | e (? : ss (?: (?: \ 's | es))? | y (?: (?: \' s | s))?) | ot (?: (?: \ 's | t (?: \ 's)? | s))? | reviat (?: e [ds]? | i (?: ng | on (?: (?: \' s | s))?)) | y (?: \ ' s)? | \ é (?: (?: \ 's | s))?) | d (?: icat (?: e [ds]? | i (?: ng | on (?: (?: \ s | s))?)) | om (?: en (?: (?: \ s | s))? | inal) | u (?: ct (? :( ?: ed | i (?: ng | on (?: (?: \ 's | s))?) | ou (?: (?: \' s | s))? | s))? | l (?: \ 's)?) ) | e (?: (?: \ 's | suis | l (?: (?: \' s | ard | son (?: \ 's)?))? | r (?: deen (?: \ 's)? | nathy (?: \' s)? | ra (?: nt | tion (?: (?: \ 's | s))?)) | t (? :( ?: t (?: e (?: r (?: (?: \ 's | s))? | d) | ing | ou (?: (?: \'s | s))?) | s))? | yance (?: \ 's)? | d))? | hor (? :( ?: r (?: e (?: n (?: ce (? : \ 's)? | t) | d) | ing) | s))? | i (?: d (?: e [ds]? | ing | jan (?: \' s)?) | gail | l (?: ene | it (?: ies | y (?: \ 's)?))) | j (?: ect (?: ly)? | ur (?: ation (?: (?: \' s | s))? | e [ds]? | ing)) | l (?: a (?: tive (?: (?: \ 's | s))? | ze) | e (? :(? : st | r))? | oom | ution (?: (?: \ 's | s))? | y) | m \' s | n (?: e (?: gat (?: e [ds] ? | i (?: ng | on (?: \ 's)?)) | r (?: \' s)?) | ormal (? :( ?: it (?: ies | y (?: \ ' s)?) | ly))?) | o (?: ard | de (?: (?: \ 's | s))? | li (?: sh (? :( ?: e [ds] | ing ))? | tion (?: (?: \ 's | ist (?: (?: \' s | s))?))?) | mina (?: bl [ey] | t (?: e [ ds]? | i (?: ng | on (?: (?: \ 's | s))?))) | r (?: igin (?: al (?: (?: \' s | s) )? | e (?: (?: \ 's | s))?) | t (? :( ?: ed | i (?: ng | on (?: (?: \' s | ist (?: (?: \ 's | s))? | s))? | ve) | s))?) | u (?: nd (? :( ?: ed | ing | s))? | t) | ve (?: (?: \ 's | board))?) | r (?: a (?: cadabra (?: \' s)? | d (?: e [ds]? | ing) | jambon (? : \ 's)? | m (?: (?: \' s | s))? | si (?: on (?: (?: \ 's | s))? | ve (? :( ?:\ 's | ly | ness (?: \' s)? | s))?)) | est | idg (?: e (? :( ?: ment (?: (?: \ 's | s)) ? | [ds]))? | ing | ment (?: (?: \ 's | s))?) | o (?: ad | gat (?: e [ds]? | i (?: ng | sur (?: (?: \ 's | s))?))) | upt (? :( ?: e (?: st | r) | ly | ness (?: \' s)?))?) | s (?: alom | c (?: ess (?: (?: \ 's | e [ds] | ing))? | issa (?: (?: \' s | [es]))? | ond (? :( ?: ed | ing | s))?) | en (?: ce (?: (?: \ 's | s))? | t (? :( ?: e (?: e ( ?: (?: \ 's | ism (?: \' s)? | s))? | d) | ing | ly | s))?) | inth (?: (?: \ 's | e ( ?: \ 's)?))? | o (?: l (?: ut (?: e (?: (?: \' s | ly | st?))? | i (?: on (?: \ 's)? | sm (?: \' s)?)) | v (?: e [ds]? | ing)) | r (?: b (? :( ?: e (?: n (? : cy (?: \ 's)? | t (?: (?: \' s | s))?) | d) | ing | s))? | pti ...s | [es]))? | ond (? :( ?: ed | ing | s))?) | en (?: ce (?: (?: \ 's | s))? | t (?: (?: e (?: e (?: (?: \ 's | ism (?: \' s)? | s))? | d) | ing | ly | s))?) | inth (?: (?: \ 's | e (?: \' s)?))? | o (?: l (?: ut (?: e (?: (?: \ 's | ly | st?))? | i (?: on (?: \ 's)? | sm (?: \' s)?)) | v (?: e [ds]? | ing)) | r (?: b (? :( ?: e (?: n (?: cy (?: \ 's)? | t (?: (?: \' s | s))?) | d) | ing | s))? | pti .. .s | [es]))? | ond (? :( ?: ed | ing | s))?) | en (?: ce (?: (?: \ 's | s))? | t (?: (?: e (?: e (?: (?: \ 's | ism (?: \' s)? | s))? | d) | ing | ly | s))?) | inth (?: (?: \ 's | e (?: \' s)?))? | o (?: l (?: ut (?: e (?: (?: \ 's | ly | st?))? | i (?: on (?: \ 's)? | sm (?: \' s)?)) | v (?: e [ds]? | ing)) | r (?: b (? :( ?: e (?: n (?: cy (?: \ 's)? | t (?: (?: \' s | s))?) | d) | ing | s))? | pti .. .

C'est vraiment illisible, mais pour une liste de 100000 mots interdits, cette regex Trie est 1000 fois plus rapide qu'une simple union regex!

Voici un diagramme du trie complet, exporté avec trie-python-graphviz et graphviz twopi:

Une chose que vous voudrez peut-être essayer est de prétraiter les phrases pour encoder les limites des mots. Transformez chaque phrase en une liste de mots en la scindant sur les limites des mots.

Cela devrait être plus rapide, car pour traiter une phrase, il vous suffit de parcourir chacun des mots et de vérifier si c'est une correspondance.

Actuellement, la recherche regex doit parcourir à nouveau la chaîne entière à chaque fois, rechercher les limites des mots, puis "rejeter" le résultat de ce travail avant le passage suivant.

Eh bien, voici une solution rapide et facile, avec ensemble de test.

Stratégie gagnante:

re.sub ("\ w +", repl, phrase) recherche des mots.

"repl" peut être un appelable. J'ai utilisé une fonction qui effectue une recherche de dict, et le dict contient les mots à rechercher et à remplacer.

C'est la solution la plus simple et la plus rapide (voir la fonction replace4 dans l'exemple de code ci-dessous).

Deuxième meilleur

L'idée est de diviser les phrases en mots, en utilisant re.split, tout en conservant les séparateurs pour reconstruire les phrases plus tard. Ensuite, les remplacements sont effectués avec une simple recherche de dict.

(voir la fonction replace3 dans l'exemple de code ci-dessous).

Timings pour les fonctions d'exemple:

replace1: 0.62 sentences/s
replace2: 7.43 sentences/s
replace3: 48498.03 sentences/s
replace4: 61374.97 sentences/s (...and 240.000/s with PyPy)

... et code:

#! /bin/env python3
# -*- coding: utf-8

import time, random, re

def replace1( sentences ):
    for n, sentence in enumerate( sentences ):
        for search, repl in patterns:
            sentence = re.sub( "\\b"+search+"\\b", repl, sentence )

def replace2( sentences ):
    for n, sentence in enumerate( sentences ):
        for search, repl in patterns_comp:
            sentence = re.sub( search, repl, sentence )

def replace3( sentences ):
    pd = patterns_dict.get
    for n, sentence in enumerate( sentences ):
        #~ print( n, sentence )
        # Split the sentence on non-word characters.
        # Note: () in split patterns ensure the non-word characters ARE kept
        # and returned in the result list, so we don't mangle the sentence.
        # If ALL separators are spaces, use string.split instead or something.
        # Example:
        #~ >>> re.split(r"([^\w]+)", "ab céé? . d2eéf")
        #~ ['ab', ' ', 'céé', '? . ', 'd2eéf']
        words = re.split(r"([^\w]+)", sentence)

        # and... done.
        sentence = "".join( pd(w,w) for w in words )

        #~ print( n, sentence )

def replace4( sentences ):
    pd = patterns_dict.get
    def repl(m):
        w = m.group()
        return pd(w,w)

    for n, sentence in enumerate( sentences ):
        sentence = re.sub(r"\w+", repl, sentence)



# Build test set
test_words = [ ("word%d" % _) for _ in range(50000) ]
test_sentences = [ " ".join( random.sample( test_words, 10 )) for _ in range(1000) ]

# Create search and replace patterns
patterns = [ (("word%d" % _), ("repl%d" % _)) for _ in range(20000) ]
patterns_dict = dict( patterns )
patterns_comp = [ (re.compile("\\b"+search+"\\b"), repl) for search, repl in patterns ]


def test( func, num ):
    t = time.time()
    func( test_sentences[:num] )
    print( "%30s: %.02f sentences/s" % (func.__name__, num/(time.time()-t)))

print( "Sentences", len(test_sentences) )
print( "Words    ", len(test_words) )

test( replace1, 1 )
test( replace2, 10 )
test( replace3, 1000 )
test( replace4, 1000 )

Modifier: vous pouvez également ignorer les minuscules lorsque vous vérifiez si vous passez une liste de phrases en minuscules et modifiez le repl

def replace4( sentences ):
pd = patterns_dict.get
def repl(m):
    w = m.group()
    return pd(w.lower(),w)

Peut-être que Python n'est pas le bon outil ici. En voici un avec la chaîne d'outils Unix

sed G file         |
tr ' ' '\n'        |
grep -vf blacklist |
awk -v RS= -v OFS=' ' '{$1=$1}1'

en supposant que votre fichier de liste noire est prétraité avec les limites de mots ajoutées. Les étapes sont les suivantes: convertir le fichier en double interligne, diviser chaque phrase en un mot par ligne, supprimer en masse les mots de la liste noire du fichier et fusionner les lignes.

Cela devrait fonctionner au moins un ordre de grandeur plus rapidement.

Pour prétraiter le fichier de liste noire à partir de mots (un mot par ligne)

sed 's/.*/\\b&\\b/' words > blacklist

Que dis-tu de ça:

#!/usr/bin/env python3

from __future__ import unicode_literals, print_function
import re
import time
import io

def replace_sentences_1(sentences, banned_words):
    # faster on CPython, but does not use \b as the word separator
    # so result is slightly different than replace_sentences_2()
    def filter_sentence(sentence):
        words = WORD_SPLITTER.split(sentence)
        words_iter = iter(words)
        for word in words_iter:
            norm_word = word.lower()
            if norm_word not in banned_words:
                yield word
            yield next(words_iter) # yield the word separator

    WORD_SPLITTER = re.compile(r'(\W+)')
    banned_words = set(banned_words)
    for sentence in sentences:
        yield ''.join(filter_sentence(sentence))


def replace_sentences_2(sentences, banned_words):
    # slower on CPython, uses \b as separator
    def filter_sentence(sentence):
        boundaries = WORD_BOUNDARY.finditer(sentence)
        current_boundary = 0
        while True:
            last_word_boundary, current_boundary = current_boundary, next(boundaries).start()
            yield sentence[last_word_boundary:current_boundary] # yield the separators
            last_word_boundary, current_boundary = current_boundary, next(boundaries).start()
            word = sentence[last_word_boundary:current_boundary]
            norm_word = word.lower()
            if norm_word not in banned_words:
                yield word

    WORD_BOUNDARY = re.compile(r'\b')
    banned_words = set(banned_words)
    for sentence in sentences:
        yield ''.join(filter_sentence(sentence))


corpus = io.open('corpus2.txt').read()
banned_words = [l.lower() for l in open('banned_words.txt').read().splitlines()]
sentences = corpus.split('. ')
output = io.open('output.txt', 'wb')
print('number of sentences:', len(sentences))
start = time.time()
for sentence in replace_sentences_1(sentences, banned_words):
    output.write(sentence.encode('utf-8'))
    output.write(b' .')
print('time:', time.time() - start)

Ces solutions se divisent sur les limites des mots et recherchent chaque mot dans un ensemble. Ils devraient être plus rapides que re.sub of word alternates (solution de Liteyes) car ces solutions sont O(n)où n est la taille de l'entrée due à la amortized O(1)recherche d'ensemble, tandis que l'utilisation de regex alternates obligerait le moteur regex à vérifier les correspondances de mots sur tous les caractères plutôt que sur les limites des mots. Ma solution prend un soin particulier à préserver les espaces qui ont été utilisés dans le texte d'origine (c'est-à-dire qu'il ne compresse pas les espaces et préserve les tabulations, les retours à la ligne et autres caractères d'espacement), mais si vous décidez que vous ne vous en souciez pas, il devrait être assez simple pour les supprimer de la sortie.

J'ai testé sur corpus.txt, qui est une concaténation de plusieurs eBooks téléchargés à partir du projet Gutenberg, et banned_words.txt contient 20000 mots choisis au hasard dans la liste de mots d'Ubuntu (/ usr / share / dict / american-english). Il faut environ 30 secondes pour traiter 862462 phrases (dont la moitié sur PyPy). J'ai défini les phrases comme tout ce qui est séparé par ".".

$ # replace_sentences_1()
$ python3 filter_words.py 
number of sentences: 862462
time: 24.46173644065857
$ pypy filter_words.py 
number of sentences: 862462
time: 15.9370770454

$ # replace_sentences_2()
$ python3 filter_words.py 
number of sentences: 862462
time: 40.2742919921875
$ pypy filter_words.py 
number of sentences: 862462
time: 13.1190629005

PyPy bénéficie particulièrement davantage de la deuxième approche, tandis que CPython s'en sort mieux avec la première approche. Le code ci-dessus devrait fonctionner à la fois sur Python 2 et 3.

Approche pratique

Une solution décrite ci-dessous utilise beaucoup de mémoire pour stocker tout le texte dans la même chaîne et pour réduire le niveau de complexité. Si la RAM est un problème, réfléchissez-y à deux fois avant de l'utiliser.

Avec join/ splittricks, vous pouvez éviter les boucles, ce qui devrait accélérer l'algorithme.

merged_sentences = ' * '.join(sentences)

regex = re.compile(r'\b({})\b'.format('|'.join(words)), re.I) # re.I is a case insensitive flag

clean_sentences = re.sub(regex, "", merged_sentences).split(' * ')

Performance

"".joinla complexité est O (n). C'est assez intuitif mais de toute façon il y a une citation abrégée d'une source:

for (i = 0; i < seqlen; i++) {
    [...]
    sz += PyUnicode_GET_LENGTH(item);

Donc avec join/splitvous avez O (mots) + 2 * O (phrases) qui est encore une complexité linéaire vs 2 * O (N ² ) avec l'approche initiale.

btw n'utilisez pas le multithreading. GIL bloquera chaque opération car votre tâche est strictement liée au processeur, donc GIL n'a aucune chance d'être libéré, mais chaque thread enverra des ticks simultanément, ce qui entraînera un effort supplémentaire et mènera même l'opération à l'infini.

Concaténez toutes vos phrases en un seul document. Utilisez n'importe quelle implémentation de l'algorithme Aho-Corasick (en voici une ) pour localiser tous vos "mauvais" mots. Parcourez le fichier, remplacez chaque mauvais mot, mettez à jour les décalages des mots trouvés qui suivent, etc.