python -regex匹配单词列表

Question

我有一个 python 脚本，它可能有 100 条左右的正则表达式行，每行匹配特定的单词。

脚本每次运行时显然会消耗高达 100% 的 cpu(我基本上向它传递一个句子，它会返回找到的任何匹配词)。

我想将它们组合成大约 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 是您要查找的最长单词)。使用正则表达式不会比使用 find 更快。它唯一能给你的是像你的第二个例子那样匹配模式的能力。

如果您只想查找单词，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

这会返回你的句子中所有在 trie 中的单词。运行时间为 O(N*L)，这意味着您可以添加任意数量的单词而不会降低算法速度。