Я использую Python 3.5.2

У меня есть два списка

• список из примерно 750 000 «предложений» (длинных строк)
• список примерно из 20 000 «слов», которые я хотел бы удалить из своих 750 000 предложений

Итак, мне нужно перебрать 750 000 предложений и выполнить около 20 000 замен, но ТОЛЬКО если мои слова на самом деле являются «словами» и не являются частью более крупной строки символов.

Я делаю это, предварительно компилируя свои слова так, чтобы они были окружены \bметасимволом

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

Затем я прокручиваю свои "предложения"

import re

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

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

• Есть ли способ использовать этот str.replaceметод (который, как я считаю, быстрее), но при этом требовать, чтобы замены выполнялись только на границах слов ?

• Как вариант, есть ли способ ускорить re.subметод? Я уже немного увеличил скорость, пропустив, re.subесли длина моего слова>, чем длина моего предложения, но это не очень хорошее улучшение.

Спасибо за любые предложения.

Вы можете попробовать скомпилировать один-единственный шаблон вроде "\b(word1|word2|word3)\b".

Поскольку reфактическое сопоставление выполняется с помощью кода C, экономия может быть значительной.

Как отметил @pvg в комментариях, он также выигрывает от однопроходного сопоставления.

Если ваши слова не являются регулярным выражением, Эрик ответит быстрее.

TLDR

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

Если вы настаиваете на использовании регулярного выражения для поиска, используйте эту версию на основе дерева , которая по-прежнему в 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())
• замена слова на ""может оставить два пробела (как в вашем коде)
• С python3 \w+также сопоставляет символы с диакритическими знаками (например, "ångström").
• Любой символ, не являющийся словом (табуляция, пробел, новая строка, знаки, ...), останется нетронутым.

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

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

Для сравнения, ответ Liteye потребовал 160 секунд на 10 тысяч предложений.

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

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

Regex union test

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

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

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

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

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) худший случай

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

Гораздо более быстрая альтернатива объединению регулярных выражений - создание шаблона регулярного выражения из дерева .

TLDR

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

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

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

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

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

пример

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

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

