支持语义耦合的设备自适应网页布局算法2.0.doc

支持语义耦合的设备自适应网页布局算法 1.技术领域 本发明主要针对现有移动终端网络浏览显示需自适应设备能力的问题, 采用最小自由度优先规则，结合网页实际语义结构，在产业界和学术界现有网页分割算法的基础上，提出局部语义耦合度和全局语义耦合度理论，设计适应设备能力的语义最小自由度优先S-LFF(Semantic Least Freedom First)布局算法和递归语义最小自由度优先RS-LFF(Recursive Semantic Least Freedom First)回溯算法。 2.背景技术 现有的移动终端网页浏览存在着设备适配能力差、可移植性弱、访问速度较慢等缺点。基于WAP的浏览需求作者额外的重新创作且界面表示能力弱，无法展现现有丰富的WWW网页资源。传统基于网页分割的解决方案对网页结构性能要求过高且忽略了网页内部的语义结构。基于内容折叠的解决方案适用于大量文本存在的网页结构，对复杂元素存在的网页结构表现不良。 网页分割技术是将基于HTML的网页转化为基于DOM的文档表示结构。在对DOM的遍历过程中根据一定的规则将不同的Tag和所属Tag的信息分为不同的组群，从而达到分割网页的效果。显示网页分割技术只搜索已定义的标志性Tag完成分割。隐式分割技术在显示分割的基础上，搜索隐藏的内容分隔符如大段空白，分隔符，装饰图片等。 最小自由度优先规则源于VLSI中的布局思想，自由度表示电路模块空间选择能力的大小。在电路模块布局过程中选择自由度最小的布局选择使得总体电路模块所占空间最小且连线长度最短。 网页内容的矩形化在基于网页分割的基础上，以一个或多个DOM节点为一组，将其表示的内容在页面上的显示区域抽象化为矩形模块。与VLSI布局中的电路模块相比，具有方向不可变更，在一定范围内具有语义耦合关系等特点。 本项技术主要在网页内容矩形化的基础上，采用最小优先度规则，提出了局部语义耦合度和全局语义耦合度理论，设计语义最小自由度优先S-LFF(Semantic Least Freedom First)布局算法和递归语义最小自由度优先RS-LFF(Recursive Semantic Least Freedom First)回溯算法。 其中布局规划用到了以下基于VLSI的布局定义： 格局 对于给定的被填入矩形，格局表示3元组。其中k表示格局的第k个状态，表示格局中的填入矩形序列.表示格局未填入的矩形序列。表示间以及同间形成的角序列。填入动作即更改格局为. 角 已知2个矩形模块， (矩形框边界也可看作特殊的矩形)。任取，中一边交于一点或延长线交于一点O。则边或延长线与点O构成一个角。成角关系分为相邻成角关系，其距离为0；相交成角关系，距离按照水平或平行函数计算；延长成角关系，距离按照欧式距离计算。 合法填角 对于一个待填矩形，如果将格局演化成格局，并且本身不和任何相交。那么称这个矩形的动作为合法填角动作。 支持语义耦合的设备自适应布局算法很好地解决了网页浏览上下文环境的问题且可以针对不同的设备能力进行不同的布局选择。其在网页矩形化的基础上，赋予不同矩形不同的语义系数；在最小自由度优先的规则下，根据算法计算不同矩形之间的语义联系并进行最优排列。 3.发明内容 本发明提出了Web-VLSI规划问题定义，使用五元组表示矩形化的网页模块，计算局部语义耦合度和全局语义耦合度，并根据S-LFF算法和RS-LFF算法对网页模块进行优化排列。具体实现过程如下： 网页内容矩形化过程： 1.网页模块表示五元组：。将采用网页分割算法后得到的组群使用不同的五元组表示。其中五元组中元素按顺序表示：左上顶点横坐标，左上顶点纵坐标，模块宽度，模块高度，语义联系系数。 2.在分割算法中根据网页原有语义关系为五元组中的赋值。要求满足以下条件: , ,其中brother函数为取相应节点的sibling, Parent函数为取相应节点的Parent，abs为取相应值得绝对值。 3.定义Web-VLSI规划问题，求解五元组序列满足： 1）对于所有，或者 2）对于所有, 3）对于,且. 根据S-LFF算法计算局部语义耦合度 1.在得到表示网页的五元组序列后，首先计算模块间紧密度. . 其中odis函数取两点欧式距离，horizontal函数取两平行矩形水平距离，vertical函数取两平行矩形垂直距离。 2.其次计算局部语义耦合度.其中w1,w2为权重系数，取值范围在0到1之间。 3.对所有的合法填角动作，计算序列，选择最优合法填角动作即具有的填角动作。更新格局继续1,2步迭代，直到布局完成。 根据RS-LFF算法计算全局语义耦合度 1.在格局和待填矩形基础上。计算局部最优填角动作产生的格局,并依次迭代产生格局序列，满足最终格局。 2．对最终格局PN，此时总面积。其中为矩形模块最大的长度