Saya menggunakan Python 3.5.2

Saya punya dua daftar

• daftar sekitar 750.000 "kalimat" (string panjang)
• daftar sekitar 20.000 "kata" yang ingin saya hapus dari 750.000 kalimat saya

Jadi, saya harus mengulangi 750.000 kalimat dan melakukan sekitar 20.000 penggantian, tetapi HANYA jika kata-kata saya sebenarnya "kata" dan bukan bagian dari rangkaian karakter yang lebih besar.

Saya melakukan ini dengan pra-kompilasi kata-kata saya sehingga mereka diapit oleh \bmetacharacter

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

Kemudian saya mengulangi "kalimat" saya

import re

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

Loop bersarang ini memproses sekitar 50 kalimat per detik , yang bagus, tetapi masih butuh beberapa jam untuk memproses semua kalimat saya.

• Apakah ada cara untuk menggunakan str.replacemetode ini (yang saya percaya lebih cepat), tetapi masih membutuhkan penggantian yang hanya terjadi pada batas kata ?

• Atau, apakah ada cara untuk mempercepat re.submetode ini? Saya telah meningkatkan kecepatan sedikit dengan melompati re.subjika panjang kata saya> dari panjang kalimat saya, tapi itu tidak banyak perbaikan.

Terima kasih atas sarannya.

Satu hal yang dapat Anda coba adalah mengkompilasi satu pola tunggal seperti "\b(word1|word2|word3)\b".

Karena rebergantung pada kode C untuk melakukan pencocokan yang sebenarnya, penghematan bisa menjadi dramatis.

Sebagaimana @pvg tunjukkan dalam komentar, itu juga mendapat manfaat dari pencocokan satu pass.

Jika kata-kata Anda bukan regex, jawaban Eric lebih cepat.

TLDR

Gunakan metode ini (dengan set lookup) jika Anda menginginkan solusi tercepat. Untuk dataset yang mirip dengan OP, kira-kira 2000 kali lebih cepat dari jawaban yang diterima.

Jika Anda bersikeras menggunakan regex untuk pencarian, gunakan versi berbasis trie ini , yang masih 1000 kali lebih cepat daripada regex union.

Teori

Jika kalimat Anda bukan string yang besar, mungkin layak untuk memproses lebih dari 50 per detik.

Jika Anda menyimpan semua kata yang dilarang ke set, akan sangat cepat untuk memeriksa apakah kata lain termasuk dalam set itu.

Kemas logika ke dalam fungsi, berikan fungsi ini sebagai argumen re.subdan Anda selesai!

Kode

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)

Kalimat yang dikonversi adalah:

' .  !
  .
GiraffeElephantBoat
sfgsdg sdwerha aswertwe

Perhatikan bahwa:

• pencarian bersifat case-insensitive (terima kasih kepada lower())
• mengganti kata dengan ""mungkin menyisakan dua spasi (seperti dalam kode Anda)
• Dengan python3, \w+juga cocok dengan karakter beraksen (mis "ångström".).
• Setiap karakter non-kata (tab, spasi, baris baru, tanda, ...) akan tetap tidak tersentuh.

Performa

Ada sejuta kalimat, banned_wordsmemiliki hampir 100.000 kata dan skrip berjalan dalam waktu kurang dari 7s.

Sebagai perbandingan, jawaban Liteye membutuhkan 160 untuk 10 ribu kalimat.

Dengan nmenjadi jumlah total kata dan mjumlah kata yang dilarang, kode OP dan Liteye adalah O(n*m).

Sebagai perbandingan, kode saya harus dijalankan O(n+m). Menimbang bahwa ada lebih banyak kalimat daripada kata-kata yang dilarang, algoritme menjadi O(n).

Tes serikat Regex

Apa kompleksitas pencarian regex dengan suatu '\b(word1|word2|...|wordN)\b'pola? Apakah itu O(N)atau O(1)?

Cukup sulit untuk memahami cara kerja mesin regex, jadi mari kita tulis tes sederhana.

Kode ini mengekstrak 10**ikata-kata bahasa Inggris acak ke dalam daftar. Itu menciptakan serikat regex yang sesuai, dan mengujinya dengan kata-kata yang berbeda:

