数据库 – 用于查找具有相似位值的附近键的数据结构

如果我有一个测试键,我想用相同的键查找我的数据中的所有值,哈希表将很容易地吐出来,在O(1)中.

什么算法/数据结构将有效地查找与查询键最相似的所有记录？这里类似的意思是大多数位是相同的,但是最小的数字被允许是错误的.这通常由Hamming distance.测量,它只是计算不匹配位数.

有两种方式可能会进行此查询,可能是通过指定不匹配率,例如“给我一个所有现有密钥的列表,其中所有现有的密钥有少于6位,不同于我的查询”或简单的最佳匹配,如“给我一个具有我查询中不同位数最少的10,000个密钥的列表.

你可能会跑到k-nearest-neighbor algorithms,但是在这里我们谈论的是独立的位,所以似乎没有像四叉树这样的结构是有用的.

这个问题可以通过简单的强力测试来解决,这个哈希表用于低位数的不同位.如果我们想要查找与查询不同的所有键,例如,我们可以枚举所有64个可能的键并测试它们.但是这个爆炸很快,如果我们想允许两位差异,那么我们必须探测64 * 63 = 4032次.对于较高的位数,它的指数变差.

那么还有另一种数据结构或策略使得这种查询更有效率？
数据库/结构可以根据需要进行预处理,这是应优化的查询速度.

解决方法

BK-tree通常用参考文本描述,并使用levenshtein距离构建树,但直接用二进制串和汉明距离来写一个.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!