python - 正则表达式匹配单词列表

Question

我有一个Python脚本，里面大概有100行正则表达式，每一行都是用来匹配特定的单词。

每次运行这个脚本时，它的CPU使用率几乎会达到100%（我基本上是给它传一个句子，它会返回找到的匹配单词）。

我想把这些正则表达式合并成大约4到5个“编译过的”正则解析器，比如：

>>> words = ('hello', 'good\-bye', 'red', 'blue')
>>> pattern = re.compile('(' + '|'.join(words) + ')', re.IGNORECASE)

我可以安全地放多少个单词在里面？这样做会有区别吗？现在如果我对一千个随机句子进行循环处理，它大约每秒能处理10个，我希望能大幅提高这个速度，最好能达到每秒处理500个（如果可能的话）。

另外，像这样列出单词是否可行？

>>> words = ('\d{4,4}\.\d{2,2}\.\d{2,2}', '\d{2,2}\s\d{2,2}\s\d{4,4}\.')
>>> pattern = re.compile('(' + '|'.join(words) + ')', re.IGNORECASE)
>>> print pattern.findall("Today is 2010 11 08)

Answer 1

你的算法基本上是 O(N*M*L)，其中 N 是句子的长度，M 是你要找的单词数量，L 是你要找的最长单词的长度。这种算法在处理每个句子时都需要这么多时间。使用正则表达式并不会比直接用查找快多少。它唯一的好处是可以匹配像你第二个例子那样的模式。

如果你只是想找单词，使用 字典树（Trie） 会是一个更好的选择。实现起来也非常简单：

TERMINAL = 'TERMINAL' # Marks the end of a word

def build(*words, trie={}):
    for word in words:
        pointer = trie
        for ch in word:
            pt = pt.setdefault(ch, {TERMINAL:False})
        pt[TERMINAL] = True
    return trie

def find(input, trie):
    results = []
    for i in range(len(input)):
        pt = trie
        for j in range(i, len(input)+1):
            if pt[TERMINAL]:
                results.append(input[i:j])
            if j >= len(input) or input[j] not in pt:
                break
            pt = pt[input[j]]
    return results

这个方法会返回你句子中所有在字典树里的单词。运行时间是 O(N*L)，这意味着你可以添加任意数量的单词，而不会让算法变慢。