基于并行编程模式的相似网页去重系统

摘要

本发明提出的基于并行编程模式的相似网页去重系统，包括网页内容预处理模块、网页特征向量提取模块、网页特征指纹计算模块、网页指纹在线去重模块、网页指纹分布式批处理去重模块、基于特定分布式计算平台。该系统能够完成对网络爬虫爬行获得的网页进行文本内容编码的统一转换、文档结构的规范化、舍弃网页噪声内容和分析识别网页的主题内容、连续文本内容的词项切分等环节、形成能够代表网页的特征向量。针对该向量可以使用相关的算法得到代表网页特征的网页指纹。本发明设计提出的系统在互联网海量数据量的情况下，准确、快速地探测由于网站镜像和网络文档转载等因素造成的网页内容完全重复或近似重复，并完成相应的去重工作，从无提高搜索引擎的存储效率，给搜索引擎带来更好的用户体验。

说明书

技术领域

本发明属于计算机互联网信息检索和分析技术，具体涉及一种基于并行编程模式的相似网页去重系统，该系统是对现有的相似网页去重系统的改进，结合现有的网页结构与主题内容分析技术，提取网页的特征向量，使用基于并行模式的网页指纹去重算法，在分布式系统环境中完成相似网页的去重功能，提高搜索引擎索引模块和检索模块的效率。

背景技术

随着近年来互联网技术和规模的空前发展，越来越多的传统资源正在向Internet上迁移，搜索引擎因其强大而不失方便的检索功能成为当今用户进行信息检索的主要工具。但是由于互联网规模庞大和地域访问限制等特征，较多网站使用服务器镜像来加速访问，此外在互联网环境下进行信息转载非常容易，致使大量的重复网页充斥着互联网，搜索引擎的返回结果中往往包含了许多重复的网页。统计结果表明，近似镜像网页数占总网页数的比例高到全部页面的29％，而完全相同的页面大约占全部页面的22％，这些网页要么内容完全相同，要么只在细微部分不同，比如广告信息、页面布局等其他无关信息。相似网页可以分为以下几个类别：

(1)网页内容和格式上没有任何区别；

(2)网页内容相同，但是格式不同；

(3)网页有部分重要的内容相同，而且格式相同；

(4)网页有部分重要的内容相同，但是格式不同；

而这些网页最终会被搜索引擎反复的收录。而相似网页探测就是利用某些算法准确、快速的发现这些重复网页，这对于提高搜索引擎的性能和服务质量有诸多好处：去除大量重复网页不仅可以给搜索引擎的爬行程序减轻很大的负担，在给网站服务器减轻压力的同时还可以减少网络通信量；去除大量重复网页，也就减少了大量的重复索引，从而大大提高了检索质量和用户体验。

对于相似文档或者是网页文档相似内容的去重问题在国内外信息提取领域已经得到了一系列的研究，其相关的技术理论基础是对于两篇文本文档使用MD5或者是Rabin指纹算法等文本摘要算法计算文档的信息指纹(通常指纹大小固定，且为2的整数次幂大小，如64bit和128bit)，然后比较指纹，如果相同则为内容相同。目前比较流行的网页去重方法有基于向量空间模型(Vector Space Model，VSM)的网页去重方法，它通常以网页中的字或词为统计对象，即以所有的字或词来组成一个多维向量的各个维，然后统计各个词项出现的频率，并以各个词项的频率作为相应维的值，该向量成为网页的特征向量，或者以文档中的全部词来组成特征向量的各个维。相似网页的特征向量之间夹角的余弦值接近于1。可以设定某个阈值，如果余弦值超过该值，判定两个特征向量代表的网页相似。该方法思想简单，实现容易。缺点是对于网页的相似，需要进行所有的两两判定，因此只利于小规模数据上的运用，对于大规模的相似网页探测则缺乏灵活，速度太慢，而且特征向量也可能需要大量存储空间。第二种方法是基于网页关键词的方法，该方法首先通过对网页的解析，提取出网页标题的关键词，然后在网页正文中获取和标题关键词相关度高的其他关键词形成该网页的关键词集，并以倒排表的结构进行组织，当需要对一个网页判定是否存在重复网页时，可以在倒排表中查询包含该网页关键词集中的全部或部分关键词的网页，然后计算两个网页的关键词集的重叠率作为网页的相似度。然后通过阈值判断两个网页是否相似。该方法也有不足之处，如有关相同主题的不同网页，可能它们的关键词集本身就具有很大的重叠率，但网页内容并不重复，而对于这类网页判断可能会产生大量的误判，即非相似的网页被认为相似，因此准确度不高。第三种方法是采用Simhash算法，Simhash算法指采用特征向量代表文本，对于特征向量的每个成员计算指纹，然后基于权重进行叠加，得到文本的指纹，基于这种做法可以使得内容接近的文本，其指纹值也比较接近。

