近似字符串匹配算法

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

您对算法有任何经验吗？你知道算法如何相互比较吗？

我真的很感激一些建议.

PS:我们用C#编码,但你不应该关心它 - 我一般都在询问算法.

哦,对不起,我忘记提及了.

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

我们无法执行正常的比较,因为从外部源提取的字符串,大多数时候,包括一些额外的单词等.

无论如何,它不是重复检测.

OK,Needleman-Wunsch(NW)是来自生物信息学文献的经典端到端("全球")对准器.它很久以前在FASTA包中可用作"align"和"align0".不同之处在于"0"版本并没有像避免端部间隙那样偏向,这通常会让高质量的内部匹配变得更容易.史密斯 - 沃特曼,我怀疑你知道,是当地的对准者,是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对齐器.

这种方法试图通过限制它的输入来增加NW,这有一个性能提升,因为你做的对齐较少,而且它们通常在相似的序列之间.与你的NW对准器有关的另一个好处是允许它在经过一定量或长度的间隙后放弃以降低成本,特别是如果你知道你不会看到或对中等质量的比赛感兴趣.

最后,此方法用于具有小字母的系统,其中K限制在查询字符串中的前100个左右位置,搜索字符串比查询大得多(DNA读数大约为1000个碱基,搜索字符串打开10000的顺序,所以我一直在寻找由编辑距离估计合理的近似子串匹配.将此方法适用于自然语言需要仔细考虑:如果您的查询字符串和搜索字符串的长度相似,您会失去字母大小.

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

希望这有用或至少有趣.

与Levenstein距离相关:您可能希望通过将结果除以较长字符串的长度来对其进行标准化,以便始终获得介于0和1之间的数字,以便您可以比较有意义的字符串对的距离方式(表达式L(A,B)> L(A,C) - 例如 - 除非你标准化距离,否则没有意义).

要查看的替代算法是agrep(agrep上的维基百科条目), FASTA和BLAST生物序列匹配算法.这些是近似字符串匹配的特殊情况,也在Stony Brook算法库中.如果您可以指定字符串彼此不同的方式,则可以专注于定制算法.例如,aspell使用"soundlike"(soundex-metaphone)距离的一些变体以及"键盘"距离来容纳不良拼写者和坏打字者.