我想对1千多万条数据记录中相似纪录进行检测，并不是仅仅针对完全匹配的冗余数据。主要针对一些由于拼写错误，格式等造成的近似纪录检测.对于确认近似记录主要是用到了一些相似度算法，比如levenshtein, smith-waterman 等等，这类算法可以计算出两个字符串的相似度。 比如John Smith, 与 Jhno Simht, 在某些算法下可以达到一些相似度。然后我根据相似度进行对所有的纪录遍历匹配。问题就出在对整个数据库的遍历上了，如果我每条记录都同所有的纪录比较一次，那就得花费 O(n^2).现在我知道有一个算法可以解决这个问题，叫做“邻近记录排序， sorted neighborhood method"主要思想是，首先给每条记录根据它的attribute建立一个索引(key), 然后根据索引排序一次。这样有相似索引的记录就都组成到一组了。然后建立一个长度为w的滑动窗口，从第一条记录开始向下滑动，每次只比较窗口内的纪录，这样整个遍历一次只需要O(nw),远远小于o(n^2).不知道有谁做过类似的程序？如何用java实现？
do{
为记录集TS中的记录选择该趟排序需要的排序关
键字；
根据排序关键字对TS中的记录进行排序；
滑动窗口W从TS的第一个记录开始滑动；
while(W没有滑动到TS的尾部)
do{
初始化执行对比的次数n=0；
while(执行的对比次数n<|W|)
do{
新进入滑动窗口的记录与第n+1个进入窗口的记录进行重复记录比较；
if(比较的记录为相似重复记录)
{
把相似重复记录的记录号添加到相似记录存储表；
}
执行n+1；
}
向下滑动窗口；
}
对相似记录存储表中的记录采用直观方法进行比较，记录相似重复记录聚类；
}
上面是这篇文章里提到的对这种窗口算法的改进。各位能否提示以下应该怎样用java实现呢？
{
for(int j=0;j<w;j++)
{
选择一个相似度算法，e.g.,smith-waterman, N-gram,etc；
比较窗口里的记录,利用最底层记录比较前w-1个记录；
匹配成功的,将序号导入一个set. ；
set是一个union, 对于已经重复的序号略过；
} }
基本上现在很多数据清洗系统都要用到这个方法。另一个方法叫Blocking methods这两个方法都是为了减少匹配次数进而降低cost而设计的。对于SNM，
创建索引是第一步，消费O(n)
然后根据索引sort一次 ，消费 O(nlogn)
然后创建窗口 遍历匹配记录消费O(nw)