发明内容

本发明的目的在于提供一种基于并行编程模式的相似网页去重系统，该系统具有较高的准确度。

本发明提供的基于并行编程模式的相似网页去重系统，其特征在于：该系统包括网页内容预处理模块、网页特征向量提取模块、网页特征指纹计算模块、网页指纹在线去重模块和网页指纹分布式批处理去重模块；

网页内容预处理模块用于处理原始的HTML网页文本数据，包括对网页文本内容和语法结构的规范化，处理后的结果仍然为HTML网页文本数据，并提供给网页特征向量提取模块；

网页特征向量提取模块对预处理后的网页文本数据进行网页特征向量提取操作；它首先识别单张网页中的网页语义块，对识别出来的网页语义块中的文本内容进行分词，提取网页主题内容，得到网页特征向量，并发送给网页特征指纹计算模块；

网页特征指纹计算模块根据接收到的网页特征向量，计算代表单个网页特征的网页指纹，根据不同的工作模式，选择发送给网页指纹在线去重模块或网页指纹分布式批处理去重模块；

网页指纹在线去重模块在系统处于在线处理模式时，处理判断单个网页指纹是否在已有的原始海量网页指纹中存在近似重复的指纹，如果存在完全重复或者近似重复的网页指纹，即可从网页库中删除该网页的内容；

网页指纹分布式批处理去重模块在系统处于分布式批处理模式下，对原始海量网页指纹和输入的批量指纹进行比对，识别出近似重复的网页指纹对，如果存在完全重复或者近似重复的网页指纹，即从网页库中删除该网页的内容。

上述结构的系统对爬行器获取的大量网页文本数据进行编码转换和网页结构规范化，然后对基于对象文档模型(Document Object Model，DOM)的网页结构进行语义分块，对于各网页块的文本内容进行分词，识别提取网页的主题内容和相关元数据信息，形成代表网页的特征向量集，针对向量集中的每一部分计算指纹，将各部分指纹叠加后得到网页的最终指纹进行存储，在分布式批处理模式和在线模式下进行网页去重。

具体而言，本发明具有如下优点：

(1)统一规范的网页结构化信息存储：网页分析处理后，相关网页的内容将按照统一的格式存放，包括标题、时间戳、主题内容、关键词、锚文本等内容。

(2)网页信息处理的鲁棒性：互联网上的网页常常存在不符合规范的内容，例如不闭合的标签、错误的标签等，本发明提供的系统使用相关开源软件处理网页文档，清除错误，使得网页的内容可以被标准的DOM解析器处理。

(3)相似网页判断较高的准确率：本发明使用特征向量指纹根据权重进行叠加的算法，能够避免单纯使用关键词重合率判断网页相似程度带来的判断偏差。

(4)海量数据规模下较高的效率：本发明使用的指纹算法具有较高的效率，在指纹比对方面牺牲空间换取时间做了优化，同时使用分布式计算平台并行处理，提高了效率，适合互联网海量数据的特定环境。

附图说明

图1是本发明系统的结构示意图。

