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匹配一個單詞列表

回答

相關問題