我有一些数据,高达一百万到十亿条记录,每个数据由位域表示,每个密钥大约64位.这些位是独立的,你可以想象它们基本上是随机位.
如果我有一个测试键,我想用相同的键查找我的数据中的所有值,哈希表将很容易地吐出来,在O(1)中.
什么算法/数据结构将有效地查找与查询键最相似的所有记录？这里类似的意思是大多数位是相同的,但是最小的数字被允许是错误的.这通常由Hamming distance.测量,它只是计算不匹配位数.
有两种方式可能会进行此查询,可能是通过指定不匹配率,例如“给我一个所有现有密钥的列表,其中所有现有的密钥有少于6位,不同于我的查询”或简单的最佳匹配,如“给我一个具有我查询中不同位数最少的10,000个密钥的列表.
你可能会跑到k-nearest-neighbor algorithms,但是在这里我们谈论的是独立的位,所以似乎没有像四叉树这样的结构是有用的.
这个问题可以通过简单的强力测试来解决,这个哈希表用于低位数的不同位.如果我们想要查找与查询不同的所有键,例如,我们可以枚举所有64个可能的键并测试它们.但是这个爆炸很快,如果我们想允许两位差异,那么我们必须探测64 * 63 = 4032次.对于较高的位数,它的指数变差.
解决方法
你想要的是一个
BK-Tree.它是一个树,非常适合索引度量空间(你的问题是一个),并支持最近邻和距离查询.我之前写过
an article.
BK-tree通常用参考文本描述,并使用levenshtein距离构建树,但直接用二进制串和汉明距离来写一个.
