python - 正则表达式搜索无法终止

Question

我正在搜索序列中的图案(其中有间隙，这就是为什么正则表达式看起来过于复杂，在模式中的每个符号后面都有一个 -* )。以下代码不会停止执行

import re
line = """MRVKE---TRKNY-QH--------S-----W-------GRGLWSLWRW-------------G---T-------MLLG--ML-M----IS-S--A-A-----E-Q---S--WVTVYYGVPVWREATT-TLFCASDAKAYDTEKH-NVWATHACVPTDPNPQEVQL--NVTENFNMWKNNMVDQMHEDIISLWDQSLKPCVQLTPLCVT-LNC-SD------TINA---TTANNTINA----------------TTT-----TPT-----I----NATT-------------ANKSMEIG---------E---MR----NCSFNIT----NM---G-K-KMK--EYALFYN----LDVV---------------SI-----------------D-------E-----------------DNNNK-------------------------------------------TS--------Y---RLK-SCNTSVI-TQACP-KVSFKPIPIHYCAPAGFAILKCND-KKFNGTGPCGNVSTVQCTHGIKPVVSTQLLLNGSLAE-E-EVVIRSENFTNNVKTIIVQLKNPVMINCTRP-NNNTR-KS-I---HM---GP----GQ-A-F-YAT-GAI---IGDIR-QAHCNI--SE-------------------------------------------K--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------E"""
pattern = "[KR]?-*[KR]?-*[KR]-*[^-]?-*[^-]?-*[KR]-*[^-]-*[^-]-*[^-]?-*[^-]?-*[ILVM]-*[^-]-*[ILVF]"

o = re.search(pattern, line)

该代码适用于其他行和其他主题(例如，以微秒为单位完成执行)以下几个:

pattern = "[KR]?-*[KR]?-*[KR]-*[^-]?-*[^-]?-*[KR]-*[^-]-*[^-]-*[^-]?-*[^-]?-*[ILVM]-*[^-]-*"
pattern = "[KR]-*[^-]?-*[^-]?-*[KR]-*[^-]-*[^-]-*[^-]?-*[^-]?-*[ILVM]-*[^-]-*[ILVF]"

如果从行尾移除大间隙，它也可以正常工作。事实上，vim 也无法完成特定 this 正则表达式搜索的执行。

Answer 1

看起来这是那些在 naive RE matchers, such as Python's 中花费超线性时间的 RE 之一.您可以通过将第一个模式重写为类似的东西来显着加快第一个模式的速度

r"(?:[KR]-*){1,3}(?:[^-]?-*){2}[KR]-*(?:[^-]-*){2}(?:[^-]?-*){2}[ILVM]-*[^-]-*[ILVF]"

其中 (?: 引入了一个非捕获组。

编辑:上面的 RE 不完全等同于你的；请更正。它的精神是:使用{m,n}操作进行重复，因为它会减少回溯。