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 字符 block ，其中 n 是 len(ptn)
• 计算每个 block 和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]