欢迎光临
微商代理新产品网

Shingling算法在网页去重中的运用

昨天无痕和大家介绍了通用去重算法框架,今天就具体来介绍网页去重的一种算法-Shingling算法在网页去重中的运用,希望通过这样的介绍,大家可以对网页去重有更深的了解。

Shingling算法二大步骤:

1、从文档中抽取能代表文档内容的特征

2、通过二个文档对应特征集合的重叠程度来判断是否近似重复。

Shingling算法将文档转换成特征集合示意图

Shingling算法实例:

假想有一个固定大小的移动窗口从第一个单字开始依次移动,每次向后移动一个单字,直到文档结尾。

在同时对汉字串做哈希计算,随着窗口的移动,会出现一系列的shingles值,这样就构成了文档对应的特征集合。

后面再进行jaccard相似性计算,计算二个集合相似部分所占总元素个数的比例。

算法缺点:

计算效率不高,当网页数量比较大时,运行时间会比较长,并不实用。

算法改进:

Shingling算法改进示意图

前面的计算过程和原始的Shingling算法是一致的,构成一个文档转换成shingles的特征集合,但是为了将特征集合映射成固定大小,会引入m个不同的哈希函数,形成哈希函数簇,对于某个特定的哈希函数F,对于每个shingles都会计算出一个哈希数值,取其中最小的值作为代表,这样m个哈希函数就会获得m个哈希数值,文档特征也就转换为固定大小m,最后再进行相似度的计算,得出相似重复页面。

Shingling算法的大概内容就是上面的介绍,希望通过这样总结性的整理归纳,能够让大家可以简单的就可以明白了解。

赞(0)
未经允许不得转载:首页 » Shingling算法在网页去重中的运用
分享到: 更多 (0)

推荐微商代理新产品 ,我们是认真的!