python - 定位距目标字符串 N 字符长距离最小的 "N Gram"个子字符串

Question

我正在寻找一种算法，最好是在 Python 中，它可以帮助我找到最接近 N 个字符长的目标字符串的现有字符串的 N 个字符长的子字符串。

考虑目标字符串，即 4 个字符长，为:

targetString -> '1111'

假设这是我可用的字符串(我将生成它的子字符串以进行“最佳对齐”匹配):

nonEmptySubStrings -> ['110101']

上面的 4 个字符长的子字符串:

nGramsSubStrings -> ['0101', '1010', '1101']

我想编写/使用一个“魔术函数”来选择最接近 targetString 的字符串:

someMagicFunction -> ['1101']

更多例子:

nonEmptySubStrings -> ['101011']
nGramsSubStrings -> ['0101', '1010', '1011']

someMagicFunction -> ['1011']

nonEmptySubStrings -> ['10101']
nGramsSubStrings -> ['0101', '1010']

someMagicFunction -> ['0101', '1010']

这个“魔术函数”是一个众所周知的子串问题吗？

我真的很想找到最小值。 nonEmptySubStrings 中的更改次数，以便将 targetString 作为子字符串。

Answer 1

我相信你需要Edit Distance . Peter Norvig's spelling corrector是python中的一个实现示例。这是一个 implementation of Levenshtein Distance .另见 this question .

编辑:这在生物信息学中相当常见。参见例如FASTA和 BLAST .生物信息学有很多这种算法的风格。参见 Sequence Alignment进行方法调查。