在Python 3中加速数百万的正则表达式替换

Question

我正在使用Python 3.5.2

我有两个清单

大约750,000个“句子”的列表（长串）
我希望从我的750,000个句子中删除大约20,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来略微提高速度，但这并没有太大的改善。

谢谢你的任何建议。

Answer 1

你可以尝试的一件事是编译一个像"\b(word1|word2|word3)\b"的单一模式。

因为re依靠C代码来进行实际匹配，所以节省的费用可能很大。

正如@pvg在评论中指出的那样，它也受益于单次传递匹配。

如果你的话不是正则表达式，那么Eric的answer会更快。

Answer 2

TLDR

如果您想要最快的解决方案，请使用此方法（使用set lookup）。对于类似于OP的数据集，它比接受的答案快约2000倍。

如果你坚持使用正则表达式进行查找，请使用this trie-based version，它仍然比正则表达式联合快1000倍。

Theory

如果你的句子不是巨大的字符串，那么处理每秒超过50的句子可能是可行的。

如果将所有被禁止的单词保存到一个集合中，检查该集合中是否包含另一个单词将非常快。

将逻辑打包成一个函数，将此函数作为参数提供给re.sub，你就完成了！

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)

转换后的句子是：

' .  !
  .
GiraffeElephantBoat
sfgsdg sdwerha aswertwe

注意：

搜索不区分大小写（感谢lower()）
用""替换一个单词可能会留下两个空格（如代码中所示）
使用python3，\w+也匹配重音字符（例如"ångström"）。
任何非单词字符（制表符，空格，换行符，标记......）都将保持不变。

Performance

有一百万个句子，banned_words有近100000个单词，脚本运行不到7秒。

相比之下，Liteye的answer需要160s才能获得1万个句子。

由于qazxsw poi是单词和qazxsw poi的总数量被禁止的单词，OP和Liteye的代码是n。

相比之下，我的代码应该在m中运行。考虑到句子比禁止的单词多得多，算法变成了O(n*m)。

Regex union test

使用O(n+m)模式进行正则表达式搜索的复杂性是多少？是O(n)还是'\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)。

Answer 3

TLDR

如果您想要最快的基于正则表达式的解决方案，请使用此方法。对于类似于OP的数据集，它比接受的答案快大约1000倍。

如果你不关心正则表达式，使用O(n)，它比正则表达式联合快2000倍。

Optimized Regex with Trie

由于正则表达式引擎regex pattern from a trie优化模式，因此this set-based version方法变得缓慢，许多被禁止的单词。

可以使用所有被禁止的单词创建一个simple Regex union并编写相应的正则表达式。由此产生的trie或regex实际上并不是人类可读的，但它们确实允许非常快速的查找和匹配。

例

doesn't do a very good job

Trie

该列表转换为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个单词的预处理矫枉过正，但它显示了数千个单词的有希望的结果。

请注意，使用needs to compare the first character是因为：

trying the 5 words将匹配(?:) non-capturing groups 或foobar|baz，foobar
baz将不需要的信息保存到but not foobaz。

码

这是一个稍微修改过的foo(bar|baz)，我们可以将它用作capturing group库：

gist

测试

这是一个小测试（与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())

它输出：

this one

有关信息，正则表达式开头如下：

