基于最大相似性匹配的网页去噪系统及其去噪方法

摘要

一种互联网技术领域的基于最大相似性匹配的网页去噪系统及其去噪方法，该系统包括：网页获取模块、预处理模块、网页DOM生成特征树模块、特征树最大相似性匹配模块和聚集评价模块，网页获取模块与预处理模块相连并传输网页代码数据，预处理模块与网页获取模块相连并传输预处理后的目标网页，预处理模块与网页DOM生成特征树模块相连并传输预处理后的网页数据，网页DOM生成特征树模块与特征树最大相似性匹配模块相连并传输特征树数据，特征树最大相似性匹配模块与聚集评价模块相连并传输网页内容块候选集，最后聚集评价模块输出网页内容块。本发明能够很好适用于大多数内容型网站。

说明书

技术领域

本发明涉及的是一种互联网技术领域的系统及方法，具体是一种基于LCS(Longest CommonSubsequence，最长共同子序列)特征树的最大相似性匹配的网页去噪系统及其去噪方法。

背景技术

随着互联网技术的不断发展，互联网的信息呈现出爆炸式的增长。如何从海量的网页信息中找到核心主题信息，成为当今Web研究领域的一种趋势。一个网页一般包含一些内容块，但除了这些内容块，往往包含导航栏、版权信息、公告消息以及各种各样形式的广告，它们的存在是为了商业目的或者便于用户使用，这些与主题无关的信息可以称之为网页噪声块。如何降低网页中的噪音，对于网页分类、特征提取、内容聚合具有重要意义，已成为在三网融合的大背景中，基于多媒体内容融合的研究热点。

经过对现有技术文献的检索发现，Yuancheng Li和Jie Yang于2009年在《InternationalJoint Conference on Artificial Intelligence(国际人工智能联合会议)》上发表的“A Novel Methodto Extract Informative Blocks from Web Pages(一种新型的从网页抽取信息块的方法)”中提出将DOM树的节点分为HTMLItem和Content两种节点，将Content按种类(图片、文字、链接)和数量计算权值，加在其所属HTMLItem节点上作为其重要性的度量，同时HTMLItem自己也有权值，且随着其深度递减。最后按权值的大小去除噪声块。该方法是基于规则的，只适用于某些类型网页，有其局限性。

又经检索发现，Ruihua Song，Haifeng Liu等人在2004年发表在《ACM SIGKDDExplorations Newsletter(美国计算机学会下属知识发现与数据挖掘会议)的“Learningimportant models for web page blocks based on layout and content analysis(基于布局和内容分析的网页块重要性学习模型)”提出利用网页布局来建立视觉结构，同时利用这个视觉结构将网页分块，在对网页分块之后，利用人工标注并通过神经网络和支持向量机来对网页块特性到块重要性的映射函数进行学习，最后得到通用的映射方法。该方法是基于机器学习的，机器学习太复杂，效率不高。

发明内容

本发明针对现有技术存在的上述不足，提供一种基于最大相似性匹配的网页去噪系统及其去噪方法，适用于各种内容型网站的网页去噪。

本发明是通过以下技术方案实现的：

本发明涉及一种基于最大相似性匹配的网页去噪系统，包括：网页获取模块、预处理模块、网页DOM生成特征树模块、特征树最大相似性匹配模块和聚集评价模块，其中：网页获取模块与预处理模块相连并传输网页代码数据，预处理模块与网页获取模块相连并传输预处理后的目标网页，预处理模块与网页DOM生成特征树模块相连并传输预处理后的网页数据，网页DOM生成特征树模块与特征树最大相似性匹配模块相连并传输特征树数据，特征树最大相似性匹配模块与聚集评价模块相连并传输网页内容块候选集，最后聚集评价模块输出网页内容块。

所述的网页获取模块下载目标网页，并利用从预处理模块得到的预处理后的目标网页，在其中寻找与目标网页URL相似的网页URL，并下载相似网页，该模块包括：网页下载单元、链接匹配单元，其中：网页下载模块通过HTTP请求指定URL的网页；链接匹配单元分析预处理后的目标网页代码并匹配出与目标网页URL相似的相似网页地址。

所述的预处理模块对获取到的网页代码进行预处理；该模块包括：去除无关代码单元、修正单元，其中：去除无关代码单元分析网页代码，将其中内容无关代码，例如注释、脚本、CSS等去除；修正单元修正网页代码中的错误。

所述的网页DOM生成特征树模块分析网页DOM树，并通过计算和重组得到特征树；该模块包括：属性计算单元、特征树构建单元，其中：属性计算单元将DOM树节点属性进行转换提取得到特征树节点的属性；特征树构建单元利用属性计算单元的结果来构建特征树。

