regex検索が終了しない

Question

私はシーケンス内のモチーフを検索しています（ギャップがあるため、正規表現はpatternの各シンボルの後に - *でオーバーコンプレックスが表示されます）。 次のコードは、コードが動作

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はこの正規表現検索の実行を終了することもできません。

Answer 1

これはnaive RE matchers, such as Python'sの超線形時間を取るそれらのREのようです。あなたは(?:は非キャプチャグループを紹介

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

のようなものとしてそれを書き換えることにより、飛躍的に第一のパターンをスピードアップすることができます。

EDIT：上記のREは、あなたと全く同じではありません。それを修正してください。それの精神は：反復のために、より少ないバックトラッキングを引き起こすので、繰り返し操作のために{m,n}オペレーションを使用します。