这个问题其实是从之前博客（http://blog.csdn.net/lgnlgn/archive/2010/11/14/6008498.aspx）介绍的爬虫去重的论文中的一个内容，问题是这样描述的：给定N个f位的指纹集合C，对一个输入指纹f’，如何找出C中与f’汉明距离小于k的所有指纹？
具体地，论文里N=80亿，f=64，K=3。
64位取3的汉明距离可能性一共有C(64,3) > 40000，也得进行超过40000次的查询…如果是有序数组，采用二分搜索或者内插搜索，总量很大时每次查询也需要几十次计算。
另外一种办法就是把64位中61位看成不变的，预先排序，这就需要排C(64,61)>40000块，查询的时候把f’拆成40000个可能并行地在这些块上进行搜索。
无论哪种方案都是时间空间承受不了的，因此论文里提出了个折中方案：预先排序多块，每块进行少量搜索。下面介绍两种方案
1.假设64为可以分成ABCD各16位的4部分，16位一共可以表示2^16种可能，如果集合里有100万个指纹，也就是2^20个；假设我们按A部分排序，那么平均地看每个指纹A部分相同的应该有2^(20-16)个。如果我们保证其中一个部分精确匹配16位，那么汉明距离变化的3位最坏的可能性让它发生在BCD部分，我们只需要逐一比较2^(20-16)个指纹。
例如B出现1位，C出现两位；或者BCD各出现一个不同位。如果A出现了1位不同，B出现2位不同，那么精确匹配C部分的16位，逐一比较C部分相同的2^(20-16)个指纹，就行了。所有的可能性都能覆盖到。那么集合需要4份不同的排序结果，按ABCD。
2.如果64位分成5部分每部分分别12-13位，最坏可能要把汉明距离限制在3块之中，一共有C(5,3)=10种可能，那么前2块能表示2^(25~26)个可能，10亿(即2^30)个指纹，精确匹配前2块以后平均只需要逐一比较2^(4~5)个。若是上一种方案，还需要平均比较2^14个呢。这种方案需要10种不同的排序。
方案其实还有，这里就不说了，下面来说下实现的考虑
一次完整的查询是对f’在不同的排序块中搜索以后再合并。64位就是一个8字节整数，假设有1亿个指纹，就是800M，不论哪种方案，放内存都不合适，要放到外存。
Java里随机访问文件可以用RandomAccessFile，后来发现用NIO里的fileChannel效率更高。
并行搜索再合并，可以开多个线程来搜索；考虑到每次搜索的时间长短不同，同时进行100次查询，需要开1000个线程，比较浪费，想到java中concurrency中的线程池更适合这样的场景。
实现方案1的时候，可以采用一些技巧来节省计算开销，例如16位一共有65536种可能，在内存中维护一个65536大小的long数组array，数组的下标表示16位比特的值，数组的值表示16位比特值代表的前缀在集合中起止偏移量，例如array[0]=3表示0000000000000000从0号偏移开始3为止。array需要提前计算好，array只占64K
* 8 = 512k大小，4块加起来也只有2M。查询f’的时候，先取出f’的4个前缀16位，在数据中直接取出文件位移，再到文件中按偏移起止直接取出每个指纹后面的48bits。
其实如果指纹总量不大，比如100万，完全可以在放在内存中，需要320M，如果出去前16bit，只需要240M，当达到千万级的时候才需要放到外存。当达到亿级的时候，方案1每次查询需要逐一比较汉明距离的次数达到一万次以上，如果采用方案2，则逐一比较量降到几百，但是总空间需要8G，如果总量达到百亿，可能还得用复制更多块的方案。
我分别实现了nio和stream、RandomAccess方法（后俩必须算好起止直接跳过），很直接的实现；测试的时候出现不能理解的问题，在千万级的数据集上，nio的一次查询时间要么0.4要么10多ms甚至有过50ms。
如果每次查询一样的数，速度会很快，而要是随机的，就会很慢。但是这一批随机数在同个进程再跑一遍的时候，缺又是和查询一样的数时候一样快。百思不得其解。
有高手说这是文件系统缓存的问题，首次读是冷启动，第二次读是热启动。如果是这样瓶颈可能出在跳偏移的地方或者逐个读取long的地方，还没测过哪个严重些，如果实后者，那必须减少逐个读取的个数，也就是必须增加复制块数。
感觉是这个模糊查询效率不高，从文件读取出的数据并不多，就这么慢了...而且多线程的情况下并发吞度量并没有明显提高。也许是本人程序水平，代码不多，希望有高手能指点一下
代码放这里了：http://download.csdn.net/source/3339688