给定长度为 N 的查询字符串 Q 和长度恰好为 N 的 M 个序列的列表 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组织成某些数据结构的大量前期成本，因为它将被查询很多次。同时，任意处理并列分数都可以。
编辑：澄清一下，我正在寻找汉明距离。
http://www.cs.princeton.edu/~rs/strings/
Sedgewick还有样例C代码。http://amta2010.amtaweb.org/AMTA/papers/2-02-KoehnSenellart.pdf
快速近似字符串匹配算法：基于后缀数组和A*解析。该方法不仅适用于单词，还适用于句子。我想你正在寻找Levenshtein编辑距离。
在SO上已经有一些关于此的问题, 我想你可以找到一些好的答案。
（注意：在每个步骤中，您都在与搜索分支的下一个字符进行比较。没有任何逐步比较跳过字符。）
我无法想出一个通用的、精确的算法，其时间复杂度小于O(N * M)。但是，如果你的M和N足够小，你可以使用比特并行操作来实现一个性能为(N + M)的算法。
例如，如果N和M都小于16，你可以使用一个64位整数的N * M查找表（16*log2(16) = 64），并在字符串的一次遍历中执行所有操作，其中计数器中的每组4位计数0-15，用于匹配其中一个字符串。显然，你需要M log2(N+1)位来存储计数器，因此可能需要更新每个字符的多个值，但通常单次查找可以比其他方法更快。因此，它实际上是O(N * M log(N))，只是具有较低的常数因子——使用64位整数会引入1/64，因此如果log2(N) < 64，则应该更好。如果M log2(N+1) < 64，则结果为(N+M)操作。但这仍然是线性的，而不是亚线性的。
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>
size_t match ( const char* string, uint64_t table[][128] ) ;
int main ()
{
const char* data[] = { "ABCCEFG", "AAAAAAA", "TTAGGGT", "ZYXWVUT" };
const size_t N = 7;
const size_t M = 4;
// prepare a table
uint64_t table[7][128] = { 0 };
for ( size_t i = 0; i < M; ++i )
for ( size_t j = 0; j < N; ++j )
table[j][ (size_t)data[i][j] ] |= 1 << (i * 4);
const char* examples[] = { "ABCDEFG", "AAAATAA", "TTAGQQT", "ZAAGVUT" };
for ( size_t i = 0; i < 4; ++i ) {
const char* q = examples[i];
size_t result = match ( q, table );
printf("Q(%s) -> %zd %s\n", q, result, data[result]);
}
}
size_t match ( const char* string, uint64_t table[][128] )
{
uint64_t count = 0;
// scan through string once, updating all counters at once
for ( size_t i = 0; string[i]; ++i )
count += table[i][ (size_t) string[i] ];
// find greatest sub-count within count
size_t best = 0;
size_t best_sub_count = count & 0xf;
for ( size_t i = 1; i < 4; ++i ) {
size_t sub_count = ( count >>= 4 ) & 0xf;
if ( sub_count > best_sub_count ) {
best_sub_count = sub_count;
best = i;
}
}
return best;
}
抱歉打扰了这个旧帖子
逐个搜索元素的意思是复杂度为O(M*N*N) - O(M)用于搜索和O(N*N)用于计算Levenshtein距离。
原帖作者正在寻找一种有效的方法来查找最小汉明距离(c)，而不是字符串本身。如果您有一个上限c（比如X），您可以在O(log(X)*M*N)的时间内找到最小的c。
正如Stefan所指出的，您可以快速找到给定汉明距离内的字符串。这个页面http://blog.faroo.com/2015/03/24/fast-approximate-string-matching-with-large-edit-distances/讲述了一种使用Tries的方法。将其修改为仅测试是否存在这样的字符串，并在0到X之间进行二分查找。
如果前期成本不重要，您可以计算每个可能输入的最佳匹配，并将结果放入哈希映射中。
当然，如果N不是非常小，则无法使用此方法。