查找接近结果的哈希

位图索引。如果你想要完整的背景资料,那就去Google上看看吧。基本上为布尔值构建bitmpa,如下所示:

010110101010
110100010100
000101001100

然后,只需对它们进行异或筛选,按匹配数排序,返回。由于所有操作都非常快(每个元素大约一个周期,并且数据结构使用(编辑)每个元素100位内存),所以即使是线性的,这通常也会起作用。

附录:如何异或。(修正了一个错误)

000101001100 source
000101001010 target
000000000110 result of XOR

 int n = 0; if (v) do { n++; } while (v &= (v-1)); return(n);

这两个1告诉你有两个错误和m-2匹配,其中m是位数。

你所描述的是 近邻搜索 :基于记录,根据任意距离函数(例如不同值的数目)查找5个最近的记录。

散列函数有意丢弃除“这些值相等”之外的任何信息,因此实际上不是这样做的。

考虑使用为最近邻搜索优化的数据结构,例如 kd-tree 或 vp-tree . 如果列表中已经存在一个高概率,那么您可以先使用哈希表查找它,然后如果它不存在,则返回到KD树上。

这是基于Kdansky的答案。

Create a dynamic array of entries.
Create a cache.

for each lookup,
   check the cache.
   return the cache entry if the value exists.
   otherwise for each value in the dynamic array,
       if hamming distance is less than threshold add to the result list
   cache the value against the result
   return the result

要找到汉明距离: 异或并找出汉明重量 http://en.wikipedia.org/wiki/Hamming_weight