Fuzzy regex（例如{e<=2}）Python中的正确用法

Question

我试着找出两个不同的字符串。在

但是，以下代码并不像我预期的那样工作，至少从我对fuzzy regex的理解来看是这样的：

import regex
res = regex.findall("(ATAGGAGAAGATGATGTATA){e<=2}", "ATAGAGCAAGATGATGTATA", overlapped=True)
print res
>> ['ATAGAGCAAGATGATGTATA']  # the second string

如您所见，这两个字符串的区别在于三个字母，而不是最多两个字母：

第一个有：ATAGGAGaagatgatgatata

第二个是：ATAGAGCAAGATGATATA

但是结果显示了第二个字符串，就好像它在e<；=2之内（重叠=False也会发生这种情况，所以不可能是这样）。在

我错过了什么？有没有办法让它只在给定模式的Hamming 2球内找到弦？在

换信是否可能被认为只是一种改变？如果是这样的话，我该怎么避免呢？在

Answer 1

你的错误是假设“错误”和“替换”是同一回事，而事实并非如此。在

^{}包的模糊匹配可以理解三种错误——插入、删除和替换。使用e指定的错误距离可以由这些错误的任意组合组成。而ATAGGAGAAGATGATGTATA只需两个这样的操作（1个删除和1个插入）就可以被编辑成{}，如下面的序列比对所示：

ATAGGAG-AAGATGATGTATA
ATAG-AGCAAGATGATGTATA

is there any way of getting this to find only strings within the Hamming 2-ball of the given pattern?

是的。注意，Hamming distance是一种编辑距离，它测量将一个字符串编辑到另一个长度相等的字符串所需的最小替换次数。因此，要只匹配模式的Hamming 2-ball中的字符串，我们需要告诉regex匹配2替换中的任何内容，这可以通过使用s错误类型而不是e：

^{pr2}$

Is it possible that a swap of letters is considered to be only one change?

不在当前的regex包中。两个字符“交换”的标准术语是“换位”。作为可能的编辑（例如Dameau-Levenshtein distance，其中编辑可以是插入、替换、删除或相邻字符的转置）的编辑距离确实存在，并且对于某些应用程序（例如，打字错误更正）是有用的。然而，在编写本文时，regex包中的模糊匹配根本不支持它们。在

Answer 2

让我们检查一下这个片段中的模糊计数：

>>> pattern_string = 'ATAGGAGAAGATGATGTATA'
>>> query_string = 'ATAGAGCAAGATGATGTATA'
>>> r = regex.compile('(%s){e<=2}' % pattern_string)
>>> r.match(query_string)
<regex.Match object; span=(0, 20), match='ATAGAGCAAGATGATGTATA', fuzzy_counts=(0, 1, 1)>

fuzzy_counts=(0, 1, 1)意味着在这种情况下，我们没有得到替换、1次插入和1次删除。所以你的过滤器工作是因为错误总数是2。在

但似乎只需要按替换计数进行筛选，因此可以修改正则表达式：

^{pr2}$

查看docs中的这个很好的示例：

• {i<；=3}最多允许3次插入，但不允许其他类型的插入
• {d<；=3}许可证 最多删除3个，但没有其他类型
• {s<；=3}最多允许3个 替换，但没有其他类型
• {i<；=1，s<；=2}最多允许1 插入，最多2次替换，但不删除
• {e<；=3}许可证 最多3个错误

• {1<；=e<；=3}允许至少1个错误，最多3个错误

• {i<；=2，d<；=2，e<；=3}最多允许2次插入，最多2次删除，在 总共3个错误，但没有替换