（：一（：（：\'S | A（：\？？？？S |陈| liyah（：\？'S）| R（？：？dvark（：（？：？：\的| S ））| ON））| b'（：\？ 'S | A（：C（：我们（：（：\？？？' S | ES））| [IK]）|英尺|孤独的（？：（？：\ 'S | S）？）| NDON（:( ?:版| ING |换货（？：\？' S）| S））| S（：？？？？E（:( ?:精神疾病：| [DS））| H（:( ?: E [DS] |荷兰国际集团））|荷兰国际集团）| T（（\'S'）：？？？？？？E（:( ?:包换（？：\'S）| [DS]））| ING | toir（？：？（：\？的| S））））| b（：如（：？？？ID）| E（？：SS（：（：\ 'Y S | | ES）？（：（：\？？？？）' |）| OT（S S））：（：\'S | T（：？？？\的）| S））| reviat？（：E [DS] | I（：？？？纳克|上（：（：\？的| S））））| Y（？：？\” ？S）| \ E（：（：？\的| S）？））| d（：ICAT（：E [DS] | I（：？？？？？纳克|上（：（：\的| S））））| OM（？：恩？（：（：\？'S | S））|伊纳勒）| U（？：？克拉（:( ?:版| I（？： NG |上（：（：\？ 'S | S）））|或？（？：（：\？' S | S））| S））| L（：？？？？\'S）））| E（：（？：？：\ 'S |上午| L（：（：\？' S | ARD |子（？：\'S）））| R（？：？？？DEEN（：\ 'S）| nathy？（？：\' S）| RA（？：？NT |重刑（：（？：？：\'S | S））？））| T（:( ?:吨（？： E（：R（：（：？\'？S | S））| d）| ING |或（：（：？\的| S）））| S））| yance（？？？？：\ '？S）| d））| HOR（:( ?: R（：E（为：n（：CE（：？？？？？\'？S）| T）| d）|荷兰国际集团）|或多个））| I？（：d（：E [DS] |荷兰国际集团|一月（：？？？\'S'））|盖尔| L（：？烯|它（？：IES | Y（?: \ '？S））））|百灵（：ECT（：LY）| UR（：？？？？通货膨胀（：（：？\'？S | S））| E [DS] |荷兰国际集团）） | L？（？：？一个（：略去（：（：？？？\的| S））| ZE）| E（:( ?: ST | R））| OOM | ution（:(？？：\'S | S））| Y）| M \的| N（？：ΔE（：GAT（：E [DS] | I（：？纳克|上（？：？\'？S）））| R（：\” ？S））| ormal（:( ?:它（：IES | Y（？：？：\？ 'S））| LY）））| O（？：？？ARD |德（？：？（：\' ？S | S））|李（：SH（:( ?: E [DS] |荷兰国际集团））|和灰（：？？？（？：？\的| IST（：（：？\的|或多个）））））|米娜（：？？？BL [EY] | T（：E [DS] | I（：？？？？？纳克|上（：（？：\的| S）））））| R（：？igin（：人（：（：？\的| S））|？E（：（：？\的| S）））| T（:(？？？？：编辑| I（？：？纳克|上（：（：\ 'S | IST（：（？：？：\'？？？S | S））| S））|阳离子）|？S）））| U：T）| | VE（ND（:( ?:编| ING | S）？）？（：（：？\的|板）？？？？））| R（：一个（：cadabra（？：\'？S）| d（？：？E [DS] |荷兰国际集团）|火腿（：\？的）|米（？：？（？：\的| S））| SI（？：对（：（：\？ 'S | S））|已经？（？：？（：\' S | LY |岬（？：？：\'S）| S））？））|东| IDG （：E（:( ?:换货（：（：？？？？\的| S））| [DS]）？）| ING |换货？（：（：？\的| S））？）| O（？：广告| GAT（：E [DS] | I（：？？？？？纳克|上（：（？：\的| S））））？）| UPT（:( ?: E：LY | |岬（ST | R？）（：\？'）））| S（S）：？ALOM | C（：？？？？ESS（：（：\的| E [DS] |荷兰国际集团））| ISSA（？：（：\的| [ES]））| OND（:( ?:编| ING | S）））| EN（：？？？？？？？CE（:( ？：\'？S | S））| T（:( ?: E（：E（：（：\？？？？的| ISM（：？\的）| S））|？d） | ING | LY | S）））| INTH（？：（：？？？\'？S | E（：\的）））| O（？：？L（：UT（：E（？？？？：（？：\的| LY | ST？））| I？（：上（：\？的）| SM？：））| v（（\'S'）：？E [DS] ？|荷兰国际集团））| R（：b（:( ?: E（为：n（：CY（：？？？？？\'？S）| T（：（：？\的| S））？）| d）| ING | S））|？PT一世...

这真是难以理解，但对于一个包含10万个被禁词的列表，这个Trie正则表达式比简单的正则表达式联盟快1000倍！

这是一个完整的trie图，用# 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))和graphviz 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导出：

trie-python-graphviz

Answer 4

您可能想要尝试的一件事是预处理句子以编码单词边界。基本上通过分割单词边界将每个句子转换为单词列表。

这应该更快，因为要处理一个句子，你只需要逐步检查每个单词并检查它是否匹配。

目前，正则表达式搜索每次都必须再次遍历整个字符串，查找字边界，然后在下一次传递之前“丢弃”此工作的结果。

Answer 5

嗯，这是一个快速简便的解决方案，带有测试集。

制胜战略：

re.sub（“\ w +”，repl，sentence）搜索单词。

“repl”可以是可调用的。我使用了一个执行dict查找的函数，dict包含要搜索和替换的单词。

这是最简单，最快速的解决方案（请参阅下面示例代码中的函数replace4）。

次好的

这个想法是使用re.split将句子分成单词，同时保留分隔符以便稍后重构句子。然后，使用简单的dict查找完成替换。

（参见下面示例代码中的函数replace3）。

计时功能：

twopi

......和代码：

Answer 6

也许Python不是正确的工具。这是一个Unix工具链

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 )

Answer 7

这个怎么样：

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

这些解决方案在字边界上分裂并查找集合中的每个单词。它们应该比re.sub of word alternates（Liteyes的解决方案）更快，因为这些解决方案是sed 's/.*/\\b&\\b/' words > blacklist，其中n是由于#!/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)集查找而导致的输入大小，而使用正则表达式替换将导致正则表达式引擎必须检查单词匹配每个字符而不仅仅是单词边界。我的解决方案需要特别注意保留原始文本中使用的空格（即它不压缩空格并保留制表符，换行符和其他空白字符），但是如果你决定不关心它，那么它从输出中删除它们应该相当简单。

我测试了corpus.txt，它是从Gutenberg项目下载的多个电子书的串联，banned_words.txt是从Ubuntu的词表（/ usr / share / dict / american-english）中随机挑选的20000个单词。处理862462个句子大约需要30秒（其中一半是PyPy）。我已将句子定义为以“。”分隔的任何内容。

O(n)

PyPy特别受益于第二种方法，而CPython在第一种方法上的表现更好。上面的代码应该适用于Python 2和3。

Answer 8

Practical approach

下面描述的解决方案使用大量内存来将所有文本存储在相同的字符串中并降低复杂性级别。如果RAM是一个问题，请在使用前再三思。

使用amortized O(1) / $ # 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技巧你可以避免循环，这应该加速算法。

用句子不包含的特殊分隔符连接句子：

join

使用split“或”正则表达式语句编译单个正则表达式，以便从句子中删除所有单词：

merged_sentences = ' * '.join(sentences)

使用编译的正则表达式下标单词，并将特殊分隔符分割回单独的句子：

Performance

regex = re.compile(r'\b({})\b'.format('|'.join(words)), re.I) # re.I is a case insensitive flag复杂度为O（n）。这非常直观，但无论如何，来源都有一个缩短的引文：

clean_sentences = re.sub(regex, "", merged_sentences).split(' * ')

因此，对于"".join，你有O（单词）+ 2 * O（句子），这仍然是线性复杂度与2 * O（N2）的初始方法。

b.t.w.不要使用多线程。 GIL将阻止每个操作，因为你的任务严格受CPU限制，因此GIL没有机会被释放，但是每个线程将同时发送滴答，这会导致额外的工作，甚至导致操作无限。

Answer 9

将所有句子连接成一个文档。使用Aho-Corasick算法（for (i = 0; i < seqlen; i++) { [...] sz += PyUnicode_GET_LENGTH(item);）的任何实现来定位所有“坏”字。遍历文件，替换每个坏词，更新后面找到的单词的偏移等。

在Python 3中加速数百万的正则表达式替换

问题描述投票：110回答：9

9个回答

TLDR

Theory

Code

Performance

Regex union test

TLDR

Optimized Regex with Trie

例

码

测试

Practical approach

Performance

最新问题

在Python 3中加速数百万的正则表达式替换

问题描述 投票：110回答：9

9个回答

TLDR

Theory

Code

Performance

Regex union test

TLDR

Optimized Regex with Trie

例

码

测试

Practical approach

Performance

最新问题

问题描述投票：110回答：9