图2是本发明网页预处理模块100和网页特征向量提取模块200示意图。

图3是本发明系统HTML标签分类示意图。

图4是本发明系统网页分块算法的示意图。

图5是本发明网页特征指纹计算流程示意图。

图6是本发明在线模式相似网页去重流程示意图。

图7是本发明64bit指纹置换示意图。

图8是本发明分布式批处理模式相似网页去重流程示意图。

具体实施方式

下面结合附图和实例对本发明作进一步详细的说明。

通常而言，相似网页探测去重包括如下几个步骤：(1)首先提取网页的某些特征；(2)然后对该特征进行编码或量化，以便进行快速的计算；(3)接着以编码后的特征值计算网页之间的相似度以判定网页是否相似；(4)最后，如需要进行大规模的计算，则必须基于较高性能的计算平台采用某种高性能算法以实现大规模计算时的高速度要求。

如图1所示，本发明提供的基于并行编程模式的相似网页去重系统包括网页内容预处理模块100、网页特征向量提取模块200、网页特征指纹计算模块300、网页指纹在线去重模块400和网页指纹分布式批处理去重模块500。

网页内容预处理模块100用于处理原始的HTML网页文本数据，包括对网页文本内容和语法结构的规范化，处理后的结果仍然为HTML网页文本数据。目前针对XML数据的DOM模型是公认的国际标准，针对DOM模型有不同的DOM语法树解析器，规范化处理后的HTML网页文本数据本质上即为XML格式，即可被不同的DOM语法树解析器进行解析。

网页特征向量提取模块200对模块100处理完后的网页数据进行网页特征向量提取操作。它首先识别单张网页中的网页语义块，对识别出来的网页语义块中的文本内容进行分词，提取网页主题内容，得到网页特征向量，并发送给网页特征指纹计算模块300。

网页特征指纹计算模块300根据接受到的网页特征向量，计算代表单个网页特征的网页指纹，根据不同的工作模式，选择发送给网页指纹在线去重模块400或网页指纹分布式批处理去重模块500。

网页指纹在线去重模块400在系统处于在线处理模式时，处理判断单个网页指纹是否在已有的原始海量网页指纹中存在近似重复的指纹人，如果存在完全重复或者近似重复的网页指纹，即可从网页库中删除该网页的内容。完全重复通常出现在网站服务器进行镜像转载的情况下，近似重复指两张网页的主题内容一致，但在非主题内容包括时间戳、页面广告，标题栏、内容版式等非主题内容出现不一致。

网页指纹分布式批处理去重模块500在系统处于分布式批处理模式下，对原始海量网页指纹和输入的批量的指纹进行比对，识别出近似重复的网页指纹对，如果存在完全重复或者近似重复的网页指纹，即可从网页库中删除该网页的内容。

如图2所示，网页预处理模块100包括网页编码预处理模块110和网页结构规范化模块120。

网页编码预处理模块110负责完成网页编码的统一转换。如果所接收到的原始网页文本数据所使用的编码不同于系统选定的编码标准，则按照选定的编码标准对其进行转换，并将转换后的文本数据传送给网页结构规范化模块120。为了使得系统能够适应国际化的需求，通常选定的编码标准为UTF-8。

网页结构规范化模块120负责完成网页结构的规范化。模块120主要针对HTML可能存在的标签不规范导致标准DOM语法树解析器无法解析的情况，对网页文档进行相应的规范处理，包括修正DOM语法树中节点(Node)的不规范属性(Attribute)、修正非正常闭合的标签、去除错误的标签等。所谓标签指的是HTML网页标准范围内的HTML标签。

如图2所示，网页特征向量提取模块200主要包括网页分块模块210、网页文本内容分词模块220、网页主题内容提取模块230。

网页分块模块210用于识别单张网页中的网页语义块。在本模块中将HTML标签进行了分类，具体分为块标签、标题标签、层次标签、忽略标签、其它标签。该模块的处理流程如图4所示：

