这里有一个快速又简单的方法，
然后是以更多内存为代价获得更好性能的变体。
在：数组 Uint X[]，例如1M 32 位字
想要：一个函数near( Uint q )--> j 小hammingdist( q, X[j] )
方法：二分查找q已排序X,
然后线性搜索周围的一个块。
伪代码：
def near( q, X, Blocksize=100 ):
preprocess: sort X
Uint* p = binsearch( q, X ) # match q in leading bits
linear-search Blocksize words around p
return the hamming-nearest of these.
这速度真快——二分查找100万字
+ 大小为 100 的块中最近的 Hammingdist
在我的 Mac ppc 上花费 will vary.)
这距离找到真正最接近的 X[j] 有多近？
我只能实验，不能做数学：
对于 1M 随机单词中的 1M 随机查询，
最近的匹配项平均相差 4-5 位，
vs. 3 距离为真正的最近（线性扫描全部 1M）：
near32 N 1048576 Nquery 1048576 Blocksize 100
binary search, then nearest +- 50
7 usec
distance distribution: 0 4481 38137 185212 443211 337321 39979 235 0
near32 N 1048576 Nquery 100 Blocksize 1048576
linear scan all 1048576
38701 usec
distance distribution: 0 0 7 58 35 0
使用块大小（例如 50 和 100）运行数据
看看比赛距离如何下降。
To get even nearer, at the cost of twice the memory,
make a copy
Xswap of
X with upper / lower halfwords swapped,
and return the better of
near( q, X, Blocksize )
near( swap q, Xswap, Blocksize )
有了大量内存，就可以使用更多的位混洗副本X,
例如32 次旋转。
我不知道性能如何随 Nshuffle 和 Blocksize 变化 -
这是 LSH 理论家面临的一个问题。
(Added): To near-match bit strings of say 320 bits, 10 words,
make 10 arrays of pointers, sorted on word 0, word 1 ...
and search blocks with binsearch as above:
nearest( query word 0, Sortedarray0, 100 ) -> min Hammingdist e.g. 42 of 320
nearest( query word 1, Sortedarray1, 100 ) -> min Hammingdist 37
nearest( query word 2, Sortedarray2, 100 ) -> min Hammingdist 50
...
-> e.g. the 37.
这当然会错过没有任何一个单词接近的近似匹配，
不过很简单，排序和binsearch就是炽热地快速地。
指针数组占用的空间与数据位完全相同。
100 个字、3200 位的工作方式完全相同。
但是：只有当 0 位和 1 位的数量大致相等时，这才有效，
不是 99%0 位。
