Estou usando o Python 3.5.2

Eu tenho duas listas

• uma lista de cerca de 750.000 "frases" (seqüências longas)
• uma lista de cerca de 20.000 "palavras" que gostaria de excluir de minhas 750.000 frases

Então, eu tenho que percorrer 750.000 frases e executar cerca de 20.000 substituições, mas SOMENTE se minhas palavras forem realmente "palavras" e não fizerem parte de uma cadeia maior de caracteres.

Estou fazendo isso pré-compilando minhas palavras para que elas sejam flanqueadas pelo \bmetacaractere

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

Então eu percorro minhas "frases"

import re

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

Esse loop aninhado está processando cerca de 50 frases por segundo , o que é bom, mas ainda leva várias horas para processar todas as minhas frases.

• Existe uma maneira de usar o str.replacemétodo (que acredito ser mais rápido), mas ainda exigindo que as substituições ocorram apenas nos limites das palavras ?

• Como alternativa, existe uma maneira de acelerar o re.submétodo? Eu já melhorei a velocidade marginalmente saltando sobre re.subse o comprimento da minha palavra é> maior que o comprimento da minha frase, mas não é uma grande melhoria.

Obrigado por todas as sugestões.

Uma coisa que você pode tentar é compilar um único padrão "\b(word1|word2|word3)\b".

Como redepende do código C para fazer a correspondência real, a economia pode ser dramática.

Como o @pvg apontou nos comentários, ele também se beneficia da correspondência de passe único.

Se suas palavras não são regulares, a resposta de Eric é mais rápida.

TLDR

Use este método (com pesquisa de conjunto) se desejar a solução mais rápida. Para um conjunto de dados semelhante ao OP, é aproximadamente 2000 vezes mais rápido que a resposta aceita.

Se você insistir em usar um regex para pesquisa, use esta versão baseada em trie , que ainda é 1000 vezes mais rápida que uma união de regex.

Teoria

Se suas sentenças não forem seqüências de caracteres enormes, provavelmente é possível processar muito mais que 50 por segundo.

Se você salvar todas as palavras banidas em um conjunto, será muito rápido verificar se outra palavra está incluída nesse conjunto.

Empacote a lógica em uma função, dê essa função como argumento re.sube pronto!

Código

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)

As frases convertidas são:

' .  !
  .
GiraffeElephantBoat
sfgsdg sdwerha aswertwe

Observe que:

• a pesquisa não diferencia maiúsculas de minúsculas (graças a lower())
• substituir uma palavra por ""pode deixar dois espaços (como no seu código)
• Com python3, \w+também combina caracteres acentuados (por exemplo "ångström").
• Qualquer caractere que não seja palavra (tab, espaço, nova linha, marcas, ...) permanecerá intocado.

atuação

Há um milhão de frases, banned_wordstem quase 100000 palavras e o script é executado em menos de 7s.

Em comparação, a resposta de Liteye precisava de 160s para 10 mil frases.

Com nsendo o amound total de palavras e ma quantidade de palavras proibidas, código de Liteye do OP e são O(n*m).

Em comparação, meu código deve ser executado O(n+m). Considerando que existem muito mais frases do que palavras proibidas, o algoritmo se torna O(n).

Teste de união Regex

Qual é a complexidade de uma pesquisa regex com um '\b(word1|word2|...|wordN)\b'padrão? É O(N)ou O(1)?

É muito difícil entender o funcionamento do mecanismo regex, então vamos escrever um teste simples.

Esse código extrai 10**ipalavras aleatórias em inglês em uma lista. Ele cria a união de expressão regular correspondente e a testa com palavras diferentes:

• claramente não é uma palavra (começa com #)
• uma é a primeira palavra da lista
• uma é a última palavra da lista
• parece uma palavra, mas não é

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))

Emite:

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

Portanto, parece que a busca por uma única palavra com um '\b(word1|word2|...|wordN)\b'padrão tem:

• O(1) melhor caso
• O(n/2) caso médio, que ainda é O(n)
• O(n) pior caso

Esses resultados são consistentes com uma pesquisa simples de loop.

Uma alternativa muito mais rápida a uma união de expressões regulares é criar o padrão de expressões regulares a partir de uma tentativa .

TLDR

Use esse método se desejar a solução mais rápida baseada em regex. Para um conjunto de dados semelhante aos do OP, é aproximadamente 1000 vezes mais rápido que a resposta aceita.

Se você não se importa com regex, use esta versão baseada em conjunto , que é 2000 vezes mais rápida que uma união de regex.

Regex otimizado com Trie

Uma abordagem simples de união do Regex fica lenta com muitas palavras proibidas, porque o mecanismo do regex não faz um bom trabalho de otimização do padrão.

É possível criar um Trie com todas as palavras banidas e escrever a regex correspondente. O trie ou regex resultante não é realmente legível por humanos, mas permite uma pesquisa e uma correspondência muito rápidas.

Exemplo

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

A lista é convertida em um trie:

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

E então para este padrão regex:

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

A grande vantagem é que, para testar se há zoocorrespondência, o mecanismo regex precisa apenas comparar o primeiro caractere (não corresponde), em vez de tentar as 5 palavras . É um exagero de pré-processo para 5 palavras, mas mostra resultados promissores para muitos milhares de palavras.

Observe que (?:)os grupos que não capturam são usados ​​porque:

• foobar|bazcorresponderia foobarou baz, mas nãofoobaz
• foo(bar|baz)salvaria informações desnecessárias em um grupo de captura .

Código

Aqui está uma essência levemente modificada , que podemos usar como uma trie.pybiblioteca:

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())

