前台相似文档去重算法
1、相似度：
任意两个文档A和B，相似度指的是两者相同特征数目占两者特征数目总和的比例。本算法中，文档特征由一个128位的二进制串代表，实现时使用两个64位的无符号数表示。
这样任意两个文档A和B，两者相同特征数目为A∩B中bit位为1的数目；两者特征数目总和为A∪B中bit位为1的数目。如果相似度大于某个设定的阈值（如：0.5），则可以判定两个文档重复。
对于有i个文档的集合K={k1,k2,……,k i}，计算它们之间的相似度的算法复杂度为i2，为减少计算代价，可以考虑采用滑动窗口机制，如果窗口大小为n。则：
对于文档集合K={k1,k2,……,k i}，仅保证连续n（n<<j）个文档中不存在重复的文档。
2、算法概要:
unsigned int getClusterID_Window(unsigned int64 value[2] )
{// 窗口去重，返回每个文档指纹对应的类型编号，编号相同的文档为重复文档
/
/1、 FINGER_WINDOWS_LENGHT 滑动窗口大小
// 2、idfingerWindows 长度为FINGER_WINDOWS_LENGHT的数组，保存每个类型的特征（两个64位无符号整数），及相应的类型标号c_id。
//3、currentID 如果输入文档是新类型，应当赋予的类型编号
unsigned int c_id ;
unsigned int64tt[2] ;
unsigned int i = 0;
while( ( i < FINGER_WINDOWS_LENGHT ) && ( i< currentID ))
{
tt[0]  = (idfingerWindows[i].finger.value[0]) & (value[0]);
tt[1]  = (idfingerWindows[i].finger.value[1]) & (value[1]);
__uint8and_value = get1Count((unsigned char*)tt) ;  //计算文档交集中1的个数
tt[0] = idfingerWindows[i].finger.value[0] | it.value[0];
tt[1] = idfingerWindows[i].finger.value[1] | it.value[1];
__uint8or_value = get1Count((unsigned char*)tt) ; //计算文档并集中1的个数
if( ((float)and_value) /(float)or_value > SIM_THRESHOLD_VALUE  )
{// SIM_THRESHOLD_VALUE 相似度阈值
return idfingerWindows[i].c_id; //与某个已有类型重复，返回已有类型的编号}
i++; //遍历整个idfingerWindows数组
}
//未发现重复类型，则到新文档在idfingerWindows中的位置，并替换相应的值
unsigned pos = currentID % FINGER_WINDOWS_LENGHT ;
idfingerWindows[pos].c_id = currentID ;  //给定新类型编号
idfingerWindows[pos].finger = value ;  //新类型特征
c_id = currentID ;
currentID++ ;  //下一个不重复类型的编号
return c_id ;
}
另外，计算64位无符号整数或者128为2进制串中1的个数的高速算法：
//算法简述：对每一个byte的1的个数可直接查表，然后相加就可以了。返回无符号的8位整数
const unsigned char numbits_lookup_table[256] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,
3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,
3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,
3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,
6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,
4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,
4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,
6, 7, 6, 7, 7, 8
字段字符串去重复}; //表示ascii  0x0  -  0xff 中包括的个数
__int8get1Count(  unsigned int64a )
{ unsigned char  *p=(unsigned char*)(&a);
return numbits_lookup_table[p[0]]+numbits_lookup_table[p[1]]+numbits_lookup_table[p[2]] +numbits_lookup_table[p[3]]+ numbits_lookup_table[p[4]]+numbits_lookup_table[p[5]]
+numbits_lookup_table[p[6]]+numbits_lookup_table[p[7]] ;
}
__int8get1Count(  unsigned char p[16] )
{
return numbits_lookup_table[p[0]] +numbits_lookup_table[p[1]]
+numbits_lookup_table[p[2]] +numbits_lookup_table[p[3]] + numbits_lookup_table[p[4]]  +numbits_lookup_table[p[5]] +numbits_lookup_table[p[6]] +numbits_lookup_table[p[7]] +numbits_lookup_table[p[8]] +numbits_lookup_table[p[9]]+numbits_lookup_table[p[10]] +numbits_lookup_table[p[11]]+numbits_lookup_table[p[12]]+numbits_lookup_table[p[13]] +numbits_lookup_table[p[14]]+numbits_lookup_table[p[15]] ;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。