python -regex匹配一个单词列表

我有一个python脚本，大概有100个左右的正则表达式行，每行匹配某些单词。python -regex匹配一个单词列表

脚本显然会在每次运行时消耗高达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)

来源

2010-11-09 Joe

这里你的算法基本上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)，这意味着您可以根据需要添加尽可能多的单词而不会减慢算法。

来源

2010-11-09 03:53:14 tghw

python -regex匹配一个单词列表

回答

相关问题