Teste

Aqui está um pequeno teste (o mesmo que este ):

# 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))

Emite:

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

Para informações, o regex começa assim:

(?: 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 (? :( ?: (?: \ '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 | am | l (?: (?: \' s | ard | filho (?: \ 's)?))?? r (?: deen (?: \ 's)? | nathy (?: \' s)? | ra (?: nt | ção (?: (?: \ '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 ))? | ção (?: (?: \ '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) | ham (? : \ 's)? | m (?: (?: \' s | s))? | si (?: on (?: (?: \ 's | s))? | ve (? :( ?:\ 's | ly | ness (?: \' s)? | s))?)) | east | idg (?: e (? :( ?: ment (?: (?: \ 's | s)) ? | [ds]))? | ing | ment (?: (?: \ 's | s))?) | o (?: ad | gat (?: e [ds]? | i (?: ng | on (?: (?: \ '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 .. .

É realmente ilegível, mas para uma lista de 100.000 palavras proibidas, esse regie Trie é 1000 vezes mais rápido que uma simples união regex!

Aqui está um diagrama da trie completa, exportada com trie-python-graphviz e graphviz twopi:

Uma coisa que você pode querer tentar é pré-processar as frases para codificar os limites das palavras. Transforme basicamente cada frase em uma lista de palavras dividindo-as nos limites das palavras.

Isso deve ser mais rápido, porque para processar uma frase, basta percorrer cada uma das palavras e verificar se é uma correspondência.

Atualmente, a pesquisa regex precisa passar por toda a sequência novamente, procurando os limites das palavras e, em seguida, "descartando" o resultado desse trabalho antes da próxima passagem.

Bem, aqui está uma solução rápida e fácil, com conjunto de testes.

Estratégia vencedora:

re.sub ("\ w +", repl, sentença) procura por palavras.

"repl" pode ser exigível. Eu usei uma função que executa uma pesquisa de ditado, e o ditado contém as palavras para pesquisar e substituir.

Esta é a solução mais simples e rápida (consulte a função replace4 no código de exemplo abaixo).

Segundo melhor

A idéia é dividir as frases em palavras, usando re.split, enquanto conserva os separadores para reconstruí-las posteriormente. Em seguida, as substituições são feitas com uma simples pesquisa de ditado.

(consulte a função replace3 no código de exemplo abaixo).

Tempos para funções de exemplo:

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)

... e código:

#! /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 )

Editar: você também pode ignorar letras minúsculas ao verificar se passa uma lista minúscula de frases e edita

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

Talvez o Python não seja a ferramenta certa aqui. Aqui está um com a cadeia de ferramentas Unix

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

supondo que seu arquivo da lista negra seja pré-processado com os limites da palavra adicionados. As etapas são: converter o arquivo em espaço duplo, dividir cada frase em uma palavra por linha, excluir em massa as palavras da lista negra do arquivo e mesclar novamente as linhas.

Isso deve executar pelo menos uma ordem de magnitude mais rápido.

Para pré-processar o arquivo da lista negra de palavras (uma palavra por linha)

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

Que tal agora:

#!/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)

Essas soluções dividem os limites das palavras e pesquisam cada palavra em um conjunto. Eles devem ser mais rápidos que o re.sub de palavras alternativas (solução da Liteyes), pois essas soluções são O(n)onde n é o tamanho da entrada devido à amortized O(1)pesquisa definida, enquanto o uso de expressões regulares regex faria com que o mecanismo regex tivesse que procurar correspondências de palavras em todos os caracteres e não apenas nos limites das palavras. Minha solução tem um cuidado extra para preservar os espaços em branco usados ​​no texto original (ou seja, não compacta os espaços em branco e preserva guias, novas linhas e outros caracteres de espaço em branco), mas se você decidir que não se importa com isso, deve ser bastante simples para removê-los da saída.

Testei no corpus.txt, que é uma concatenação de vários eBooks baixados do Projeto Gutenberg, e banned_words.txt contém 20.000 palavras escolhidas aleatoriamente na lista de palavras do Ubuntu (/ usr / share / dict / american-english). Demora cerca de 30 segundos para processar 862462 sentenças (e metade disso no PyPy). Eu defini frases como qualquer coisa separada por ".".

$ # 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

O PyPy se beneficia particularmente mais da segunda abordagem, enquanto o CPython se sai melhor na primeira abordagem. O código acima deve funcionar no Python 2 e 3.

Abordagem prática

Uma solução descrita abaixo usa muita memória para armazenar todo o texto na mesma string e reduzir o nível de complexidade. Se a RAM é um problema, pense duas vezes antes de usá-la.

Com join/ splittruques você pode evitar loops, o que deve acelerar o algoritmo.

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(' * ')

atuação

"".joina complexidade é O (n). Isso é bastante intuitivo, mas de qualquer maneira há uma citação abreviada de uma fonte:

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

Portanto, join/splitvocê tem O (palavras) + 2 * O (sentenças), que ainda é uma complexidade linear vs 2 * O (N ² ) com a abordagem inicial.

btw não use multithreading. O GIL bloqueará cada operação porque sua tarefa é estritamente vinculada à CPU, portanto, o GIL não tem chance de ser liberado, mas cada thread envia ticks simultaneamente, o que causa um esforço extra e até leva a operação ao infinito.

Concatene todas as suas frases em um único documento. Use qualquer implementação do algoritmo Aho-Corasick ( aqui está um ) para localizar todas as suas palavras "ruins". Percorra o arquivo, substituindo cada palavra incorreta, atualizando os deslocamentos das palavras encontradas que se seguem, etc.