在工作中，我们经常需要从字符串列表中找到与其他输入字符串最匹配的字符串。目前，我们正在使用 Needleman-Wunsch 算法。该算法经常返回很多误报（如果我们将最低分数设置得太低），有时它在应该找到匹配时（当最低分数太高时）找不到匹配，而且大多数时候，我们需要手动检查结果。我们认为我们应该尝试其他替代方案。
你有算法方面的经验吗？你知道算法之间的比较吗？
我真的很感激一些建议。
PS：我们用 C# 编码，但你不应该关心它——我问的是一般的算法。
哦，对不起，我忘了提到这一点。
不，我们没有使用它来匹配重复数据。我们有一个我们正在寻找的字符串列表——我们称之为搜索列表。然后我们需要处理来自各种来源（如 RSS 提要、网站、论坛等）的文本——我们提取这些文本的一部分（有整套规则，但这无关紧要），我们需要匹配那些反对搜索列表的人。如果该字符串与搜索列表中的一个字符串匹配 - 我们需要对该事物进行一些进一步的处理（这也是无关紧要的）。
我们无法进行正常的比较，因为从外部来源提取的字符串大多数时候都包含一些额外的单词等。
无论如何，它不是用于重复检测。
好的，Needleman-Wunsch(NW) 是生物信息学文献中经典的端到端（“全球”）校准器。它很久以前在 FASTA 包中以“align”和“align0”的形式提供。不同之处在于“0”版本并没有那么偏向于避免末端间隙，这通常允许更容易偏爱高质量的内部匹配。我怀疑你知道 Smith-Waterman 是一个局部校准器，并且是 BLAST 的原始基础。FASTA 也有自己的局部矫正器，但略有不同。所有这些本质上都是用于估计与单个字符对的评分度量相关的 Levenshtein 距离的启发式方法（在生物信息学中，通常由 Dayhoff/“PAM”、Henikoff&Henikoff、
让我们不要对标签感到珍贵：至少在实践中引用的 Levenshtein 距离基本上是编辑距离，您必须估计它，因为一般计算它是不可行的，而且即使在有趣的特殊情况下精确计算也很昂贵：水在那里快速深入，因此我们拥有久负盛名的启发式方法。
现在至于您自己的问题：几年前，我必须根据已知正确的参考序列检查短 DNA 读数的准确性，我想出了我称之为“锚定比对”的东西。
这个想法是通过查找给定 N 字符子字符串出现的所有位置来获取您的参考字符串集并“消化”它。选择 N 以便您构建的表不会太大，但也可以使长度为 N 的子字符串不太常见。对于像 DNA 碱基这样的小字母，可以在 N 个字符的字符串上得出一个完美的哈希值，然后制作一个表格，并将每个 bin 中的匹配项链接到一个链表中。列表条目必须标识映射到它们出现在其列表中的 bin 的子字符串的序列和起始位置。这些是要搜索的字符串列表中的“锚点”，NW 对齐可能有用。
处理查询字符串时，您从查询字符串中的某个偏移量 K 开始获取 N 个字符，对它们进行哈希处理，查找它们的 bin，如果该 bin 的列表非空，则遍历所有列表记录并执行对齐记录中引用的查询字符串和搜索字符串。进行这些对齐时，您将查询字符串和搜索字符串排列在锚点处，并提取搜索字符串的子字符串，该子字符串与查询字符串的长度相同，并且在相同的偏移量 K 处包含该锚点。
如果您选择足够长的锚长度 N 和一组合理的偏移量 K 值（它们可以分布在查询字符串中或限制为低偏移量），您应该获得可能对齐的子集，并且通常会获得更清晰的赢家。通常，您会希望使用末端偏向较小的 align0-like NW aligner。
这种方法试图通过限制它的输入来稍微提高 NW，这会提高性能，因为你做的比对更少，而且它们更经常出现在相似的序列之间。使用 NW 矫正器的另一件好事是允许它在出现一定数量或长度的间隙后放弃以降低成本，特别是如果您知道您不会看到或对中等质量的匹配不感兴趣。
最后，这个方法被用在一个小字母的系统上，K 限制在查询字符串中的前 100 个左右位置，搜索字符串比查询大得多（DNA 读数大约 1000 个碱基，搜索字符串在10000 的顺序，所以我正在寻找通过专门估计编辑距离来证明的近似子字符串匹配）。将此方法应用于自然语言需要仔细考虑：您会损失字母大小，但如果您的查询字符串和搜索字符串的长度相似，您就会受益。
无论哪种方式，允许同时使用来自查询字符串不同端的多个锚点可能有助于进一步过滤馈送到 NW 的数据。如果这样做，请准备好可能将每个包含两个锚点之一的重叠字符串发送到对齐器，然后协调对齐...或者可能进一步修改 NW 以强调在对齐期间使用惩罚修改期间保持锚点基本完整算法的执行。
希望这会有所帮助或至少很有趣。
与 Levenstein 距离有关：您可能希望通过将结果除以较长字符串的长度来对其进行归一化，这样您总是得到一个介于 0 和 1 之间的数字，这样您就可以有意义地比较一对字符串的距离方式（例如，表达式 L(A, B) > L(A, C) 是没有意义的，除非您将距离标准化）。
我们正在使用Levenshtein 距离方法来检查我们数据库中的重复客户。它工作得很好。
可供研究的替代算法是agrep（关于 agrep 的维基百科条目）、 FASTA 和 BLAST生物序列匹配算法。这些是近似字符串匹配的特殊情况，也在Stony Brook 算法存储库中。如果您可以指定字符串彼此不同的方式，您可能可以专注于定制算法。例如，aspell 使用一些变体的“soundslike”（soundex-metaphone）距离与“keyboard”距离相结合，以适应糟糕的拼写者和糟糕的打字者。
为了尽量减少由于拼写中的细微变化或错误导致的不匹配，我使用了 Metaphone 算法，然后在 Metaphone 编码上使用了 Levenshtein 距离（以百分比匹配的形式缩放到 0-100）来衡量接近度。这似乎工作得很好。
为了扩展 Cd-MaN 的答案，听起来您正面临标准化问题。如何处理不同长度的对齐之间的分数并不明显。
鉴于您感兴趣的内容，您可能希望获得对齐的 p 值。如果您使用的是 Needleman-Wunsch，您可以使用 Karlin-Altschul 统计数据http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html获得这些 p 值
BLAST 可以使用这些统计数据进行局部对齐和评估。如果您担心速度，这将是一个很好的工具。
另一种选择是使用 HMMER。HMMER 使用 Profile Hidden Markov 模型来比对序列。就个人而言，我认为这是一种更强大的方法，因为它还提供了位置信息。http://hmmer.janelia.org/