（计算机应用技术专业论文）基于网页分块思想的搜索引擎索引系统.pdf

中文摘要 现有的搜索引擎都是对整个页面建立索引并用于检索的，但某些页面中可能 包含不同的主题块，如果用户提交的多个关键词恰好分别位于不同的主题块内， 则即使页面与用户检索请求不相关，搜索引擎仍会把该页面返回给用户。 为改进搜索引擎的索引系统，引入了网页分块的思想。本文选择了v i p s 算 法作为网页分块算法，但经典v i p s 算法在实际应用中存在着切分粒度不好控制 的问题，针对切分过粗和切分过细两种情况，本文分别引入了节点深度阈值和叶 子节点数目阈值，使得v i p s 算法可以根据页面特征进行切分粒度的自适应。在 三大门户网站爬取页面作为测试集，通过改进算法与经典算法的对比试验，证明 了改进算法的有效性。 对给定网页先行分块，并基于块内容将主题相关的块合并为子文档，然后再 对各子文档分别建立索引。这样只有当用户提交的多个关键词完全包含在某个子 文档内时，搜索引擎才会把原页面返回给用户。基于网页分块，设计了改进的搜 索引擎索引系统，制定了一些规则过滤与正文无关的块，并对剩下的块进行分类。 最后，通过拟定三组种子关键词组，并向g o o g l e 提交查询得到测试集，将该集 合与索引改进后的检索结果进行比较。实验证明，本文所提供的索引方案较大程 度上提高了检索的准确率和f 1 测试值。 关键词：网页分块索引系统分类搜索引擎 a b s t r a c t e x i s t i n gs e a r c he n g i n e si n d e xe v e r yp a g e a saw h o l ea n du s et h e mf o r i n f o r m a t i o nr e t r i e v a l ，b u ts o m ep a g e sm a yc o n t a i nb l o c k sa s s o c i a t e dw i t hd i f f e r e n t t o p i c s ，t h e r e f o r e ，i ft h ek e y w o r d su s e rs u b m i t t e da to n et i m ea r ej u s tl o c a t e di nb l o c k s w h i c hh a v ed i f f e r e n tt o p i c s ，s e a r c he n g i n e sw i l ls t i l lr e t u r nt h e s ep a g e st ou s e re v e ni f t h e ya r en o ta c t u a l l yr e l e v a n tt ot h eu s e rn e e d t oi m p r o v et h es e a r c he n g i n ei n d e x i n gs y s t e m ，t h ep a g es e g m e n t a t i o na p p r o a c hi s i n t r o d u c e di n t ot h i sp a p e r v i p sa l g o r i t h mi sc h o s e na st h ep a g es e g m e n t a t i o n a l g o r i t h m , b u tt h ec l a s s i c a lv i p sa l g o r i t h mh a st h es h o r t c u to fh a r dt o c o n t r o l s e g m e n t a t i o ng r a n u l a r i t yi np r a c t i c a la p p l i c a t i o n s a st ot h ep r o b l e m so fs e g m e n t a t i o n t o oc o a r s e l yo rt o of m e l y , t h i sp a p e ri n t r o d u c e st w op a r a m e t e r s ，t h r e s h o l do fl e a f n o d e s d e p t ha n dt h r e s h o l do fl e a fn o d e s n u m b e r , t oa u t o m a t i c a l l yc o n t r o lt h e s e g m e n t a t i o ng r a n u l a r i t yb a s e do nt h ef e a t u r e so fe a c hp a g e w e bp a g e sc r a w l e df r o m t h r e em a j o rp o r t a ls i t e sa r et a k e na st e s ts e t a n dt h ec o m p a r a t i v ee x p e r i m e n t a lr e s u l t s v a l i d a t eo u ra p p r o a c h a f t e rag i v e np a g eb e i n gs e g m e n t e di n t os e v e r a lb l o c k s ，t h o s eu n r e l a t e dt om a i n t e x ta r ef i l t e r e db yp r e s e th e u r i s t i c sr u l e s ，a n dt h er e s ta r ec l a s s i f i e di n t od i f f e r e n t s u b d o c u m e n t sb yt h e i rt o p i c s t h ei n d e x i n gi sb u i l to nt h e s es u b d o c u m e n t ss ot h a t o n l yw h e nt h ek e y w o r d sl a s e rs u b m i t t e da r ec o n t a i n e di nas u b d o c u m e n tc o m p l e t e l y , t h es e a r c he n g i n ew i l lr e t u mt h eo r i g i n a lp a g et ot h eu s e r f o rt h r e eu s e rq u e r i e s ，t h e i n i t i a lr e s u l t sr e t r i e v a l e df r o mg o o g l ea r ec o m p a r e dw i t ht h es e a r c hr e s u l t so f i m p r o v e di n d e x i n gs y s t e m , w h i c hs h o w st h a to u ra p p r o a c hg e t sah i g h e rp e r f o r m a n c e i nt e r m so f p r e c i s i o na n df 1 一m e a s u r e k e y w o r d s ：p a g es e g m e n t a t i o n ，i n d e x i n gs y s t e m ，c l a s s i f i c a t i o n , s e a r c he n g i n e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得：苤鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：z f 。诤 签字日期：川年月年日 学位论文版权使用授权书 本学位论文作者完全了解鑫盔盘堂有关保留、使用学位论文的规定。 特授权丞生盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：叩锑 签字日期：砂p 1 年月4 日 聊虢j 7 平毫 签字日期：p ( 年月午日 天津大学硕士学位论文第一章绪论 第一章绪论 1 1w e b 页面区域划分研究的背景及意义 随着i n t e m e t 的发展，万维网已经成为巨大的，并且分布广泛的信息源。它 涉及新闻、政治、体育、教育、军事等多方面信息。而在我国，它的发展尤为迅 猛。2 0 0 9 年1 月1 3 日，中国互联网络信息中心( c n n i c ) 在京发布了第2 3 次中国互联网络发展状况统计报告【i j 。报告显示，截至2 0 0 8 年底，我国互联 网普及率以2 2 6 的比例首次超过2 1 9 的全球平均水平。同时，我国网民数达 到2 9 8 亿，其中宽带网民数达到2 7 亿，国家c n 域名数达1 3 5 7 2 万，三项指 标继续稳居世界排名第一。同时，随着3 g 时代的到来，无线互联网将呈现出爆 发式的增长趋势。而在网络求职、网络购物等实用型互联网应用率大幅增长的同 时，网络音乐、网络视频等娱乐型应用的使用率所占比重则呈现下行趋势，我国 互联网正经历着由娱乐化应用向价值应用时代的转变。 由于当前网络内容爆炸性增长，为了更好的利用w e b ，本文越来越多的使用 搜索引擎，并且为了随时能够登录w e b ，人们也越来越多的利用手机、p d a 等 小屏幕手持设备移动上网【2 1 。当前条件下，人们均是通过向搜索引擎提交查询关 键字来进行检索 3 】，但是目前的结果并不很令人满意，尤其是在同时检索多个关 键词的时候，有时返回的页面相关性8 r d , t 4 1 。 发生这种现象的原因之一是搜索引擎选择的索引文件过于庞大【5 】，其中很多 与检索关键字相关性不大，或者包括的内容质量不高。经分析发现主要是因为 w e b 页面中通常包括多类不同主题的信息【6 】，如页面正文、导航信息、交互信息、 广告等等。但是目前搜索引擎主要是对整个页面内容建立索引，因此引入了很多 无关信息。为了减少无关信息对检索结果的影响，本文需要对页面进行结构分析， 以使搜索引擎针对页面不同主题的内容分别建立索引，页面结构分析也可作为信 息抽取的预处理过程。与信息检索类似，对页面主要内容进行抽取显然比对整个 页面内容抽取的效率和准确性高【_ 7 1 。 此外，页面区域划分，在w e b 页面适应( w e bp a g ea d a p t a t i o n ) 和页面清洗( p a g e c l e a n i n g ) 方面也有重要作用。页面适应是指将页面内容如何在p d a 、手机之类 的小屏幕电子设备上显示【8 】。因为这些设备屏幕较小，所以需将页面内容分成不 同部分，然后按照一定的顺序依次显示在屏幕上。而页面清洗是指从w e b 页面 天津大学硕士学位论文第一章绪论 中划分出更精确的信息单位【9 】，并根据检索、分类等后续应用的需求，将页面中 不需要的部分去除，将需要的部分提取出来。通过对页面进行主题区域划分，可 以将页面分主题区域地在手持设备上显示，也可以只返回核心主题的内容给访问 者。 随着互联网的蓬勃发展，通过对页面进行主题区域划分，既可以节省浏览者 的时间，又能准确迅速地引导潜在用户通过搜索引擎检索到目标页面【l0 1 ，对于用 户体验和网站的实际利益都具有较大的提升，因此，对页面区域划分和页面结构 分析进行研究是有着重大意义的，并在实际生活中具有广泛的应用价值。 1 2 国内外研究现状 w e b 页面语言为标记语言，通过对文本文档等进行标记和标注，浏览器可以 方便的进行解析。该过程中使用的标记则指明了在显示被标注的文本时，采用什 么样的格式。因此，w e b 页面文件中，除了页面信息外，亦包含了很多标记，这 使得w e b 页面文件不同于传统文档和具有统一数据结构的数据库文件，本文称 页面文件的这种特征为半结构特征。由于页面文件具有半结构特征，本文对其进 行自动结构分析就比较困难。w e b 页面区域划分即通过显式或隐式的方式在页面 上分割出不同的部分，且每部分的轮廓为矩形区域，每个区域中的内容也有一定 的语义含义，譬如文本信息、超链接信息、图像信息等等】，因此对w e b 页面 进行可视化分析就是一个将页面文档中的结构特征抽取出来，并利用这些特征对 页面进行区域划分的过程。而结构特征的抽取主要是依据页面文档中存在的标记 及对标记间的相互关系进行分析来完成。 对页面文档进行自动结构分析比较困难，国内外在w 曲页面可视化领域进 行了大量的工作，使用各种不同的方法来解决相关问题。主要有传统的模板化分 块方法和非模板页面分块方法。 传统的模板化分块方法需要人工制定分块规则，即模板。但模板的获取是费 时费力且需要较高智能的工作，往往只能适用于特定网站。常见的模板化分块方 法有： s o n g 1 2 通过记录页面中分隔标记出现的频次来决定如何抽取页面内容：根 据在一定位置上出现分隔标记的频次来对页面进行区域划分。但是由于很多标记 都具有分隔的作用，一方面不同的标记在页面上会表现出相同的效果，另一方面 相同的标记由于出现的顺序不同，在页面上也会表现出不同的效果，所以仅仅从 分隔标记出发进行内容抽取，不但繁琐，而且准确率不高。 c h e l a t l 3 】提出基于功能的对象模型( f u n c t i o nb a s e do b j e c tm o d e l ) 方式对页面 天津大学硕士学位论文第一章绪论 内容抽取的方法，在p d a 设备屏幕上显示页面。它将不可分的标记定义为基本 标记，然后根据标记在页面中的显示内容和作用的不同，把简单标记组合为不同 种类的复杂标记，逐步表示出页面内容的层次结构。但是因为复杂标记的生成规 则不很明确，给算法的实现带来不便。 非模板分块方法是最近研究的主要方向，它主要可以分为基于纯d o m 树、 基于统计和基于视觉三个方向【i4 】。常见的非模板分块方法如下： 哥伦比亚大学自然语言组的m c k e o w n 等人的算法【l5 】依靠统计w e b 页面中 的文本数来发现最大主体块并对文档内容归类。这种方法适用于简单的页面，而 对于多主体文档的处理，尤其包含随机分布的广告图片的文档，会产生噪音或不 准确的结果。 r a b m a n e l 6 等人提出另外一种技巧就是使用结构分析、语义分析和归纳的方 法：首先分析一个h t m l 文档，然后再将其适当地分解为一些小的子块。最后 分别提取和归纳这些单个部分的内容。然而，这个提议目前还没有实现。此外， 他们的提议只是为页面分析提出了前提条件，并没有提出具体的实现方法。 c h e n 【l7 】等提出了一种基于“图像定位 的页面区域划分方法，通过对页面 中各部分内容在屏幕中位置、长和宽的不同，来划分出多个区域，该方法能很好 地运用到p d a 等小屏幕设备中，但是对于w e b 挖掘、信息检索( 瓜) 等领域而言， 要从“图像定位”的角度对页面结构进行分析处理还比较困难。 f i n n 1 8 1 等提出了一种使用单文章源的方法，该方法将单一页面分解成文本与 标签，使用边界对文档页面进行分割。这样使得大部分标签位于外部区域，大部 分文本位于正文区域，这种方法对只有一个主体部分的文档比较适用，但它破坏 了h t m l 页面的结构，不适用于多主体文档，而且在处理多主体文档时，算法 时间复杂度是与主体块数目相关的多项式时间复杂度。譬如在处理具有8 个主体 的页面时，其时间复杂度是o ( n8 ，【1 9 1 ，实际使用有较大限制。 北京大学的张志刚等人提出的算法则需要有一组启发式规则为先行基础，利 用信息检索的技术，并根据w e b 页面的特征，对网页内容的主题及其主题相关 内容进行信息抽取，从而进行页面内容划分，找到页面主体内犁2 0 1 。该方法必须 对w e b 页面采用一种人为的启发式规则来进行分类，而且只对一些较为明显的 主题型页面有一定的效果，并不能自动对其他类型的页面产生效果，对于广告内 容的区分效果也不够好。 另外，还有许多方法用于格式化w e b 页面，以适应在一些小屏幕设备上显 示，这些方法包括o p e r a 浏览器洲和b i s t r e a mn u n d e r h a w k 【2 2 】。然而，它们需要 对w e b 页面的内容重新组织，而且需要用户滚动屏幕对内容进行浏览寻找。 尽管在w e b 页面可视化领域有很多人员在进行研究，也提出了一些方法， 天津大学硕士学位论文第一章绪论 但尚未有很好的可广泛应用且正确率高的方法。并且，当前的研究主要集中在页 面净化和页面适应上，对这项技术在日常搜索引擎中的应用基本没有考虑到，上 述各种方法出发点都是如何在手持设备上优化浏览体验，至今尚未有人为提高日 常搜索引擎检索准确度而进行w e b 页面区域划分技术研究。 1 3 本文研究内容 本课题研究针对w e b 页面，如何根据其页面内容所属的不同主题而对该页 面进行区域划分。本文内容分为如下几个研究方面： 1 、从互联网上选取典型网站，并使用网络爬虫从中爬取页面作为数据集， 对数据集进行深入分析，以明确当前w e b 页面流行的结构，并对未来w e b 页面 的发展方向进行探讨，这样可以尽量提高本文研究内容的适用性。 2 、深入研究h t m l 、x m l 和x h t m l 语言，并了解了d o m 技术，对d o m 树结构进行了学习，同时就如何生成w e b 页面的d o m 树结构进行了研究，并 对当前流行的处理d o m 树结构的方法进行了分析和比较。 3 、对经典v i p s 算法进行了研究，并对其进行改进，利用改进后的算法来 对w e b 页面的不同区域进行自动划分，并抽取出各部分的内容，进行实验，验 证划分可靠性。 4 、将上述算法运用到搜索引擎索引中来，为搜索引擎构建了一个改进的索 引系统，通过实验对页面先行分析和未分析直接建立索引两种情况下，在搜索引 擎中的检索效果进行比较。 1 4 论文的组织 全文共六章。 第一章，介绍研究课题的背景与意义，并对国内外研究现状进行分析，提出 本文所要做的工作。 第二章，分析当前页面结构，介绍d o m 的定义及d o m 技术的主要特点， 接着分析d o m 如何对h t m l 页面进行分析，如何构建d o m 树，最后对经典 v i p s 算法进行介绍。 第三章，对经典v i p s 算法进行改进，以自动对w e b 页面进行更有效的区域 划分，并用实验证明其有效性。 第四章，根据改进的v i p s 算法，结合页面语义处理构建搜索引擎的改进的 索引系统，对给定w e b 页面，可以得到其内部蕴含的不同主题子文档集。通过 天津大学硕士学位论文 第一章绪论 对各子文档分别建立索引以提高搜索体验。 第五章，以g o o g l e 检索特定关键词组得到的结果为测试集，进行改进的索 引系统与g o o g l e 索引系统的对比实验，证明改进的有效性。 第六章，总结本文取得的成果，分析现有工作中的不足之处，对后续研究进 行展望。 天津大学硕士学位论文第二章相关技术研究 第二章相关技术研究 2 1 当前w e b 页面结构分析及语言规范 要对w e b 页面进行区域划分，首先需要对页面结构进行分析，页面结构分 析在页面区域划分、信息检索、页面分类与适应等多方面都有重要作用。 w e b 页面一般都由h t m l e 2 3 1 ( h y p e rt e x tm a r k u pl a n g u a g e ，超文本标记语 言) 写成，w 3 c 组织虽然对h t m l 语言制定了相关的规范，但并未严格要求遵 循，因此纵观当前万维网，绝大部分h t m l 页面都是无结构或半结构化的文本， 在这些文本中同时包含有大量的标记、超链接及其他元素，且相当一部分并不遵 循w 3 c 规范，要对这样复杂的页面进行自动处理是比较困难的。在认识到这一 点后，w 3 c 又推出了x m l 2 4 】( e x t e n s i b l em a r k u pl a n g u a g e ，可扩展标记语言) 和x h t m l 【2 卅( e x t e n s i b l eh y p e rt e x tm a r k u pl a n g u a g e ，可扩展超文本标记语言) 规范，相比h t m l 规范，这两种规范更加严密，并要求严格遵循其格式，如果 能将普通的h t m l 页面文本转化为x m l 或者x h t m l 语言文本，则机器处理难 度就小了很多，所以，本文首先在w e b 页面结构分析上及相关语言规范上进行 了研究。 2 1 1h t m l 语言介绍 h t m l 语言是网页的通用语言，本文将首先对其进行介绍。 w 3 c 组织对h t m l 语言的定义是“为了发布全球化信息，人们需要一种通 用的礼节性语言，一种所有计算机本质上可以理解的发布的母语，万维网使用 h t m l 语言作为其发布语言”。从w 3 c 的描述可以看出，h t m l 语言是目前w e b 上的官方描述语言，其用描述性标记符来对文档的不同内容进行区分。标记符是 将文本各个部分分开的分界符，可以将h t m l 文档分成不同的逻辑结构，如标 题、正文、表格等等。 h t m l 页面是由元素( e l e m e n t ) 构成的，元素本身有多种，它们的作用也 不同：有的用于描述文本，有的用于描述链接，有的用于制表等，元素整体指明 了页面的结构。每个元素都有名称及属性，大部分元素还有起始和结尾标记，本 文称具有这两个标记的元素为容器。元素起始标记为“起始链接标签( s t a r tt a g ) ”， 天津大学硕士学位论文第二章相关技术研究 可以在其中标明元素名称与属性，结尾标记为“结尾链接标签( e n d t a g ) 9 9 9 起始 与结尾标记中间的为元素体。例如标题元素( t i t l e ) ： 天外天影视天地 第一行为标题元素的起始标记，说明标题元素从此开始：第二行为该元素的 元素体：第三行为该元素的结尾标记。 h t m l 的不同标记间存在嵌套关系，如一般h t m l 页面都有类似下面的标 记嵌套结构： ，h e a d 元素和b o d y 元 素都被嵌套在h t m l 元素中，而h e a d 元素和b o d y 元素两者是平行关系，整个结 构恰如h c a d 和b o d y 是h t m l 树的两个叶子节点一样，因此本文可以用树状结构 来描述h t m l 页面的结构。对一棵h t 池结构树而言，其根节点总是h t m l 元素， 然后根节点含有n 个节点，每个节点对应页面中的一个标记，其中的父子关系 表示子节点嵌套于父节点范围之内。本文可以根据页面节点问的嵌套关系来构造 这样的结构树。 值得一提的是h t m l 文本本身只是普通的文档，并不包含图像、声音、视 频等多媒体元素，本文在浏览页面时之所以能看到这些元素，是因为h t m l 页 面文本中包含了指向这些多媒体文件的指针，即链接，然后浏览器自动下载播放 这些元素的缘故。 综上，人们可以利用h t m l 语言作为通用语言在万维网上发布多样化的资 源，诸如含有视频等多媒体资源的文档、含有可执行程序的文档或通过w e b 远 程处理本地事务。 2 1 2x m l 语言介绍 x m l 语言是可扩展标记语言，提到它就不得不提s g m l ( s t a n d a r d g e n e r a l i z e dm a r k u pl a n g u a g e ，标准通用标记语言) ，s g m l 语言具有很强的灵活 性，但其过于繁琐，x m l 语言就是w 3 c 组织在保证语言简洁性的前提下，为获 得s g m l 语言的灵活性而提出的。虽然x m l 语言只是s g m l 的一个受限形式， 却保留了s g 池语言的大部分功能和灵活性，具有s g 池常用的特性。 x m l 文档本身只是一种文本，一个x m l 文件就是遵循x m l 标准写就的文 本文件。由于其只是一个文本，所以易于创建与传播：使用任何文本编辑器均可 以书写它，而在不同平台间传输也十分容易，正是由于其规范严密及易于传输， x m l 标准在发布后就受到了人们的广泛欢迎和使用。 x m l 语言和h t m l 语言一样，也是使用标记来识别不同的元素，这样使得 天津大学硕士学位论文第二章相关技术研究 一份x m l 文件看起来很像h t m l 文件，但x m l 文件和h t m l 文件实质上是截 然不同的，不论从格式还是目的上：h t m l 文件是为了向w e b 浏览器描述如何 绘制显示一个w e b 页面，而x m l 文件则是为了说明存储在该文档内的数据，即 x m l 文件只是作为数据载体而存在。 2 1 3x h t m l 语言介绍 x h t m l 语言是x m l 和h t m 语言的混合物，它是为网络设备显示( 包括 w e b 浏览器、p d a 设备和移动电话) 特别设计的。w 3 c 组织于2 0 0 2 年1 月2 6 曰正式将x h t m l l 0 作为w e b 标记的新标准。 w 3 c 主管t i mb e m e r s l e e 这样评价x h t m l ：“x h t m 连接了现在的w e b 和将来的w e b ，它为网站和页面作者提供了进入结构化语言x m l 世界的桥梁， 同时依然能够保持与h t m i a 的可操作性。”并认为x h t m l 的主要优点在于其 可扩展性和可移植性。 可扩展性：x m l 文档要求格式严格规范，即元素必须正确嵌套。而使用 h t m l ，添加新的元素组需要更改整个d t d ( d o c u m e n tt y p ed e f i n i t i o n ，文档类 型定义) 。在基于x m l 的d t d 中，新的元素组只需内部一致并格式良好，就可 以添加到先有的d t d 中，这极大的简化了新元素集的开发与集成。 可移植性：现在人们越来越频繁的使用非台式设备对w e b 文档进行存取， 而在大部分情况下，这些设备并不具备台式机的计算能力，并且对格式不标准的 h t m l 文档进行处理易发生错误，因此，如果这些非台式设备没有接收到格式良 好的文档标记，它们可能根本无法对文档进行处理。而x h 砷血文档则具备了良 好的标记，因而易于移植。 x h t m l 页面举例如下： o x r n lv e r s i o n = ”1 0 ”e n c o d i n g = ”u t f - 8 ”? v n t u a ll i b r a r y m o v e d t o v l i b o r g 天津大学硕士学位论文第二章相关技术研究 从这个例子可以看出，首先，由于x h t m l 是以x m l 文档表示的h t m l ， 所以它必须在文档项部包含x 池声明及版本号：“ ”。而 x h t m l 文档必须由三组标准规则中一组来表示，这些规则存储在称为“文档类 型定义( d t d ) ”的文档中，它们可以验证x h t m l 文档的结构正确性。 x h t m l 文档必须包含文件头部区域，该区域包含头部起始标记( ) 和标题标记( ) ，然后以 结束。头部区域结束后是正文的起 始和结尾标记( ) ，在正文中可以放置传统的h t m l 编码标记， 但它们必须符合标准，否则不能与x h t m l 规范契合。x h t m l 文档最后以结尾 标记( ) 结束。 页面区域划分的第一步就是对w e b 页面进行结构分析，本节对当前通用w e b 页面结构进行了分析，对流行的页面语言及其结构进行了介绍。 2 2d o m 树结构研究 如上一节介绍的，h t m l 页面是一个树形结构页面，而本节介绍的d o m 树 结构则是研究h t m l 页面布局结构的重要根据。d o m 2 6 】全称是d o c u m e n to b j e c t m o d e l ( 文档对象模型) ，它定义了一组与平台和语言无关的接口，以便程序和脚 本能够动态访问和修改x m l 文档内容、结构及样式。将半结构化的h t m l 页面 转化为结构化的d o m 树结构，会对本文对页面的分析研究提供很大的帮助。 2 2 1d o m 技术介绍 w 3 c 认为d o m 是一个方便人们对h t m l x m l 文件进行操作的接口和平 台。通过d o m ，人们可以自动化的利用程序动态对h t m l x m l 文件内容及结 构进行存取和更新操作。d o m 本身由两部分构成：d o m 核和d o m 扩展，前者 主要定义了处理x m l 文件所需的功能，后者则定义了处理h t m l 文件所需的功 能。 d o m 是一种用于h t m l 和x m l 文档的应用程序编程接口，人们可以利用 d o m 模型自由的构造h t m l x m l 文档，并向其增加、修改或删除元素。d o m 本身是由组对象及对文档对象进行处理的接口构成。在d o m 中，本文将代表 h t m l x m l 文件的程序设计对象，称为节点( n o d e s ) 。当浏览器处理被链接的 h t m i j x m l 文件，并将其储存于d o m 中时，浏览器会为h t x ，文件的 每个基本组件建立一个节点，这些基本组件包括了元素、属性等，而d o m 也会 用不同形态的节点表示不同形态的x m l 组件。表2 1 介绍了几种常见的节点类 型【2 7 1 。 天津大学硕士学位论文 第二章相关技术研究 表2 - 1 常见的d o m 节点类型 节点形态 节点对象所代表的 节点名称( n o d e n a m e节点的值( n o d e v a l u e x m l 组件 对象属性)对象属性) 文件( d o c u m e n t )文件中的根节点( 代 # d o c u m e n tn u l l 表整个x m l 文件) 元素( e l e m e n t )元素 元素形态名称( 如 n u l l c a r ) 文本( t e x t )属于该节点父节点所 t e x t父x m l 组件上的文 代表的元素上的文本 太 属性( a t t r i b u t e )属性( 以及其他的名属性名称( 如属性值 ( 如 值对，如处理指令中 b i n d i n g ) h a r d c o v e r ) 的名字和值) 处理指令( p r o c e s s i n g处理指令( x m l 规范 处理指令的目标( 如除去目标之外整个处 i n s t r u c t i o n ) 中定义的或自定义的x m l 本身)理指令的内容 处理指令) 批注( c o m m e n t )批注# c o m m e n t 表示注释的内容 d o m 与编程采用的语言无关，即它具有语言独立性，它的编程接口是由符 合工业标准的i d l ( i n t e r f a c ed e f i n i t i o nl a n g u a g e ，界面定义语言) 描述，而不限 制实现这些接口所采用的语言。d o m 的核心思想是将面向对象( o b j e c t o r i e n t e d ) 的思想引入对h t m l x m l 文件的处理过程中。在d o m 技术没有出现之前，人 们把h t m l x m l 文件都认为是包含各种组件的数据集，所以都以面向数据的方 式管理文件。在d o m 技术出现并引入“对象”的概念后，h t m l x m l 的组件 除了包含数据之外，每个文件中的元素还包含有方法( m e t h o d ) 及属性 ( a t t r i b u t e ) ，而d o m 正是通过使用包含这些方法和属性的a p i 来存取访问文件 中的组件的。 2 2 2d o m 树结构 h t m l 文件一般都由标题( t i t l e ) 、文件头( h e a d ) 、正文( b o d y ) 及蕴含 在它们中的其他组件，比如超链接( h y p e r l i n k ) 等组成，而浏览器对h t m l 文 件中组件的解析顺序也一般与组件在文件中的存储顺序成正相关。本文利用 d o m 技术，通过对一个h t m l 文件进行解析，可得到其树形结构，本文称之为 该文件的d o m 树逻辑结构。 天津大学硕士学位论文 第二章相关技术研究 通过得到的d o m 树结构，本文可以准确描述该h t m l 文件中各组件的相 对位置与逻辑关系，可以大大降低对于像w e b 页面这种半结构化文档的自动分 析难度。由于一般的h t m l 文档语法上都可能不合w 3 c 规范，标记的对应上可 能存在错误，所以本文首先要将h t m l 文件规范化，然后通过语法分析器完成 h t m l 文档到d o m 树结构的转化。值得一提的是，这种转化是可以双向完成的， 即有了d o m 树结构后，也可以还原该h t m l 文档，可见，d o m 树结构是很方 便的，计算机易于处理，并能够恰当的表示h t m l 文档。 d o m 在对h t m l 文件进行解析时，将文件看成一棵树，其根节点是 组件，而文件中的其他组件则被看成子节点， 为整棵树的结束。子节点 本身也可以作为父节点来包含其他子节点，也可以作为其他节点的子节点，具有 同一个父节点的子节点之间称为兄弟节点。下面是一个示例文档及其对应的 d o m 树结构： t r e e s ，t r e e s ，e v e r y w h e r e t r e e s ，t r e e s ，e v e r y w h e r e c o m ea g a i ns o o n 口 r r _ r l _ l l r i r _ _ l r _ 上 i 器嚣1 嚣怒1一一一i 图2 - i十h t m l 文挡机器对心的d o m 树结构 由上述文档发对应d o m 树可以看出首先树的根节点是 而 和 是 的子节点，而 正有自己的子节点 肢孙节点， 也同洋有两个了节点 和 。虬及对应的孙节点；整个页而结构 目了然十分清晰。要对页面进行操作也变得很简单本文只需耍操作对应的节 点部分即可。比如漆加段话，本文h 需要生成1 个新的节点并将其插入特定 节点b 可，而删际和更改也同样方便。率之还可咀对网页视图进行重构，改变其 结构，但是不改变网页的内容。同时利用生成的d o m 树本文a r 咀从其上根 据自已的需求导出或生成”种代表该文档某些特征的新的结构， 2 2 3d o m 树的操作 从d o m 的角度看来h t m l x m l 文档就是由节点对象构成的树，所谓的 节点对象不仪表示了馥文档中出现过的元索，也包拓了文档巾的其他内窖比如 文档中的属性、数据和注释都被包含进节点对象0 4 了。d o m 的操作是针对树上 的竹点来进行的，前见的节点类型共有1 2 种它们是：e l e m e n t 、a t t r i b u t e 、 乃x t 、c d 一弼s c c t i o n ，c o m l n e n t 、d c 4 2 l l m e n t 、d o c u m e m t y p e ，d o c t t r n e n t f r a g m e n t 、 p r o c e s s i n g l n s t r u c t i o n 、e n t i t y 、e n t i t y r e f e r e n c e 和n o t a t i o n 。每个节点都有自己的 操作接1 2 这些接，节点代表的内容一对应，事实上这些操作接口本身也 是节点。通过这蝗接u 本文可以对文档树进行节点的增删修改树的结构或 者对文档树进行导航。d o m 是一种与平台和语言无关的接口，它允许程序和删 天津大学硕士学位论文第二章相关技术研究 本动态访问和修改文档的内容结构和类型。它定义了一系列的对象和方法对 d o m 树的节点进行各种随机操作。比如d o c u m e n t 对象，作为树的最高节点， 它是对整个文档进行操作的入口；e l e m e n t 和a t t r i b u t e 对象，它们是文档某一部 分的映射，节点的定级层次恰好反映了文档的结构；t e x t 对象，则作为e l e m e n t 和a t t r i b u t e 对象的子节点，表达了元素或属性的文本内容，而且它不再包含任何 子节点。事实上，节点类型决定了节点是否允许包含子节点，表2 2 列出了每种 节点的子节点类型【2 引。 表2 2 节点及其允许的子节点 节点类型允许的子节点的类型 d o c u m e n t c o m m i t 、d o c u m e n t t y p e 、e l e m e n t 、p r o c e s s i n g l n s t r u c t i o n d o c u m e n f f m g m e n tc d a t a s e c t i o n ，c o m m e n t ，e l e m e n t ，e n t i t y r e f e r e n c e ， p r o c e s s i n g l n s t r u c t i o n 、t e x t d o c u m e n t t y p e n u l l e l e m e n t c d a t a s e c t i o n 、c o m m e m 、e l e m e m 、e n t i t y r e f e r e n c e 、 p r o c e s s i n g i n s t r u c t i o n 、t e x t c o m m e n tn u l l t e x tn u l l a t t r i b u t e t e x t 、e n t i t y r e f e r e n c e e n t i t y r e f e r e n c ec d a t a s e c t i o n ，c o m m e n t ，e l e m e n t ，e n t i t y r e f e r e n c e ， p r o c e s s m g l n s t r u c t i o n 、t e x t e n t i t yc d a t a s e e t i o n 、c o m m e m 、e l e m e n t 、e n t i t y r e f e r e n c e 、 p r o c e s s i n g l n s t r u c t i o n 、t e x t c d d a s e c t i o n n u l l n o m f i o nn 嘎j l l p r o c e s s i n g n s a - u c t i o n n u l l 如果程序在处理子节点的时候出现错误，比如将一个n o t a t i o n 节点插入t e x t 节点作为后者的子节点。d o m 就会抛出一个异常，以提示该操作非法。事实上， 在使用d o m 解析器进行解析操作的时候，h t m l x m l 文档会被立即处理并保 存在内存中。在这个过程中，很多东西都会出现错误。大多数d o m 下的异常都 是作为d o m e x c e p t i o n 类的一个实例发生的。这个类支持1 5 种不同的、具体的 异常条件。每种条件都被指定为d o m e x c e p t i o n 类的一个成员，叫做c o d e 。除了 这个c o d e 成员，d o m e x c e p t i o n 类还包含一组1 5 个静态成员，它们被用来确定 天津大学硕士学位论文 第二章相关技术研究 异常的条件。在c o d e 中指定的1 5 种异常条件如表2 3 所示。 表2 3 在c o d e 中指定的异常条件 发生e x c e p t i o n 对应代码 对产生错误的说明 i n d e x s i z e e r r 说明数组或字符串下标的溢出错误。 d o m s t r i n g s i z e e r r 说明请求的文本太大，文本的指定范围不适 合d o m s t r i n g 。 h i e r a r c h y _ r e q u e s t _ e r r 说明发生了要把节点放在文档树层次中的不 合法位置的操作。 w r o n g 。d o c u m e n t e r r 说明发生了从创建节点的文档以外的文档使 用使用该节点的操作。 i n v a l i d c h a r a c t e r e r r 说明( 比如在元素名中) 使用了不合法的字 符。 n o d a t a a l l o w e d e r r 为不支持数据的n o d e 指定数据。 n o m o d i f i c a t i o n 。a l l o w e d e r r 说明发生了修改只读的、不允许修改的节点 的操作。 n o j o u n d e r r 说明在期龌的位置没有找到指定的节点 n o t s u p p o r t e d 。e r r 说明当前的d o m 实现不支持某个属性或 方法。 i n u s e a t i r