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

Question

给定一个长度为 N 的查询字符串 Q 和一个长度恰好为 N 的 M 序列列表 L，在 L 中找到与 Q 不匹配位置最少的字符串的最有效算法是什么？例如:

Q = "ABCDEFG";
L = ["ABCCEFG", "AAAAAAA", "TTAGGGT", "ZYXWVUT"];
answer = L.query(Q);  # Returns "ABCCEFG"
answer2 = L.query("AAAATAA");  #Returns "AAAAAAA".

显而易见的方法是扫描 L 中的每个序列，使搜索时间复杂度为 O(M * N)。有没有办法在亚线性时间内做到这一点？我不在乎将 L 组织成某种数据结构是否需要大量的前期成本，因为它会被查询很多次。此外，任意处理平分也是可以的。

编辑:澄清一下，我正在寻找汉明距离。

Answer 1

除了提到最好的第一个算法的那个以外，所有的答案都离得很远。本地敏感散列基本上是在做梦。这是我第一次在 stackoverflow 上看到如此多的答案。

首先，这是一个很难但标准的问题，很多年前就已经解决了以不同的方式。

一种方法使用 trie，例如预设的Sedgewick 在这里:

http://www.cs.princeton.edu/~rs/strings/

Sedgewick 也有示例 C 代码。

我引用了 Bentley 和 Sedgewick 的题为“排序和搜索字符串的快速算法”的论文:

“‘‘近邻’’查询定位给定汉明距离内的所有单词查询词的距离(例如，code 与 soda 的距离为 2)。我们给出了一种新的字符串近邻搜索算法，提供了一个简单的 C 实现，并描述了其效率的实验。”

第二种方法是使用索引。将字符串拆分为字符 n-gram 和索引使用倒排索引(谷歌搜索 Lucene 拼写检查器，看看它是如何完成的)。使用索引拉取潜在候选人，然后对候选人运行汉明距离或编辑距离。这是保证最有效(并且相对简单)的方法。

第三个出现在语音识别领域。查询是一个 wav 信号，数据库是一组字符串。有一个“表格”将信号片段与单词片段相匹配。目标是找到最匹配的单词来发出信号。这个问题被称为单词对齐。

在发布的问题中，将查询部分与数据库部分进行匹配会产生隐性成本。例如，一个人可能有不同的删除/插入/替换成本，甚至不匹配的不同成本说“ph”与“f”。

语音识别中的标准解决方案使用动态规划方法，该方法通过直接修剪的启发式方法变得高效。这样，只保留最好的，比如 50 名候选人。因此，名称最佳优先搜索。从理论上讲，您可能无法获得最佳匹配，但通常会获得良好的匹配。

这里引用后一种方法:

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

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

这种方法不仅适用于单词，也适用于句子。