第5章Web页面逻辑链接块研究 链接块是Web页面中广泛存在的一种区块结构。在现有的涉及链接块的相关研究和应用中，存在两类主要问题： 一是仅针对物理结构上的链接块，甚至仅针对Block级别的HTML元素链接块； 二是链接块的发现与识别等处理都是建立在Web页面标签树的基础之上，这一方面影响了Web页面的处理速度，另外也无法应付当前互联网上多样化而又不规范的Web页面。针对目前相关方法的不足，本章提出逻辑链接块的概念和逻辑链接块的发现方法和判别方法。该方法无须解析网页标签树或者DOM［62］ 树，相关处理程序健壮性大幅度提高，且不再受限于某些特定的Block层次的链接块，既可以处理Block层次的链接块，也可以处理Inline层次的链接块，而且还可以处理跨越块级元素的链接块。实验结果表明： 本章提出的方法可以有效地发现页面中的逻辑链接块，判别规则简单，为链接块的识别及文本提取提供了一种新的方式，在对链接块粒度要求不高的场合具有广泛的应用前景，在其他Web信息处理和挖掘领域中也具有一定的实际应用价值。 5.1引言 万维网是一个通过页面之间的链接构建起来的超大型复杂网络。链接在Web信息组织和展示、页面导航等方面发挥着巨大的作用。网络爬虫依靠Web页面之间的链接实现互联网的遍历爬行，互联网用户则正是依靠页面之间的链接实现同主题内容的“聚合”阅读。Web页面中的链接往往以不同的粒度块来组织，粒度块越精细则所含链接的主题相关性越高； 随着粒度块的增大，链接块的主题“内聚”性逐渐减弱。如图51所示，当粒度要求极其精细时，则其将被划分为三个链接块； 而当精细度要求不高时，则可以将其视为一个链接块，整个链接块的用途即“导航”。在针对链接块的相关研究中，根据研究目的不同，对链接块的粒度精细要求也将不同。在专门针对链接块进行分析的研究中，对链接块粒度的要求往往较为精细，而在其他非链接块研究中，如Web页面文本提取中，则对链接块的粒度要求不高。 图51链接块的粒度 在技术实现上，视觉上的分块往往也对应着块（block）级标签元素（blocklevel elements）［63］，目前的涉及链接块的应用和研究基本仅针对该实现方式。然而，由于网页设计技术和实现的多样性，视觉上的分块，在实现方式上并不总是采用Block类型标签实现，也有可能采用内联类型标签（inline elements）［63］实现，这也就意味着无法准确地预知设计者使用何种方式实现链接块，或者需要建立在对HTML标签属性的精细解析基础之上，这给基于海量Web数据的一些自动化应用带来了诸多麻烦。 5.2相关研究及存在的问题 Web页面链接块的研究历史悠久，对Web页面进行分块或者信息提取的方法众多。文献［64］将Web页面的抽取方法总结为基于Wrapper、模板、机器学习、视觉布局特征、HTML特征等五类。这五类方法同样可以适用于Web页面链接块的分块。其中，Wrapper和模板法的通用性较差，且一般需要人工参与，并需要更新维护，极为耗时费力，鉴于此有研究人员提出了无须模板支持或人工监督的Wrapper算法［6567］ ，并取得了较好的效果； 机器学习的方法需要借助合适的训练集和适量的特征［68］ ，且难以完全脱离人工监督； 利用视觉布局特征的方法的典型代表即VIPS［69］ ，该方法虽然准确率高，但是对网页的解析要求过于精细，计算消耗大，面对大量非规范化的网页时健壮性难以保证，且在当前普遍采用CSS［70］ 来控制各页面标签属性视觉呈现的情况下，还需要另行解析相关CSS，最终导致解析任务量大，程序健壮性欠缺； 基于HTML特征的相关方法多偏向一些启发式规则［7174］ 或一些统计规律，通用性有待提高。此外，也有研究者提出了其他的一些方法，例如，利用模糊神经网络实现页面分块的方法［75］ 、MSS页面分块方法［76］ 等。虽然相关研究方法多种多样，各有特点，然而经过分析总结可以发现： 目前关于Web页面链接块的发现和识别相关算法基本都是基于标签树［73, 7781］ ，而DOM［82］ 是一种构建标签树最为常见的方式； 其他方法则都以HTML标签树或DOM为基础［8384］ 。 另外，在对Web页面进行分块的相关研究中，有相当一部分基本都仅仅针对块级层次的HTML标签元素，如div、table、tr、td等，其中由于table功能的多样性和强劲性［85］ ，早期网页布局修饰和内容组织几乎对table不可或缺，相应的，部分文献也仅考虑了针对table布局的网页［81］ ，且未能很好地区分用于布局的table和用于内容组织的table。Son等［81］专门研究了基于table设计的网页，对table的两种作用做了区分并分别识别，实验证明了所提出方法的先进性。但仅针对table的处理方式局限性太大，目前的网页设计基本都是table和div共存，Uzun等［77］ 同时考虑了这两种情况，先根据div和td获得分块信息，其次结合决策树生成抽取规则，取得了良好的效果，特别是在抽取速度上获得了和手工规则相当的性能； Wang等［71］ 则提出了BSU概念，并基于此采用聚类和启发式规则两种方法实现页面信息抽取，比采用基于div和table的方法结果更好。 现有的对链接块进行分块的算法，尤其是基于标签树的各种方法需要Web页面遵从较好的规范，这种规范既包括HTML、XHTML等标签语法规范（如标签的配对关系），也包括语义设计方面的规范（如通过浏览器渲染后在视觉上呈现块状的内容在实际的代码中也会通过块级元素div、table等来呈现，视觉上的标题通过h1、h2等标签来呈现等）。但实际上，海量的Web页面中，有相当数量的Web页面并不遵从HTML等标签语法规范和语义设计规范。虽然HTML标签语法上的不规范性可以通过一些现有的或自行设计的Web页面规范化程序进行矫正，但并不能保证100%的正确率； 语义设计规范问题的矫正难度则更大。这就决定了基于标签树的各种方法仅能在设计规范或易于矫正的Web页面中获得良好的效果，在非规范化Web页面中则显得捉襟见肘。 由于在已有的Web页面处理相关研究中，一般只将块级标签对应的代码块称为块，这种处理方式虽然极大地提高了诸多Web页面处理的效果。然而在面对纷繁复杂的Web页面时，在某些情况下，这种处理方式可能带来两种后果： 误判或无法检出。例如在很多Web页面中，存在着并非块级的广告，在页面正文抽取等研究领域，按传统的块级处理方式，无法检出这些广告链接，如图52所示。 图52非块级的嵌入式广告链接 本章基于现有链接块识别方法的不足，提出标签距离和逻辑链接块的概念，并基于标签距离提出了逻辑链接块的发现和判别方法，并实现逻辑链接块的识别和判别。逻辑链接块的识别在对链接块精细力度要求不高的场合具有良好的应用场景。 5.3方法及原理 为了后文表述方便，首先定义如下概念。 在Web页面的HTML代码中，两个标签之间存在着两类距离： 代码距离和文本距离。分别定义如下。 代码距离： 任意两个标签之间的代码距离即介于前一个标签的标签结束符“>”和后一个标签的标签开始符“<”之间所有内容的长度。在本章的计算中，将先去除各标签的属性然后才执行代码距离的计算，例如，“
ABC
”经过去除标签属性得到“
ABC
”。 文本距离： 任意两个标签之间的文本距离即介于前一个标签的标签结束符“>”和后一个标签的标签开始符“<”之间所有文本的长度。 但是在计算文本距离时，遵从如下规则： ① 英文等字符以单词为统计单位，即一个单词长度计为1； ② 中文等字符以单个字为统计单位，即一个汉字长度计为1； ③ 数字以一个完整数字为统计单位，即一个完整数字长度计为1，例如“北京2008”的长度计为3； ④ 日期字符串以日期整体为统计单位，即一个完整日期长度计为1，例如“今天是2014年3月8日”的长度计为4； ⑤ 标点符号与汉字统计规则一样，但是若相邻的若干标点符号相同，则长度只计1。 链接距离： 即Web页面中相邻两个链接之间的距离。链接距离可以采用如下两种度量方式之中的一种： (1) 代码距离： 即前一个链接的“”与后一个链接的“”之间的代码距离。 (2) 文本距离： 即前一个链接的“”与后一个链接的“”之间的文本距离。 逻辑块： 即由不少于一个且相邻或相近的标签所构成的连续代码区域。逻辑块可能是一个标签块，也有可能是几个相邻或相近的标签块合并构成，且被包含在逻辑块中的各个标签并不要求都是完整的，被包含在逻辑块中的各个标签也不必是块级标签。如图53所示，A与B为相邻的兄弟标签，构成逻辑块； A1与A2均是A的相邻子标签，构成逻辑块； A2与B1虽然隶属于不同的父标签，但A2与B1相近，通过A的后半部分代码和B的前半部分代码，可以最终使得A2和B1成为一个连续的代码区域，故也是逻辑块。 图53逻辑块 逻辑链接块： 设某逻辑块中的链接数为Clink，逻辑块内各相邻链接之间的距离为(d1,d2,…,dClink-1)，若该逻辑块满足如下条件，则称该逻辑块为逻辑链接块。 Clink≥Ct max(di)
90时，这种差别几乎不再存在。这也就意味着，在索引页中，无论是人工组中的门户网站索引页面，还是随机抽取的常规索引页面，相邻链接之间的代码距离基本都在90以内。由于dct越小，其对Web页面的分割作用越“精细”； 反之dct越大，其分割作用越“粗糙”，更易凸显Web页面的宏观结构特性。可见，无论Web页面规模的大小如何，都存在一定的宏观结构相似性。这种特性在针对内容页的实验中同样存在。 与采用文本距离方式的实验结果类似，针对内容页的代码覆盖率显著低于索引页，其他方面则无显著差异。 3. 从文本距离谈Ct对Web页面链接块的影响 逻辑链接块中链接数阈值Ct决定了一个逻辑块要成为一个逻辑链接块所必需的最小链接数。在dt（dct和dtt）确定的情况下，Ct越小，则在逻辑链接块的扫描发现过程中，各个逻辑块更容易达标而成为链接块，也将包含更多的链接，链接的纳入，必将相应地吸纳更多的链接间代码； 反映在曲线上，即链接覆盖率和代码覆盖率的高位。反之Ct越大，各个逻辑块则更难以被认定为链接块，诸多的逻辑块虽然包含了链接，但由于数目上小于Ct从而被舍弃，其结果就是更多的链接将被排除在逻辑链接块之外，相应的也将有更多的代码未能纳入逻辑链接块； 反映在曲线上，即链接覆盖率和代码覆盖率的低位。同时由于诸多“准链接块”被舍弃，也将导致逻辑链接块总数的衰减。实验结果证实了上述结论，如图57所示。 图57Ct对逻辑链接块的影响——索引页 从图57可见，人工组的逻辑链接块数受Ct的影响较为显著，而随机组的逻辑链接块数基本无大幅度变化。这主要是因为在本实验中dtt=40，而绝大多数的随机组Web页面中较少存在长度超过40的纯文本，这也就导致了无论Ct取值如何，整个Web页面被划分为逻辑链接块时的分界点较为固定，即那些数量很少且长度超过40的纯文本充当了分界点角色。不难推断，若dtt较小时，充当这种分界点角色的纯文本就逐渐增多，此时逻辑链接块数也将呈现为较大波动。实验数据证实了这一推断。 图58Ct对逻辑链接块的影响——内容页 针对内容页的实验结果(如图58所示)，与索引页相比其最大不同表现在： ①逻辑链接块数量少，基本都在4个以下。这主要是因为在内容页中纯文本几乎集中呈现，即使文本中偶尔会出现孤立的超链接，但往往由于这些超链接与其他超链接距离过远而无法纳入到链接块中。这恰好能够维持文本块的完整性。倘若将dtt继续增大，则可能导致文本块被部分甚至全部归属到链接块中。②逻辑链接块数随着Ct的增大一直呈现平缓的下滑，不再出现类似上述在Ct较小时链接块数波动较大的情况。这主要是因为在内容页中的长文本数量和位置基本固定所致。在dtt较大且确定的情况下，无论Ct如何变化，对逻辑链接块划分起决定性作用的都是那些长文本。在内容页中的长文本集中呈现，这也就决定了当dtt增大到某个值时，绝大多数的内容页将被划分为两个链接块： 正文之前作为一个链接块，正文之后作为一个链接块。该结论在实验中得到证实。③当Ct较小时，链接覆盖率与索引页基本持平，而随着Ct的增大，链接覆盖率与索引页的差距逐渐增大。这主要是因为： 在索引页中，链接分布比较密集而均匀，而在内容页中，例如，在某些正文中零星分布少量链接的页面中，特别是在某些附带评论的博客页面和论坛页面中，链接呈现为一种相对“离散”分布。这样当Ct较小时，零星散落的链接只要距离不致太远，或者能以小团簇形式（典型的如博客或论坛中每条回复周围关于发帖人个人信息的一些链接）出现，它们仍能被认定为逻辑链接块； 随着Ct的增大，越来越多的以团簇形式存在的小链接区域由于无法满足最小链接数阈值Ct的要求，且相邻链接团簇又因为被某些较长的文本切断而被排除在链接块之外。这种情况在索引页中是极其少见的，因而导致了这一现象。④代码覆盖率远低于索引页。其本质原因在于内容页中存在着大篇幅的主题文本块，这些文本块基本不会被纳入逻辑链接块中，从而也就导致了内容页的代码覆盖率显著低于索引页。⑤人工组的链接覆盖率显著高于随机组。其主要原因正如③中所述，博客页面或论坛页面中的往往由于部分篇幅较长帖文对页面的分割作用所致。这些长帖文的存在，将导致部分包含的链接数低于Ct的逻辑块未被认定为链接块，从而丢弃了大量的链接，这一现象在人工组的门户新闻页面中几乎不存在。最终造成链接覆盖率的降低，相应的也使得代码覆盖率降低。⑥人工组的代码覆盖率显著高于随机组。其主要原因在于： 第一，人工组的页面往往较随机组中的页面更长，然而从其所包含的正文长度而言，则两者并无显著差异，依据代码覆盖率的计算表达式不难看出这将导致整体篇幅短的内容页其代码覆盖率也更低。第二，正如⑤中所述，部分篇幅较长帖文对页面的分割作用导致了代码覆盖率的降低。 4. 从代码距离谈Ct对Web页面链接块的影响 对索引页实验结果而言，采用代码距离和采用文本距离的方式相比较，主要差异体现在四个方面： ①采用代码距离时的链接块数更多。原因与前文一致，不再赘述。②代码覆盖率和链接覆盖率更低。原因同前文，不再赘述。③随机组和人工组的逻辑链接块数差异不明显。 对内容页实验结果而言，采用代码距离和采用文本距离的方式相比较，主要差异与索引页基本相同。 5.5结论 本章提出的逻辑链接块，扩展了常规链接块的范畴； 本章的逻辑链接块发现方法，避开了传统链接块识别所不可或缺的标签树解析或者DOM解析过程，从而也就无须在标签树解析或DOM解析上耗费大量的计算资源，同时避免了解析纷繁复杂且缺乏规范的HTML时的各种问题； 另外，链接块的判别规则简单，无须复杂计算，在对Web页面进行一次扫描即可同时完成逻辑链接块的发现与判别。本章的方法分析速度快，抗干扰性强，能更好地适应设计不规范的Web页面，且不要求链接块内的链接主题内聚性高，这也就决定了该方法在Web页面文本抽取方面有着潜在的应用价值，在其他对链接块精细粒度要求不高的Web信息处理和挖掘领域中也具有广泛的应用前景。