面向网页去看的特征提取与重复模式发现

摘要

互联网的快速发展给人们带来了新的获取信息和交流的方式。随着网站和网页数目的不断增加,为了用户能方便的访问它们,搜索引擎应运而生。但由于互联网上存在大量的因转载或抄袭形成的重复网页,这些网页被搜索引擎重复的存储和检索,造成存储空间的浪费和检索效率的降低,同时也带来了较差的用户体验。因此网页去重是搜索引擎中比较重要的一个环节。
　　 本文针对网页去重着重研究以下两个问题:第一个问题是网页特征提取。网页特征提取的前提是网页正文提取,但由于广告等噪声的存在,导致目前的正文提取算法均不能完全准确的提取出网页正文内容,这对后续的网页去重造成了较大的影响。如何在存在少许噪声的正文中提取纯净的网页特征在很大程度上决定了网页去重的准确率。本文提出了基于层次筛选的特征提取算法,充分考虑了段落、句子与关键词的联系,逐层筛选网页信息得到特征词、词性对集合,达到将网页本身结构和内部信息权重结合的目的,使提取出的特征不仅能均匀覆盖网页,还具有一定的抗噪性。
　　 第二个问题是网页特征重复模式发现。目前的重复模式发现算法主要分为两种:基于集合的实现和基于特征串的实现。基于集合的实现比较注重特征集合中特征项的权重,但忽视了特征项的顺序,加上HaSh值冲突问题带来的误判,此实现并不适合用于网页去重;基于特征串的实现虽然考虑了特征项的顺序,但采用最长公共子串衡量网页重复度则过于严格,检测不出非连续重复的网页。为了解决上述问题,本文提出了基于改进最长公共子序列的重复模式发现算法。将特征词、词性对集合以句子为单位计算最长公共子序列,既降低了维度、保证了句子的完整性,又能改善Hash值冲突问题。为了提高计算和查找的效率,本算法改进了最长公共子序列算法的经典实现和倒排表组织方式,并将其应用于网页重复模式发现。
　　 最后,本文进行了相关实验验证工作,结果表明改进后的算法在召回率和准确率上都优于目前的常用算法。