https://stackoverflow.com/questions/49263
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
在这里在工作中，我们常常需要找到一串串名单，是最接近的匹配，其他一些输入串。目前，我们正在使用裁缝-Wunsch算法。算法往往会返回一个很大的误报(如果我们设定的最低得分太低)，有时没有找到匹配时，它应该(在最低的分数太高)，大部分的时候，我们需要检查的结果。我们认为我们应该试试其它的替代品。
你有任何经验的算法？你知道怎么算法进行比较吗？
我真的很欣赏一些建议。
PS:我们编码在C#但你不该关心它-我在问关的算法。
哦，对不起，我忘记提到这一点。
不，我们不使用这匹配的重复数据。我们有一串名单，我们正在寻找的-我们称它为搜索名单。然后我们需要处理的文本，从各种来源(如RSS源、网站、论坛，等等。) -我们中提取零部件的这些案文(也有整套的规则，但这无关)，我们需要那些对搜索清单。如果串一个相匹配的串的搜索名单-我们需要做一些进一步处理的问题(这也是无关紧要的).
我们不能执行正常比较，因为串取从外部来源，大部分的时间，包括一些额外的话等。
无论如何，这不是重复检测。
解决方案
OK，裁缝-Wunsch(西北)是一个典型的终端到终端("全球化")的矫正器从生物信息学文献。这是很久以前可以作为"调整"和"align0"在FASTA包。的区别是，"0"的版本没有为偏见的关于避免最终缺口，其中往往允许有利于高质量的内部比赛更容易。史密斯-沃特曼，我怀疑你是知道的，是一个当地矫正器，并且是原始基础的爆炸。FASTA有它自己的当地矫正器，以及那是略有不同。所有这些都基本上启发式方法，用于估计Levenshtein distance相关的分指标对于个人角色对(在生物信息学，往往通过Dayhoff/"PAM",一致&一致，或其他矩阵和通常更换的东西更简单、更合理地反映了替代语言字形态时，应用于自然语言)。
让我们不是宝贵的有关标签:Levenshtein的距离，引用在实践中至少，基本上是编辑距离你必须估计，因为它是不可行的计算通常，这是昂贵的计算准确甚至在有趣的特殊情况：水深快速有，因而我们有启发式方法的长期和良好的声誉。
现在为你自己的问题：几年前，我要检查精确性的简短的DNA读对附序称为是正确的和我想出了一些我所谓的"锚定路线".
这个想法是采取参考串集和"文摘"，它通过寻找所有位置的其中一个给予N字符串发生。选择N使表你的建立是不是太大，但也这样子的长度N不太常见。对于小的字母就像DNA基地，它可以拿出一个完美的哈希上串N字符和使表和链的匹配在一个链表从每一桶。名单条目必须确定的顺序，并开始位置的子串，地图以站在谁的名单，他们会发生。这些都是"锚"在串名单可搜索在这一NW准可能是有用的。
当处理的查询string,你把N字开始在一些偏K查询字符串中，散他们，看他们站，并且如果列表对这一站是非空，然后你去过所有的列表中记录和执行路线之间的串查询和检索字符串中引用的记录。当做这些比，你行的串查询和检索字符串 在 锚和中提取一串的搜索字符串，同样的长度作为查询串，其中包含锚在相同的偏移，K.
如果你选择一个足够长的锚长N和合理设置的价值观的偏K(他们可以传播到全串查询或者被局限于低偏移量)你应该得到一个子集的可能的路线，并经常将得到更清楚的获奖者。通常你将要使用的低端偏align0状NW矫正器。
这种方法试图提高NW一位通过限制它的输入和这有一个能获得，因为你做的小的比对和它们之间更经常相似的序列。另一个良好的事情要做你的NW矫正器是允许它放弃之后，一些数量或长度的间隙发生削减成本，尤其是如果你知道你不会看见或者有兴趣在中等质量相匹配。
最后，这种方法是使用系统上的小字母，K限于第100或因职位串查询和检索字符串远大于查询(DNA读周围1000基地和检索字符串了10000，所以我在寻找近似子串匹配的理由的估计距离编辑具体地说).适应这种方法自然语言将要求认真考虑:你失去了关于字母的大小，但你获得如果你的查询和搜索字符串串的类似的长度。
无论哪种方式，允许多个锚从不同端的查询串同时使用可能有助于进一步筛选数据输送到NW。如果你这样做，准备可能发串重叠，每个含有两个锚矫正器，然后协调的路线...或者可能进一步修改NW强调保持你的锚点主要是完整的在一个校准使用修改刑期间的算法的执行。
希望这是有帮助的，或至少有趣的。
其他提示
关于莱文史丹距离：你可能希望正常化，它通过将其结果与长度的时间越长串，这样，你总是能得到一个数量在0和1之间和所以，你可以比较的距离对串有意义的方式(表达L(A、B)L(A、C)-例如-是毫无意义，除非你正常化的距离)。
替代的算法来看是 桑巴 (维基百科上的条目桑巴), FASTA和爆炸 生物序匹配的算法。这些是特殊情况下的 近似匹配串, 也在 Stony Brook算法repositry.如果你可以指定方式串彼此不同，你也许可以重点量身定做的算法。例如，支持采用一些变体"soundslike"(soundex-音位)的距离，结合"键盘的"距离，以适应不良的拼写和坏typers一样。
我们正在使用的 Levenshtein distance 方法为检查重复的顾客在我们的数据库。它工作得很好。
为了尽量减少错配，由于轻微的变化或错误拼写，我用音位的算法，然后编辑距离(缩小到0-100的百分比作匹配)在音位编码，用于衡量亲近。这似乎运作得相当好。
扩大在Cd-男人的回答，这听起来像是你面对一个正规化的问题。这不是显而易见如何处理之间的成绩比对不同的长度。
鉴于你是什么感兴趣，你可能想要获得p-值取向。如果您使用的是裁缝-Wunsch，可以获得这些p-值使用卡林-Altschul统计数据 http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html
爆炸将能当地对准和评估它们使用这些统计数据。如果你关心的速度，这将是一个很好的工具来使用。
另一个选择是使用HMMER.HMMER使用配置文件隐马模型对准序列。就个人而言，我认为这是一个更强有力的方法，因为它还提供了位置的信息。 http://hmmer.janelia.org/
我曾经工作的一些最肮脏的数据，你永远也找不到。平均大约5000行的数据(相当于数百万美元)所需匹配是完全用尽。我的第一个经验与模糊匹配是一个算法从先生Excel写在VBA。它有某些问题的一致性在这的事情，我预计以零百分比不是临屋区和东西，大约60%的人看起来更像是90%。因此，我搬到编辑和后来到Damerau-Levenshtein.这是一个重大的改善，但是相当缓慢。接下来我跳过伽罗-温克勒但是很快放弃了它不久之后。最后，在2016我写了我自己的(基于n-gram)和精它在未来的2年。今天它是一个附加的名为Flookup;你可以在床单，并看看如何保持。
