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

4

1 に答える 1

2

これは、PythonなどのナイーブなREマッチャーで超線形時間を要するREの1つであるように見えます。最初のパターンを次のように書き直すことで、劇的にスピードアップできます。

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

ここで(?:、非キャプチャグループを紹介します。

編集：上記のREはあなたのものと完全に同等ではありません。訂正してください。その精神は次のとおり{m,n}です。バックトラックが少なくなるため、操作を繰り返しに使用します。

于 2012-04-19T09:51:57.867 に答える