简述
如果您想要最快的解决方案,请使用此方法(使用set查找)。对于类似于OP的数据集,它的速度大约比接受的答案快2000倍。
如果您坚持使用正则表达式进行查找,请使用基于trie的版本,它仍然比正则表达式联合快1000倍。
理论
如果您的句子不是非常长的字符串,则可能可以每秒处理多个句子。
如果将所有被禁止的单词保存到一个set中,则检查另一个单词是否包含在该set中将非常快速。
将逻辑打包成一个函数,将此函数作为参数传递给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
有近十万个单词,脚本运行时间不到7秒。
相比之下,Liteye的
答案需要160秒才能处理1万个句子。
对于总单词数为
n
和禁止单词数为
m
,OP和Liteye的代码是
O(n*m)
。
相比之下,我的代码应该以
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)
O(n)
最坏情况
这些结果与简单循环搜索一致。
一个比正则表达式联合更快的替代方法是从 trie 中创建正则表达式模式。