找到输入最相似字符串的最快方法？

给定长度为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和索引与倒排索引(google for Lucene拼写检查器,看看它是如何完成的).使用索引来吸引潜在的候选人,然后运行汉明距离或编辑候选人.这种方法保证最佳(并且相对简单).

第三个出现在语音识别领域.那里的查询是一个wav信号,数据库是一组字符串.有一个"表"将信号的各个部分与单词相匹配.目标是找到最佳匹配的单词来发出信号.此问题称为单词对齐.

在发布的问题中,将查询部分与数据库部分匹配存在隐式成本.例如,一个人可能有不同的删除/插入/替换成本,甚至不匹配的不同成本说"ph"与"f".

语音识别中的标准解决方案使用动态编程方法,通过直接修剪的启发式方法使其有效.通过这种方式,只保留最好的50个候选人.因此,名称最好先搜索.从理论上讲,你可能没有得到最好的比赛,但通常你会得到一个很好的比赛.

以下是对后一种方法的参考:

http://amta2010.amtaweb.org/AMTA/papers/2-02-KoehnSenellart.pdf

使用后缀数组和A*解析快速近似字符串匹配.

这种方法不仅适用于单词,也适用于句子.