sorting - 快速汉明距离计分

Question

有一个包含 N 个固定长度字符串的数据库。
有一个相同长度的查询字符串。
问题是从数据库中获取到 q 的汉明距离最小的前 k 个字符串。

N很小(大约400)，字符串很长，长度固定。数据库不会改变，所以我们可以预先计算索引。查询变化很大，缓存和/或预计算不是一种选择。每秒有很多。我们总是需要 k 个结果，即使 k-1 个结果匹配 0(按汉明距离排序并取第一个 k，因此局部敏感散列和类似方法将不起作用)。 kd-tree 和类似的空间分区的性能可能比线性搜索差(字符串可能很长)。 BK-tree 目前是最好的选择，但它仍然比它需要的更慢和复杂。

感觉就像有一个算法，它会建立一个索引，它会在很少的步骤中丢弃大部分条目，留下 k <= t << N 个条目来计算真正的汉明距离。

人们建议基于 Levenstein 距离进行模糊字符串匹配 - 谢谢，但问题要简单得多。基于广义距离度量的方法(如 BK 树)很好，但也许有一些利用上述事实的东西(小 DB/长固定大小字符串，简单的汉明距离)

链接、关键词、论文、想法？ =)

Answer 1

这似乎是一项任务，其中 Vantage Point (VP tree)可能有用……因为汉明距离应该满足三角不等式定理，你应该能够应用它……它也有助于识别 k-closest。我在图像索引数据库设置中见过它...你可以查看 this paper 的第 5 部分作为我正在谈论的一个例子(尽管在不同的领域)。