(1)预处理，将经过模块120处理后的规范化网页文本数据加载到内存，形成DOM语法树。从DOM语法树去除其中的忽略标签，去除的过程中可以对文本内容进行清理，去除首尾的空白字符、去除仅包含空白字符的文本段，同时提取关键词、描述、时间戳等元数据，这类数据通常出现在HTML内容的<meta>标签中；

(2)将DOM语法树的叶子节点依次加入到先进先出的队列中；

(3)取队列中的一个节点，判断该节点的标签类别：如果该标签属于标题标签，则提取文本内容，并标识该节点代表的文本块为标题内容块，转入步骤(4)；如果该标签属于块标签，则判断其中的文本信息或者层次标签的数目是否超过阈值，本实施例中，阈值设定为文本信息阈值为100个字符，层次标签5个，如果超过，就加入到网页块池中，如果没有则传递自身节点信息和节点文本长度信息到父节点，父节点加入到队列中，转入步骤(4)；如果该标签属于层次标签，则将自身节点信息和节点文本长度信息传递至父节点，父节点加入到队列中，转入步骤(4)；如果该标签属于其它标签，则将节点文本长度信息传递至父节点，父节点加入到队列中，转入步骤(4)；

(4)判断队列是否为空，如果为空，结束，否则转入步骤(3)。

经过模块210的处理，网页的内容被处理成为文本块的队列，每个文本块记录了相应的文本内容、带HTML标签的内容、链接锚文本内容、链接数目等信息。

网页文本内容分词模块220用于对识别出来的网页语义块中的文本内容进行分词，

在本发明中，模块220的处理过程为对于模块210处理完后形成的文本块队列中单个文本块的文本内容进行基于词典的分词，并根据预设的词典去除中英文中常见的停用词和虚词等与主题无关的词项。

网页主题内容提取模块230对模块220处理完后的网页内容进行网页主题内容提取，然后形成代表网页特征的特征向量。主题内容应该包括标题内容、跟网页相关的关键词描述、正文主题内容、和主题一致的锚文本内容等。形成的特征向量中的每一维就应该对应于上面的某一项。

在本发明中，模块230经历的基本流程为：

所有模块220处理的分块中选择文本长度最大的那个网页块判定为主题内容块。余下网页块逐个与最大的网页块比较文本相似度，文本相似度的比较方法为，使用模块220进行切词，去除停用词后，存储成词项(Word)流，对Word进行排序，取得两网页块的公共Word流的数目，它除于较小网页块的Word流的结果即为两者的文本相似度：若文本相似度大于某个特定阈值，本实施例中，该阈值设定为0.3，该网页块也判定为主题内容块；若在主题内容块中，锚文本(Anchor Text)的比率大于特定阈值，本实施例中，该阈值设定为0.7，该网页块被判定为主题锚文本块；若文本块未被判断为任何类型的文本块，即为噪音文本块。

经过模块230的处理，各个网页文本块被标识为特定的类型，包括主题内容块、标题内容块(在模块210处理过程中即被标识)、主题锚文本块、噪音文本块等。在去掉噪音文本块后，剩下的几类文本块结合预先设定的权重，便组成了代表网页特征的特征向量。

网页特征指纹计算模块300接收模块200提供的单个网页的特征向量，基于文档子序列Shingle特征对Simhash算法进行改进增强来计算代表网页特征指纹。

Shingle是指文档中连续的一个子序列，本发明下文使用文档子序列代替Shingle的概念，Shingle的长度是指该连续的子序列所包含的词的个数。对于一个文档D，本申请定义S(D，w)为文档D中所有长度为w的Shingle所组成的集合。例如文档D为下列词序列：

(we，love，our，great，country)

w值为3的S(D，w)：

{(we，love，our)，(love，our，great)，(our，great，country)}.

在本发明中选取指纹大小为64bit作为实施例，计算网页特征指纹的流程为(如图6所示)：

(1)首先针对每个网页，初始化维度为k的整型数组，k的取值应该与指纹bit长度保持一致，本实施例中取k＝64；

