3

我正在寻找序列中的主题（其中有间隙，这就是为什么正则表达式看起来过于复杂，在模式中的每个符号之后都有一个 -* ）。以下代码不会停止执行

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 正则表达式搜索的执行。

4

1 回答 1

2

看起来这是在天真的 RE 匹配器中花费超线性时间的那些 RE 之一，例如 Python 的. 您可以通过将第一个模式重写为类似的东西来显着加快第一个模式

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

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

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

于 2012-04-19T09:51:57.867 回答