python - 近似匹配的位置

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的初始位置？

我已经尝试过像 Levenshtein 或 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