（计算机应用技术专业论文）基于结构和视觉特征的网页信息抽取技术的研究与实现.pdf

浙江大学硕士学位论文a b s t r a c t a b s t r a c t t h ew e bi sp e r h a p st h es i n g l el a r g e s td a t as o u r c ei nt h ew o r l d ，a n dm o r ea n dm o r e o r g a n i z a t i o n sr e l e a s et h e i rd a t at h r o u g ht h ei n t e m e t v e r t i c a ls e a r c he n g i n e s ，a l s o k n o w na sd o m a i ns p e c i f i cs e a r c he n g i n e ，s e n dt h e i rs p i d e r so u tt oar e f i n e dd a t a b a s e a n dc r a w ls o m et y p eo fi n f o r m a t i o nf r o mt h ew e bs i t e ，t h e np o s tt h ei n f o r m a t i o nf o r u s e rt o q u e r ya f t e ri n t e g r a t i o na n dp o s t p r o c e s s i n g w e bi n f o r m a t i o ne x t r a c t i o n t e c h n o l o g yi s t h ef u n d a m e n t a lf o rv e r t i c a ls e a r c he n g i n e ，a n di t sa l s ot h ek e r n e l m o d u l eo fs e a r c he n g i n e sb a c k - e n d d e v e l o p i n ge x t r a c t i o ns y s t e mm a n u a l l ym a yb e s i m p l e ，b u ti th a sm a n yw e l l k n o w ns h o r t c o m i n g ss u c ha si t sd i f f i c u l tt om a i n t a i n t h e mb e c a u s ew e bs i t e sa l w a y sc h a n g ei no r d e rt os u r v i v e ，a n di tn e e do n em o r e p r o g r a m t os u p p o r tan e wd a t as o u r c ew h i c hi saw a s t eo f r e s o u r c e t h i sp a p e rp r e s e n t sav i s i o n - b a s e dw e bs t r u c t u r a li n f o r m a t i o ne x t r a c t i o nt e c h n o l o g y , w h i c hn o to n l ym a k eu s eo ft h es t r u c t u r a li n f o r m a t i o no fh t m l p a g e s ，b u ta l s ot a k ea g o o du s eo f t h ev i s i o ni n f o r m a t i o n i tc o n s i s t so f t w os t e p s ：( 1 ) i d e n t i f yi n d i v i d u a ld a t a r e c o r d si nap a g e ，a n d ( 2 ) a l i g n i n ga n de x t r a c t i n gd a t ai t e m sf r o mt h ei d e n t i f i e dd a t a r e c o r d s i nt h ef i r s ts t e p ，v i s i o ni n f o r m a t i o nh e l p st of i l t e ro u tm o s to ft h en o i s ei nt h e w e bp a g e ，w h i c ha c c e l e r a t et h ea l g o r i t h mb a s e do nh t m ls t r u c t u r e ，i ta l s om a k et h e a l g o r i t h mm o r ea c c u r a t e i nt h es e c o n ds t e p ，t h ei m p r o v e dt r e ea l i g na l g o r i t h mi su s e d f o rt h ea l i g n m e n to fa t t r i b u t e s ，w h i c hi se f f i c i e n ta n dr o b u s t a n di nt h ea l i g n m e n to f m u l t i p l et r e e s ，t h ei n t r o d u c t i o no fs e e dt r e er e d u c e st h ec o m p u t a t i o no ft h ea l g o r i t h m ， s oi m p r o v et h ep e r f o r m a n c ew h e nt h ea l g o r i t h ma p p l i e dt ol a r g ew e bp a g e s t h e e x p e r i m e n t ss h o wt h a tt h ee x t r a c tm e t h o dh a sah i g hd e g r e eo fa u t o m a t i o n ，n e e d a l m o s tn om a n u a l i n t e r v e n t i o n a n di t sa l s ov e r ye f f i c i e n ta n da c c u r a t e k e y w o r d s ： v e r t i c a ls e a r c h ，i n f o r m a t i o ne x t r a c t i o n ，v i s i o n - b a s e d 浙江大学硕士学位论文 表目录 表目录 表2 1 各种工具的比较2 0 表6 1 实验结果一6 4 表6 2 横向比较结果一6 6 v i 浙江大学硕士学位论文 图目录 图目录 图1 1 一个垂直搜索引擎的体系结构3 图2 1 网页信息抽取模型1 2 图2 2 形式化表示13 图2 3 数据来源网站一的数据格式1 4 图2 4 数据来源网站二的数据格式1 4 图2 5 互联网网站近年来变化趋势一15 图2 6 包装器与信息抽取1 7 图3 1 体系结构图2 3 图3 2 网页输入处理子模块2 4 图3 3 输出子模块结构图2 5 图4 1 自动化网页数据记录定位的例子2 8 图4 2 图4 1 的h t m l 标签树示意2 9 图4 3 数据区域与数据组合3 1 图4 4 节点组合生成。3 2 图4 5 标签树的匹配3 6 图4 6 标签树的跨层匹配和替换匹配3 6 图4 7 匹配算法演示标签树a 和b 3 9 图4 8 动态规划中相同节点的优先选择3 9 图4 。9 数据区域的嵌套4 1 图4 1 0 数据记录定位设计4 7 图5 1 标签树节点的插入图示一5 1 图5 2 标签树节点的插入图示二5 2 图5 3 标签树节点的插入图示三5 3 图5 4 标签树节点的插入图示四5 4 1 v 浙江大学硕士学位论文图目录 图5 5 两颗标签树的对齐操作。5 5 图5 6 数据记录对齐和数据提取模块类图5 8 图6 1 某网站查询杭州的酒店数据( 共1 9 条，显示2 条) 6 0 图6 2 图6 1 的抓取结果( 部分显示) 6 1 图6 3 某网站机票数据6 2 图6 4 图6 3 中机票的抓取结果。6 3 v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝姿盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：季翻l 签字日期：枷占年占月j 日 学位论文版权使用授权书 本学位论文作者完全了解迸江盘堂有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝婆盘堂可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 善凯 导师签名： 签字日期：7 舢粤年匆月日 签字日期： o 日 浙江大学硕士学位论文 第1 章绪论 第1 章绪论 1 1 垂直搜索引擎技术的介绍 垂直搜索引擎是致力于在互联网上搜索特定领域数据的搜索引擎，是普通搜 索引擎的细分和延伸。 当今时代是一个信息爆炸的时代，互联网作为越来越多的人获取信息的重要 渠道，提供的信息虽然丰富，但同时也是非常杂乱的。如何从茫茫互联网的海洋 当中找到自己关心的领域的信息是很多人都关心的问题。 垂直搜索引擎正是对互联网中专门的信息进行整合，取出需要的数据进行处 理后以某种形式返回给用户。 垂直搜索引擎和普通的网页搜索引擎的最大的区别是垂直搜索引擎对信息 进行了结构化的抽取，将网页的非结构化数据抽取成特定的结构化数据。网页搜 索是以网页为最小单位，而垂直搜索是以结构化的数据为最小单位。提取后的数 据一般会被存储到数据库中，进行进一步的加工处理，比如去除重复，重新分类， 然后可能还需要分词以及建索引以满足客户的搜索需求。 垂直搜索引擎一般都是针对特定的领域的，选择垂直搜索引擎来寻找自己需 要信息的用户一般也是比较专业或者是有某种特定需求的用户。因此把自己的信 息放在专门的垂直搜索引擎对于一些特定领域的公司来说是一个非常好的选择， 因为那些通过垂直搜索引擎链接过来的用户非常可能就是他们的潜在客户。比如 说现在比较流行的机票垂直搜索引擎面对的就是想通过飞机出行的人，房屋垂直 搜索引擎面对的就是想在某个地段租房或者买房的人，除此之外还有很多的工作 垂直搜索引擎，旅游线路垂直搜索引擎+ 。 垂直搜索引擎的盈利模式也比一般的搜索引擎直接，最愿意付钱的是那些希 望用户通过垂直搜索引擎找到自己的那些公司，因为选择通过垂直搜索引擎来寻 + 现有非常多的优秀垂直搜索引擎，比如6 t o u r e n 还有q u n a r c o m 浙江大学硕士学位论文第l 章绪论 找信息的客户很有可能就是购买这个公司产品的人，因此这些公司会比较愿意为 垂直搜索引擎服务支付相应的费用。 垂直搜索引擎是一个高速发展的领域，越来越多的产品和网站已经涌现出 来，而且随着需求的增多，越来越多的领域都会涌现出相关的垂直搜索产品。蓬 勃发展的产业需要底层技术的更新，本章将展开介绍垂直搜索引擎的一般体系结 构和关键技术，最后会说到本文的重点信息抽取技术在垂直搜索引擎中的作用。 1 2 垂直搜索引擎的一般体系结构 垂直搜索引擎可以分为以下几个模块( 见图1 1 一个垂直搜索引擎的体系结 构) ：由图可见，垂直搜索引擎可以分为前端和后端，前端主要是负责与用户的 交互包括用户界面的设计，用户界面逻辑开发。后端主要负责数据的采集工作， 负责抓取相关网站数据，提取数据并且经过整理去重后存入数据库供前端查询。 2 厂、 数据采集模块 量坡日敢据( c r a w l e r ，p a r s e r ， i n t e g r a t o r ) 原始数据文件l 服务器 标准化数据 - l 采集教据库 厂、 l 数据预处理优化模块 结构化数据 大最频繁 ( i n d e x ，c a c h e 。 所有结构 读取少 s t a t i c a l i z e ) 量更 新的 小l f 象 包含索引 | 高频度访问的页面等 ，上 、r 分布式对象缓 静态文件缓存 只读在线数据库 存 一 1r 回馈 厂、 在线搜索服务接口 i ， l j日志与统计分 i _ 6 越 用户请求 析 i q1 图1 1 一个垂直搜索引擎的体系结构 3 浙江大学硕士学位论文第1 章绪论 1 3 垂直搜索引擎中涉及到的技术 通用搜索弓l 擎主要是利用一个s p i d e r 程序到网络上爬行【i 】，一般是某个特定 的周期派出一次将网页更新：垂直搜索引擎同样有一个s p i d e r 程序，但该程序只 在一些特定的网络上爬行，并不会对每一个链接都感兴趣，相对来说，垂直搜索 引擎的搜索的范围大大缩小了。通用搜索引擎对一些动态脚本是不敏感的，很多 动态生成的网页一般不被收录，而恰恰是这类动态网页包含了丰富的内容，垂直 搜索引擎是必须收录这些动态脚本的，这就需要在技术上做一些特殊处理；另外 由于目前网页中的链接形式非常多，不但有动态脚本也有f l a s h 做的链接，这些 链接方式通过传统的s p i d e r 程序是很难解析出来的，在垂直搜索引擎中这些都予 以解决了。 垂直搜索技术主要分为两个层次：模板级和网页库裂2 1 。模板级是针对网页 进行模板设定或者自动生成模板的方式抽取数据，对网页的采集也是针对性的采 集，适合规模比较小、信息源少且稳定的需求。优点是快速实施、成本低、灵活 性强，缺点是后期维护成本高，信息源和信息量小。网页库级信息抽取是采用页 面结构分析与智能节点分析转换的方法，自动抽取结构化的数据。它在信息源数 量上、数据容量上、检索容量上、稳定性、可靠性上都是网页库搜索引擎级别的 要求，和模板级方式最大的区别是对具体网页不依赖，可针对任意正常的网页进 行信息采集或信息抽取。完全自动化，不用对具体网站事先生成模板，这就导致 这种方式在数据容量上和模板方式有质的区别，但是其灵活性差、成本高。当然 模板方式和网页库级的方式不是对立的，这两者对于垂直搜索引擎来说是相互补 充的。 基本原理和主要功能组件方而，垂直搜索引擎与通用搜索引擎基本相同。两 者主要的区别在于s p i d e r 爬行范围和网页信息处理深度两方面。垂直搜索引擎与 通用搜索引擎的网页爬行策略的一个本质的区别是：普通搜索引擎采取逐页爬行 的原则，对所有的网页全部进行分析，然后对网页进行索引放入数据库。垂直搜 索引擎则根据系统对网页与主题相关性的计算，采取一定的策略预测相关网页的 4 浙江大学硕士学位论文 第1 章绪论 位置，动态的调整网页爬行方向；使系统尽可能的在与主题相关的网页集中的地方 爬行，对网页进行分析。这一点是垂直搜索引擎的优势所在，它节约了系统运行 的硬件和网络资源开销。相关网页的预测策略实际上就是算法所实现的内容，所 以选样一个高效率的搜索算法将会决定整个系统的运行效率。这里先对页面分析 技术进行概述，然后研究决定爬行方向的超链分析算法和页面内容加工的结构化 分析算法。 1 3 1 页面分析技术 由于w w w 网上的信息主要是以h t m l 文档的形式存放的，因此要根据 h t m l 文档的特点，对其进行扫描分析，以提取信息。h t m l 文档包括五个定义 好的组件：文本、注释、简单标签、起始标签、结束标签。通过分析，文本和表示 链接的标签在搜索中起到了决定性的作用，所以，在页面分析技术中，应该重点 关心这两方面的内容。文本实际上就是显示在浏览器中的文字，其显示方式由包 围它的标签来决定。网页相关的主题大都是通过文本来表达的，所以文本信息必 须被完全提取出来，以便进一步处理。 在所有的标签中，标签 是最有用的。标签 在h t m l 中叫做 链接标签，它决定了当在浏览器中点击该标签的文本时所要打开的网页的u r l 。 除了标签 外，一些图像映像也能将用户带到相应的新页面。图像映像当 中的超级链接可以由图像的 简单标签中的h r e f 属性得到。另外，框架中的 s r c 属性也可以设置超级链接。 1 3 2 超链分析算法 经过对初始页面的初步分析技术后，接下来需要讨论的就是与该页面所链接 的u r l 的重要度，作为下一步搜索和页面分析的顺序权值。目前有两种比较流 行的网页排序算法，一种是h i t s a 算法，另一种是p a g e r a n k 4 1 算法。h i t s 算法 强调中心网页和权威网页的相互加强，而p a g e r a n k 算法强调超链权值的标准化 5 浙江大学硕士学位论文第l 章绪论 和随机冲浪模型。 p a g e r a n k 算法为w e b 上每个网页计算了一个全局的p a g e r a n k 值，用以标记 网页的相对重要性。p a g e r a n k 算法中对于向外链接的权值贡献是平均的，也就是 不考虑不同链接的重要性。搜索时根据网页的r a n k 值对搜索到的结果进行排序， 把p a g e r a n k 值最高的网页放置到最前面，但是如果最重要的网页不在结果网页 集中，p a g e r a n k 算法就无能为力了，p a g e r a n k 算法与查询的主题无关，不适合 进行垂直搜索。 j k l e i n b e r g 提出的h i t s 算法中引入了另外一种网页，称为h u b 网页( 中心网 页) ，h u b 网页是提供指向权威网页链接集合的w e b 网页，它本身可能并不重要， 或者说没有几个网页指向它，但是h u b 网页却提供了指向就某个主题而最为重要 的站点的链接集合，比如一个课程主页上的推荐参考文献列表、视频分享网 站的分类列表等。一般来说，好的中心网页指向许多好的权威网页，好的权 威网页是有许多好的中心网页指向的网页。这种h u b 与a u t h o r i t y 网页之间的相 互加强关系，可用于权威网页的发现和w e b 结构和资源的自动发现，这就是 h u b a u t h o r i t y 方法的基本思想。h i t s 算法由康奈尔大学的k l e i n b e r g 创立，他将 网页的权值分为目录型权值和权威型权值分别进行计算，目录型权值衡量它包含 重要网页链接数的程度，权威型权值衡量它的网页内容中包含重要信息的程度。 在h i t s 算法中，所有链接的不同之处可以从它的导向词与查询词的匹配度不同 来体现。此处的导向词是指u r l 出现在网页中前后约1 5 0 个字符之内的信息， 它一般含有关于该u r l 所指向网页内容的重要信息。 h i t s 算法非常巧妙地构造了一个基于链接的w e b 表示模型，但它也存在着 很多缺陷，例如，一些网页编写者基于各种原因无根据地制造链接或者该网页是 完全自动牛成，那么此时网页上的链接的参考价值就不大。同时完全基于链接的 分析会产生主题漂移现象。这时，h i t s 算法与传统的基于文本匹配的方法结合 就会产生很好的效果。 综上所述，利用在搜索网页内容相对集中，如仅限于网络视频搜索时，h i t s 算法己经足够求出搜索网页的权值排序了。 6 浙江大学硕士学位论文第1 章绪论 1 3 3 网页信息的结构化抽取 在利用h i t s 算法求出网页的爬行方向和网页重要度排序后，垂直搜索引擎 和通用搜索引擎的另一区别就是对页面存储器中的网页信息进行结构化抽取，以 向用户提供更加专业的搜索服务。如比较购物搜索需要抓取网页后，对网页中的 商品信息进行抽取，抽取出商品名称、价格、简介甚至可以进一步将笔记本 简介细分成“品牌、型号、c p u 、内存、硬盘、显示屏、；房产信息搜索那 就应该抽取出：类型、地域、地址、房型、面积、装修情况、租金、联系人、联 系电话等；公司企业信息搜索那就应该抽取出：公司名称、地址、电话、联系人 等结构化信息：而网络视频的搜索则应该抽取出：视频名称、视频说明、视频类别、 视频发布者、视频制作者、视频来源网站地址、发布日期、点击次数等结构化信 息。w e b 结构化信息抽取的技术水平是决定垂直搜索引擎质量的重要技术指标。 将网页中的非结构化数据按照一定的需求抽取成结构化数据。有两种方式，简单 的就是模板方式，模板方式是事先对特定的网页进行配置模板，抽取模板中设置 好的需要的信息，可以针对有限个网站的信息进行精确的采集。模板方式的特点 是简单、精确、技术难度低、方便快速部署。缺点则是需要针对每一个信息源的 网站模板进行单独的设定在信息源多样性的情况下维护量巨大是不可完成的维 护量。所以这种方式适合少量信息源的信息处理，不是搜索引擎级的应用，很难 满足用户对查全率的需求。 网页信息结构化抽取的第二种方式就是网页库结构化信息抽取，该方法采用 页面结构分析与智能节点分析转换的方法，自动抽取结构化的数据。特点是可对 任意的正常网页进行抽取，完全自动化，不用对具体网站事先生成模板，对每个 网页自动实时得生成抽取规则，完全不需要人工十预。智能抽取准确率高，不是 机械的匹配，采用智能分析技术，准确率能达到9 8 以上。能保证较快处理速度， 由于采用页面的智能分析技术，先去除了垃圾块，降低分析的压力，是处理速度 大大提高。通用性较好，易于维护，只需设定参数、配置相应的特征就能改进相 应的抽取性能；一般的非专业人员经过简单培训就能维护。缺点是技术难度高， 7 浙江大学硕士学位论文 第1 章绪论 前期研发成本高，周期长。适合网页库级别结构化数据采集和搜索的高端应用。 中文网页的结构化信息抽取过程中，面临着一些难以克服的困难。其中中文 命名实体的识别技术发展较为缓慢。命名实体是文本中基本的信息元素，是正确 理解文本的基础。命名实体识别的难点在于：在不同领域、场景下，命名实体的 外延有差异；数量巨大，不能枚举，难以全部收录在词典中；某些类型的实体名称 变化频繁，并且没有严格的规律可以遵循；表达形式多样；首次出现后往往采用缩 写形式等。在网络视频中，目前网络视频类别、网络视频名称等，名字千奇百怪， 对他们进行识别就更加困难了。命名实体识别的方法主要分为：基于规则的方法 和基于统计的方法。 1 3 4 暗藏网页的信息抽取 因特网上还存在一个被称为“暗藏网”( t h eh i d d e nw e b ) 的网络1 5 】，即那些网 上数据库系统。据估计因特网上8 0 的内容存在于这种看不见的因特网中。特别 是在网络视频分享网站中，各个网站提供的网络视频信息大都以底层数据库的形 式存在，用户输入查询信息后，这些网页自动生成。搜索引擎的“网络爬虫”抓 不到这些网页。所以，为了收集这些信息，还需要一种独立的工具。即“分装器” ( w r a p p e r ，也译“包装器”) 。 分装器是一个程序，用于从特定的信息源中抽取相关内容，并以特定形式加 以表示。在数据库环境下，分装器是软件的组成部分，负责把数据和查询请求从 一种模式转换成另外一种模式。在因特网环境下，分装器的目的是把网页中储存 的信息用结构化的形式储存起来，以方便进一步的处理。 1 4 网页信息抽取技术在垂直搜索引擎系统中的地位 网页信息抽取技术在垂直搜索引擎中有相当重要的地位，一个好的网页信息 抽取模块可以极大地减少网页后台程序人员的工作量，增强垂直搜索引擎的可维 护性，在垂直搜索引擎系统当中处在一个比较核心的地位，也是研究的热点所在。 8 浙江大学硕士学位论文 第l 章绪论 1 5 本章小结 本章主要介绍了垂直搜索引擎的概念和其体系结构还有垂直搜索中涉及到 的一般技术，包括页面分析技术、超链接分析算反，网页信息的结构化抽取和暗 藏网页的信息抽取，最后阐明了网页信息抽取在垂直搜索引擎当中的重要作用。 9 浙江大学硕士学位论文第2 章网页信息抽取的相关工作 第2 章网页信息抽取的相关工作 本章将主要介绍网页信息抽取领域相关的工作，2 1 节将给出网页信息抽取 问题的描述，包括信息抽取的历史和网页信息抽取的形式化定义。2 2 节将结合 现在互联网的特点总结网页信息抽取的特点和难点。2 3 节将讨论网页信息抽取 的技术现状，将根据不同的分类方法讨论现有的网页信息抽取方法，对当前的方 法进行比较。 2 1 网页信息抽取问题的描述 信息抽取是从一个文档提取出相关的结构化信息。网页信息抽取是在互联网 环境下的信息抽取问题。本文讨论的信息抽取都是指网页信息抽取。输入信息抽 取系统的是原始网页，输出的是固定格式的信息点。信息点从各种各样的网页中 被抽取出来，然后以统一的形式集成在一起。这就是信息抽取的主要任务。 信息以统一的形式集成在一起的一个好处是方便检查和比较，例如比较来自 不同网站的商品信息，这可以帮助互联网用户从更大地范围寻找自己感兴趣的商 品。还有一个好处是能对数据作自动化处理。结构化的数据是开发人员比较喜欢 的数据方式，处理起来比原本网络上的异构数据要方便许多。 网页信息抽取技术对于从大量的网页中抽取需要的特定信息说是非常有用 的。在网上，同一主题的信息通常分散存放在许多不同网站上，表现的形式也各 不相同。若能将这些信息收集在一起，用结构化形式储存，那将是有益的，成功 的信息抽取系统将把互联网变成巨大的数据库 2 1 1 信息抽取和信息检索的区别 信息抽取( i n f o r m a t i o ne x t r a c t i o n ) 和信息检索( i n f o r m a t i o nr e t r i e v a l ) 是不同的， 信息检索的目的是根据用户的查询请求从文档库中找出相关的文档。用户必须从 l o 浙江大学硕士学位论文第2 章网页信息抽取的相关工作 找到的文档中翻阅自己所要的信息。 就其目的而言，信息检索和信息抽取的不同可表达如下：信息检索从文档库 中检索相关的文档，而信息抽取是从文档中取出相关信息点。这两种技术因此是 互补的。若结合起来可以为文本处理提供强大的工具【6 】。 信息检索和信息抽取不单在目的上不同，而且使用的技术路线也不同。部分 原因是因为其目的差异，另外还因为它们的发展历史不同。多数信息抽取的研究 是从以规则为基础的计算语言学和自然语言处理技术发源的。而信息检索则更多 地受到信息理论、概率理论和统计学的影响【6 1 。 2 1 2 信息抽取的历史 自动信息检索已是一个成熟的学科，其历史与文档数据库的历史一样长。但 自动信息抽取技术则是近十年来发展起来的。有两个因素对其发展有重要的影 响：一是在线和离线文本数量的几何级增加，另一是“消息理解研讨会，【7 】( m u c ) 近十几年来对该领域的关注和推动。 i e 的前身是文本理解。人工智能研究者一直致力于建造能把握整篇文档的精 确内容的系统。这些系统通常只在很窄的知识领域范围内运行良好，向其他新领 域移植的性能却很差【8 】。 八十年代以来，美国政府一直支持m u c 对信息抽取技术进行评测。各届m u c 吸引了许多来自不同学术机构和业界实验室的研究者参加信息抽取系统竞赛。每 个参加单位根据预定的知识领域，开发一个信息抽取系统，然后用该系统处理相 同的文档库。最后用一个官方的评分系统对结果进行打分【7 】。 研讨会的目的是探求i e 系统的量化评价体系。在此之前，评价这些系统的方 法没有章法可循，测试也通常在训练集上进行。m u c 首次进行了大规模的自然 语言处理系统的评测。如何评价信息抽取系统由此变成重要的问题，评分标准也 随之制定出来。各届研讨会的测试主题各式各样，包括拉丁美洲恐怖主义活动、 合资企业、微电子技术和公司管理层的人事更迭。 浙江大学硕士学位论文第2 章网页信息抽取的相关工作 过去五、六年，i e 研究成果丰硕。英语和日语姓名识别的成功率达到了人类 专家的水平。通过m u c 用现有的技术水平，我们已有能力建造全自动的i e 系 统。在有些任务方面的性能达到人类专家的水平【8 】。不过自1 9 9 3 年以来，每届最 高组别的有些任务，其成绩一直没有提高( 但要记住m u c 的任务一届比一届复 杂) 。一个显著的进步是，越来越多的机构可以完成最高组别的任务。这要归公 于技术的普及和整合。目前，建造能达到如此高水平的系统需要大量的时间和专 业人员。另外，目前大部分的研究都是围绕书面文本，而且只有英语和其他几种 主要的语言。 2 1 3 网页信息抽取的形式化描述 一个简单的网页信息抽取模型可概括为：向特定资源库发出一个查询请求， 得到相应的响应页，然后网页抽取模块从响应页中抽取出所需要的信息，将其映 射成相应的标记信息，如图2 1 网页信息抽取模型所示。 图2 1 网页信息抽取模型 图中q 是以查询语言q 构造的查询表达式，表达了用户所需要的信息。它可 能是s q l 或k q m l 语句，也有可能是c g i 脚本参数所组成的语句。p 为查询响 应页，可以把它看成是a s c i i 字符集中的字符串，含有一个或多个所需信息的 元组( 例如，假设我们要抽取的信息为各个国家所对应的电话号码区域号，则具 1 2 浙江大学硕士学位论文第2 章网页信息抽取的相关工作 体的( 国家，区域号) 即为一个元组。它有两个属性：国家，区域号。形式地讲， 一个元组可表达为一个具有k 个字符串属性的向量 ) s 为特定的信 息资源库，可以看成是一个将查询表达式转化成响应页p 的函数。l 为标记信息 集，个标记信息集l 就是一个响应页中所要抽取的所有信息元组集合。其形式 化表示如图2 2 所示： 即该响应页中含有lll o 个元组，每个元组具有k 0 个属性。整数1 k k 是属性索引号，而整数1 m ill 则是该响应页中的元组索引号，每个 表示为一个单一的属性集。b 呲是第m 个元组的第k 个属性在该响应页 中的起始位置，e m , k 则是它的结束位置。因此，第m 个元组的第k 个属性的值为 该响应页中处于b m , k 和e 札k 两个位置点之间的字符内容。 l = ( j ， ， ) ， ( ， ， ) ， ( ， ， ) 图2 2 形式化表示 w 也被称为包装器，是整个信息抽取模型的核心，可以将w 看成是一个将 响应页p 映射成标记信息集l 的函数。用公式表示即为w ( p ) = l ，也就是说，在响 应页p 上调用w 所得结果为标记信息集l 2 1 4 信息抽取的例子 互联网上的信息分属于不同的组织，可能会有成千上万个网站发布同一种类 的信息，这就导致了信息的极端异构性和无序性，这也使得互联网上的信息加工、 浙江大学硕士学位论文第2 章网页信息抽取的相关工作 分类和检索都非常困难。 从图2 3 数据来源网站一的数据格式和图2 4 数据来源网站二的数据格式 中我们可以看到，两个网站都多同样的一条数据记录做出了显示，但是，其显示 格式却截然不同。 m 瓣u 5 1 麓6 8 ；警麓0 7 = 3 0 7 ：3 7 3 75 0 1 0 0 0 9 ：3 0 磊裟8 秀篷以 _ 蘑山秽t 场 所有舱位暹改簦 图2 3 数据来源网站一的数据格式 价格怠飞，羹斌耋抗斑搬税费o 蚣逋致篝l i t e r ￥9 2 0 ：裟瑟瑟黼 。末麓m u 5 1 6 8 7 3 7 ，5 0 臻醴藿錾霹 班 图2 4 数据来源网站二的数据格式 最终我们都要把其中的数据统一为数据库表中的格式，可能包括如下内容航 空公司、机场税、出发机场、出发城市、舱位类型、航班号、目的机场、目的城 市、出发时间、到达时间、飞机折扣、燃油税、原价、机型和现价信息。 以上整个过程就是网页的信息抽取。 2 2 网页信息抽取对象的特点和难点 历经几十年的研究，信息抽取领域积累了丰富的理论和技术，将成熟的信息 抽取技术应用到互联网上是早期网页信息抽取系统的自然做法，但由于互联网有 着不同于传统信息抽取的特点，这样是不够的。仔细分析，互联网信息抽取在下 述方面区别于传统信息抽取，有着自己的特点，同时这些特点也是网页信息抽取 的难点所在： 海量规模。人们开发了专门的方法估测互联网的大小，h e t c r a f t 1 4 浙江大学硕士学位论文 第2 章网页信息抽取的相关工作 是一家著名的调研公司，它会统计互联网上的服务器数量以统计各大服务器 系统供应者的市场占有率，我们可以使用它的数据粗略的估算互联网的大小。 最新统计表明，2 0 0 8 年4 月是，互联网上仅仅是网站就有1 6 5 ，7 1 9 ，1 5 0 个， 它们都包含数量巨大的网页，其中隐藏着更多的动态网页。因此，网页信息 提取的对象网页有着海量的规模( 如图2 5 ) 。 卜t - - 饥价oo 一一nn nn 寸寸l i dn9 bb 西饥西饥饥西西西ooo 口oo o o o o oo 口口口口o o 西饥。西饥西价oo o o o o o o o o o o9 9 99 一卅州一一一d n nn n n nn n n nn nn 州 焉；焉写写写焉弓写号焉；暴；焉；磊- ；焉- ；磊写写弓焉 1 1 - 怔 图2 5 互联网网站近年来变化趋势 异构性。今天互联网覆盖全球几乎所有国家，内容基本上包括全部的 学科领域、语言，跨越不同的政治派别、宗教信仰。互联网上的各网站、页 面分属不同的组织机构或个人所有，使用互联网的目的从严肃的科学研究到 政治宣传、谋求商业利润、娱乐消遣无所不有。互联网页面的风格、创作方 式也是五花八门的。互联网的多样性与其巨大数量一样是空前的。 动态性。互联网从诞生到今天直保持爆炸性的高速增长，而且据专 家预测这种趋势在将来会持续相当一段时间。在互联网上新的站点页面不断 出现，各站点页面的拥有者经常进行更新维护，有些在一段时间后被删除。 互联网上每时每刻都在发生着变化。 1 s 一 一 一 一 一 一 一 一 一 。 1 1 j i 浙江大学硕士学位论文第2 章网页信息抽取的相关工作 半结构化。h t m l 是一种典型的半结构化数据，在互联网上存在许多 不严格的结构关系，如页面之间的链接关系、用户访问记录。页面内部结构 信息更加丰富，包括h t m l 页面规范，各种标签( t a g ) 透露的信息 检索对象质量良莠不齐。互联网上的页面从尖端科研报告到初学者的 试验页面，其质量差别非常大。而经典信息抽取在其理论和技术中没有质量 方面的考虑。 2 3 当前技术现状 网页信息抽取程序( i n f o r m a t i o ne x t r a c t o r ) 也被成为包装器( w r a p p e r ) ，用于从特 定的信息源中抽取相关内容，并以特定形式加以表示。在信息集成系统当中，包 装器是指把来自于不同数据源的异构数据包装成统一界面供用户调用的组件。在 包装器的帮助下，查询模块的逻辑在应用到不同数据源( 比如说不同的数据库) 时 就不需要做大的修改。如果数据源是一个w e b 服务器，包装器就需要通过h t t p 或者其它协议访问相应的服务器，然后从得到的可能是h t m l 网页中抽取相关的 数据，然后再把这些数据与来自于其它数据源的数据集成在一起供用户查询。在 这整个过程当中，信息抽取是最关键的步骤( 如图2 6 所示) ，因此很多时候也 把包装器就称为是信息抽取【9 】。 根据不同的标准可以把当前的网页信息抽取工具分成不同的类别，以下分别 按所采用的技术手段和自动化程度把当前的工具和技术做一个分类阐述。 1 6 浙江大学硕士学位论文第2 章网页信息抽取的相关工作 w e b 数弩蠼岁 w e b 数謦婆夕之芝! 譬e 翟 土 数据源广数据源，。箍一乏 、一、7 商 苗i 罄藿 薄 蠢雪 羹霎 妇l 与 鍪壹 田 躏苫 多驴妙 临列数据库临时数据库临时数据库 一 五稚 一 豇 彗 好 营 肄 描 礁 j b 图2 6 包装器与信息抽取 2 3 1 按照主要技术手段分类 随着需求的增加，人们提出了多种不同的技术来实现w e b 页面的数据抽取， 涉及到多个研究领域，譬如自然语言处理过程、语言和语法处理、机器学习、信 息检索、数据库以及本体论等。这些技术之间有着非常明显的差异，处理能力和 适用对象也各不相同。下面把在包装器开发中采用的主要技术手段作为分类的依 据，对使用特定技术开发的典型系统及实现方法进行分析【9 】。 面向包装器开发过程而设计的语言 包装器语言是一种特定的抽取和包装应用逻辑语法描述规则的集合。由于面 向半结构化数据的抽取和包装过程涉及到特定的应用领域，因此针对包装器开发 过程而设计的语言是对传统编程语言功能的一种扩展，对于包装器的开发过程非 常有效，并被广泛采用。例如m i n e r v a 1 0 1 、t s i m m i s t l1 1 、w e b o q l t l 2 1 和i n t e m e t s o t t b o t s 1 3 。 1 7 浙江大学硕士学位论文第2 章网页信息抽取的相关工作 基于h t m l 结构特征的工具 这类工具充分利用h t m l 文件所固有的结构特征来实现数据抽取任务。在数 据抽取过程之前，先将文档转换为一个反映出h t m l 文件中标记所处层次的解析 树；然后通过自动或者半自动的方式生成抽取规则，并将规则应用于解析树上。 基于这种方式的代表性系统包括w 4 f t l 4 1 、x w r a p t l5 1 、r o a d r u n n e r 1 6 1 和l i x t o 17 1 。 基于自然语言处理的包装工具 这类工具借助了自然语言处理技术( n l p ) 来归纳数据抽取规则，对符合自 然语言规则的文档的数据进行抽取。这些工具通常使用包括过滤、词性标注在内 的自然语言处理技术来建立短语和短语之间的关系，进而获得抽取规则。所产生 的抽取规则通常基于语法约束和语义约束。因此，基于自然语言处理技术而实现 的抽取工具更加适用于由符合语法规则的文本构成的h t m l 文档，如用列表形式 表示的求职信息页面等。使用n l p 且面向h t m l 文档的代表性工具包括 r a p i e r t l 8 1 、s r v 1 9 】和w h i s k 2 们。 包装器归纳工具 包装器归纳工具通过对一系y u i ) i i 练样本文档的分析，归纳得到基于定界符的 抽取规则。这类工具与基于自然语言处理的工具之间的主要差别在于前者并不依 赖于语言约束，而是依据半结构化文档中的格式化特征形成抽取规则。与基于自 然语言处理的包装工具相比，这类工具更加适合于h t m l 文档，代表性的工具包 括w i e n 2 1 1 、s o f t m e a l y 2 2 】和s t a l k e r 2 3 1 。 基于建模方式的工具 这类工具的实现方式是定义出所需抽取数据对象的结构，系统对源文档进行 搜索，查找符合这种结构的数据片段。数据结构的定义通过符合一种特定的数据 模型的建模原语完成，例如元组、列表等形式。这种类型的典型工具包括 n o d o s e 2 4 】和d e b y e 2 5 , 2 6 。 基于本体的工具 前面介绍的这些技术均基于内容数据在文档中的表示特征来生成抽取规则 或抽取模式，而基于本体的工具则直接依赖于内容数据本身完成。针对一个特定 1 r 浙江大学硕士学位论文 第2 章网页信息抽取的相关工作 的领域应用，一个本体可以被定义并用于对出现在文档中的常量进行定位，同时 完成本体对象的封装。基于本体的方法首先需要本体的领域专家进行手工建模， 在本体模型建立后，数据的抽取就可以实现自动化，且具有很好的适应性。最具 有代表性的工具是由b r i g h a m y o u n g 大学的数据抽取研究小组开发的原型系统 【2 7 】 o 2 3 2 按照自动化程度分类 除了按照主要技术手段分类，还可以从各种方法的自动化程度来看，信息抽 取即包装器生成依照其自动化程度可以分为手丁编写、半自动生成和现在正在研 究的全自动化生成三类。 手工编写包装器不仅要求用户有一定的编程水平，而且开发费时，维护难。 使用面向包装器开发过程而设计的语言生成包装器，基本上都需要手工编写代 码。 基于自然语言处理技术、包装器归纳技术和基于建模技术的方法都是半自动 的方法，在这些技术中都不仅要求用户提供训练实例集，还要求用户对页面内容 有一定的先验知识，系统的适应性较差。因此，还需要进行改进。当前大部