algorithm - 近似字符串匹配算法

Question

在工作中，我们经常需要从字符串列表中找到与其他输入字符串最匹配的字符串。目前，我们正在使用 Needleman-Wunsch 算法。该算法通常会返回很多误报(如果我们将最低分数设置得太低)，有时它应该找不到匹配项(当最低分数太高时)，而且大多数时候，我们需要手动检查结果。我们认为我们应该尝试其他选择。

你对算法有什么经验吗？
您知道算法之间的比较吗？

我真的很感激一些建议。

PS:我们用 C# 编码，但你不应该关心它 - 我在问一般的算法。

哦，对不起，我忘了提到这一点。

不，我们没有使用它来匹配重复数据。我们有一个我们正在寻找的字符串列表——我们称之为搜索列表。然后我们需要处理来自各种来源(如 RSS 提要、网站、论坛等)的文本 - 我们提取这些文本的一部分(有整套规则，但这无关紧要)并且我们需要匹配那些反对搜索列表的人。如果字符串与搜索列表中的字符串之一匹配 - 我们需要对事物进行一些进一步的处理(这也是无关紧要的)。

我们无法进行正常的比较，因为从外部来源提取的字符串，大多数情况下，包括一些额外的单词等。

无论如何，它不是用于重复检测。

Answer 1

好的，Needleman-Wunsch(NW) 是来自生物信息学文献的经典端到端(“全局”)对准器。很久以前，它在 FASTA 包中以“align”和“align0”的形式出现。不同之处在于“0”版本并没有那么偏向于避免结束间隙，这通常允许更容易地偏爱高质量的内部匹配。我怀疑你知道，Smith-Waterman 是一个局部矫正器，是 BLAST 的原始基础。 FASTA 也有自己的局部矫正器，略有不同。所有这些本质上都是用于估计与单个字符对的评分指标相关的 Levenshtein 距离的启发式方法(在生物信息学中，通常由 Dayhoff/“PAM”、Henikoff&Henikoff 或其他矩阵给出，通常用更简单、更合理地反射(reflect)替换的东西代替在应用于自然语言时的语言词形态学中)。

让我们不要珍惜标签:至少在实践中引用的 Levenshtein 距离基本上是编辑距离，您必须估计它，因为一般计算它是不可行的，即使在有趣的特殊情况下精确计算也很昂贵:水在那里快速深入，因此我们有长期和良好声誉的启发式方法。

现在关于你自己的问题:几年前，我不得不根据已知正确的引用序列检查短 DNA 读数的准确性，我想出了一种我称之为“ anchor 定比对”的东西。

这个想法是通过查找给定的 N 字符子字符串出现的所有位置来获取您的引用字符串集并“消化”它。选择 N 以便您构建的表不会太大，而且长度为 N 的子串不会太常见。对于像 DNA 碱基这样的小字母表，可以对 N 个字符的字符串进行完美的散列，并制作一个表格并将匹配项链接到每个 bin 的链表中。列表条目必须标识映射到它们出现在列表中的 bin 的子字符串的序列和开始位置。这些是要搜索的字符串列表中的“ anchor ”，其中 NW 对齐可能有用。

在处理查询字符串时，您从查询字符串中的某个偏移量 K 处取 N 个字符，对它们进行散列，查找它们的 bin，如果该 bin 的列表非空，那么您将遍历所有列表记录并在它们之间执行对齐记录中引用的查询字符串和搜索字符串。在进行这些对齐时，您将查询字符串和搜索字符串在 anchor 处对齐，并提取搜索字符串的子字符串，该子字符串与查询字符串的长度相同，并且在相同的偏移量 K 处包含该 anchor 。

如果您选择足够长的 anchor 长度 N 和一组合理的偏移 K 值(它们可以分布在查询字符串中或限制为低偏移)，您应该获得可能对齐的子集，并且通常会获得更清晰的获胜者。通常，您会希望使用末端偏向较小的类似 align0 的 NW 对准器。

这种方法试图通过限制它的输入来稍微提高 NW 并且这有一个性能增益，因为你做的比对更少，而且它们更经常出现在相似的序列之间。使用 NW 矫正器的另一个好处是让它在出现一定数量或长度的间隙后放弃以降低成本，特别是如果您知道自己不会看到中等质量的比赛或对中等质量的比赛不感兴趣。

最后，这种方法被用在一个小字母系统上，K 限制在查询字符串中的前 100 个左右的位置，并且搜索字符串比查询大得多(DNA 读数大约为 1000 个碱基，搜索字符串位于10000 的顺序，所以我正在寻找近似的子串匹配，特别是对编辑距离的估计)。将此方法应用于自然语言需要仔细考虑:您会损失字母大小，但如果您的查询字符串和搜索字符串的长度相似，则您会受益。

无论哪种方式，允许同时使用来自查询字符串不同端的多个 anchor 可能有助于进一步过滤馈送到 NW 的数据。如果您这样做，请准备好可能将每个包含两个 anchor 之一的重叠字符串发送到对齐器，然后协调对齐...算法的执行。

希望这是有帮助的或至少是有趣的。