Używam Pythona 3.5.2

Mam dwie listy

• lista około 750 000 „zdań” (długie ciągi znaków)
• listę około 20 000 „słów”, które chciałbym usunąć z moich 750 000 zdań

Muszę więc przejść przez 750 000 zdań i wykonać około 20 000 podmian, ale TYLKO wtedy, gdy moje słowa są rzeczywiście „słowami” i nie są częścią większego ciągu znaków.

Robię to, wstępnie kompilując moje słowa, tak aby były otoczone \bmetaznakiem

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

Następnie przeglądam moje „zdania”

import re

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

Ta zagnieżdżona pętla przetwarza około 50 zdań na sekundę , co jest miłe, ale przetwarzanie wszystkich moich zdań nadal zajmuje kilka godzin.

• Czy istnieje sposób na użycie tej str.replacemetody (która moim zdaniem jest szybsza), ale nadal wymaga, aby zamiany miały miejsce tylko na granicach słów ?

• Alternatywnie, czy istnieje sposób na przyspieszenie tej re.submetody? Już nieznacznie poprawiłem prędkość, pomijając, re.subjeśli długość mojego słowa jest>> długość mojego zdania, ale nie jest to duża poprawa.

Dziękuję za wszelkie sugestie.

Jedną rzeczą, którą możesz spróbować, jest skompilowanie jednego pojedynczego wzorca, takiego jak "\b(word1|word2|word3)\b".

Ponieważ reopiera się na kodzie C, aby dokonać właściwego dopasowania, oszczędności mogą być dramatyczne.

Jak @pvg wskazał w komentarzach, korzysta również z dopasowania pojedynczego przebiegu.

Jeśli twoje słowa nie są wyrażeniami regularnymi, odpowiedź Erica jest szybsza.

TLDR

Użyj tej metody (z wyszukiwaniem zestawów), jeśli chcesz uzyskać najszybsze rozwiązanie. W przypadku zbioru danych podobnego do PO jest około 2000 razy szybszy niż zaakceptowana odpowiedź.

Jeśli nalegasz na użycie wyrażenia regularnego do wyszukiwania, użyj tej wersji opartej na trie , która jest nadal 1000 razy szybsza niż unia wyrażeń regularnych.

Teoria

Jeśli twoje zdania nie są wielkimi ciągami znaków, prawdopodobnie możliwe jest przetworzenie znacznie więcej niż 50 na sekundę.

Jeśli zapiszesz wszystkie zabronione słowa w zestawie, bardzo szybko sprawdzisz, czy inne słowo jest zawarte w tym zestawie.

Spakuj logikę do funkcji, podaj tę funkcję jako argument re.subi gotowe!

Kod

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)

Zdania konwertowane to:

' .  !
  .
GiraffeElephantBoat
sfgsdg sdwerha aswertwe

Zauważ, że:

• wyszukiwanie nie rozróżnia wielkości liter (dzięki lower())
• zastąpienie słowa ""może pozostawić dwie spacje (jak w twoim kodzie)
• W python3 \w+dopasowuje również znaki akcentowane (np "ångström".).
• Wszelkie znaki niebędące słowami (tabulator, spacja, nowa linia, znaki, ...) pozostaną nietknięte.

Występ

Jest milion zdań, banned_wordsprawie 100000 słów, a skrypt działa w mniej niż 7 sekund.

Dla porównania, odpowiedź Liteye potrzebowała 160 sekund na 10 tysięcy zdań.

Ponieważ njest to całkowita liczba słów i mliczba zakazanych słów, kod OP i Liteye to O(n*m).

Dla porównania, mój kod powinien działać O(n+m). Biorąc pod uwagę, że jest o wiele więcej zdań niż zakazanych słów, algorytm staje się O(n).

Test związku Regex

Jaka jest złożoność wyszukiwania wyrażeń regularnych ze '\b(word1|word2|...|wordN)\b'wzorcem? Czy to jest O(N)czy O(1)?

Trudno jest pojąć, jak działa silnik wyrażeń regularnych, więc napiszmy prosty test.

Ten kod wyodrębnia 10**ilosowe angielskie słowa do listy. Tworzy odpowiednią sumę wyrażeń regularnych i testuje ją za pomocą różnych słów:

