我有一些数据，最多一百万到十亿条记录，每条记录都由一个位域表示，每个键大约 64 位。这些位是独立的，您基本上可以将它们想象成随机位。
如果我有一个测试键，并且我想用相同的键找到我的数据中的所有值，哈希表将很容易地在 O(1) 中吐出这些值。
什么算法/数据结构可以有效地找到与查询键最相似的所有记录？这里的相似意味着大多数位是相同的，但允许有最少的错误。这传统上是用 Hamming distance. 来衡量的，它只计算不匹配位的数量。
有两种方法可以进行此查询，一种可能是通过指定不匹配率，例如“给我一个与我的查询不同的少于 6 位的所有现有 key 的列表”，或者通过简单的最佳匹配，例如“给我一个 10,000 个键的列表，这些键与我的查询具有最少的不同位。”
您可能会想跑到 k-nearest-neighbor algorithms ，但这里我们讨论的是独立位，因此像四叉树这样的结构似乎不太可能有用。
这个问题可以通过简单的暴力测试哈希表的少量不同位来解决。例如，如果我们想找到与我们的查询相差一位的所有键，我们可以枚举所有 64 个可能的键并测试它们。但这很快就爆炸了，如果我们想允许两个位的差异，那么我们必须探测 64*63=4032 次。对于更多的位数，它会呈指数级恶化。
那么是否有另一种数据结构或策略可以让这种查询更加高效呢？ 数据库/结构可以任意预处理，需要优化的是查询速度。
最佳答案
你想要的是一个BK-Tree .这是一棵非常适合索引度量空间的树(你的问题是一个)，并支持最近邻和距离查询。我写了an article前段时间讲过。
BK-Trees一般是引用文本描述的，使用levenshtein距离来构建树，但是用二进制字符串和汉明距离来写一个更简单。
关于database - 用于查找具有相似位值的附近键的数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/977375/