《网页分块算法(版本1).docx》由会员分享，可在线阅读，更多相关《网页分块算法(版本1).docx（6页珍藏版）》请在金锄头文库上搜索。
1、网页分块算法(版本1)网页分块1. 网页分块的基本思想为了网页分块描述的方便性，首先我们引入一些基本概念：（1）基本对象：通常在DOM树上我们将叶子节点定义为基本对象，因为这些节点已经不能再被继续分割了。（2）最小原子块（原子块）：该节点中的内容作为一个整体出现，这些节点或者是一个基本对象或者是一些基本对象的组合。不能被继续分割。该节点采用或者标签来划分。（3）有效节点(Valid node)：如果一个节点能够在浏览器中表现出来，那么这个节点就是有效节点。另外如果一个节点内部没有任何有用的信息，我们也称之为无效节点。无效节点包含有空元素节点或者具有display:none等样式设置的元素节点。
2、（4）Inline节点：如果该节点的标签能够影响文字的外观同时不会引起换行的话，那么这类节点我们称之为Inline节点，比如、Line-break节点，则就是除了 inline节点之外的所有节点。（5）文本节点：这类节点通常是指HTML中的文字，通常它们不被任何标签所包围。虚拟文本节点(这个定义是递归定义)：如果一个节点是文本节点，那么它自然就是虚拟文本节点如果一个节点是inline节点，并且它的所有子节点要不是文本节点，要不是虚拟文本节点，那么这个节点也就是虚拟文本节点。（6）疑似分割概率DoC(Degree of Coherence)：该值的大小反映了当前块内部内容联系的紧密程度。它具有下
3、面两个重要的特性：DoC值越小，则块内部的内容之间的联系紧密程度就越大，它们之间关系就越连续，反之就越小。在层次数上，父块的DoC的值肯定要比子块的值大。（7）PDoC(Permitted Degree of Coherence):通过该值来限定分割块的粗糙程度。当块的DoC值达到PDoC值之后，迭代分割就停止。PDoC越大，则分割的语义块就越粗糙，反之，分割的块就越精细。该算法的基本思想如下：我们将网站原始的HTML文档通过某种工具进行解析得到的遵循W3C规范的XML文档，该文档通常以DOM树的结构呈现。我们首先遍历该DOM树，找到最小原子块，并且为最小原子块的节点添加DoC属性，并赋值0，
4、然后从最小原子块开始往上按照“疑似分割权重度规则”设置相关父节点的DoC属性值，最终在整个文档的节点内为每个节点都赋上了DoC属性，并且DoC属性值随着节点深度的不同而不同，节点深度越深，DOC属性值就越小。最后我们再次遍历该DOM树，根据预设的PDoC值，如果节点的DoC属性值小于或者等于该值，就停止分割，并将该节点作为一个块节点，否则，继续遍历子节点，直到子节点的DoC属性值该值为止。2. 网页分块的算法实现基于上面的网页分块思想，我们给出一些推理规则用以设定当前节点的DoC值。网页分块的疑似分割权重度规则如下：规则1：如果当前节点是最小原子块，则该节点的DoC属性值设为0；规则2：如果当
5、前节点不是最小原子块，但是该节点所包含的子节点全部是内联节点，则将该节点的DoC属性值设为0；附：该规则主要用于处理UL或者P等元素的节点情况。规则3：除了前面两种情况外，如果该节点是虚拟文本节点，则将该节点的DoC属性值设为0；规则4：如果当前节点只有一个有效的孩子节点，那么该节点的DoC属性值等于他的孩子节点的DoC属性值；规则5：如果当前节点的所有子节点都是最小原子块或者是虚拟文本节点，根据该节点包含的内联节点的数量(InlineCount)以及预定的门槛值大小，设置值可能为5，10，15或者30等值。具体规则如下：内联节点的数量(InlineCount)小于一级门槛大小，设置值为5内联
6、节点的数量(InlineCount)大于一级门槛小于二级门槛大小，设置值为15内联节点的数量(InlineCount)大于二级门槛大小并且该节点包含的平均文本数量不超过5个字的大小，则设置为10，否则设置为30规则6：对于其他情况的节点，DoC属性值的设定根据该节点的所有子节点的DoC属性值的最大值(DoCMax)，该节点包含的内联节点的数量(InlineCount)以及预定的门槛值大小来确定，具体规则如下：内联节点的数量(InlineCount)小于一级门槛大小，设置值为DoCMax+10；内联节点的数量(InlineCount)大于一级门槛小于二级门槛大小，设置值为DoCMax+15；内联
7、节点的数量(InlineCount)大于二级门槛大小，设置值为DoCMax+30；在上面的疑似分割权重度规则中需要使用到门槛大小以及内联节点的数量，这里我们做以下两个规定：规定1：一级门槛大小设置为20，二级门槛大小设置为45规定2：内联节点数量的计算规则是该节点中包含的内联节点的数量，但是不包括该节点的子节点中包含有display:none等样式设置的元素节点的内联节点数量。基于上面的分块规则，其算法的具体实现步骤（递归处理）如下：（1）遍历DOM树，如果该节点是最小原子块，则为其添加DoC属性，设置其值为0；否则转向(2)（2）如果该节点里面的所有元素都是内联节点，则为该节点添加DoC属性
8、，设置其值为0；否则，转向(3)（3）如果一个节点是虚拟文本节点，则为该节点添加DoC属性，设置其值为0。（4）遍历DOM树，对于该DOM树中的每一个节点，如果该节点不存在DoC属性，但是它的所有子节点都包含有DoC属性，则转向（5）-（11）处理，否则转向（12）；（5）如果当前节点只有一个有效的孩子节点，那么该节点的DoC属性值等于他的孩子节点的DoC属性值。否则转向（6）（6）获取当前节点的所有子节点的DoC属性值的最大值(DoCMax)，以及当前节点包含的内联节点的数量(InlineCount)，该两个参数作为该节点DoC属性值判断的依据。（7）如果InlineCount小于一级门槛大
9、小(FIRST_THRESHOLD)，则转向（8）,否则转向(9)；（8）如果DoCMax=0，则将该节点的DoC属性值设置为5。否则，将节点的DoC属性值设置为DoCMax+10；（9）如果InlineCount小于二级门槛大小（SECOND_THRESHOLD），则转向（10），否则转向（11）；（10）将该节点的DoC属性值设置为DoCMax+15；（11）如果DoCMax=0并且TextLen/InlineCount（12）递归遍历该节点，直到找到满足条件（4）的节点，然后按照步骤（5）-（11）进行处理。参考文档：VIPS:基于视觉的Web页面分页算法注：在该算法思想中借鉴了VIPS算法中相关定义，比如有效节点，Inline节点，文本节点，疑似分割概率DoC和PdoC等。在网页分块的疑似分割权重度规则中对于规则1，规则3，规则4也是借鉴了该算法。同时对于节点的DoC属性值的界定以及一级门槛和二级门槛的设定均是来自对大量网站进行反复测试的经验值。