所述的特征树最大相似性匹配模块对目标网页特征树和相似网页特征树进行基于LCS特征树最大相似性匹配，得到网页内容块候选集；该模块包含：特征节点序列生成单元、相似性匹配单元，其中：特征节点序列生成单元采用逐层遍历将特征树转化为特征节点队列；相似性匹配单元并对目标网页的特征节点队列和相似网页的特征节点队列进行LCS匹配，找出两个序列不同之处得到网页内容块候选集。

所述的聚集评价模块将网页内容块候选集进行聚集并对每个聚集的集合进行特征分析并评分并找出最重要的内容块；该模块包含：聚集单元、评价单元，其中聚集单元消除内容块候选集中的祖先和子孙关系，并将在特征树位置上比较接近的节点汇聚在一个集合里；评价单元用于对网页信息块聚集簇中的每个集合进行特征分析并评分，找出最重要的内容块。

本发明涉及上述系统的去噪方法，包括以下步骤：

第一步、通过网页获取模块的网页下载单元下载目标网页，通过预处理模块对获取到的目标网页的代码进行预处理。预处理模块首先利用去除无关代码单元去除注释、脚本、CSS等内容无关代码；然后通过修正单元修正网页代码中存在的错误和相对链接；

第二步、通过网页获取模块的链接匹配单元对第一步中得到的预处理后的目标网页寻找与目标网页URL相似的网页URL，并通过网页下载单元下载相似网页；对得到的相似网页利用预处理模块进行预处理；

第三步、通过网页DOM生成特征树模块对第一步得到的预处理后的目标网页和第二步中得到的预处理后的相似网页分析其DOM树，并通过计算和重组得到特征树。首先通过遍历DOM树节点并利用属性计算单元将DOM树节点属性转换为特征树节点的属性；然后通过得到的属性利用特征树构建单元依次构建并得到目标网页特征树和相似网页特征树；

第四步、通过特征树最大相似性匹配模块对第三步中的得到的目标网页特征树和相似网页特征树进行基于LCS特征树最大相似性匹配，得到网页内容块候选集。首先利用特征节点序列生成单元将特征树转换为特征节点序列；然后利用相似性匹配单元对目标网页的特征节点队列和相似网页的特征节点队列进行最长子序列匹配，找出两个序列不同之处得到网页内容块候选集；

第五步、通过聚集评价模块对第四步得到的网页内容块候选集进行聚集并对每个聚集的集合进行特征分析并评分并找出最重要的内容块。首先通过聚集单元消除内容块候选集中的祖先和子孙关系，并将在特征树位置上比较接近的节点汇聚在一个集合里；然后利用评价单元用于对网页信息块聚集簇中的每个集合进行特征分析并评分，找出最重要的内容块，即滤除了噪声内容。

本发明的有益效果在于，以基于LCS特征树结构最大相似性匹配算法为核心，对目标网页及其相似网页生成的特征树进行相似性匹配，然后根据匹配结果的不同之处生成信息块候选集，并对候选集根据信息块的相似程度和树结构进行聚集，对聚集结果的特征进行分析评分得到最后的信息块，以达到网页去噪的目的。这样，在考虑内容的情况下，即不需要太复杂的机器学习，又具有广泛的适应性，能够很好适用于大多数内容型网站。本发明的其他优点将通过下面的说明书及附图来说明。

附图说明

图1为本发明系统的结构图。

图2为实施例特征树示意图。

图3为实施例操作流程图。

具体实施方式

下面结合附图和实施例对本发明作详细说明，本实施例在以本发明技术方案为前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

如图1所示，本实施例包括：网页获取模块101、预处理模块102、网页DOM生成特征树模块103、特征树最大相似性匹配模块104和聚集评价模块105，其中：网页获取模块101与预处理模块102相连并传输网页代码数据，预处理模块102与网页获取模块101相连并传输预处理后的目标网页，预处理模块102与网页DOM生成特征树模块103相连并传输预处理后的网页数据，网页DOM生成特征树模块103与特征树最大相似性匹配模块104相连并传输特征树数据，特征树最大相似性匹配模块104与聚集评价模块1.6相连并传输网页内容块候选集，最后聚集评价模块105输出网页内容块。

所述的网页获取模块101下载目标网页，并利用从预处理模块得到的预处理后的目标网页，在其中寻找与目标网页URL相似的网页URL，并下载相似网页，该模块包括：网页下载单元、链接匹配单元，其中：网页下载模块通过HTTP请求指定URL的网页；链接匹配单元分析预处理后的目标网页代码并匹配出与目标网页URL相似的相似网页地址。