(2)将模块200处理后的各个网页特征向量按照文档子序列进行切分，特征向量中的每一维可以看作为词项的序列，针对文档子序列中的每一词项，计算词频，得到词项词频权重，将文档子序列中的所有词频权重与文档子序列所在网页特征权重叠加即可得到该文档子序列的权重；

(3)针对单个文档子序列使用Rabin指纹算法，得到64bit的指纹，考虑每一比特位，如果该比特位为1，则在初始化的整型数组中加上该文档子序列的权重，如果为0，则在数组中减去该文档子序列的权重；

(4)依照(3)中的方法，处理所有特征向量的文档子序列；

(5)考虑处理完所有文档子序列的整型数组，由于多次的叠加，对于数组中值为正的元素进行归1操作，对于数组中值为负的元素进行归0操作，这样的话，64位的数组即可看作为k bit的二进制向量，将64位的数组转化为长整型数，即得到代表网页特征的指纹。

通过模块300的处理，得到代表网页特征的指纹，以下模块在进行去重的过程中也是基于指纹进行操作的。

网页指纹在线去重模块400主要基于在线模式，例如网络爬虫在获取一个网页后，经过模块100、模块200、模块300处理后得到k bit的指纹，此时该指纹需要与已经存在的海量网络文档的指纹进行比对，以确定相似的内容是否已经被获取过，如果之前已经获取过完全重复或者是近似重复的网页，那么改网页将不被添加到网页库中去。

本发明假定指纹大小为64bit，可以设定系统原始积累了指纹库，其中指纹库中的每条指纹对应于某张网页，对于原始指纹库，并不确保其中不存在重复或者近似重复的指纹，对于某条需要加入到指纹库中的单条指纹，其判断原始指纹库中是否已存在与该条指纹近似重复的指纹的实施具体流程如图7所示：

(1)对待匹配的一条指纹，进行四等分，将第二、第三、第四部分的16bit的数据分别与第一部分的16bit分别进行置换，得到三条置换后的指纹；

(2)依次从指纹库中读取一批指纹到内存中；

(3)对于读入到内存中的这批指纹，根据特定的规则扩展成四组指纹，扩展的规则为：对于其中的单条指纹将64bit均分为4等分，将第二、第三、第四部分的16bit的数据与第一部分的16bit分别进行置换，如图7所示。这样处理之后，这批指纹扩展成为四组指纹，每组指纹的规模与读入到内存的这批指纹一致，然后对这四组指纹排序，排序的规则为只比较64bit指纹数据的前16bit数值的大小；

(4)将(1)得到的4条指纹分别同(3)得到的对应四组指纹进行4次二分法查找比对，判断待匹配的指纹及其置换后的指纹与(3)得到的四组指纹的前k/4bit是否对应相同，如果4次比对发现符合要求的指纹，进入步骤第(5)步，否则进入(6)；

(5)对于4次比对找到的4组结果，使用每组对应的待匹配指纹同组内每条指纹进行汉明距离计算，如果其汉明距离小于指定的阈值，即可认为原系统中存在与该指纹所代表网页内容相似的网页，原指纹库中的那条指纹将被标识为删除，由于该条指纹可能经过置换操作，所以在从原指纹库中找到待删除指纹之前，可能需要进行反置换操作。该指纹对应的网页将被从网页库中删除，转入(6)；没有发现与待匹配指纹汉明距离小于指定阈值的指纹，转入(6)；

(6)判断指纹库中的全部指纹是否读取完毕，如果是，那么可以认为该指纹所代表的网页没有相似网页存在，该指纹所代表的网页将添加到网页库中去，否则转入(2)。

