（控制理论与控制工程专业论文）基于块文本长度的网页主题信息抽取算法.pdf

ad i s s e r t a t i o ns u b m i t t e dt o s o u t h e a s tu n i v e r s i t y f o rt h ea c a d e m i cd e g r e eo fm a s t e ro f e n g i n e e r i n g b y m a s h e n g s u p e r v i s e db y a s s o c i a t ep r o f s h a 0j i ay u s c h o o lo f a u t o m a t i o n s o u t h e a s tu n i v e r s i t y m a r c h2 0 1 0 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示了谢意。 研究生签名：兰盥 e l 期：弘，口午，2 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名：曼盛王导师签名：e l 期：即他午f 摘要 摘要 随着i n t e m e t 的飞速发展，w e b 已经发展成为一种巨大的、分布式和共享的信息资 源。目前w e b 数据大多以h t m l 页面的形式出现。由于h t m l 语言的半结构化特征， 以及嵌入网页的各种广告信息等原因，给基于网页内容的应用搜索引擎带来很多困 难。因此，需要研究一种有效的获取网页信息的方法。 本文通过对大量主题型网页的分析，发现主题型网页一般采用大段的文本来描述一 个或多个主题。在h t m l 的d o m 树形结构中，这些描述主题的文本信息通常分布在一 些离得比较近的块节点下。通过对现有的各种网页信息抽取算法分析基础上，结合主题 型网页的特点，本文提出了一种基于h t m l 块文本长度的网页主题信息抽取算法。然 后在用于解析h t m l 的开源项目h t m l p a r s e r 基础上实现了这个算法。 具体地，本文的主要工作有： 1 完善了关于网页分块的理论与相关概念，提出了块文本的概念。 2 通过分析不同类型网页的特征，提出了一种用于辨别网页类型的网页统计模型。 通过编程获取大量的基准网页，然后经过统计实验获得一种判断主题型网页的 方法。 3 通过分析w e b 全文搜索引擎的分析子系统和查询子系统中与网页数据直接或 间接关联的关键功能模块，提出了一种方便实用的网页结构化模型。 4 在网页分块理论的基础上，提出了一种基于块文本长度的网页主题信息抽取算 法。使用j a v a 语言编程实现了这个算法，并通过实验证明该方法切实可行，具 有较高的准确率。 5 在本文提出的的网页信息抽取算法、网络蜘蛛程序h e r i t r i x 、索引工具l u c e n e 、 m v c 框架s t r u t s 2 以及n j a x 等基础之上实现了一个全文搜索引擎一东南大学 校园搜索引擎。 关键词：网页分块，h t m l p a r s e r ，网页类型，网页统计模型，网页结构化模型， 信息抽取 c o n c e p to fb l o c kt e x t 2 b ya n a l y z i n gt h ec h a r a c t e r i s t i c so fd i f f e r e n tk i n d o fw e bp a g e s ，p r o p o s e sa w e b - p a g es t a t i s t i c a lm o d e lw h i c hi su s e dt oi d e n t i f yp a g et y p e a c c e s st oal a r g en u m b e r o fb a s ep a g e s ，a n dt h r o u g ht h es t a t i s t i c a le x p e r i m e n tt oo b t a i nam e t h o dt od e t e r m i n et h e t h e m e b a s e dp a g e s 3 t h r o u g ht h ea n a l y s i so ft h ek e yf u n c t i o nm o d u l e sw h i c hr e l a t e dt ot h ew e bp a g e d a t ad i r e c t l yo ri n d i r e c t l y , p r o p o s e sac o n v e n i e n ta n d p r a c t i c a lw e b - p a g es t r u c t u r a lm o d e l 4 a na l g o r i t h mi sp r o p o s e db a s e do nt h el e n g t ho fb l o c kt e x ta f t e rp a g eb l o c kt h e o r y i sa n a l y z e di nt h i sp a p e r u s ej a v al a n g u a g ep r o g r a m m i n gr e a l i z e dt h i sa l g o r i t h m ，a n d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h i sm e t h o di sf e a s i b l ea n dh a sh i g ha c c u r a c y 5 b a s eo nt h ew e bp a g e si n f o r a m t i o ne x t r a c ta l g o r i t h m ，i n t e m e ta r c h i v e sw e b c r a w l e rh e r i t r i x ，i n d e x i n gt o o ll u c e n e ，m v cf r a m e w o r ks t r u t s 2a n da ja xt h i s p a p e r i m p l e m e n t saf u l l - t e x ts e a r c he n g i n e s e us e a r c h i n g k e yw o r d s ：w e b p a g es e g m e n t a t i o n ，b l o c kt e x t ，h t m l p a r s e r , w e b p a g et y p e ，w e b p a g e s t a t i s t i c a lm o d e l ，w e b p a g es t r u c t u r a lm o d e l ，i n f o r m a t i o ne x t r a c t i o n， i i 目录 目录 摘要i a b s t r a c t 1 目j 录i i i 第1 章绪论1 1 1搜索引擎介绍1 1 1 1搜索引擎的发展历史1 1 1 2w e b 全文搜索引擎的框架1 1 2 本文的研究背景与主要工作7 1 3本文的内容安排8 第2 章w e b 信息抽取研究综述与相关技术介绍。1 0 2 1w e b 信息抽取技术1 0 2 1 1 w e b 信息抽取的发展历史一1 0 2 1 2 w e b 信息抽取技术分类1 1 2 2已有的w e b 主题信息抽取方法。1 2 2 3相关概技术1 3 2 3 1h t m l 介绍1 3 2 3 2 x m l 介绍一1 4 2 3 3 d o m 介绍1 6 2 3 4 h t m l p a r s e r 介绍17 2 4 小结18 第3 章主题型网页判断1 9 3 1相关概念介绍1 9 3 1 1网页分块1 9 3 1 2块节点类型2 2 3 2主题型网页的判断2 2 3 2 1网页类型2 2 3 2 2网页统计模型2 5 3 3实验及结果分析2 8 3 3 1获取基准网页2 8 3 3 2实验及结果分析2 8 3 4 小结3 2 第4 章网页信息结构化模型3 3 i i i 东南大学硕士学位论文 相关技术介绍3 3 4 1 1网页分类3 3 4 1 2网页去重3 5 4 1 3网页排名3 8 4 1 4网页摘要4 0 4 1 5中文分词4 0 4 2 网页信息结构化4 2 4 2 1网页基本元信息4 2 4 2 2网页结构化模型4 3 4 3 爿、结4 6 第5 章基于块文本长度的网页主题信息抽取算法。4 7 5 1网页主题信息抽取系统框架4 7 5 2 网页主题信息抽取的各个步骤4 8 5 2 1原始网页预处理4 8 5 2 2获取主题块节点5 0 5 2 3净化主题块与结果持久化5 3 5 3实验结果及分析5 5 5 3 1主题信息抽取系统介绍5 5 5 3 2实验结果与分析5 7 5 4 小结5 9 第6 章东南大学校园搜索引擎。6 0 6 1系统架构设计6 0 6 1 1开发环境介绍6 0 6 1 2系统整体框架6 l 6 2 索引子系统6 l 6 2 1使用l u c e n e 建立索引6 l 6 2 2l u c e n e 分析器与厄分词6 6 6 3检索子系统6 8 6 3 1检索子系统框架设计6 8 6 3 2 a j a x 技术与s t r u t s 2 技术整合7 1 6 3 3检索子系统功能模块7 4 6 3 4 用户行为跟踪模块：7 6 6 3 5相关搜索推荐模块8 0 6 3 6系统运行效果8 3 i v 致谢9 2 第1 章绪论 1 1 搜索引擎介绍 1 1 1 搜索引擎的发展历史 第1 章绪论 早在w e b 出现以前，互联网上就已经存在许多旨在让人们共享的信息资源了。那 些资源当时主要存在于各种允许匿名访问的f t p 站点，内容以学术报告、研究性软件居 多，它们以计算机文件的形式存在，文件材料的编码通常是p o s t s c r i p t 或纯文本。为了 便于人们在分散的f t p 站点资源中找到所需资源，出现了互联网信息检索工具a r c h i e t 。 a r c h i e 是加拿大麦吉尔大学计算机学院的师生开发的一个软件，它定期搜集分析f t p 系 统上的文件名，然后将这些文件名建立个索引，以供快速查找分布在这些f t p 站点上 的文件。a r c h i e 被认为是现代搜索引擎的鼻祖。 第一代搜索引擎目录式搜索引擎。目录式搜索引擎通过人工发现信息，依靠编 辑人员的知识甄别来分类。然后用户可以在这些分类中挑选自己感兴趣的内容。这种搜 搜索引擎最有名的是早期的雅虎( y a h o o ! ) 和国内的搜狐( s o h u ) 。由于这类系统主要 是靠人为挑选分类编辑整理网络上的资源，不能处理海量的网络数据，在数据量方面限 制很大，而且最终提供给用户的往往是网站的入口地址，提供给用户的最终信息的粒度 不够细腻。 第二代搜索引擎全文搜索引擎。全文搜索引擎是针对万维网上的所有的网页进 行全文的检索的搜索引擎。全文搜索系统由下载系统以某种策略自动地发现和下载万维 网上的信息，然后由索引系统将这些信息建立索引，由检索系统根据用户查询请求从索 引中检索相关的信息返回给用户。全文搜索引擎的特征是信息自动抓取和自动排序检 索。全文搜索引擎的代表是g o o g l e 和国内的百度系统。根据用户的请求，这类系统通 常会返回大量相关的结果，用户自己必须从中筛选。 文献【2 】对元搜索引擎做了详尽的介绍。这类搜索引擎没有自己的数据，而是将用户 的请求同时提交给多个其他的搜索引擎，然后集合这些搜索引擎返回的结果，去除重复 网页后并重新排序作为自己的结果返回给用户。 1 1 2w e b 全文搜索引擎的框架 从用户角度出发，w e b 全文搜索引擎的工作流程大致为：通过检索接口提交关键 词短语，然后检索系统在一个可以接受的时间内返回一个与用户查询信息相匹配的网页 东南大学硕士学位论文 信息列表，列表信息按重要性从高到低的顺序排序。返回的列表中主要包含了网页的主 题、网页的i r _ l 、网页抓取时间、网页摘要以及网页快照的链接地址等等信息。如图 1 1 是百度搜索引擎搜索“w e b 搜索引擎的结果返回页面。 弛啊页魍题幽鲢磁 b a i 猫百度垂豳鐾夔二二二二二二二二 哩匠圈臣囹盟i 酸鳇 挺良豁醴主西 型2 垒燕至呈l 鏊迫进塑塞窭金盘嚣垒适殴玺= 云 瑟梨黧嘉嚣繁端裟翥舞落器恭黧要麓的罔如y a 页h o 嚣。们取回来 - 卟结果 放到本地的数据库中用户的查向请隶可以通过查询车地的数据库采得刊。 厂 o q 7 5 豫黔：冀鬻翼p c 洲蝴矗4 5 k 2 c ( e - 11 - 1 7 酝盥 - j 熟i 型g q 塑圭静墓垒结墨 - j 陌瓦覆幕翮野两琢丽要蟊蟊睇f _ 西磊雨 丽o ，千r ，j i * i l 蔽蔼蒡藕陬焉蕊涎螽f 丽西零弱嗫藕器：育菰同霸匡1 瑕两砸n 摘要 结柬语? ? 7 搜索引擎( s e a r c he n g i n e ) 是指根据一定的笨略、运用特定的计算机程序搜j w 州 a v a e y ec 0 m ，l i ：0 ic 墨q 塾噬盔空：坠迎q 咝壹墨i 墼逡盔盏渣 w e b ：澧牵引擎技术孝考 述w e b ：i 女荤引擎能为用户提供一种查找所需_ 资源的服务，已经成为互联 阿上仅次千电千邮件的第二大服务_ 本文首先介绍了搜索引擎的原理和实现技术然后 d a v c s d nn e b a r t i c l e 删5 1 s h t m4 7 k2 0 0 6 - 4 - 2 2 蔓越 巳丑呈筮拄工程圃：监控塞量l 鏊i 殳让塑兰翌坌援匿| 自d 幽的垦l q 翊：捣： 暮搜索引擎2 0 0 5 4 3 3 2 2k e n g s h e n ga i e x a 开放w e b 拨掌数据库a p 嘿务效集超g o o g l e2 0 0 拿1 2 1 6f l m u s i c ch 巳岫元素d 维用2 0 0 1 - 0 4 - 0 5k i n g z e u si 转帖 g o o g ie 馊熏弓l 擎 b l 。gc s d nn e l f j a k e t s e n g r e l a t e d a t t l c l e s 4 4 9 k2 9 靠坞重压迭塑 睦g ：9 0 ：鲤上数墓童结墨 坠垒搜麦呈| 鏊遗垃独翘金堑：越耋鏖盈壬堑：壹渔豳 w e t ：j 笋鼋引掌设计和实现分析作者：来源l3 6 5 b a s e 发布时间：2 0 0 6 0 7 2 6 【为了解决这 个问题，搜索引擎就随之诞生现在在随上的搜索引擎也己经有很多 i n d u s l r yc c i d n e tc o r r j a r t 111 1 ，2 0 0 5 嘶1 6 2 0 k2 d 口良 - 2 1 酉廑挂照 图1 1 百厦搜索引孥检索结果返【回页面 搜索引擎是一个庞大的、复杂的系统，它收集了万维网上成千上万甚至是上百亿的 网页。如g o o g l e 系统目前收集了上百亿的网页【3 】。虽然各个w e b 全文搜索系统的具体 实现不尽相同，但是大多可以将其分为四个子系统：数据收集子系统、分析子系统、索 引子系统和检索子系统。w e b 全文搜索系统的简单的整体框架如图1 2 所示。 1 ) 收集子系统 在w e b 全文搜索引擎的各个子系统中，收集子系统是基础。搜索引擎中被检索的 海量数据都是通过这个系统来获取的。收集子系统又叫下载子系统、网络蜘蛛、网络爬 虫等等【4 】。 收集子系统其实就是一个网络资源的下载程序，下载包括网页、图片、d o c 文档、 p d f 文档、音频、视频等等资源。通常情况下只下载文本资源，比如网页、d o c 文档、 p d f 文档。 万维网上的资源都是通过超级链接关联在一起的。如果将一个网页看作一个结点， 将一个链接看作当前网页结点指向另一个网页结点的有向边，那么整个万维网就是一个 有向图，如图1 3 所示。 网络蜘蛛的基本原理就是将整个万维网可以看作一个巨大的有向图，通过这些有向 边遍历网络中的节点。即通过少数的入口网页地址( 也叫种子地址) ，然后下载这些网 2 第1 章绪论 页，接着从这些下载的网页中解析出新的网页地址，再下载，如此周而复始，便可以遍 历整个网络，下载需要的信息。 图1 2w e b 全文搜索引擎框架 图1 3 乃维网上由网页组成的有向图 由于w e b 网络拥有的网页数量巨大，导致下载子系统的设计与实现都十分困难。 第一，种子的选取。实验证明万维网是具有蝴蝶结型的结构【5 】：整个网络看起来就 像是一只蝴蝶，9 0 的网站位于蝴蝶结4 个截然不同的区域，而其余约1 0 的部分则是 与整个蝴蝶结完全分离。通过万维网的结构特征可以得出结论：种子地址尽量选取蝴蝶 结“起点 网站的一侧或中部连接核心部分的网页，通常是一些导航类网站。 的一个网页会用超链接指向多个 当网络蜘蛛在抓取的时候没有采 是导致循环抓取。所以必须要采 取策略以防止这种情况发生。防止重复抓取的关键是记住已经抓取过的页面。一种简单 易懂的办法就是在蜘蛛程序中维护两个网页u r l 队列，一个队列存储已被抓取的网页 u r l ，另一个存贮新提取出来的网页u r l ，每次从未被抓取队列中取出一个u r l ，查 询它是否存在于已被抓取队列中，如果不存在，则抓取该页面，并将该u r l 存入已被 抓取队列中；如果存在，则放弃。 第四，提高抓取效率。在网络正常的情况下，下载网络上的一个页面通常需要秒级 别的时间，而搜索引擎需要抓取海量的页面，时间是必须要考虑的问题。搜索引擎的蜘 蛛程序会定期遍历整个网络，周期通常为是几周或一个月。因此网络蜘蛛必须要采取措 施提高下载效率，在尽量短的时间内下载尽量多的网页。在提高效率方面通常会采用多 线程技术和分布式技术。 第五，网页重访策略。网络上的网页会不定时的被修改、删除，也会有新的网页被 创建，考虑到与网路上的资源保持一致性，网络蜘蛛应该经常遍历整个网络，以更新网 页库。但是由于整个网络巨大，建立索引库的时间复杂度较大，除此之外，在较短时间 内网页库与网络上的实际的资源的不一致性引起的负面影响是可以接受的。所以网页重 访策略就要解决重访时间等一系列问题。最简单的网页重访策略是整个网络重新遍历， 建立新的网页库，将原来的网页库作废。这种策略简单易懂，但是没有利用抓取网页的 历史信息。在较短时间内，网络上的大量网页是没有做过修改的，这种策略会加重网络 负荷，并且每次遍历都下载所有的网页，所需要的时间也会很多。更好的方式是增量式 的搜索策略，这种策略会利用抓取网页的历史信息。第一次遍历的时候搜集一些，往后 只需要抓取新出现的网页、上次抓取后被修改的网页以及删除那些已经不存在的网页【引。 第六，礼貌问题。网络蜘蛛在网络上抓取资源的时候应该遵循r o b o t s 协议。并且 应该注意同一网站的抓取密度，以减轻网站服务器的负荷而不影响其正常的服务。 2 ) 分析子系统 信息收集子系统收集到的海量网页集合，距离面向网络用户的检索服务还有相当远 的距离【9 j 。网页信息或者下载的文档一般要先经过分析，用于后续的索引子系统建立索 引。对于全文搜索引擎，网页抽取技术主要对下载的数据进行正文的提取分析操作。而 对于垂直搜索引擎，在结构化操作以后，还要对其进行数据挖掘，进行领域信息识别， 4 第1 章绪论 从而提高信息质量。 网页分析子系统主要包括关键词的提取、网页分类、网页去重、网页排名等等几个 方面。网页分类、网页去重和网页排名等将在第四章中做详细的介绍，此处不再赘述。 3 ) 索引子系统 w e b 搜索引擎要求快速性，而收集子系统下载的海量数据不能一次性全部放入内 存中，需要一种方法对原文档进行处理然后建立一种便于检索的数据结构，以此来提高 检索速度，这种数据结构就是索引。索引的功能是对收集子系统收集的信息进行分析处 理，从中抽取索引项，用于表示文档以及生成文档库的索引表。 搜索引擎普遍借鉴了传统信息检索中的索引模型，包括倒排文档、矢量空间模型、 概率模型等【1 0 j 1 1 。为了快速定位特定的信息，建立索引数据库是一个常用的方法，即将 文档表示成一个便于检索的方式，并存放于索引数据库中。现代的搜索引擎普遍采用倒 排索引的结构。 在建立倒排索引之前需要将所有的文档按索引项建立正向索引，然后再根据正向索 引建立倒排文档。由前向索引转换为倒排索引的过程如图1 4 所示。 前向索引 文档1 文档2 文档3 文档1 0 倒排索引 索引项1 索引项2 索引项3 医寸匹乎哑捆 图1 4 由正向索引建立倒排索引 当信息检索系统所要处理的文档数量巨大时，建立索引能显著提高信息检索的速 圃固 譬圈i 东南大学硕士学位论文 度。不过由于建立索引是一个复杂的过程，索引系统不支持信息的快速更新。 4 ) 检索子系统 w e b 搜索引擎的检索子系统直接面对用户，在接受用户的请求后，先将请求字符 串进行过滤和切词，从倒排文档中检索到相关的文档，然后结合文档的排序以及摘要信 息等，返回给用户一个按相关度及重要性倒排的相关网页信息的列表。图1 1 为百度系 统查询“w e b 搜索引擎”的结果返回页面，页面中给出了一个与查询词相关联的网页 信息列表，并且每个返回的网页给出了网页标题、u r l 、网页大小、网页抓取时间、摘 要信息以及快照等信息。 检索子系统一般都采用了布尔模型和向量空间模型结合的方法来进行信息检索，布 尔模型的效率高且易于实现【1 2 1 ；向量空间模型 1 0 - 1 3 1 能够提高检索的相似度，通过相似 度排序的手段能够大大改善查询效果。搜索引擎结合了二者的优势后，完整的检索过程 如图1 5 所示。 图1 5 检索过程 w e b 全文搜索引擎的索引库巨大，面向的用户群体也是非常巨大的。对于单个的 用户来说查询请求千差万别，但是整体从统计上看，某些查询请求会被频繁查询，相反 6 第1 章绪论 有些只是偶尔被查询。为了更进一步提高处理用户查询请求的速度，可以采用缓存部分 用户感兴趣的查询请求结果的方法【1 4 】。每当用户有新请求的时候，如果在缓存中存在就 直接返回结果，而不用再次查找并生成返回结果页面，当不存在于缓存中的时候才去查 询。所以更合理的查询请求处理过程如图1 6 所示。 图1 6 有缓存的查询请求处理过程 1 2 本文的研究背景与主要工作 互联网的飞速发展，使得网络上的网页数目呈指数增长，网络成为人们获取信息的 重要途径，准确迅速获取信息成为人们迫切的需求。据c n n i c2 0 0 9 年2 月发布的统计 数据 i s 】表明：截至到2 0 0 8 年底，中国搜索引擎用户达到2 0 3 亿人，与2 0 0 7 年底相 比，搜索引擎用户增长了5 1 0 0 万人，年增长率达到3 3 6 。目前，搜索引擎在全国网 民中的使用率为6 8 ，在各种互联网应用中位列第四。 随着网络信息的不断增多，给搜索引擎的研究带来了新的挑战，所以必须对其进行 更加深入的研究以满足人们的需求。国外的搜索引擎技术发展的较早，已经有十几年的 历史，y a h o o 是最早提供分类目录向导的搜索引擎。根据用户输入的检索信息，y a h o o 将返回相关的分类目录、w e b 网站、w e b 网页和新闻。目前a l t a v i s t a 是i n t e m e t 上最大 的搜索引擎之一，它提供常规搜索、高级搜索和主题搜索，包括图像、视频和音频等。 a l t a v i s t a 所拥有的庞大数据库使得用户找到所需信息的可能性大大增加。2 0 0 8 年g o o g l e 就有八十亿个可搜索网页，每天处理的搜索请求己达2 亿次，在操作界面中提供多达 3 0 多种语言选择，包括英语、主要欧洲国家语言、日语、中文简繁体、朝语等。 国内开始研究搜索引擎是在上世纪末本世纪初，虽然国内起步较晚，但是己经涌现 7 东南大学硕士学位论文 出了一些很优秀的产品。目前国内技术水平最高的搜索引擎是百度，它的功能齐全，包 括新闻搜索、网站搜索、m p3 搜索、图片搜索等，在中文搜索支持方面有些地方甚至 超过了g o o g l e ，更新速度也相对较快。在搜索结果中百度还设置了相关搜索功能。能够 提供用户与查询关键词有联系的信息，从而进一步提高了查询的准确度。随着搜索市场 价值的不断增加，越来越多的公司开发出了自己的搜索引擎，中国搜索、搜狐的搜狗、 阿里巴巴的商机搜索等也陆续面世，自然，搜索引擎技术也成为技术人员关注的热点。 本文主要研究了搜索引擎分析子系统中的网页主题信息抽取算法，主要的工作内容 有： 在已有理论基础上，完善了关于网页分块的理论与相关概念，并提出块文本的 概念。 通过分析不同类型的网页特征，提出了一种用于辨别网页类型的网页统计模型。 通过编程获取大量的基准网页，然后经过统计实验获得一种判断主题型网页的 方法。 通过分析w e b 全文搜索引擎的分析子系统和查询子系统中与网页数据直接或 间接关联的关键功能模块，提出一种方便实用的网页结构化模型。 在网页分块的理论基础上，提出一种基于块文本长度的网页主题信息抽取算法。 使用j a v a 语言编程实现该算法，并通过实验证明该方法切实可行。 1 3 本文的内容安排 本文的工作内容安排如下： 第1 章是绪论，首先简单介绍了搜索引擎，其次介绍了本文的研究目的、主要工作 和本文的内容安排。 第2 章主要介绍网页信息抽取以及与网页信息抽取相关的技术。介绍了信息抽取的 定义和历史，然后逐渐深入到w e b 信息抽取。接着分析了现有的些w e b 信息抽取 方法，并分析了这些方法的不足。最后介绍了与网页信息抽取相关的技术。 第3 章主要介绍与网页信息抽取相关的概念和主题型网页的判断。首先，对与块节 点相关的概念做了详解的介绍。接着分析了三种不同类型网页的特征，为寻求一种量化 的方式来判断主题型网页，提出了一种网页实验统计模型。最后在此模型基础上通过大 量统计实验找到了一种辨别主题型网页的方法及该方法下的最佳参数。 第4 章提出了一种网页结构化模型。首先对w e b 全文搜索引擎的分析子系统、检 索子系统中与网页中间模型相关的功能模块进行详细的分析。然后提出了一种简单易用 的网页网页结构化模型，这种模型可以作为网页信息抽取的中间模型，有助于减少重复 的数据处理和减少存储空间。 8 9 东南大学硕士学位论文 第2 章w e b 信息抽取研究综述与相关技术介绍 本章首先介绍了网页信息抽取技术的发展历史与及技术分类，接着分析并指出当前 一些网页主题信息抽取方法的不足。最后介绍了与网页信息抽取相关的技术。 2 1w e b 信息抽取技术 2 1 1w e b 信息抽取的发展历史 w e b 信息抽取( w e bi n f o r m a t i o ne x t r a c t i o n ，w i e ) 的前身是信息抽取( i n f o r m a t i o n e x t r a c t i o n ，i e ) 1 1 6 1 7 j 。i e 的主要目的是从文本中抽取出特定的事实信息( f a c t u a l i n f o r m a t i o n ) 。比如从新闻事件报道中提取出事件发生的时间、地点、人物；从经济新闻 中提取出公司、公司法人、公司地址、公司产品等等信息；从酒店详细介绍的文本中提 取酒店的名称、酒店的地点、酒店的简单介绍、到达酒店的公交、酒店规模、酒店价格 等等详细信息。然后将这些详细信息进行结构化，存入数据库中以供用户查询或者更进 一步的分析利用。 从自然语言文本中获取结构化信息的研究最早开始于2 0 世纪6 0 年代，以两个长期 的、研究性的自然语言处理项目为代表。 美国纽约大学开展的l i n g u i s t i cs t r i n g 项目【1 8 】开始于2 0 世纪6 0 年代中期并一直延 续到8 0 年代。该项目主要研究内容是建立一个大规模的英语计算语法，与之相关的应 用是从医疗领域的x 光报告中和医院的出院记录中抽取信息格式( i n f o r m a t i o nf o r m a t s ) 。 另一个项目是耶鲁大学r o g e rs c h a n k 及其同事在2 0 世纪7 0 年代开始的有关故事理 解的研究。由他的学生g e r a l dd ej o n g 设计实现的f r u m p 系统【1 9 1 是根据故事脚本理论 建立的一个信息抽取系统。这个系统可以从新闻报道中抽取信息。 得益于离线文本的几何级增长和消息理解系列会议( m e s s a g eu n d e r s t a n d i n g c o n f e r e n c e ，m u c ) 的召开，从2 0 世纪8 0 年代末开始，信息抽取技术蓬勃发展起来。 m u c 是由美国国防高级研究计划委员会资助。m u c 的显著特点并不是会议，而是对信 息抽取系统的评测【2 0 1 。自1 9 8 7 年到1 9 9 8 年，m u c 共举行了七届。m u c 系列会议对信 息抽取这一研究方向的确立和发展起到了巨大的推动作用。 近几年来，信息抽取技术的研究与应用更加活跃。在研究方面主要侧重于以下几个 方面：利用机器学习技术增强系统的可移植性、探索深层理解技术、篇章分析技术、多 语言文本处理能力、w e b 信息抽取以及对时间的处理等等。至今已有不少以信息抽取 技术产品为主的公司出现，比较著名的有c y m f o n y 、b h a s h a 、l i n g u a m a t i c s 和r e v s o l u t i o n 1 0 第2 章w e b 信息抽取研究综述与相关技术介绍 公司。 中文信息抽取方面的研究起步较晚，还集中在命名实体识别方面，遵照m u c 规范 的完整的中文信息提取系统还处于探索阶段2 。其中我国的国立台湾大学和新加坡肯特 岗数字实验室参加了m u c 7 的中文命名实体识别的测评。i n t e l 中国研究中心的 z h a n g y i m i n 和z h o uj o ef 等在a c l 2 0 0 0 上演示了他们开发的一个抽取中文命名 实体以及这些实体之间相互关系的抽取系统，该系统利用基于记忆的学习算法获取抽取 规则用以抽取命名实体以及它们之间的关系【2 2 1 。 2 1 2w e b 信息抽取技术分类 随着互联网的发展，互联网上的信息成爆炸性增长，互联网提供了一个巨大的信息 源，这激发了w e b 信息抽取技术的研究。w e b 信息抽取与传统的信息抽取有很大的不 同。互联网上的信息大多是以h t m l 文档的形式存在，且h t m l 文档主要是用于浏览， 而不是用于数据操作和应用。w e b 信息抽取技术在传统的信息抽取研究的基础上，将 重点放在如何从半结构化的h t m l 文档中的抽取某些特定的信息。然后转化为结构化 的信息存储在数据库中，供查询或更进一步的研究。 w e b 信息抽取按不同的方式有不同的划分方法。如按自动化程度可以划分为人工 方式、半自动方式及全自动方式三类。而根据信息抽取的原理可以划分为基于自然语言 的处理( n a t u r a ll a n g u a g ep r o c e s s i n g ，n l p ) 方式、包装器( w r a p p e r ) 归纳方式、基于 o n t o l o g y 方式、基于h t m l 结构方式和基于w e b 查询方式等五大类。 1 ) 基于自然语言处理的w e b 信息抽取 这种方式一般可以归为语音、词、词形、语法、语义、篇章、语用等7 个不同的抽 象级别。这类信息抽取主要适用于源文档中包含大量的文本，在一定的程度上借鉴了自 然语言处理技术，利用了句子结构、短语和子句之间的关系建立基于语法和语义的抽取 规则来实现信息抽取。n l p 方式的难点在于信息抽取的速度较慢，不适用于互联网上的 海量信息处理；信息抽取与文本理解之间存在较大的差距信息抽取只关心相关的内 容，而文本理解则能体会作者的细微用意和目的。目前这类典型的系统有r a p i e r 、s e v 和w n i s k 。 2 ) 基于包装器( w r a p p e r ) 方式的w e b 信息抽取 这类方式是目前主要使用的方式之一【2 3 1 。所谓的包装器就是一个能从h t m l 文档 中抽取出信息，并转换为结构化数据的软件。包装器由一组抽取规则来制定抽取网页中 的特定的信息。一般而言，一个包装器只能抽取一类特定的网页类型。与自然语言处理 方式相比较，包装器方式较少依赖于全面的句子语法分析和分词等复杂的自然语言处理 技术，更注重于文本结构和表格的分析。采用这种方式的典型系统有s t a l k e r 、 s o h t m e a l y 及w i e n 。 东南火学硕士学位论文 3 ) 基于o n t o l o g y 方式的w e b 信息抽取 这类方法主要基于o n t o l o g y 概念。按照s t a n f o r da i 专家t o mg r u b e r 的定义， o n t o l o g y 是为了帮助程序和人共享知识的概念化规则，在知识表达和共享的领域， o n t o l o g y 描述了在代理之间的概念和关系( c o n c e p t sa n dr e l a t i o n s ) 。在w e b 上o n t o l o g y 表现为分类法和一组推理。基于o n t o l o g y 的w e b 信息抽取方法主要依赖于一个完整的 知识库。知识库定义了各个元素的抽取模式，以及它们之间的联系。在抽取之前需要将 包含的数据的记录块分割开来，然后依次对每个信息进行抽取。这种方式不依赖于任何 结构和表现形式，它使用o n t o l o g y 来定位关键信息并使用这些元素构造对象。这种方式 要求有一个完整的o n t o l o g y 库。 4 ) 基于h t m l 结构的w e b 信息抽取 基于h t m l 结构特点的信息抽取充分利用了h t m l 自身的结构特点。在信息抽取 之前将h t m l 文档解析成语法树，然后通过半自动或全自动的方式生成抽取规则，将 信息抽取转化为对语法树的操作。这类方法的效率较高，且自动化程度也较高。采用这 类方式的系统有r o a d r u n n e r 2 4 1 、w 4 f 2 5 1 及l i x t o 2 6 】等。 5 ) 基于w e b 查询方式的w e b 信息抽取 使用w e b 的相关技术解决w e b 的问题称为w e b 技术风范。上述的信息抽取工具， 采用了不同的原理，抽取规则的形式和感兴趣信息的定位方式也各不相同，因此均不具 有通用性。具有w e b 技术风范的信息抽取，将w e b 信息抽取转化为使用标准的w e b 查 询语言对w e b 文档的查询，具有通用性。采用该类技术的典型的系统有：w r e b o q l 以及自主开发的原型系统p q a g e n t 。 2 2 已有的w e b 主题信息抽取方法 在网页主题信息抽取领域已经有大量的研究工作。主要有以下几种方法：一类方法 着眼于探测同站点网页中的一般模式。这些方法都是基于这样的一个假设：“对同一 个网站，那些与主题无关的部分常常有着相同的内容和表现风格”1 2 7 】。基于此， b a r - y o s s e f 把页面之间相同的部分称为模板( t e m p l a t e ) 。他们的实验表明删掉这些模板可 以提高搜索引擎c l e v e r 的准确率，而不引起召回率下降。文献【3 】综合考虑了网页的结 构和内容两个方面的相似性，提出了相似树比较算法。这类方法对于用程序自动生成网 页的站点效果较好，但是对许多其他的网站的效果却不是太好，而且还要维护模板。 第二类方法是从视觉效果方面对页面进行处理。典型的代表就是微软亚洲研究院提 出的v i p s ( v i s i o n b a s e dp a g es e g m e n t a t i o n ) 【2 8 】。该方法充分分析了页面的字体大小、 颜色、位置等视觉特征，把页面划分成各个视觉块，进而提取信息。但是由于视觉特征 的复杂性，划分的启发式规则比较模糊，需要人工干预完善启发式规则，自动化程度不 1 2 第2 章w e b 信息抽取研究综述与相关技术介绍 高。 第三类方法集中在对d o m 树的挖掘上。把h t m l 源文件转换成d o m 的树形结构， 对w e b 页面结构进行分析，去除与主题内容无关的部分，最后输出页面主题内容。文 献【2 9 】采取的方法是将h t m l 页面表示成d o m 树形结构，然后找到所有的t a b l e 标 签，按照t a b l e 标签中字符个数进行降序排列。最后比较各个t a b l e 标签中的字符个 数，得到该页面的主题信息。该方法不具有通用性，只能运用于页面主题信息包含在一 个t a b l e 标签中的情况。 还有一类方法注重的是h t m l 页面的源代码。f i n n 等【3 0 1 等人提出从网页的源代码 入手，将h t m l 的源代码表示成词和标记的组合文本，然后找出包含词最多的区域， 从而确定主题信息。刘艳敏等人【3 l 】在预处理阶段将网页分割为头、脚、左、右和中间五 个区