所述的预处理模块102对获取到的网页代码进行预处理；该模块包括：去除无关代码单元、修正单元，其中：去除无关代码单元分析网页代码，将其中内容无关代码去除；修正单元修正网页代码中的错误。

所述的网页DOM生成特征树模块103分析网页DOM树，并通过计算和重组得到特征树；该模块包括：属性计算单元、特征树构建单元，其中：属性计算单元将DOM树节点属性进行转换提取得到特征树节点的属性；特征树构建单元利用属性计算单元的结果来构建特征树。

所述的特征树最大相似性匹配模块104对目标网页特征树和相似网页特征树进行基于LCS特征树最大相似性匹配，得到网页内容块候选集；该模块包含：特征节点序列生成单元、相似性匹配单元，其中：特征节点序列生成单元采用逐层遍历将特征树转化为特征节点队列；相似性匹配单元并对目标网页的特征节点队列和相似网页的特征节点队列进行LCS匹配，找出两个序列不同之处得到网页内容块候选集。

所述的聚集评价模块105将网页内容块候选集进行聚集并对每个聚集的集合进行特征分析并评分并找出最重要的内容块；该模块包含：聚集单元、评价单元，其中聚集单元消除内容块候选集中的祖先和子孙关系，并将在特征树位置上比较接近的节点汇聚在一个集合里；评价单元用于对网页信息块聚集簇中的每个集合进行特征分析并评分，找出最重要的内容块。

如图3所示，以著名中文门户网站新浪的一个网页为实施例，其URL地址为“http://news.sina.com.cn/w/2010-09-27/202421181404.shtml”，将其作为方法的输入。

步骤S301，下载目标网页，并对得到的目标网页进行预处理，去除掉一些与网页内容无关项(如JavaScript脚本、注释等等)，JavaScript是动态客户端脚本，一般用于网页与用户的互动，与网页内容无关；注释是网页设计者为了方便设计而添加的网页页面不可见的内容，因此也可以直接删除；同时修正相对路径问题，由于网页是下载到本地后进行处理，处理完后无法放到原网站环境下去显示，因此需要把相对URI地址要转化为绝对URI地址，这包括链接、图片、CSS文件、iframe、frame的URI地址；修正不符合W3C标准的网页错误，这包括标签的错误嵌套，标签不成对出现等等。

步骤S302，在对目标网页进行预处理之后，将其发送给网页获取模块，对预处理后的目标网页进行链接匹配，搜索目标网页中的所有链接，并根据说明书中的四个原则来粗略获取相似网页的链接，然后下载相似网页，并再发送给预处理模块进行预处理。

步骤S303，对预处理后的目标网页和相似网页，分析其HTML的DOM树形式，并利用其得到特征树。特征树由特征节点(CNode)构成，以网页body节点为根节点。CNode去除了DOM树节点中不利于做相似性匹配的属性，加入了一些由DOM树种的属性进行变换融合的属性。

步骤S304，通过基于LCS特征树最大相似性匹配模块对目标网页和相似网页进行匹配，寻找特征节点序列中的不同节点。这一步骤可以分为以下几个环节：

一是由于LCS算法不能直接运用于树，所以首先将特征树按逐层遍历转换为节点队列，特征树的示意图如图2，将特征树CT1转换为序列为ABCDEFG，特征树CT2转换为序列为A’B’C’D’E’F’G’。

二是定义两个二维数组scoreTable和pointerTable，分别保存子问题相似度累和与回溯方向，此处表格单元格代表子序列相似度累加的最大值，假设scoreTable行方向的序列是S1，列方向的序列是S2，然后运用LCS算法进行最大相似性匹配：

1.初始化两个二维数组

scoreTable所有单元格赋值为0；pointerable第一行除第一个单元格外全部记录向左方向，第一列除第一个单元格外全部记录向上方向。

2.循环计算子问题的相似度累和以及回溯方向

从scoreTable第二行第二列开始逐行计算单元格值和pointerTable对应单元格的方向值。m是序列S2的长度，n是序列S1的长度。

for(row＝1to m)

   for(col＝1to n)

       Vtop＝scoreTable[row-1，col]//获取上方单元格的值

       Vleft＝scoreTable[row，col-1]//获取左方单元格的值

       Vtopleft＝scoreTable[row-1，col-1]+

                 CompareTwoCNode(S1[col-1]，S2[row-1])//计算左上方单元格与当前两节点的相似度的和

scoreTable[row，col]＝Max(Vtop，Vleft，Vtopleft)//计算单元格值(子问题解)

pointerTable[row，col]＝getDirection(Vtop，Vleft，Vtopleft)//计算回溯方向

   end offor

end offor

其中CompareTwoCNode是计算两个特征节点相似性的函数，输入为两个节点，输出是一个介于0到1之间的值，即相似度。CompareTwoCNode的实现方法如下：