网页指纹分布式批处理去重模块500主要基于分布式计算平台实现对批量指纹和原始海量指纹的比对，识别出近似重复的指纹对，并从网页库中去除重复的网页。分布式计算平台可以构建计算节点集群，在各台主机计算平台相关服务启动后，即可以向该分布式计算平台提交计算任务，计算平台负责任务调度、数据分布、同步、进程间通信(IPC)、鲁棒和容错性等分布式系统核心问题。计算平台附带的文件系统负责数据文件的存储、切分、传输。分布式处理的过程主要基于映射/规约(Map/Reduce)编程模式，它是与处理海量数据集的实现相关的，用户指定一个映射函数，通过这个映射函数处理键/值对，并且产生一系列的中间键/值对，并且使用规约函数来合并所有的具有相同键的中间键/值对中的值部分。使用分布式计算平台和映射/规约编程模式使得程序员可以不需要有什么并发处理或者分布式系统的经验，就可以处理超大的分布式系统资源。

本发明中，可以假设系统原来由网页特征指纹计算模块300处理得到的指纹历史数据，规模大小达到数十GB以上，每条指纹占空间。需要说明的是，原始指纹数据可以从无开始积累，添加新数据并去重的过程总体来说是更新和扩充的过程。指纹文件存放于分布式计算平台后，按照64MB的大小进行数据分割，以冗余的形式存放于文件系统中，即同一份数据，在集群中多台机器中存在备份，保证在分布式计算环境下单点失效之后数据依然能够被正确处理。这部分数据在下述部分被称为原始指纹库，单台机器可能会处理多个原始指纹块。根据实际需求，可能有一批新的指纹需要被添加到指纹库，同时原始指纹库中与新的指纹相似的指纹就会被删除，然后这批新的指纹将被完整地添加到指纹库中。这批新的指纹在下述部分中被称为待匹配指纹，待匹配指纹数量为数十MB。整个处理流程如图9所示：

(1)移动待匹配的指纹集到分布式计算平台中；

(2)根据网页指纹在线去重模块400中建立64bit指纹冗余置换指纹库的方法，针对待匹配的指纹建立冗余置换指纹库；

(3)进行映射过程调用：映射的过程输入的键为原始指纹中单条指纹在该原始指纹块中的文件偏移位置；输入的值为单条原始指纹，映射过程为将单条原始指纹扩张为4条指纹在冗余表格中比对，具体比对的流程与模块400提到的算法类似，比对后的结果输出键/值对，输出的键为待匹配单条指纹，输出的值为原始指纹中的单条指纹；

(4)分布式计算平台自动对映射模块的输出数据进行排序合并，合并的规则是具有相同键的键/值对合并在一起，以便规约模块进行规约过程调用；

(5)进行规约过程调用：规约的过程为收集归并映射模块输出的指纹对，以待匹配单条指纹为键，原始指纹中与该待匹配指纹汉明距离小于指定阈值的指纹列表为值输出到指定文件中。该指定阈值通常与网页指纹在线去重模块400中的指定阈值相同。

经过该模块计算处理后，系统生成相应的键/值对文件，键为待匹配的指纹集中的单个指纹，值为系统原始指纹中与键汉明距离小于特定阈值的指纹集合，系统可以对原始指纹中与被比对指纹中近似重复的指纹标识为删除，并从网页库中删除特定的网页文件，然后将待匹配的指纹完整添加到原始指纹库中，完成更新，同时将待匹配的指纹对应的网页添加到原有的网页库中，完成更新。

本发明提出的基于并行编程模式的相似网页去重系统在被指定为网页在线去重模式的情况下，可以和网络爬虫配合工作，在网络爬虫获取到网页内容的情况下，通过本发明的相关模块提取特征向量，并计算代表网页特征的指纹，在与已有的海量指纹比对后，确定是否该指纹代表的网页与已获取的网页存在近似重复。在被指定为分布式批处理模式下，该发明系统可以在特定分布式计算环境下完成批量指纹的比对去重，并具备较高的时间效率和较高的准确率。

以上所述为本发明的较佳实施例而已，但本发明不局限于该实例和附图所公开的内容。所以凡是不脱离本发明所公开的精神下完成的等效或修改，都在本发明保护的范围内。