Ich benutze Python 3.5.2

Ich habe zwei Listen

• eine Liste von ungefähr 750.000 "Sätzen" (lange Zeichenketten)
• eine Liste von ungefähr 20.000 "Wörtern", die ich aus meinen 750.000 Sätzen löschen möchte

Ich muss also 750.000 Sätze durchlaufen und ungefähr 20.000 Ersetzungen durchführen, aber NUR, wenn meine Wörter tatsächlich "Wörter" sind und nicht Teil einer größeren Zeichenfolge sind.

Ich dies tun pre-Kompilierung meine Worte , so dass sie durch die flankiert sind \bmetacharacter

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

Dann durchlaufe ich meine "Sätze"

import re

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

Diese verschachtelte Schleife verarbeitet ungefähr 50 Sätze pro Sekunde , was nett ist, aber es dauert immer noch mehrere Stunden, um alle meine Sätze zu verarbeiten.

• Gibt es eine Möglichkeit, die str.replaceMethode zu verwenden (die meiner Meinung nach schneller ist), aber dennoch zu verlangen, dass Ersetzungen nur an Wortgrenzen erfolgen ?

• Gibt es alternativ eine Möglichkeit, die re.subMethode zu beschleunigen ? Ich habe die Geschwindigkeit bereits geringfügig verbessert, indem ich übersprungen habe, re.subwenn die Länge meines Wortes> als die Länge meines Satzes ist, aber es ist keine große Verbesserung.

Vielen Dank für Anregungen.

Eine Sache, die Sie versuchen können, ist, ein einzelnes Muster wie zu kompilieren "\b(word1|word2|word3)\b".

Da reder eigentliche Abgleich auf C-Code basiert, können die Einsparungen dramatisch sein.

Wie @pvg in den Kommentaren hervorhob, profitiert es auch vom Single-Pass-Matching.

Wenn Ihre Worte nicht regulär sind, ist Erics Antwort schneller.

TLDR

Verwenden Sie diese Methode (mit Set-Lookup), wenn Sie die schnellste Lösung wünschen. Bei einem Datensatz, der den OPs ähnlich ist, ist er ungefähr 2000-mal schneller als die akzeptierte Antwort.

Wenn Sie darauf bestehen, einen regulären Ausdruck für die Suche zu verwenden, verwenden Sie diese trie-basierte Version , die immer noch 1000-mal schneller ist als eine reguläre Vereinigung.

Theorie

Wenn Ihre Sätze keine riesigen Zeichenfolgen sind, ist es wahrscheinlich möglich, viel mehr als 50 pro Sekunde zu verarbeiten.

Wenn Sie alle gesperrten Wörter in einem Satz speichern, können Sie sehr schnell überprüfen, ob ein anderes Wort in diesem Satz enthalten ist.

Packen Sie die Logik in eine Funktion, geben Sie diese Funktion als Argument an re.subund Sie sind fertig!

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)

Konvertierte Sätze sind:

' .  !
  .
GiraffeElephantBoat
sfgsdg sdwerha aswertwe

Beachten Sie, dass:

• Bei der Suche wird die Groß- und Kleinschreibung nicht berücksichtigt (danke an lower()).
• Wenn Sie ein Wort durch ersetzen, bleiben ""möglicherweise zwei Leerzeichen (wie in Ihrem Code).
• Stimmt mit python3 \w+auch mit Akzentzeichen überein (z "ångström". B. ).
• Alle Nicht-Wort-Zeichen (Tabulator, Leerzeichen, Zeilenumbruch, Markierungen, ...) bleiben unberührt.

Performance

Es gibt eine Million Sätze, banned_wordshat fast 100000 Wörter und das Skript läuft in weniger als 7 Sekunden.

Im Vergleich dazu benötigte Liteyes Antwort 160 Sekunden für zehntausend Sätze.

Mit nder Gesamt amound von Wörtern zu sein und mdie Menge der verbotenen Wörter, OPs und Liteye Code sind O(n*m).

Im Vergleich dazu sollte mein Code in laufen O(n+m). Wenn man bedenkt, dass es viel mehr Sätze als verbotene Wörter gibt, wird der Algorithmus O(n).

Regex Union Test

Wie komplex ist eine Regex-Suche mit einem '\b(word1|word2|...|wordN)\b'Muster? Ist es O(N)oder O(1)?

Es ist ziemlich schwer zu verstehen, wie die Regex-Engine funktioniert. Schreiben wir also einen einfachen Test.

Dieser Code extrahiert 10**izufällige englische Wörter in eine Liste. Es erstellt die entsprechende Regex-Union und testet sie mit verschiedenen Worten:

