Положение приблизительных совпадений

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

результат в этом случае: 0 17, но что если в отчете сценария также указаны приблизительные совпадения? т. е. если максимально допустимая ошибка (допуск или порог) равна 1 (в любой позиции шаблона запроса), как можно сообщать о начальных позициях HLH, PLH, KLP, KPH?

Я уже пытался включить меру расстояния, как Левенштейн или SequenceMatcher, но безуспешно.

Заранее спасибо за помощь.

Answer 1

Основной способ:

• группа stn последовательные куски n символы где n является len(ptn)
• Посчитайте, сколько символов одинаковы для каждого куска и 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]

Answer 2

Просто измените шаблон:

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