网页查重技术起源于复制检测技术,即判断一个文件内容是否存在抄袭、复制另外一个或多个文件的技术。
1993年Arizona大学的Manber(Google现副总裁、工程师)推出了一个sif工具,寻找相似文件。1995年Stanford大学的Brin(Sergey Brin,Google创始人之一)和Garcia-Molina等人在“数字图书观”工程中首次提出文本复制检测机制COPS(Copy Protection System)系统与相应算法[Sergey Brin et al 1995].之后这种检测重复技术被应用到搜索引擎中,基本的核心技术既比较相似。
网页和简单的文档不同,网页的特殊属性具有内容和格式等标记,因此在内容和格式上的相同相似构成了4种网页相似的类型。
1、两个页面内容格式完全相同。
2、两个页面内容相同,但格式不同。
3、两个页面部分内容相同并且格式相同。
4、两个页面部分重要相同但格式不同。
实现方法:
网页查重,首先将网页整理成为一个具有标题和正文的文档,来方便查重。所以网页查重又叫“文档查重”。“文档查重”一般被分为三个步骤,
一、特征抽取。
二、相似度计算和评价。
三、消重。
1.特征抽取
我们在判断相似物的时候,一般是才能用不变的特征进行对比,文件查重第一步也是进行特征抽取。也就是将文档内容分解,由若干组成文档的特征集合表示,这一步是为了方面后面的特征比较计算相似度。
特征抽取有很多方法,我们这里主要说两种比较经典的算法,“I-Match算法”、“Shingle算法”。
“I-Match算法”是不依赖于完全的信息分析,而是使用数据集合的统计特征来抽取文档的主要特征,将非主要特征抛弃。
“Shingle算法”通过抽取多个特征词汇,比较两个特征集合的相似程度实现文档查重。
2.相似度计算和评价
特征抽取完毕后,就需要进行特征对比,因网页查重第二步就是相似度计算和评价。
I-Match算法的特征只有一个,当输入一篇文档,根据词汇的IDF值(逆文本频率指数,Inverse document frequency缩写为IDF)过滤出一些关键特征,即一篇文章中特别高和特别低频的词汇往往不能反应这篇文章的本质。因此通过文档中去掉高频和低频词汇,并且计算出这篇文档的唯一的Hash值(Hash简单的说就是把数据值映射为地址。把数据值作为输入,经计算后即可得到地址值。),那些Hash值相同的文档就是重复的。
Shingle算法是抽取多个特征进行比较,所以处理起来比较复杂一些,比较的方法是完全一致的Shingle个数。然后除以两个文档的Shingle总数减去一致的Shingle个数,这种方法计算出的数值为“Jaccard 系数”,它可以判断集合的相似度。Jaccard 系数的计算方法集合的交集除以集合的并集。
3.消重
对于删除重复内容,搜索引擎考虑到众多收录因素,所以使用了最简单的最实用的方法。先被爬虫抓取的页面同时很大程度也保证了优先保留原创网页。
网页查重工作是系统中不可缺少的,删除了重复的页面,所以搜索引擎的其他环节也会减少很多不必要的麻烦,节省了索引存储空间、减少了查询成本、提高了PageRank计算效率。方便了搜索引擎用户。