• satu jelas bukan kata (itu dimulai dengan #)
• satu adalah kata pertama dalam daftar
• satu adalah kata terakhir dalam daftar
• yang terlihat seperti sebuah kata tetapi tidak

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

Ini menghasilkan:

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

Jadi sepertinya pencarian untuk satu kata dengan '\b(word1|word2|...|wordN)\b'pola memiliki:

• O(1) kasus terbaik
• O(n/2) kasus rata-rata, yang masih O(n)
• O(n) kasus terburuk

Hasil ini konsisten dengan pencarian loop sederhana.

Alternatif yang jauh lebih cepat daripada gabungan regex adalah membuat pola regex dari trie .

TLDR

Gunakan metode ini jika Anda menginginkan solusi berbasis regex tercepat. Untuk dataset yang mirip dengan OP, kira-kira 1000 kali lebih cepat dari jawaban yang diterima.

Jika Anda tidak peduli dengan regex, gunakan versi set-based ini , yang 2000 kali lebih cepat daripada regex union.

Dioptimalkan Regex dengan Trie

Sebuah sederhana serikat Regex pendekatan menjadi lambat dengan banyak kata-kata dilarang, karena mesin regex tidak melakukan pekerjaan yang sangat baik mengoptimalkan pola.

Dimungkinkan untuk membuat Trie dengan semua kata yang dilarang dan menulis regex yang sesuai. Trie atau regex yang dihasilkan tidak benar-benar dapat dibaca oleh manusia, tetapi mereka memungkinkan pencarian dan pencocokan yang sangat cepat.

Contoh

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

Daftar ini dikonversi menjadi trie:

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

Dan kemudian ke pola regex ini:

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

Keuntungan besar adalah untuk menguji apakah zoococok, mesin regex hanya perlu membandingkan karakter pertama (tidak cocok), daripada mencoba 5 kata . Ini adalah kerja keras yang berlebihan untuk 5 kata, tetapi ini menunjukkan hasil yang menjanjikan untuk ribuan kata.

Perhatikan bahwa (?:)grup yang tidak menangkap digunakan karena:

• foobar|bazakan cocok foobaratau baz, tetapi tidakfoobaz
• foo(bar|baz)akan menyimpan informasi yang tidak dibutuhkan ke grup penangkap .

Kode

Inilah inti yang sedikit dimodifikasi , yang bisa kita gunakan sebagai trie.pyperpustakaan:

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

Uji

Inilah tes kecil (sama dengan yang ini ):

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

Ini menghasilkan:

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

Untuk info, regex dimulai seperti ini:

(?: a (?: (?: \ s | a (?: \ | chen | liyah (?: \ 's)? | r (?: dvark (?: (?: \' s | s ))? | pada)) | b (?: \ a | a (?: c (?: us (?: (?: \ | s)))? | [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))?) | atau (?: (?: \ s | s))? | s))? | l (?: \ s)?) ) | e (?: (?: \ 's | am | l (?: (?: \' s | ard | son (?: \ 's)?))? | r (?: deen (?: \ 's)? | nathy (?: \)) | ra (?: nt | tion (?: (?: \' s | s))?)) | t (? :( ?: t (?: e (?: r (?: (?: \ s | s))? | d) | ing | atau (?: (?: \ 's | s))?) | s))? | yance (?: \ 's)? | d))? | hor (? :( ?: r (?: e (?: n (?: n (?: ce (? : \ 's)? | t) | d) | ing) | s)) | | i (?: d (?: e [ds]? | ing | jan (?: \' s)?) | gail | l (?: ene | it (?: ies | y (?: \))))) | 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 (?: \)?)) | 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)) )? 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 | pada (?: (?: \ 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 ( ?: (?: \ is | ism (?: \)? | s))? | d) | ing | ly | s))?) | inth (?: (?: \? s | e ( ?: \ 's)?))? | o (?: l (?: ut (?: e (?: (?: \' s | ly | st?))? | i (?: on (?: 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 (?: (?: \ isme (?: \ 's)? | s))? | d) | ing | ly | s))?) | inth (?: (?: \ s | e (?: \)?))? | 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 (?: (?: \ isme (?: \ 's)? | s))? | d) | ing | ly | s))?) | inth (?: (?: \ s | e (?: \)?))? | 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 .. .

Ini benar-benar tidak dapat dibaca, tetapi untuk daftar 100000 kata yang dilarang, rege Trie ini 1000 kali lebih cepat daripada gabungan regex sederhana!

Berikut diagram dari trie lengkap, diekspor dengan trie-python-graphviz dan graphviz twopi:

Satu hal yang Anda mungkin ingin coba adalah pra-pemrosesan kalimat untuk menyandikan kata batas. Pada dasarnya mengubah setiap kalimat menjadi daftar kata-kata dengan memisahkan batas kata.

Ini harus lebih cepat, karena untuk memproses kalimat, Anda hanya perlu menelusuri setiap kata dan memeriksa apakah itu cocok.

Saat ini pencarian regex harus melalui seluruh string lagi setiap kali, mencari batas kata, dan kemudian "membuang" hasil pekerjaan ini sebelum lulus berikutnya.

Nah, inilah solusi cepat dan mudah, dengan set tes.

Strategi kemenangan:

re.sub ("\ w +", repl, kalimat) mencari kata-kata.

"repl" bisa menjadi callable. Saya menggunakan fungsi yang melakukan pencarian dict, dan dict berisi kata-kata untuk dicari dan diganti.

Ini adalah solusi paling sederhana dan tercepat (lihat fungsi replace4 dalam kode contoh di bawah).

Kedua terbaik

Idenya adalah untuk membagi kalimat menjadi kata-kata, menggunakan re.split, sambil melestarikan pemisah untuk merekonstruksi kalimat nanti. Kemudian, penggantian dilakukan dengan pencarian dict sederhana.

(lihat fungsi replace3 dalam kode contoh di bawah).

Pengaturan waktu misalnya fungsi:

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)

... dan kode:

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

Sunting: Anda juga dapat mengabaikan huruf kecil saat memeriksa apakah Anda lulus daftar Kalimat huruf kecil dan mengedit balasan

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

Mungkin Python bukan alat yang tepat di sini. Inilah satu dengan toolchain Unix

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

dengan asumsi file daftar hitam Anda diproses terlebih dahulu dengan batas kata ditambahkan. Langkah-langkahnya adalah: mengonversi file menjadi dua spasi, membagi setiap kalimat menjadi satu kata per baris, menghapus secara massal kata-kata daftar hitam dari file, dan menggabungkan kembali baris.

Ini harus menjalankan setidaknya urutan besarnya lebih cepat.

Untuk memproses ulang file daftar hitam dari kata-kata (satu kata per baris)

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

Bagaimana dengan ini:

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

Solusi ini terpecah pada batas kata dan mencari setiap kata dalam satu set. Mereka harus lebih cepat daripada penggantian kata alternatif (solusi Liteyes 'karena solusi ini adalah di O(n)mana n adalah ukuran input karena amortized O(1)pencarian yang diatur, sementara menggunakan regex alternatif akan menyebabkan mesin regex harus memeriksa kecocokan kata pada setiap karakter daripada hanya pada batas kata. Solusi saya adalah berhati-hati untuk melestarikan spasi putih yang digunakan dalam teks asli (yaitu tidak mengkompresi spasi putih dan mempertahankan tab, baris baru, dan karakter spasi putih lainnya), tetapi jika Anda memutuskan bahwa Anda tidak peduli, itu harus cukup mudah untuk menghapusnya dari output.

Saya menguji pada corpus.txt, yang merupakan gabungan dari beberapa eBook yang diunduh dari Proyek Gutenberg, dan banned_words.txt adalah 20.000 kata yang dipilih secara acak dari daftar kata Ubuntu (/ usr / share / dict / american-english). Diperlukan sekitar 30 detik untuk memproses 862462 kalimat (dan setengahnya di PyPy). Saya telah mendefinisikan kalimat sebagai sesuatu yang dipisahkan oleh "."

$ # 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 khususnya mendapat manfaat lebih dari pendekatan kedua, sementara CPython bernasib lebih baik pada pendekatan pertama. Kode di atas harus berfungsi pada Python 2 dan 3.

Pendekatan praktis

Solusi yang dijelaskan di bawah ini menggunakan banyak memori untuk menyimpan semua teks pada string yang sama dan untuk mengurangi tingkat kompleksitas. Jika RAM bermasalah, pikirkan dua kali sebelum menggunakannya.

Dengan join/ splittrik Anda dapat menghindari loop sama sekali yang seharusnya mempercepat algoritma.

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

Performa

"".joinkompleksitasnya adalah O (n). Ini cukup intuitif tetapi ada kutipan singkat dari sumber:

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

Oleh karena itu dengan join/splitAnda memiliki O (kata) + 2 * O (kalimat) yang masih linear kompleksitas vs 2 * O (N ² ) dengan pendekatan awal.

tapi jangan gunakan multithreading. GIL akan memblokir setiap operasi karena tugas Anda benar-benar terikat CPU sehingga GIL tidak memiliki kesempatan untuk dirilis tetapi setiap utas akan mengirimkan kutu secara bersamaan yang menyebabkan upaya ekstra dan bahkan menyebabkan operasi hingga tak terbatas.

Gabungkan semua kalimat Anda menjadi satu dokumen. Gunakan implementasi algoritma Aho-Corasick ( berikut ini ) untuk menemukan semua kata "buruk" Anda. Lintasi file, ganti setiap kata buruk, perbarui offset kata-kata yang ditemukan yang mengikuti dll.