TLDR

используйте этот метод (с set lookup), если вы хотите самое быстрое решение. Для набора данных, подобного OP, это примерно в 2000 раз быстрее, чем принятый ответ.

если вы настаиваете на использовании регулярного выражения для поиска, используйте эта версия на основе trie, который по-прежнему в 1000 раз быстрее, чем регулярное выражение Союза.

теория

если ваши предложения не являются огромными строками, вероятно, возможно обработать еще много чем 50 в секунду.

если вы сохраните все запрещенные слова в набор, это будет очень быстро, чтобы проверить, если другое слово входит в этот набор.

упакуйте логику в функцию, дайте этой функции в качестве аргумента re.sub и ты молодец!

код

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)

преобразовать предложения:

' .  !
  .
GiraffeElephantBoat
sfgsdg sdwerha aswertwe

внимание:

• поиск без учета регистра (спасибо lower())
• замена a слово с "" может оставить два пробела (как в вашем коде)
• С python3,\w+ также соответствует символы с диакритическими знаками (например,"ångström").
• любой символ, не являющийся буквой (табуляция, пробел, перевод строки, знаки, ...) останется нетронутым.

производительность

есть миллион предложений, banned_words имеет почти 100000 слов и скрипт работает менее чем за 7 секунд.

для сравнения, Liteye это ответ необходимые 160s для 10 тысяча предложений.

С n будучи общим количеством слов и m количество запрещенных слов, OP и код Liteye являются O(n*m).

для сравнения, мой код должен работать в O(n+m). Учитывая, что предложений намного больше, чем запрещенных слов, алгоритм становится O(n).

тест объединения регулярных выражений

какова сложность поиска регулярных выражений с помощью '\b(word1|word2|...|wordN)\b' шаблон? Разве это O(N) или O(1)?

довольно трудно понять, как работает механизм регулярных выражений, поэтому давайте напишем простой тест.

этот код извлекает 10**i случайные английские слова в список. Он создает соответствующее регулярное выражение union и проверяет его с помощью разных слов:

• один явно не слово (оно начинается с #)
• первое слово в списке
• одно последнее слово в списке
• выглядит как слово, но не

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

он выводит:

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

так что это похоже на поиск одного слова с '\b(word1|word2|...|wordN)\b' модель имеет:

• O(1) в лучшем случае
• O(n/2) средний случай, который все еще O(n)
• O(n) худшем случае

эти результаты согласуются с простым циклом поиска.

гораздо более быстрая альтернатива регулярному выражению союз заключается в создании регулярное выражение шаблон из trie.

TLDR

используйте этот метод, если вы хотите получить самое быстрое решение на основе регулярных выражений. Для набора данных, подобного OP, это примерно в 1000 раз быстрее, чем принятый ответ.

если вы не заботитесь о регулярном выражении, используйте эта версия на основе набора, что в 2000 раз быстрее, чем объединение регулярных выражений.

оптимизированное регулярное выражение с Trie

A простое регулярное выражение union подход становится медленным со многими запрещенными словами, потому что регулярное выражение двигателя не очень хорошо работает оптимизации шаблона.

можно создать Trie со всеми запрещенными словами и написать соответствующее регулярное выражение. Полученное trie или регулярное выражение на самом деле не читается человеком, но они позволяют очень быстро искать и сопоставлять.

пример

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

список преобразуется в trie:

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

а потом это регулярное выражение шаблон:

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

огромное преимущество заключается в том, чтобы проверить, если zoo соответствует, только движок регулярных выражений нужно сравнить первый символ (это не соответствует), вместо пробовать 5 слов. Это препроцесс перебор для 5 слов, но он показывает многообещающие результаты для многих тысяч слов.

отметим, что (?:) группы без захвата несколько потому что:

• foobar|baz будет соответствовать foobar или baz,а не foobaz
• foo(bar|baz) сохранит ненужную информацию в захват группы.

код

вот немного модифицированный суть, который мы можем использовать как trie.py библиотека:

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

тест

вот небольшой тест (то же самое, что этот один):

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

он выводит:

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

для информации регулярное выражение начинается так:

действительно нечитабельно, но для списка из 100000 запрещенных слов это регулярное выражение Trie в 1000 раз быстрее, чем простое объединение регулярных выражений!

вот схема полного синтаксического дерева, экспортирована с trie-python-graphviz и graphviz twopi:

одна вещь, которую вы можете попробовать, это предварительная обработка предложений для кодирования границ слов. В основном превратите каждое предложение в список слов, разделив его на границы слов.

Это должно быть быстрее, потому что для обработки предложения, вы просто должны пройти через каждое из слов и проверить, если это совпадение.

В настоящее время поиск регулярных выражений должен проходить через всю строку снова каждый раз, ища границы слов, а затем "отбрасывая" результат из этой работы перед следующим проходом.

Ну, вот быстрое и простое решение, с установить тест.

выигрышная стратегия:

re.sub ("\w+", repl,sentence) выполняет поиск слов.

"repl"может быть вызываемым. Я использовал функцию, которая выполняет поиск dict, и dict содержит слова для поиска и замены.

Это самое простое и быстрое решение (см. функцию replace4 в примере кода ниже).

второй лучший

в идея в том, чтобы разделить предложения на слова, используя re.сплит, сохраняя при этом разделители, чтобы восстановить предложения позже. Затем замены выполняются с помощью простого поиска диктанта.

(см. функцию replace3 в примере кода ниже).

тайминги например функции:

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)

