跳到主要內容

用 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

留言

這個網誌中的熱門文章

(C/C++ ) 如何在 Linux 上使用自行編譯的第三方函式庫

以使用 LevelDB 為例。 抓好並編好相關檔案,編譯方式見第三方函式庫附的說明:$ ls include/ # header files leveldb/ $ ls out-shared/libleveldb.so* # shared library out-shared/libleveldb.so@ out-shared/libleveldb.so.1@ out-shared/libleveldb.so.1.20* 下面的例子用 clang++ 編譯,這裡用到的參數和 g++ 一樣。 問題一:找不到 header$ clang++ sample.cpp sample.cpp:5:10: fatal error: 'leveldb/db.h' file not found #include "leveldb/db.h" ^ 1 error generated. 解法:用 -I 指定 header 位置 問題二:找不到 shared library$ clang++ sample.cpp -I include/ /tmp/sample-2e7dd8.o: In function `main': sample.cpp:(.text+0x1e): undefined reference to `leveldb::Options::Options()' sample.cpp:(.text+0x6f): undefined reference to `leveldb::DB::Open(leveldb::Options const&, std::string const&, leveldb::DB**)' sample.cpp:(.text+0x10c): undefined reference to `leveldb::Status::ToString() const' sample.cpp:(.text+0x7d0): undefined reference to `leveldb::Status::ToString() const' clang: error: linker command failed with exit code 1 (u…

熟悉系統工具好處多多

記一下以前很困擾, 現在秒殺的小事。 更新這篇的時候, 忘了函式庫用的 man page 裝在那個 package。以前就會想辦法 google, 運氣好一下會找到, 運氣不好會多找一會兒。 這回我想到新作法:$ strace -e open man 3 printf > /dev/null # 發現是讀 /usr/share/man/man3/printf.3.gz $ dpkg --search /usr/share/man/man3/printf.3.gz # 找到套件名稱 manpages-dev $ aptitude show manpages-dev # 確認描述符合, 收工

virtualbox 使用 USB 裝置

2012-12-16 更新 現在 (4.x 版) 似乎無需做任何設定, 只要有裝 Oracle VM VirtualBox Extension Pack, 在 VirtualBox 視窗右下角按 USB 的圖示, 再點目標裝置, 即可加入或移除該裝置 同一時間只有 host 或 guest 可擁有該裝置, 所以從 guest OS 移除, 相當於接回 host OS 目前 VirtualBox 只支援 USB 2.0 的插槽, 若偵測不到時, 注意一下是否為這個問題 有時拔拔插插, VirtualBox 會進入奇怪的狀態, 接上去 guest OS 無法連接且跳出 device is busy 的錯誤訊息。試看看拔除該裝置, 重開 guest OS (續上則) 若重開 guest OS 無效, 並且 host OS 已移除該裝置, VirtualBox 的 USB 清單卻仍顯示 "captured", 試看看拔除該裝置, 重開 host OS原文網路上搜一下, 比較多是 Ubuntu 當 host 的解法, 我的情況是 Win7 當 host, Ubuntu 當 guest。 這兩篇說明很詳細《Learn How to Set Up USB and Networking Options in VirtualBox》《幻影千瞳的部落格: VirtualBox 使用筆記(二):使用 USB 裝置》 現在的版本圖形介面很好用了, 不用像第二篇說的那樣用指令操作。這裡記下我的操作步驟: 關掉 guest OS 在 VirtualBox 選單, 選擇 guest OS -> Settings -> USB -> Enable USB 2.0 會出現訊息框, 說明要安裝 Oracle VM VirtualBox Extension Pack。下載後安裝它 host OS 插入 USB 隨身碟 在 VirtualBox 選單, 選擇 guest OS -> Settings -> USB, 點右邊有綠色 "+" 的 USB 頭的圖示, 選擇該 USB 隨身碟, 加入它的 filter 從 host OS 移除 USB 隨身碟 開啟 guest OS 插入 USB 隨身碟, 於是 guest OS 會自動偵測…