一日一技：使用二分法排查正则表达式的异常
- 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)
运行结果如下图所示：
原来出问题的地方在：.*??，这里多写了一个问号。把这一行改成|赵大.*?包以后，编译成功通过。
思考题
- 如果要把出问题的这一行所在的行号打印出来，应该如何修改代码？
- 如果有问题的正则表达式不止一行，应该如何修改代码，从而打印所有有问题的正则表达式？
