论文部分内容阅读
引言：本文提出了一种基于关键词提取的网页去重算法。该算法考虑了文本的内容信息，其基本思路是：首先解析网页，提取每篇网页文档的标题关键词，以基于窗口搜索的方式寻找正文中与标题关键词相关度高的其它关键词以构成该项篇网页文档的关键词集，并根据关键词集中的所有关键词为网页文档建立倒排表，文档去重就是计算两篇文档的关键词重叠率，如果重叠率高于某个阂值时，认为两篇文档内容重叠。该算法的优点是考虑了正文中与主题相关度高的非高频词，避免了仅使用统计值依赖高频词去重的缺陷。
一、算法
目前对于网页去重的研究方法主要有基于聚类的方法、排除相同URL方法、基于特征码的方法等。
（l）基于聚类的方法是基于网页的文本内容进行的，它以6763个汉字作为向量的基，文本的汉字字频就构成了代表网页的向量。通过计算向量的夹角决定是否是相同网页。这种方法的优点是简单，容易实现。缺点就是对大规模网页聚类的类别数目大，难以确定，计算量大；只利用字频信息，没有利用文本的结构信息；实时性差，对于新网页需要重新聚类以决定是否重复。因此，在实际应用中难以适用。
（2）排除相同URL方法是各种元搜索引擎去重的主要方法。这种方法主要分析来自不同搜索引擎的网页URL，相同的URL认为是相同的网页，然后去重。这种方法的优点也是简单，容易实现，可去除一部分相同的网页。其缺点是只利用了URL信息未利用网页的文本内容，不能对转载造成的重复网页去除。
（3）基于特征码的方法是利用标点符号多数出现在网页文本中的特点，以句号两边各五个汉字作为特征码来唯一地标识网页。因为特征码的精确匹配可以与先进的检索系统联系起来，去重效率较高。
二、关键词提取算法
本文提出的网页去重算法是基于关键词提取的去重算法，该算法考虑了文本的内容信息，其基本思路是：首先解析网页，提取每篇网页文档的标题关键词，以基于窗口搜索的方式寻找正文中与标题关键词相关度高的其它关键词，文档去重就是计算两篇文档的关键词重叠率，如果重叠率高于某个阑值时，认为两篇文档内容重叠。
概括地说，基于关键词比较的网页去重算法分三步实现：解析网页，从每个网页中提取标题和正文内容。以标题关键词为种子点，以基于窗口搜索的方式查找正文中的关键词。计算两篇网页文档的关键词重叠率以确认两网页是否重复。
（l）网页解析。W亡b网页与普通文本相似，但其有自身的特点，这为网页分析提供了一些线索。
（2）搜索正文关键词。对解析得出的标题和正文，首先经过分词、去停用词之后形成一系列的词串，其中标题分词后形成的词串我们称为标题关键词集，正文分完词后形成的词串我们称为正文词集。采用基于窗口搜索的方式寻找正文词集中与标题关键词集相关度高的词（称为正文关键词）。基于窗口搜索的方式搜索正文关键的思路是：正文中如果几个词经常与标题关键词在同一窗口中共同出现，则认为它们与标题关键词在表达该文档上相关度很高，即它们是正文关键词。将所有的标题关键词和正文关键词统称为该网页文档的关键词。
（3）计算关键词重叠率。文档去重的过程就是比对两篇文档的所有关键词，为了避免文档间的两两对比，本文通过建立关键词倒排表，文档中的每一个关键词都在关键词倒排表中查询出现的文档号，并求交集。
三、实验结果
实验所用的数据是四大门户网站（sina，sohu，163，263）的娱乐体育新闻，为了验证上述算法，本文分别采用文献叫中算法（以下称Forman算法）、文献中的算法（以下称lyer算法）和本文算法从去重效果和速度两个方面做了比较。
评价去重效果时有两种情况：一种将不相同的两篇文档判定为相同文档，本文称为混淆错误 CE（Confused Error），另一种是将相同的两篇文档判定为不相同，本文将这种判定错误称为排斥错误 EE（Exclusive Error）。
混淆错误率计算公式：
四、实验结果分析
Forman算法是基于文档内容进行对比的方法，当文档中相同的文档块经hash映射后（这里采用MDS）相同的个数超过一定范围则认为文档相似，否则不相似。实验中如果两篇文档分块后做hash，如果80%的哈希值相同，则认为这两篇文档是重复文档。Iyer算法是基于关键词提取的用于论文剽窃检测的算法，同样认为树结构中有80%的哈希值相同，则认为两篇文档是重复文档。
从表2中可以看出，Forman算法的混淆错误率很低，因为该算法对文档相似的检验很严格，排斥错误率高是由于只根据语句判定相似，而没有考虑文本所表达的含义。Iyer算法混淆错误率较低，排斥错误率高的原因是当树的上层剪枝错误时去重算法失效。本文算法混淆错误率比Forman算法和Iyer算法高的原因是还存在不同的文档判定为相同文档的可能性，但由于本文算法在提取关键词充分考虑了文档正文所表达的含义，排斥错误率低。从综合评价指标F来看本文算法比其它两种算法效果更好。
为了对上述方法进行运行速度的比较，本文建立了大小为124个文档，1191个文档和10287个文档三个数据集。表3为去重判定时间比较。
从表3中可以看出，Forman算法运行所需时间最多，因为所有的文档都要进行分段后计算哈希值，计算后还要进行哈希值比较，因此耗时多。Iyer算法虽然对文档中每句话都抽取关键词，但是由于组成树状结构，比对过程中可以剪枝，因此速度稍快。本文算法以标题中的词为种子点只考虑与标题词相关的词生成的词汇集，去掉大量与主题无关的信息，因此速度较快。从实验结果可看出，在去重效果和运行速度上本文算法都具有一定的优势。
参考文献
[1]张海军，潘伟民，木妮娜，栾静. 一种自定义顺序的字符串排序算法[J]. 小型微型计算机系统.2012（09）.
（作者單位：河南农业职业学院）
一、算法
目前对于网页去重的研究方法主要有基于聚类的方法、排除相同URL方法、基于特征码的方法等。
（l）基于聚类的方法是基于网页的文本内容进行的，它以6763个汉字作为向量的基，文本的汉字字频就构成了代表网页的向量。通过计算向量的夹角决定是否是相同网页。这种方法的优点是简单，容易实现。缺点就是对大规模网页聚类的类别数目大，难以确定，计算量大；只利用字频信息，没有利用文本的结构信息；实时性差，对于新网页需要重新聚类以决定是否重复。因此，在实际应用中难以适用。
（2）排除相同URL方法是各种元搜索引擎去重的主要方法。这种方法主要分析来自不同搜索引擎的网页URL，相同的URL认为是相同的网页，然后去重。这种方法的优点也是简单，容易实现，可去除一部分相同的网页。其缺点是只利用了URL信息未利用网页的文本内容，不能对转载造成的重复网页去除。
（3）基于特征码的方法是利用标点符号多数出现在网页文本中的特点，以句号两边各五个汉字作为特征码来唯一地标识网页。因为特征码的精确匹配可以与先进的检索系统联系起来，去重效率较高。
二、关键词提取算法
本文提出的网页去重算法是基于关键词提取的去重算法，该算法考虑了文本的内容信息，其基本思路是：首先解析网页，提取每篇网页文档的标题关键词，以基于窗口搜索的方式寻找正文中与标题关键词相关度高的其它关键词，文档去重就是计算两篇文档的关键词重叠率，如果重叠率高于某个阑值时，认为两篇文档内容重叠。
概括地说，基于关键词比较的网页去重算法分三步实现：解析网页，从每个网页中提取标题和正文内容。以标题关键词为种子点，以基于窗口搜索的方式查找正文中的关键词。计算两篇网页文档的关键词重叠率以确认两网页是否重复。
（l）网页解析。W亡b网页与普通文本相似，但其有自身的特点，这为网页分析提供了一些线索。
（2）搜索正文关键词。对解析得出的标题和正文，首先经过分词、去停用词之后形成一系列的词串，其中标题分词后形成的词串我们称为标题关键词集，正文分完词后形成的词串我们称为正文词集。采用基于窗口搜索的方式寻找正文词集中与标题关键词集相关度高的词（称为正文关键词）。基于窗口搜索的方式搜索正文关键的思路是：正文中如果几个词经常与标题关键词在同一窗口中共同出现，则认为它们与标题关键词在表达该文档上相关度很高，即它们是正文关键词。将所有的标题关键词和正文关键词统称为该网页文档的关键词。
（3）计算关键词重叠率。文档去重的过程就是比对两篇文档的所有关键词，为了避免文档间的两两对比，本文通过建立关键词倒排表，文档中的每一个关键词都在关键词倒排表中查询出现的文档号，并求交集。
三、实验结果
实验所用的数据是四大门户网站（sina，sohu，163，263）的娱乐体育新闻，为了验证上述算法，本文分别采用文献叫中算法（以下称Forman算法）、文献中的算法（以下称lyer算法）和本文算法从去重效果和速度两个方面做了比较。
评价去重效果时有两种情况：一种将不相同的两篇文档判定为相同文档，本文称为混淆错误 CE（Confused Error），另一种是将相同的两篇文档判定为不相同，本文将这种判定错误称为排斥错误 EE（Exclusive Error）。
混淆错误率计算公式：
四、实验结果分析
Forman算法是基于文档内容进行对比的方法，当文档中相同的文档块经hash映射后（这里采用MDS）相同的个数超过一定范围则认为文档相似，否则不相似。实验中如果两篇文档分块后做hash，如果80%的哈希值相同，则认为这两篇文档是重复文档。Iyer算法是基于关键词提取的用于论文剽窃检测的算法，同样认为树结构中有80%的哈希值相同，则认为两篇文档是重复文档。
从表2中可以看出，Forman算法的混淆错误率很低，因为该算法对文档相似的检验很严格，排斥错误率高是由于只根据语句判定相似，而没有考虑文本所表达的含义。Iyer算法混淆错误率较低，排斥错误率高的原因是当树的上层剪枝错误时去重算法失效。本文算法混淆错误率比Forman算法和Iyer算法高的原因是还存在不同的文档判定为相同文档的可能性，但由于本文算法在提取关键词充分考虑了文档正文所表达的含义，排斥错误率低。从综合评价指标F来看本文算法比其它两种算法效果更好。
为了对上述方法进行运行速度的比较，本文建立了大小为124个文档，1191个文档和10287个文档三个数据集。表3为去重判定时间比较。
从表3中可以看出，Forman算法运行所需时间最多，因为所有的文档都要进行分段后计算哈希值，计算后还要进行哈希值比较，因此耗时多。Iyer算法虽然对文档中每句话都抽取关键词，但是由于组成树状结构，比对过程中可以剪枝，因此速度稍快。本文算法以标题中的词为种子点只考虑与标题词相关的词生成的词汇集，去掉大量与主题无关的信息，因此速度较快。从实验结果可看出，在去重效果和运行速度上本文算法都具有一定的优势。
参考文献
[1]张海军，潘伟民，木妮娜，栾静. 一种自定义顺序的字符串排序算法[J]. 小型微型计算机系统.2012（09）.
（作者單位：河南农业职业学院）