• man ist eindeutig kein Wort (es beginnt mit #)
• Eines ist das erste Wort in der Liste
• Eins ist das letzte Wort in der Liste
• man sieht aus wie ein Wort, ist es aber nicht

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

Es gibt aus:

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

Es sieht also so aus, als hätte die Suche nach einem einzelnen Wort mit einem '\b(word1|word2|...|wordN)\b'Muster Folgendes:

• O(1) I'm besten fall
• O(n/2) Durchschnittsfall, der noch ist O(n)
• O(n) schlimmsten Fall

Diese Ergebnisse stimmen mit einer einfachen Schleifensuche überein.

Eine viel schnellere Alternative zu einer Regex-Vereinigung besteht darin, das Regex-Muster aus einem Versuch zu erstellen .

TLDR

Verwenden Sie diese Methode, wenn Sie die schnellste Regex-basierte Lösung wünschen. Bei einem Datensatz, der den OPs ähnlich ist, ist er ungefähr 1000-mal schneller als die akzeptierte Antwort.

Wenn Sie sich nicht für Regex interessieren, verwenden Sie diese satzbasierte Version , die 2000-mal schneller ist als eine Regex-Union.

Optimierter Regex mit Trie

Ein einfacher Regex-Union- Ansatz wird mit vielen gesperrten Wörtern langsam, da die Regex-Engine das Muster nicht sehr gut optimiert.

Es ist möglich, einen Trie mit allen gesperrten Wörtern zu erstellen und den entsprechenden regulären Ausdruck zu schreiben. Der resultierende Trie oder Regex ist nicht wirklich lesbar, ermöglicht jedoch eine sehr schnelle Suche und Übereinstimmung.

Beispiel

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

Die Liste wird in einen Versuch konvertiert:

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

Und dann zu diesem Regex-Muster:

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

Der große Vorteil ist, dass zoodie Regex-Engine zum Testen von Übereinstimmungen nur das erste Zeichen vergleichen muss (es stimmt nicht überein), anstatt die 5 Wörter auszuprobieren . Es ist ein Vorverarbeitungs-Overkill für 5 Wörter, aber es zeigt vielversprechende Ergebnisse für viele tausend Wörter.

Beachten Sie, dass (?:)nicht erfassende Gruppen verwendet werden, weil:

• foobar|bazwürde passen foobaroder baz, aber nichtfoobaz
• foo(bar|baz)würde nicht benötigte Informationen in einer Erfassungsgruppe speichern .

Code

Hier ist ein leicht modifizierter Kern , den wir als trie.pyBibliothek verwenden können:

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

Prüfung

Hier ist ein kleiner Test (der gleiche wie dieser ):

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

Es gibt aus:

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

Zur Information, der Regex beginnt wie folgt:

(?: 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))?) | oder (?: (?: \' s | s))? | s))? | l (?: \ 's)?) ) | e (?: (?: \ 's | am | l (?: (?: \' s | ard | son (?: \ 's)?)) | r (?: deen (?: \ 's)? | nathy (?: \' s)? | ra (?: nt | tion (?: (?: \ 's | s))?)) | t (? :(?: t (?: e (?: r (?: (?: \ 's | s))? | d) | ing | oder (?: (?: \'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) | 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))?))) | upp (? :(?: 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 .. .

Es ist wirklich unlesbar, aber für eine Liste von 100000 verbotenen Wörtern ist dieser Trie-Regex 1000-mal schneller als eine einfache Regex-Vereinigung!

Hier ist ein Diagramm des gesamten Tries, das mit Trie-Python-Graphviz und Graphviz exportiert wurde twopi:

Eine Sache, die Sie versuchen möchten, ist die Vorverarbeitung der Sätze, um die Wortgrenzen zu codieren. Verwandeln Sie jeden Satz in eine Liste von Wörtern, indem Sie die Wortgrenzen aufteilen.

Dies sollte schneller sein, da Sie zum Verarbeiten eines Satzes nur jedes der Wörter durchgehen und prüfen müssen, ob es übereinstimmt.

Derzeit muss die Regex-Suche jedes Mal die gesamte Zeichenfolge erneut durchlaufen, nach Wortgrenzen suchen und dann das Ergebnis dieser Arbeit vor dem nächsten Durchgang "verwerfen".

Hier ist eine schnelle und einfache Lösung mit Testsatz.

Gewinnstrategie:

re ("\ w +", repl, satz) sucht nach Wörtern.

"repl" kann aufrufbar sein. Ich habe eine Funktion verwendet, die eine Diktatsuche durchführt, und das Diktat enthält die Wörter, die gesucht und ersetzt werden sollen.

Dies ist die einfachste und schnellste Lösung (siehe Funktion replace4 im folgenden Beispielcode).

Zweitbester

Die Idee ist, die Sätze mit re.split in Wörter aufzuteilen und dabei die Trennzeichen beizubehalten, um die Sätze später zu rekonstruieren. Das Ersetzen erfolgt dann mit einer einfachen Diktatsuche.

(siehe Funktion replace3 im folgenden Beispielcode).

Timings zum Beispiel Funktionen:

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)

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

Bearbeiten: Sie können auch Kleinbuchstaben ignorieren, wenn Sie prüfen, ob Sie eine Kleinbuchstabenliste mit Sätzen übergeben und repl bearbeiten

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

Vielleicht ist Python hier nicht das richtige Werkzeug. Hier ist eine mit der Unix-Toolchain

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

Angenommen, Ihre Blacklist-Datei ist mit den hinzugefügten Wortgrenzen vorverarbeitet. Die Schritte sind: Konvertieren Sie die Datei in doppelte Abstände, teilen Sie jeden Satz in ein Wort pro Zeile, löschen Sie die Blacklist-Wörter massenweise aus der Datei und führen Sie die Zeilen wieder zusammen.

Dies sollte mindestens eine Größenordnung schneller laufen.

Zur Vorverarbeitung der Blacklist-Datei aus Wörtern (ein Wort pro Zeile)

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

Wie wäre es damit:

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

Diese Lösungen teilen sich an Wortgrenzen auf und suchen jedes Wort in einer Menge. Sie sollten schneller sein als die Wiederholung von Wortalternativen (Liteyes-Lösung), da bei diesen Lösungen O(n)n die Größe der Eingabe aufgrund von istamortized O(1) festgelegten Suche ist, während die Verwendung von Regex-Alternativen dazu führen würde, dass die Regex-Engine nach auf alle Zeichen und nicht nur auf Wortgrenzen. Meine Lösung achtet besonders darauf, die im Originaltext verwendeten Leerzeichen beizubehalten (dh es werden keine Leerzeichen komprimiert und Tabulatoren, Zeilenumbrüche und andere Leerzeichen werden beibehalten), aber wenn Sie entscheiden, dass Sie sich nicht darum kümmern, ist dies der Fall sollte ziemlich einfach sein, um sie aus der Ausgabe zu entfernen.

Ich habe auf corpus.txt getestet, einer Verkettung mehrerer eBooks, die aus dem Gutenberg-Projekt heruntergeladen wurden. Banned_words.txt enthält 20000 Wörter, die zufällig aus Ubuntus Wortliste (/ usr / share / dict / american-english) ausgewählt wurden. Die Verarbeitung von 862462 Sätzen dauert ungefähr 30 Sekunden (und die Hälfte davon auf PyPy). Ich habe Sätze als alles definiert, was durch "." Getrennt ist.

$ # 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 profitiert besonders mehr vom zweiten Ansatz, während CPython beim ersten Ansatz besser abschnitt. Der obige Code sollte sowohl auf Python 2 als auch auf Python 3 funktionieren.

Praktischer Ansatz

Eine unten beschriebene Lösung verwendet viel Speicher, um den gesamten Text in derselben Zeichenfolge zu speichern und die Komplexität zu verringern. Wenn RAM ein Problem ist, überlegen Sie es sich zweimal, bevor Sie es verwenden.

Mit join/ splitTricks können Sie Schleifen vermeiden, die den Algorithmus beschleunigen sollten.

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

"".joinKomplexität ist O (n). Das ist ziemlich intuitiv, aber es gibt trotzdem ein verkürztes Zitat aus einer Quelle:

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

Daher join/splithaben Sie mit O (Wörter) + 2 * O (Sätze) immer noch eine lineare Komplexität gegenüber 2 * O (N ² ) mit dem anfänglichen Ansatz.

Übrigens verwenden Sie kein Multithreading. GIL blockiert jede Operation, da Ihre Aufgabe streng an die CPU gebunden ist, sodass GIL keine Chance hat, freigegeben zu werden, aber jeder Thread sendet gleichzeitig Ticks, die zusätzlichen Aufwand verursachen und sogar die Operation bis ins Unendliche führen.

Verketten Sie alle Ihre Sätze zu einem Dokument. Verwenden Sie eine beliebige Implementierung des Aho-Corasick-Algorithmus ( hier eine ), um alle Ihre "schlechten" Wörter zu lokalisieren. Durchlaufen Sie die Datei, ersetzen Sie jedes fehlerhafte Wort, aktualisieren Sie die Offsets der folgenden gefundenen Wörter usw.