정규 표현식 검색이 종료되지 않음

시퀀스에서 모티프를 검색하고 있습니다 (간격이 있기 때문에 정규 표현식이 패턴의 각 심볼 다음에 - *가있는 것으로 나타납니다). 다음 코드는 코드가 작동정규 표현식 검색이 종료되지 않음

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은이 regex 검색에 대한 실행을 완료하지 못합니다.

출처

2012-04-19 InternazionalIV

naive RE matchers, such as Python's에 수퍼 선형 시간이 걸리는 RE 중 하나입니다. 당신은 (?: 비 캡처 그룹을 소개

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

처럼 뭔가로 다시 작성하여 극적으로 첫 번째 패턴을 속도를 높일 수 있습니다.

편집 : 상기 RE는 귀하와 완전히 동일하지 않습니다. 수정하십시오. 그것의 정신은 다음과 같습니다. 반복을 위해 {m,n} 작업을 사용하십시오. 백 트랙킹이 적기 때문입니다.

출처

2012-04-19 09:51:57

이것은 정규 표현식과 동일하지 않습니다. 예를 들어'[KR]'은 처음 두 번 선택 사항입니다 ... –

@TimPietzcker : 그 이유는 그룹 뒤에'{1,3} '이 있기 때문입니다. –

같은 방식으로 작동하지 않습니다. '-K-'는'[KR]? - * [KR]? * [KR] - *'과 일치하지만'(? : [KR] - *) {1,3}'과는 일치하지 않습니다. –

정규 표현식 검색이 종료되지 않음

답변

관련 문제