...и код:

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

возможно, Python не является правильным инструментом здесь. Вот один с Unix toolchain

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

предполагая, что ваш файл черного списка предварительно обработан с добавлением границ слов. Шаги: преобразуйте файл в двойной интервал, разделите каждое предложение на одно слово в строке, массово удалите слова черного списка из файла и объедините обратно строки.

Это должно работать, по крайней мере на порядок быстрее.

для предварительной обработки файла черного списка из слов (одно слово в строке)

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

как насчет этого:

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

эти решения разбиваются на границы слов и просматривают каждое слово в наборе. Они должны быть быстрее, чем огонь.sub of word чередуется (решение Liteyes), поскольку эти решения O(n) где n-размер входного сигнала из-за amortized O(1) установить поиск, в то время как использование регулярных выражений чередуется приведет к тому, что механизм регулярных выражений должен будет проверять совпадения слов на каждом символе, а не только на границах слов. Мое решение позаботиться о том, чтобы сохранить пробелы, которые были использованы в исходном тексте (т. е. он не сжимает пробелы и сохраняет вкладки, новые строки и другие символы пробела), но если вы решите, что вам это не нужно, должно быть довольно просто удалить их из вывода.

Я проверил на корпусе.txt, который представляет собой объединение нескольких электронных книг, загруженных из проекта Гутенберга, и banned_words.txt-это 20000 слов, случайно выбранных из списка слов Ubuntu (/usr / share/dict / американо-английский). Это занимает около 30 секунд, чтобы обработать 862462 предложения (и половина из них на PyPy). Я определил предложения как что-либо разделенное ". ".

$ # 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 особенно выигрывает от второго подхода, в то время как CPython лучше справился с первым подходом. Приведенный выше код должен работать на Python 2 и 3.

практический подход

решение, описанное ниже, использует много памяти для хранения всего текста в одной строке и для снижения уровня сложности. Если ОЗУ является проблемой, подумайте дважды, прежде чем использовать его.

С join/split трюки вы можете избежать петли на всех, которые должны ускорить алгоритм.

объединить предложения с специальный разделитель, который не содержит предложения:

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

производительность

"".join сложность-O (n). Это довольно интуитивно, но в любом случае есть сокращенная цитата из источника:

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

поэтому с join/split у вас есть O (слова) + 2*O(предложения), который по-прежнему линейная сложность против 2*O(N²) при первоначальном подходе.

---

b. t. w.не используйте многопоточность. GIL будет блокировать каждую операцию, потому что ваша задача строго связана с процессором, поэтому у GIL нет шансов быть освобожденным, но каждый поток будет отправлять тики одновременно, что вызывает дополнительные усилия и даже приводит к бесконечности.

объединить все свои предложения в один документ. Используйте любую реализацию алгоритма Aho-Corasick (вот), чтобы найти все ваши "плохие" слова. Пройдите файл, заменяя каждое плохое слово, обновляя смещения найденных слов, которые следуют и т. д.