• wyraźnie nie jest słowem (zaczyna się od #)
• jeden jest pierwszym słowem na liście
• jedno jest ostatnim słowem na liście
• wygląda na słowo, ale nim nie jest

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

Wyprowadza:

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

Wygląda więc na to, że wyszukiwanie pojedynczego słowa ze '\b(word1|word2|...|wordN)\b'wzorem ma:

• O(1) najlepszy przypadek
• O(n/2) przeciętny przypadek, który nadal jest O(n)
• O(n) najgorszy przypadek

Te wyniki są zgodne z prostym wyszukiwaniem w pętli.

Znacznie szybszą alternatywą dla unii wyrażeń regularnych jest utworzenie wzorca wyrażenia regularnego z próby .

TLDR

Użyj tej metody, jeśli chcesz uzyskać najszybsze rozwiązanie oparte na wyrażeniach regularnych. W przypadku zbioru danych podobnego do PO jest to około 1000 razy szybsze niż zaakceptowana odpowiedź.

Jeśli nie obchodzi Cię regex, użyj tej wersji opartej na zestawie , która jest 2000 razy szybsza niż suma wyrażeń regularnych.

Zoptymalizowany Regex z Trie

Prosty Regex unia podejście staje się powoli z wielu zakazanych słów, ponieważ silnik regex nie robi bardzo dobrą robotę optymalizacji wzoru.

Możliwe jest utworzenie Trie ze wszystkimi zakazanymi słowami i napisanie odpowiedniego wyrażenia regularnego. Wynikowe trie lub regex nie są tak naprawdę czytelne dla człowieka, ale pozwalają na bardzo szybkie wyszukiwanie i dopasowywanie.

Przykład

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

Lista jest konwertowana na trie:

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

A potem do tego wzorca wyrażenia regularnego:

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

Ogromną zaletą jest to, że aby sprawdzić, czy zoopasuje, silnik regex musi porównać tylko pierwszy znak (nie pasuje), zamiast wypróbować 5 słów . Jest to przesada preprocesu dla 5 słów, ale daje obiecujące wyniki dla wielu tysięcy słów.

Zwróć uwagę, że grupy (?:)nieprzechwytywane są używane, ponieważ:

• foobar|bazpasowałaby foobarlub baz, ale niefoobaz
• foo(bar|baz)zapisałby niepotrzebne informacje w grupie przechwytującej .

Kod

Oto nieco zmodyfikowana treść , której możemy użyć jako trie.pybiblioteki:

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

Test

Oto mały test (taki sam jak ten ):

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

Wyprowadza:

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

Aby uzyskać więcej informacji, wyrażenie regularne zaczyna się tak:

(?: 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))?) | lub (?: (?: \' s | s))? | s))? | l (?: \ 's)?) ) | e (?: (?: \ 's | am | l (?: (?: \' s | ard | syn (?: \ 's)?))? | r (?: deen (?: \ 's)? | nathy (?: \' s)? | ra (?: nt | tion (?: (?: \ 's | s))?)) | t (? :( ?: t (?:) e (?: r (?: (?: \ 's | s))? | d) | ing | or (?: (?: \'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 ))? |ation (?: (?: \ '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 | plansza))?) | r (?: a (?: cadabra (?: \' s)? | d (?: e [ds]? | ing) | ham (? : \ 's)? | m (?: (?: \' s | s))? | si (?: on (?: (?: \ 's | s))? | ve (? :( ?:\ 's | ly | ness (?: \' s)? | s))?)) | wschód | 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 .. .

To naprawdę nieczytelne, ale dla listy 100000 zabronionych słów to wyrażenie regularne Trie jest 1000 razy szybsze niż proste połączenie wyrażeń regularnych!

Oto diagram kompletnej trie, wyeksportowany za pomocą trie-python-graphviz i graphviz twopi:

Jedną z rzeczy, których możesz chcieć spróbować, jest wstępne przetwarzanie zdań w celu zakodowania granic słów. Zasadniczo zamień każde zdanie w listę słów, dzieląc je na granice słów.

Powinno to być szybsze, ponieważ aby przetworzyć zdanie, wystarczy przejść przez każde ze słów i sprawdzić, czy pasuje.

Obecnie wyszukiwanie wyrażeń regularnych musi za każdym razem przejść przez cały ciąg, szukając granic słów, a następnie „odrzucając” wynik tej pracy przed następnym przebiegiem.

Oto szybkie i łatwe rozwiązanie z zestawem testowym.

Zwycięska strategia:

re.sub ("\ w +", repl, zdanie) wyszukuje słowa.

„repl” może być wywoływalne. Użyłem funkcji, która wyszukuje słowa, a dykta zawiera słowa do wyszukania i zastąpienia.

Jest to najprostsze i najszybsze rozwiązanie (zobacz funkcję replace4 w przykładowym kodzie poniżej).

Drugi najlepszy

Pomysł polega na podzieleniu zdań na słowa za pomocą funkcji re.split, zachowując jednocześnie separatory do późniejszej rekonstrukcji zdań. Następnie zastąpienia są wykonywane za pomocą prostego wyszukiwania dyktowania.

(zobacz funkcję replace3 w przykładowym kodzie poniżej).

Czasy na przykład funkcje:

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)

... i kod:

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

Edycja: Możesz także ignorować małe litery podczas sprawdzania, czy przekazujesz listę zdań małymi literami i edytujesz odpowiedź

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

Być może Python nie jest tutaj odpowiednim narzędziem. Oto jeden z łańcuchem narzędzi Unix

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

zakładając, że plik czarnej listy jest wstępnie przetworzony z dodanymi granicami słów. Kroki są następujące: przekonwertować plik do podwójnych odstępów, podzielić każde zdanie na jedno słowo w wierszu, masowo usunąć słowa z czarnej listy z pliku i ponownie scalić wiersze.

Powinno to przebiegać przynajmniej o rząd wielkości szybciej.

Do wstępnego przetwarzania pliku czarnej listy ze słów (jedno słowo w wierszu)

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

Co powiesz na to:

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

Te rozwiązania dzielą się na granice słów i wyszukują każde słowo w zestawie. Powinny być szybsze niż re.sub of word alternates (rozwiązanie Liteyes'a), ponieważ te rozwiązania są O(n)tam, gdzie n jest rozmiarem wejścia ze względu naamortized O(1) wyszukiwania zestawu, podczas gdy użycie alternatywnych wyrażeń regularnych spowodowałoby, że silnik wyrażeń regularnych musiałby sprawdzać dopasowania słów na każdym znaku, a nie tylko na granicach słów. Moje rozwiązanie: zwróć szczególną uwagę, aby zachować białe znaki, które były użyte w oryginalnym tekście (tj. Nie kompresuje białych znaków i zachowuje tabulatory, nowe linie i inne białe znaki), ale jeśli zdecydujesz, że Cię to nie obchodzi, powinno być dość proste, aby usunąć je z wyjścia.

Testowałem na corpus.txt, który jest konkatenacją wielu eBooków pobranych z projektu Gutenberg, a banned_words.txt to 20000 słów losowo wybranych z listy słów Ubuntu (/ usr / share / dict / american-english). Przetworzenie 862462 zdań zajmuje około 30 sekund (i połowę tego na PyPy). Zdefiniowałem zdania jako wszystko oddzielone znakiem „.”.

$ # 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 szczególnie skorzystał na drugim podejściu, podczas gdy CPython wypadł lepiej w pierwszym podejściu. Powyższy kod powinien działać zarówno na Pythonie 2, jak i 3.

Praktyczne podejście

Rozwiązanie opisane poniżej wykorzystuje dużo pamięci do przechowywania całego tekstu w tym samym ciągu i do zmniejszenia poziomu złożoności. Jeśli problemem jest pamięć RAM, zastanów się dwa razy, zanim go użyjesz.

Dzięki join/ splittricks możesz w ogóle uniknąć pętli, co powinno przyspieszyć algorytm.

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

Występ

"".joinzłożoność jest O (n). Jest to dość intuicyjne, ale i tak jest skrócony cytat ze źródła:

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

Dlatego z join/splittobą masz O (słowa) + 2 * O (zdania), co jest nadal liniową złożonością w porównaniu z 2 * O (N ² ) z początkowym podejściem.

przy okazji nie używaj wielowątkowości. GIL zablokuje każdą operację, ponieważ twoje zadanie jest ściśle związane z procesorem, więc GIL nie ma szans na zwolnienie, ale każdy wątek będzie wysyłał tiki jednocześnie, co powoduje dodatkowy wysiłek, a nawet prowadzi do nieskończoności.

Połącz wszystkie zdania w jeden dokument. Użyj dowolnej implementacji algorytmu Aho-Corasick ( tutaj jeden ), aby zlokalizować wszystkie swoje „brzydkie” słowa. Przeszukuj plik, zastępując każde złe słowo, aktualizując przesunięcia znalezionych słów, które następują itp.