搜索引擎原理之:网页去重算法

　　搜索引擎原理之:网页去重算法

　　去重算法总结：

　　一、基础：

　　1、去重算法原理：抽取网页特征、计算相似度、消重；

　　图片来如网络

　　2、4大算法：Shinglin算法、I-Match算法、SimHash算法、SpotSig算法；

　　3、网页去重好处：节省存储空间、提升计算效率；

　　二、4大算法介绍：

　　--------------------------

　　SimHash算法： ----核心算法

　　图片来如网络

　　特征抽取：第1步，文档分词，清洗停止词；提取n个特征关键词；

　　第2步，给每个特征关键词，加权重，形成特征对(关键词，权重)。注：权重可以是IDF（逆文本频率）权值，也可以是词频+位置。

　　第3步，对关键词及权重，进行hash降维01组成的6位（一般是64位或128位）签名，形成hash值。（如：101110）

　　第4步，然后向量加权，对于每一个6位的签名的每一位，如果是1，hash和权重正相乘，如果为0，则hash和权重负相乘，至此就能得到每个特征值的向量。

　　第5步，合并所有的特征向量相加，得到一个最终的向量，然后降维，对于最终的向量的每一位如果大于0则为1，否则为0，这样就能得到最终的simhash的指纹签名

　　第6步，降维得指纹信息，如：110001

　　

　　注：3-6步，SEO可一带而过；

　　计算相似度：用海明距离，与所属分组内文档的指纹，进行相似计算。

　　如：文档A和文档B

　　A指纹 = 110001;

　　B指纹 = 101010;

　　计算A和B的海明距离，如果小于等于3,即是近似重复文档。

　　优 点：效率高，目前最优秀的去重算法，Google采集此算法。

　　--------------------------

　　Shingling算法：

　　特征抽取：第1步，将文档按顺序的，划分为含X个字的单词片段，相似于叠瓦片。

　　如：文档“新浪发布财报微博用户破亿”，将其划为4个字的单词片段（瓦片）：“新浪发布”、“浪发布财”、“发布财报”.....，依次类推，一直到文档结束。

　　第2步，每个单词片段（瓦片），对应的哈希值为一个Shingle，将文档所有Shingle，作为特征集合。

　　计算相似度：计算2个特征集合中，其中重叠部份比例。

　　特 点：效率低，并不实用。

　　--------------------------

　　I-Match算法：

　　特征抽取：第1步，计算全局特征词典（可能是某类行业的特征词典），即：根据语料进行统计，对语料库所有单词，按单词的IDF（逆文本频率）值由高到低进行排序。删除IDF得分过高，及得分过低的单词。保留中间部份单词，作为特征词典。（很大可能按行业，或按某类来做语料库）

　　第2步，将文档分词，用全部分词，与全局特征词典对比，将全局特征词典没有的词，过滤掉。

　　第3步，以文档中剩下的词为特征，对其进行哈希计算，得到唯一哈希数值，以此为网页信息指纹。

　　

　　计算相似度：将网页指纹信息，与所属分类的文档集合，进行对比，两者相同，为近似重复网页。

　　优 点：效率高

　　缺 点：1、对文档单词顺序不敏感，比如：2个文档包含相同单词，但单词顺序，或段落变换，被认定为重复内容。

　　2、短文本容易误判，比如：2个不同的短文档，经过特征词典过滤后，只保留很少单词为特征，容易重复误判，此问题在短文本中非常严重。

　　3、对增删单词敏感，比如：在文档A中，增加某单词，形成文档B，经过全局特征词典过滤后。如果增加的单词，在特征词典中，那么文档B比文档A多一个新增加的单词，2文档指纹不同；如果增加的单词，不在特征词典中，那么文档A和文档B指纹相同；

　　--------------------------

　　SpotSig算法： ---主要用于新闻内容

　　特征抽取：选文档中X个停止词，作为锚点。从锚点开始，向后顺序扫描，取固定X个单词，以此为固定特征部份。取出所有的特征集合.

　　如：文档“你知道吗新浪发布的财报说他们用户破亿”，取“你、吗、的、说”停止词为锚点。取锚点后面2个字为特征：“你:知:道”、“吗:新:浪”、“的:财:报”、“说:用:户”(没有作为锚点的停止词过滤掉).....，依次类推，一直到文档结束。

　　计算相似度：加快计算方法 1，文档分组，2，倒排索引，

　　特 点：1、2个文档长度相差太大，相似度低；2、根据特征集合的大小对文档集合进行分组；

　　三、核心点：

　　1、文档*敏*感*词*的对比，计算相似度；

　　2、对文档聚类、分组，仅对同类文档计算相似度；

　　3、网页消重原则:

　　a、版权角度考虑，保留原创，过滤转载或复制网页；

　　b、网页寿命角度考虑，保留大型网站网页，过滤网站质量不高的网页；

　　c、容易实现的角度，首先保留被爬虫抓取的网页，丢弃相同的或相似网页；

　　d、简单实用方法，保留先被爬虫抓取的网页，很大程度保证优先保留原创网页；（广泛使用）

　　4、任何页面，都不可能仅存留1个页面；