模糊正则表达式（例如 {e<=2}）在 Python 中的正确用法

Question

我试图找到与原始模式字符串最多有两个错误 'away' 的字符串（即它们最多相差两个字母）。

但是，下面的代码并没有像我预期的那样工作，至少从我对模糊正则表达式的理解来看是这样的：

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

如您所见，两个字符串在三个字母上不同，而不是最多两个：

第一个有：ATAGGAGAAGATGATGTATA

第二个有：ATAGAGCAAGATGATGTATA

但结果显示第二个字符串，就好像它在 e<=2 内一样（这也发生在 overlapped=False 的情况下，所以不可能是这样）。

我在这里错过了什么？有没有办法让它只找到给定模式的汉明 2 球内的字符串？

是否可以将字母交换视为仅一次更改？如果是这样 - 我怎样才能避免这种情况？

Answer 1

让我们检查一下这段代码的模糊计数：

>>> 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。

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

import regex
res = regex.findall("(ATAGGAGAAGATGATGTATA){s<=2}", "ATAGAGCAAGATGATGTATA", overlapped=True)
print res

查看 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 个错误，但没有替换

Answer 2

您的错误是认为 "errors" 与 "substitutions" 是同一回事，但事实并非如此。

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

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 是一种编辑距离，用于衡量将一个字符串编辑为另一个等长字符串所需的替换的最小数量。因此，为了仅匹配汉明 2 球模式中的字符串，我们需要告诉 regex 匹配 2 substitutions 中的任何内容，我们可以使用 [=17] =] 错误类型而不是 e:

import regex
res = regex.findall("(ATAGGAGAAGATGATGTATA){s<=2}", "ATAGAGCAAGATGATGTATA", overlapped=True)
print res

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

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

模糊正则表达式（例如 {e<=2}）在 Python 中的正确用法

Fuzzy regex (e.g. {e<=2}) correct usage in Python

python

regex

fuzzy-search

pypi-regex