给定长度为N的查询字符串Q，以及长度恰好为N的M个序列的列表L，找到L中具有最少错配位置的字符串的最有效算法是什么？例如：
Q = "ABCDEFG";
L = ["ABCCEFG", "AAAAAAA", "TTAGGGT", "ZYXWVUT"];
answer = L.query(Q); # Returns "ABCCEFG"
answer2 = L.query("AAAATAA"); #Returns "AAAAAAA".
显而易见的方法是扫描L中的每个序列，使搜索采用O（M * N）。在次线性时间有没有办法做到这一点？我不在乎将L组织到某个数据结构中需要大量的前期成本，因为它会被查询很多次。此外，任意处理捆绑分数也没问题。
编辑：为了澄清，我正在寻找汉明距离。
除了提到最好的第一个算法的答案之外的所有答案都非常不合适。 本地敏感的哈希基本上是在做梦。这是我第一次在stackoverflow上看到很多答案。
首先，这是多年前已经解决的一个难以解决的标准问题 以不同的方式。
一种方法使用trie，例如预先设定的那种 通过Sedgewick在这里：
http://www.cs.princeton.edu/~rs/strings/
Sedgewick也有样本C代码。
我引用Bentley和Sedgewick撰写的题为“快速排序和搜索字符串算法”的论文：
“'近邻''查询 找到给定汉明距离内的所有单词 一个查询词 （例如，代码与苏打水的距离为2）。我们为字符串中的近邻搜索提供了一种新算法，提出了一种简单的C实现，并描述了它的效率实验。“
第二种方法是使用索引。将字符串拆分为字符n-gram和index 使用倒排索引（google for Lucene拼写检查器，看看它是如何完成的）。 使用索引来吸引潜在的候选人，然后运行汉明距离或编辑候选人。这种方法保证最佳（并且相对简单）。
第三个出现在语音识别领域。那里的查询是一个wav信号，数据库是一组字符串。有一个“表”将信号的各个部分与单词相匹配。目标是找到最佳匹配的单词来发出信号。这个问题称为单词对齐。
在发布的问题中，将查询部分与数据库部分匹配存在隐式成本。 例如，删除/插入/替换甚至可能有不同的成本 不匹配的不同成本称“ph”与“f”。
语音识别中的标准解决方案使用动态编程方法，通过直接修剪的启发式方法使其有效。通过这种方式，只保留最好的50个候选人。因此，名称最佳第一搜索。从理论上讲，你可能没有得到最好的比赛，但通常你会得到一个很好的比赛。
以下是对后一种方法的参考：
http://amta2010.amtaweb.org/AMTA/papers/2-02-KoehnSenellart.pdf
使用后缀数组和A *解析快速近似字符串匹配。
这种方法不仅适用于单词，也适用于句子。
局部敏感散列 正如我从中理解的那样，似乎是已知的渐近最佳方法的基础 审查CACM中的文章。所说的文章非常多毛，我没有读完。也可以看看 最近邻搜索。
要将这些引用与您的问题联系起来：它们都处理度量空间中的一组点，例如n维向量空间。在您的问题中，n是每个字符串的长度，每个坐标上的值是可以出现在字符串中每个位置的字符。
我想你正在寻找 Levenshtein编辑距离。
有一个 这里几乎没有关于此问题的问题，我想你可以找到一些好的答案。
“最佳”方法会根据您的输入集和查询集而有很大差异。具有固定的消息长度将允许您在分类上下文中处理此问题。
信息理论决策树算法（例如C4.5）将提供最佳的性能保证。为了从此方法中获得最佳性能，必须首先根据互信息将字符串索引聚类为要素。请注意，您需要修改分类器以返回最后一个分支处的所有叶节点，然后计算每个叶节点的部分编辑距离。仅需要为树的最后一次分割所表示的特征集计算编辑距离。
使用这种技术，查询应为~O（k log n），k << m，其中k是特征大小的期望，m是字符串的长度，n是比较序列的数量。
保证初始设置小于O（m ^ 2 + n * t ^ 2），t <m，t * k~m，其中t是项目的特征计数。这是非常合理的，不需要任何严肃的硬件。
由于固定的m约束，这些非常好的性能数字是可能的。请享用！
您可以将每个序列视为N维坐标，将结果空间块化为知道序列中出现的序列的块，然后在查找中首先搜索搜索序列的块和所有连续块，然后根据需要向外展开。 （保持几个分块范围可能比搜索真正大块的块更为可取。）
你在寻找吗？ 汉明距离 字符串之间（即相同位置的不同字符数）？
或者“两个”字符之间的距离（例如英文字母的ASCII值之间的差异）对您来说也很重要吗？
各种各样的 最佳搜索 在目标序列上比O（M * N）好得多。这个的基本思想是你将候选序列中的第一个字符与目标序列的第一个字符进行比较，然后在第二次迭代中只与具有最少不匹配数的序列进行下一个字符比较，等等。在你的第一个例子中，你最后第二次与ABCCEFG和AAAAAAA比较，ABCCEFG仅第三次和第四次，所有序列第五次，之后只有ABCCEFG。当您到达候选序列的末尾时，具有最低不匹配计数的目标序列集是您的匹配集。
（注意：在每个步骤中，您将与下一个字符进行比较 那 搜索的分支。渐进式比较都没有跳过字符。）