在这里，我们经常需要从字符串列表中找到与其他输入字符串最接近的字符串。当前，我们正在使用Needleman-Wunsch算法。该算法通常会返回很多假阳性(如果我们将最小得分设置得太低)，有时它在应有的时间(当最小得分太高时)找不到匹配项，并且在大多数情况下，我们需要手工检查结果。我们认为我们应该尝试其他替代方法。

我们对算法有任何经验吗？
我们知道算法之间的比较吗？

我真的很感谢一些建议。

PS：我们正在用C＃进行编码，但是我们一般不必关心它，而是在询问有关算法的一般信息。

哦，对不起，我忘了提了。

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

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

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

解决方案

回答

我们正在使用Levenshtein距离方法来检查数据库中是否有重复的客户。效果很好。

回答

与Levenstein距离有关：我们可能希望通过将结果除以较长字符串的长度来对其进行归一化，以便始终获得0到1之间的数字，以便可以比较有意义的字符串对的距离方式(例如，除非规范化距离，否则表达式L(A，B)> L(A，C)毫无意义)。

回答

好的，Needleman-Wunsch(NW)是来自生物信息学文献的经典端到端("全局")比对仪。很早以前在FASTA软件包中就可以将其用作" align"和" align0"。所不同的是，" 0"版本在避免终止间隔方面没有偏见，这通常使得更容易支持高质量的内部匹配。我怀疑我们知道，史密斯·沃特曼(Smith-Waterman)是本地对准器，并且是BLAST的原始基础。 FASTA也有自己的本地校准器，但略有不同。所有这些本质上都是启发式方法，用于估计与各个字符对的得分度量相关的莱文施泰因距离(在生物信息学中，通常由Dayhoff /" PAM"，Henikoff＆Henikoff或者其他矩阵提供，通常用更简单，更合理地反映替换的替换方法来替换)语言语言形态学应用于自然语言时)。

让我们对标签不那么珍贵：至少在实践中提到的Levenshtein距离基本上是编辑距离，我们必须对其进行估算，因为通常无法计算距离，即使在有趣的特殊情况下，精确计算也很昂贵很快就在那里变得很深，因此我们有了启发性的长期良好声誉的方法。

现在是关于我们自己的问题：几年前，我不得不对照已知正确的参考序列检查短DNA读取的准确性，然后提出了一种称为"锚定比对"的方法。

这个想法是通过查找参考字符串集并通过查找给定N字符子字符串出现的所有位置来"消化"它。选择N，以使生成的表不太大，但长度N的子字符串也不太常见。对于像DNA碱基这样的小字母，可以对N个字符的字符串进行完美的哈希处理，然后制作表格并将匹配项从每个bin中链接到链表中。列表条目必须标识子字符串的顺序和开始位置，该子字符串映射到它们出现在其列表中的bin。这些是要搜索的字符串列表中的"锚点"，在该字符串处可能会使用NW对齐。

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

如果选择足够长的锚点长度N和合理的偏移量K值集(它们可以分布在查询字符串中或者限制为低偏移量)，则应该获得可能的对齐方式的子集，并且通常会获得更清晰的赢家。通常，我们将需要使用末端偏斜的，类似align0的NW对准器。

此方法尝试通过限制其输入来稍微提高NW，这会提高性能，因为我们进行的比对较少，而且它们通常在相似序列之间。与NW对准器一起做的另一件好事是允许它在出现一定数量或者长度的间隙以降低成本后放弃，尤其是如果我们知道我们不会看到或者对中等质量的比赛感兴趣的话。

最终，此方法用于具有小字母的系统，其中K限制在查询字符串的前100个左右位置，并且搜索字符串比查询大得多(DNA读数约为1000个碱基，并且搜索字符串位于数量级为10000，因此我一直在寻找近似子字符串匹配项，具体取决于估算的编辑距离)。使这种方法适应自然语言将需要仔细考虑：我们会损失字母大小，但是如果查询字符串和搜索字符串的长度相似，则会有所收获。

无论哪种方式，允许同时使用来自查询字符串不同端的多个锚点可能有助于进一步过滤馈给NW的数据。如果执行此操作，请准备好将可能包含两个锚点之一的重叠字符串发送到对齐器，然后协调对齐方式……或者可能进一步修改NW以强调在对齐期间使用惩罚修改来使锚点在大多数情况下保持完好无损。算法的执行。

希望这会有所帮助或者至少有趣。

回答

要查看的其他算法是agrep(agrep上的Wikipedia条目)，
FASTA和BLAST生物序列匹配算法。这些是近似字符串匹配的特殊情况，在Stony Brook算法存储库中也是如此。如果我们可以指定字符串彼此不同的方式，那么我们可能会专注于量身定制的算法。例如，aspell使用" soundslike"(soundex-metaphone)距离的某种变体与" keyboard"距离相结合，以适应错误的拼写者和错误的打字员。