(1)如果两个节点标签名不同，返回0；

(2)如果两个节点都是BODY节点，返回1，BODY节点是一个特殊的节点，它是每棵特征树的根节点，对于BODY节点，不管它们是否有特征不相同，都认为它们是相似的，而且相似度为1；

(3)如果一个是BODY节点，一个不是，返回0；

(4)如果两个节点的父节点不相似，返回0；

(5)如果两个节点的都是内容节点，则比较它们的innerHTML，相同返回1，否则返回0，对于内容节点，在比较时要求比较苛刻，除了在特征上要求相似，还要求其在内容上相同；

(6)如果两个节点一个是内容节点，一个是结构节点，返回0；

(7)在上面所有情况都不满足的情况下，计算两个节点各特征相同的数目与特征总数目的比值，返回比值。这里的特征包括ID、样式表类名(className)、节点在特征树中的深度(Depth)、节点代表的网页块的宽度、高度、左边距、上边距等。

算法中用到的getDirection用于计算回溯方向，输入是三个方向上的相似度累和，输出是上、左、左上中的一个方向。其计算方法如下：

(1)在不相同的情况下，选取相似度累和最大的那个方向；

(2)在有两个或三个方向上相似度累和相同的情况下，按优先选取左上，然后是上，最后是左的原则。

3.算法回溯

假设CTree1是目标网页的特征树，CTree2是相似网页的特征树。与LCS算法不同，感兴趣的是不是两棵树相似之处，而是希望得到CTree1上特有的，而CTree2上没有或不同的树枝或节点。回溯从表格右下角开始，pointerTable记录了回溯方向。考虑要将S1变换为S2，对于向上的方向，对S1来说此处发生了添加操作，添加操作意味着该节点是S1没有而S2有的节点，不是S1不同于S2的节点，忽略。对于向左的方向，S1发生了删除操作，意味着S1有而S2没有的节点，将其加入目标网页信息块候选集。对于左上方向，本单元格的值是左上单元格相似度累和与本单元格位置上的S1序列和S2序列的节点之间的相似度之和，因此可以用本单元格值减去左上单元格值得到此处两节点的相似度，与相似度阈值(Ts)进行比较，如果大于阈值，则认为两节点相似，忽略；如果小于阈值，此处发生替换操作，意味着S1有S2也有但不相似的节点，将其加入目标网页信息块候选集。

步骤S305，通过聚集评价模块，消除内容快候选集中的祖先和子孙关系，并将在特征树位置上比较接近的节点汇聚在一个集合里面。在实验中首先检查候选集类是否有某个节点的子孙节点，有则将子孙节点从候选集中去除；然后随机选取一个候选集中的节点，在候选集其他节点中寻找与其有相同父亲节点的节点或那些爷爷节点是其父亲节点的节点，将它们置于同一个集合中，继续对剩下的节点做同样的操作，直到候选集中所有节点都处理完毕。最后得到多个集合，称之为网页信息块聚集簇。然后对网页信息块聚集簇中的每个集合进行特征分析并评分，找出最重要的信息块。计算文本长度、面积、有效面积、内容标签数目、链接率、文本代码比率等指标后，对于有助于寻找信息块的指标(如文本长度)，给排名靠前的聚集簇加分，对于有利于寻找噪声块的指标(如链接率)，对排名靠前的减分惩罚。对于每个指标对聚集簇按从大到小排序，对前三个进行打分。对于链接率，按-5、-3、-1分值打分；对其他指标按5，、3、1分值打分。最后每个聚集簇都有一个评分，对其进行排名，选取靠前的几个分值比较接近的聚集簇作为最后的结果，即目标网页的信息块。

利用上述方法从几个著名中文门户网站(新浪、腾讯、网易和搜狐)获取共计2458个不同类别的网页地址，作为输入进行了测试，通过对比原网页和去噪后结果，看出导航栏和广告等都被滤除，由于利用了相似网页来去噪，算法达到了平均95.1％的正确率，比“A NovelMethod to Extract Informative Blocks from Web Pages(一种新型的从网页抽取信息块的方法)”文中提出的方法的平均正确率85.9％有明显的提高，证明本发明方法对于网页都有很好的去噪效果。本发明中提出的基于DOM树构建特征树，所构建的特征树适合于LCS算法进行最大相似性匹配，并利用了LCS算法能找到全局最优解的特点，从而在网页去噪中取得了更好的效果。

同时，本方法通过分析计算网页块的文本长度、面积、有效面积、内容标签数目、链接率、文本代码比率等指标，然后根据噪声块和内容块各自特点对网页内容块候选集进行评分筛选，能有效区分噪声块和内容块，从而达到很好的去噪效果。