근사 일치 위치

Question

문자열에서 특정 패턴의 대략적인 일치를 만들 수있는 스크립트 작업 중입니다.이 패턴 (중첩 될 수 있음)이 시작되는 위치 만보고합니다.

지금까지, 나는 정확히 일치의 위치를보고 할 수있는 스크립트를 얻을 수 있지만 대략적인 사람을위한 성공 :

import re 
stn = 'KLHLHLHKPLHLHLPHHKLHKLPKPH' 
pat = 'KLH' 
matches = re.finditer(r'(?=(%s))' % re.escape(pat), stn) 
finalmatch= [m.start() for m in matches] 
pos = ' '.join(str(v) for v in finalmatch) 
print pos 

이 경우 결과는 다음과 같습니다 하지만 경우 스크립트 보고서도 대략 일치합니까? 즉 허용 된 최대 오류 (허용치 또는 임계 값)가 1 (쿼리 패턴의 모든 위치) 인 경우 HLH, PLH, KLP, KPH의 초기 위치는 어떻게보고 될 수 있습니까?

나는 이미 Levenshtein이나 SequenceMatcher와 같은 거리 측정을 포함 시키려고했으나 성공하지 못했습니다.

미리 도움을 주셔서 감사합니다.

Answer 1

그냥 패턴을 변경

import re 
from itertools import chain 
stn = 'KLHLHLHKPLHLHLPHHKLHKLPKPH' 
pats = ['KLH', 'KL, 'LH, 'K', 'L', 'H'] 
matches = [] 
for pat in pats: 
    matches = chain(matches, (re.finditer(r'(?=(%s))' % re.escape(pat), stn)) 
finalmatch= [m.start() for m in matches] 
pos = ' '.join(str(v) for v in finalmatch) 
print pos 

Answer 2

기본 방법 :

• 그룹 n는 각 청크와 동일 얼마나 많은 문자 len(ptn)
• 카운트가 n 문자의 stn 연속 덩어리와 ptn
• 시작하기 얼마나 많은 이들은 len(ptn)

예에서 하나 개의 문자 다르다 :

stn = 'KLHLHLHKPLHLHLPHHKLHKLPKPH' 
pat = 'KLH' 

n_combos = zip(*[stn[n:] for n in range(len(pat))]) 
m_counts = (sum(1 for i, j in zip(el, pat) if i == j) for el in n_combos) 
indices = [idx for idx, val in enumerate(m_counts) if val >= len(pat) - 1] 
# [0, 2, 4, 8, 10, 17, 20, 23]