用 regexp 的 lookahead 尋找符合 pattern A 但不符合 pattern B 的字串

偶而會需要找內含字串 A 但不含字串 B 的字串, 若剛好得用 regexp 表示的話, 會有點麻煩 (像是用 Android logcat filter 的時候)。查了一下, 發現 regular expression 有個強大的語法叫作 lookaround, 用它可相對容易地達到此需求, 還可以應付各種情況。詳見 Regex Lookarounds: Lookahead and Lookbehind 的介紹。關鍵在於 lookaround 的語法只是從「目前的位置」往前或往後「看看是否符合目標 pattern」,不會實際占去符合的字串。看文件的例子會比較好理解。

以下是用 Python RE 比對「內含 abc 但 abc 之後不含 def 的字串」:

In [70]: re.search('(?!.*def)abc', 'abcdef')

(?!.*def)abc 的意思是每一個位置都做以下的事:

1. 先往後找看看有沒有符合 .*def, 找不到才算成立。(?!...) 的意思是 negative lookahead
2. negative lookahead 成立後, 看看目前位置是否能找到 abc

反之, 下面這個寫法是錯的, 比對 abcdef 仍會有結果:

In [69]: re.search('(?!def)abc', 'abcdef')
Out[69]: <_sre.SRE_Match at 0x2f2fd98>

因為它的意思是在目前位置看看是否不符合 def, 於是一開始比對 abc 時就成立了, 然後再比對成功 abc, 於是回傳比對成功的結果。

(?!.*def)abc 看起來很美好, 但它無法避開 defabc, 也就是 abc 之前有 def 的情況。雖然有 lookbehind 的語法, 但它只能比對固定長度的 pattern, 無法應付 xxxdefxxxabc, 所以得換個方式表示。

regex - Regular expression to match string not containing a word? 說明如何用 regexp 表示不含目標字串的字串, 並有圖解說明運作的過程。了解之後, 可運用同樣的技巧表示「內含 abc 但 abc 之前不含 def 的字串」:

In [145]: re.search('^((?!def).)*abc', 'defabc')

1. (?!def) 檢查目前位置是否不含 def
2. (?!def). 注意多加了一個 '.', 表示檢查完後占去一個字元
3. ((?!def).)* 比對 0 到多個符合 (?!def). 的字元

利用 regexp greedy 的特性, pattern 3 會盡可能占去符合這個的字元, 於是 ^((?!def.)*abc 就會比對出「內含 abc 但 abc 之前不含 def 的字串」。

再和一開始用的 lookahead 合在一起, 就能表示「內含 abc 但不含 def 的字串了」:

In [147]: re.search('^((?!def).)*(?!.*def)abc', 'abcdef')

In [148]: re.search('^((?!def).)*(?!.*def)abc', 'defabc')

In [149]: re.search('^((?!def).)*(?!.*def)abc', 'abc')
Out[149]: <_sre.SRE_Match at 0x2f2de40>

In [150]: re.search('^((?!def).)*(?!.*def)abc', 'xxxabcxdefxx')

In [151]: re.search('^((?!def).)*(?!.*def)abc', 'xdefxxabcxxx')

In [152]: 

就算一時之間無法消化也無所謂, 記得關鍵字 lookaround, lookahead, lookbehind, 之後比較方便找 regexp 進階用法。每次找 regexp 的說明, 都會學到新東西, 真是博大精深的表示法。

2014/07/07 更新

經 weiyu 提醒, 移動 abc 到中間效率會比較好, 以下是程式和測試結果:

$ cat a.py
import re
import time

begin = time.time()
pattern = re.compile('^((?!def).)*(?!.*def)abc')
for i in xrange(1000000):
    pattern.search('xxxxxxabcxxxxxx')
    pattern.search('xxxdefxxxabcxxxxxx')
    pattern.search('xxxxxxabcxxxdefxxx')
print time.time() - begin

begin = time.time()
pattern = re.compile('^((?!def).)*abc(?!.*def)')
for i in xrange(1000000):
    pattern.search('xxxxxxabcxxxxxx')
    pattern.search('xxxdefxxxabcxxxxxx')
    pattern.search('xxxxxxabcxxxdefxxx')
print time.time() - begin
$ python a.py
4.64261507988
3.08146381378