一日一技：使用二分法排查正則表達式的異常
- 2020 年 1 月 23 日
- 筆記
現在我有10億條微博正文，並從同事手上拿到了15000條需要過濾的垃圾資訊正則表達式，只要微博正文符合任何一條正則表達式，就刪除這條微博。
正則表達式的格式為：
^你成功領取 |^感謝您的積 |^在第d+次抽獎. |^只有幫主才 |^目標有相應 |^寶寶#G. |^提交失敗， |^您已領取過 |^破軍爭奪戰 |^首席大弟子 |數第d+個丫鬟 |你的店鋪 |恭喜.*?投中了 |<web |你將該物品拆解成 |^你身上沒有 |歡迎參加微博抽獎 |蔡徐坤 |王一博 |朱一龍 ...
存放在一個名為trash.txt的文本文件中，每個正則表達式一行。
一般情況下，我只需要使用如下幾行程式碼就能實現這個功能：
import re with open('trash.txt', encoding='utf-8') as f: lines = [x.strip() for x in f] pattern = re.compile(''.join(lines)) for weibo in weibo_list: if pattern.search(weibo): print('垃圾資訊，過濾！')但是當我的程式碼運行到re.compile這一行時，報錯了，如下圖所示：
並且，即使你在 Google 上面搜索：re.error: multiple repeat at position，截至2019年12月30日，你能找到的都是對這個報錯的討論，但沒有一個討論能解決本文描述的問題。
那我們自食其力，來試著解決一下這個問題。它報錯報的是position 167，那麼我們來看看第167個字元有什麼問題。在 PyCharm 中，可以在右下角查看你選中了多少個字元，如下圖所示：
從截圖中可以看到，第167個字元所在的這一行正則表達式為：|張三丰.*?張翠山.*?張無忌，但是我完全看不出這一行正則表達式有什麼問題。
由於報錯了，那麼肯定至少有一行正則表達式有問題，我們假設有問題的正則表達式有且只有一行。現在我們有15000行正則表達式，如何找出有問題的這一行呢？
這個時候，我們就可以使用二分查找來解決這個問題，，我們最多查找14次就能找到有問題的這一行正則表達式。
由於正則表達式一共有15000行，我們就先看0-7500行在編譯時是否會報錯，如果報錯，在看0-3750行是否報錯，如果不報錯，在看3750-7500行是否報錯……如此分割下去，直到找到報錯的這一行正則表達式。
二分查找的程式碼如下：
import re with open('trash.txt', encoding='utf-8') as f: lines = [x.strip() for x in f] def is_compile_success(regex): try: re.compile(regex) return True except Exception: return False def search(regex_list): if len(regex_list) == 1: print(regex_list[0]) return mid = len(regex_list) // 2 part_1 = ''.join(regex_list[: mid]) part_2 = ''.join(regex_list[mid: ]) if not is_compile_success(part_1): search(regex_list[: mid]) return if not is_compile_success(part_2): search(regex_list[mid:]) return search(lines)運行結果如下圖所示：
原來出問題的地方在：.*??，這裡多寫了一個問號。把這一行改成|趙大.*?包以後，編譯成功通過。
思考題
- 如果要把出問題的這一行所在的行號列印出來，應該如何修改程式碼？
- 如果有問題的正則表達式不止一行，應該如何修改程式碼，從而列印所有有問題的正則表達式？