{
    '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

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

(: а (: (: \ 's | а (:? \'?? s | чен | liyah (: \ 's) | г (:? dvark (: (:? \' ы | s )) | на)) | б? (?: \ 's | а (? с (: нас (: (: \?? ы | эс)) | [ик]) | фт | одинокий (? : (?: \ 's | с)?) | ndon (? :( ?: изд | ИНГ | Мент (: \' s) |?? с)) | S (: е (:( ?:? Мент: | [DS])) | ч (:( ?: е [DS] | луг)) | -й) | т ((\ 's?)???? е (:( ?: Мент ( : \ 's) | [DS])) | ING | ТОиР (?:? (: \?' s | с)))) | Ь (: а (:?? ид) | е (? : сс ((:? \ 's | эс)) |? у (: (: \?' |) | а (ы)): (?:? \ 's | т (: \ 's) | с)) | reviat? (: е [DS] | я (:? нг | на (?: (: \?' s | с)))) | у (:? \» ? s) | \ é (: (:? \ 's | с)?)) | d (: ICAT (: е [DS] | я (?:? нг | на (?:? (: \ 's | с)))) | ом (?: еп (: (: \?? s | с)) | Инал) | и (??? а (:( ?: изд | я (?: нг | на (: (: \? 's | с))) | или? ((:? \' s | S)???) | с)) | л (: \ 's)) ) | е (: (:? \ 's | ч | л ((:? \' s | ARD | сын (?:? \ 's))) | г (:? Deen (: \ 's) | Nathy? (?: \' s) | ра (?:? нт | ние ((?: \ 's | S?)))) | т (:( ?: т (?: е (? г (: (: \? 's | с)) | d?) | ИНГ | или (?:? (: \'ы | с))) | с)) | Yance (:? \ 'ы) | г)) | Hor (:( ?: г (:???? е (: п (: се (?? : \ 's) | т) | d) | -й) | с)) | я (?:? d (: е [DS] | ING | январь (?:? \? s)) | Гейл | л (: ена | это (:? е годы | у (: \ 's?))) | J | ур ((:: ЭСТ (LY?):?? ция (: (: \?)' s | с)) | е [DS] | луг)) | л (??? а (: TIVE ((:?? \ 's | с)) | г) | е (:(? : ул | г)) | ООМ | социологическое загрязнение (?:? (???? \ '? ы | с)) | у) | т \' ы | п (: е (: гат (: е [DS] ? | я (: нг | на (?: \ 's)?) | г (?: \?)' s)) | НПУ (:( ?: это (:? х годов | у (:? \» s)) | Ly))) | о (:?? ARD | де ((:?? \ 's | с)) | ли (? ш (:( ?: е [DS] | ИНГ )) | Тион? (:? (: \ 's | IST (: (: \?' s | с))))) | Mina (:? бл [еу] | т (? е [ DS] | я? (: нг | на (?:? (: \ 'ы | с))?))) | г (:??? igin (: аль (: (: \' ы | с) ) | е? (:? (: \ 's | с))) | т (:( ?: изд | я (:? нг | на (? (:? \' s | IST (?: ) | ы)) | ве) | с))) | и (| (\ 'ы?):???? й (:( ?: изд | ИНГ | с)) | т) | ве (: (:? \ 's | доска))) | г (:??? а (: Cadabra (: \? s) | d (?:? е [DS] | ю) | ветчину (? : \ '? s) | м (: (:? \' s | с)?) | си (: на (: (:? \ 's | с)) |? ве (:( ?:?\ 'S | LY | Несс (: \? | С)))) | восток | IDG (ы):? Е (:( ?: Мент (: (:? \' S | с)) ? | [DS])) | ING | Мент (?:? (: \ 's | с))) | о (:? объявления | гат (: е [DS] | я (?:? нг | на (: (: \??? ы | с))))) | УПТ (:( ​​?: е (??? й | г) | | лы Несс (: \ 's)))) | s (:? АЛОМА | с (: ESS (: (: \ 's | е [DS] | луг)) | МАСО (?:? (?: \'?? s | [исп])) | Зонд)) | еп (:( ?: изд | | ING S?) (?: с ((:? \ 's | S)??) | т (:( ?: е (: е ( ?: (?: \ 's | изма (: \? s) | S?)) | d) | ИНГ | LY | с))) | INTH (:? (:? \' s | е ( : \ 's))) | о? (:? л (: ут (: е (: (: \?' s | LY | й)?) | я (:? на (?: \ '? s) | см (?: \'? s))) | v (: е [DS] | -й)) | г (?:? б (:( ?: е (: п (?? : су (: \? | т s)? ((:? \ 's | S?))) | d) | ИНГ | с)) | PTI ...s | [исп])) | Зонд (:( ?: изд | ИНГИ | с))) | еп (??? с (: (:? \ 's | с)) | т (?: ? (: е (: е ((:?? \? s | изма (: \ '? s) | с)) | d) | ИНГ | LY | с))) | INTH (?: (?: \ 's | е (: \? s)?)) | о (:? л (: ут (: е (: (: \' s | LY | й?))?? | я (: на (: \ 's) | см (:? \?? s?))) | v (: е [DS] | ю)) | г (?:? б (:( : е (: п (: су (: \ 's) | т (: (:? \'?? s | с))) | d) |? ИНГ | с)) | PTI .. ,s | [исп])) | Зонд (:( ?: изд | ИНГИ | с))) | еп (??? с (: (:? \ 's | с)) | т (?: ? (: е (: е ((:?? \? s | изма (: \ '? s) | с)) | d) | ИНГ | LY | с))) | INTH (?: (?: \ 's | е (: \? s)?)) | о (:? л (: ут (: е (: (: \' s | LY | й?))?? | я (: на (: \ 's) | см (:? \?? s?))) | v (: е [DS] | ю)) | г (?:? б (:( : е (: п (: су (: \ 's) | т (: (:? \'?? s | с))) | d) |? ИНГ | с)) | PTI .. ,

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

Вот диаграмма полного дерева, экспортированного с помощью trie-python-graphviz и graphviz twopi:

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

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

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

Что ж, вот быстрое и простое решение с тестовым набором.

Стратегия победы:

re.sub ("\ w +", repl, предложение) ищет слова.

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

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

Второе место

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

(см. функцию 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 )

Изменить: вы также можете игнорировать строчные буквы при проверке, передаете ли вы список предложений в нижнем регистре и редактируете ответ

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

Возможно, Python здесь не тот инструмент. Вот один с набором инструментов Unix

sed G file         |
tr ' ' '\n'        |
grep -vf blacklist |
awk -v RS= -v OFS=' ' '{$1=$1}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)

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

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

$ # 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, так и на Python 3.

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

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

С помощью join/ splittricks можно вообще избежать циклов, что должно ускорить алгоритм.

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 ² ) с начальным подходом.

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

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