用于检查单词黑名单的正则表达式-估计预期的生产性能

Question

我有许多HTML页面，需要检查是否存在列入黑名单的单词。我知道内置的in比正则表达式快得多，但在这里我试图将许多in与单个正则表达式进行比较。

以来

re.match()只在字符串

的开头检查是否匹配

我使用了类似于.*(word|word...)的正则表达式，并用空格替换了换行符。

---

from timeit import timeit
import re
from urllib2 import urlopen
html = urlopen('http://en.wikipedia.org/wiki/Main_Page').read()
# Random reversed strings to avoid unwanted match + one secure match
words = [
    "zihw","elbadartnu", "retlob", "ssenenif", "nnub", "detartsehcro",
    "elbappirnu", "banehc", "rebmunbus", "gnizilodi", "noituac", "deludehcsnu",
    "/body", "latnanosnocerp", "cihportomeh"
]

def in_test(html, blacklist):
    html_lower = html.lower()
    return any(k in html_lower for k in blacklist):

def search_test(html, pattern):
    if re.search(pattern, html):
        return True
    return False

def match_test(html, pattern):
    html_line = html.replace("rn", " ").replace("r", " ").replace("n", " ")
    if re.match(pattern, html_line):
        return True
    return False

# patternX is word|word|word... patternX_exc is .*(word|word|...)
pattern5 = re.compile("|".join(words[:5]), re.I)
pattern5_exc = re.compile(".*(" + "|".join(words[:5]) + ")", re.I)
pattern10 = re.compile("|".join(words[:10]), re.I)
pattern10_exc = re.compile(".*(" + "|".join(words[:10]) + ")", re.I)
pattern15a = re.compile("|".join(words[:15]), re.I)
pattern15a_exc = re.compile(".*(" + "|".join(words[:15]) + ")", re.I)
words[12] = "doctype"  # A secure match at the beginning of the page
pattern15b = re.compile("|".join(words[:15]), re.I)
pattern15b_exc = re.compile(".*(" + "|".join(words[:15]) + ")", re.I)
words[12] = "featured list"  # A secure match at ~half page
pattern15c = re.compile("|".join(words[:15]), re.I)
pattern15c_exc = re.compile(".*(" + "|".join(words[:15]) + ")", re.I)

---

in vs re.match vs re.search无匹配

print timeit("in_test(html, words[:5])", "from __main__ import *")
print timeit("search_test(html, pattern5)", "from __main__ import *")
print timeit("match_test(html, pattern5_exc)", "from __main__ import *")
0.127397060394
2.05020999908
2.17416286469

print timeit("in_test(html, words[:10])", "from __main__ import *")
print timeit("search_test(html, pattern10)", "from __main__ import *")
print timeit("match_test(html, pattern10_exc)", "from __main__ import *")
0.210324048996
3.73544692993
3.8765540123

这些测试没有匹配任何单词。in显然是赢家，速度似乎随着单词数量的增加而线性增加。

---

in vs re.match vs re.search，匹配位置不同

print timeit("in_test(html, words[:15])", "from __main__ import *")
# Match at the end
print timeit("search_test(html, pattern15a)", "from __main__ import *")
print timeit("match_test(html, pattern15a_exc)", "from __main__ import *")
# Match at the beginning
print timeit("search_test(html, pattern15b)", "from __main__ import *")
print timeit("match_test(html, pattern15b_exc)", "from __main__ import *")
# Match at ~half page
print timeit("search_test(html, pattern15c)", "from __main__ import *")
print timeit("match_test(html, pattern15c_exc)", "from __main__ import *")

输出为

0.258332967758
5.9074420929
0.0433299541473
0.000770807266235
6.0548210144
2.47815990448
3.25421690941

当匹配发生时，regex可以比in快得多，但这取决于匹配的位置。在开始时，re.search会更好，在结束时，re.match是更好的选择，在~半页时，两者都明显比in慢。

---

正则表达式将帮助我不重复单词(例如:è, è，…)，让我忘记大写/小写(特别是非ascii字符)。但速度似乎变化太大，平均而言，比in慢。

这些测试正确吗?如果是这样，在这种情况下，是否有其他内置方法可以测试或其他过程可以帮助我?黑名单会越来越多，所以我需要考虑到这一点。

Answer 1

问题总体

它有一个时空权衡:

• 最快的(也是最需要内存的)解决方案是一个N- tree(其中N是字母表中的字母数)。每个节点都有N个指针，如果列表中有以该字母为下一个字母的单词，则每个指针都是非空的，设置一个标志是有一个单词在这里结束。
• 另一个占用空间小得多的快速实现是T9查找。
• 哈希表(在本例中为set，因为您只对存在键感兴趣)的开销较大(哈希计算、与冲突相关的操作)，但可伸缩性非常好，因为在典型情况下它的查找时间几乎是恒定的。Python的映射类型实现自动调整哈希表的大小，以控制潜在的无限冲突相关开销。
• 一个regex(最好通过最小化回溯的数量来优化)的占用可以忽略，但速度很慢，因为python使用一个regex导向的引擎来多次遍历文本:它是一个像egrep那样的文本导向的引擎，更适合这个任务。其他因素是它的工作时间高度依赖于输入(有时是灾难性的)，并且它不能随着单词列表的增长而很好地扩展。与单词列表进行比较的
• 本质上是一种原始的文本定向正则表达式引擎。它不做回溯，但有更大的比较和列表遍历开销。它可能比正则表达式更快或更慢，这取决于如何比较这些开销。

两种方法比较的具体问题:

测试的解释是正确的-对于他们所执行的材料。但是，正如我所说，这两种方法的性能(因此，相对性能)在很大程度上取决于单词列表大小、输入大小、输入本身和正则表达式的最优性。

建议的行动方案

因此，您应该在一些实际的示例上进行测试，这些示例为典型用例建模。例如

• 优化正则表达式，如果并以同样的方式，你打算在生产
• 取几个文档的平均值，其中
  • 匹配的百分比
  • 匹配位置分布
  • 词表单词的相对出现率

与生产中预期的相同。

我建议也测试一下哈希表:它有更大的初始开销，但是对于大的输入和/或单词列表，它应该开始优于其他两个。

为了避免重复单词，您可能希望在搜索之前尝试对输入进行消毒(小写，& -seq替换)的方法。同样，这是额外的开销，在一定规模后开始得到回报。

使用数学方法最小化测试数据

假设匹配位置均匀分布，词表词的出现率相等，则测试数据可简化为:

1. 没有匹配的文本，没有许多像单词列表开头的单词("最佳典型"输入)
2. 文本没有匹配，但完全是与wordlist单词相同的开头方式，"正面"大致均匀地分布在wordlist中(两种方法的"最坏"输入-见1)，如果在生产中可能出现灾难性的失败;2)这种情况对最终结果的影响有多大?
3. 具有一半匹配的文本，其中在单词列表中定位单词需要大约一半的文本和正则表达式匹配器的工作，并且没有许多其他像单词列表中开头的单词

然后，最终的"预期平均"时间:

Txa = (Tn+(Ts-Tn)*Ps)*Pn + (Tm+((Ts-Tm)*Ps)/2)*Pm

其中T -次数，P -期望概率;n -输入不匹配，s -(慢)像单词列表开头的单词，m -输入匹配。