（计算机科学与技术专业论文）增量式web信息采集与信息提取系统的研究与实现.pdf

，独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其它人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 学位论文使用授权书 v t l 兰铲 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其它复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ： 磅碜嗲导师( 签名) ：问嘶期：侈，岁加 摘要 随着网络的迅猛发展，人们越来越依赖从网络上获取信息。网络信息资源 的保存寿命通常只有几十天，随着时间的推移，大量旧的网络信息资源正在被 新的网络信息淹没。如何更迅速更准确地从互联网上采集有用的信息成为研究 的热点。大规模的非增量式采集技术已经发展很成熟。为了避免因重复搜集未 变化的网页而带来时间上的浪费，增量采集技术应运而生。为了提高更新采集 的效率和信息抽取的抽准率，本文主要针对增量更新的w e b 信息采集及基于隐 马尔夫模型的信息提取进行了研究。 本文分析了w e b 信息采集系统的研究背景、研究意义、发展现状以及其面 临的各种困难和挑战，阐述了信息采集系统的工作原理和网络爬虫的工作流程， 在研究信息采集系统以及信息抽取的核心技术的基础上结合增量信息采集系统 的需求，明确了系统开发过程中要解决的问题，提出了具体的设计方案，构建 了一个性能良好，具有可扩展性的增量信息采集及信息提取系统。该系统包括 如下几个模块：页面采集、页面解析、u r l 去重、页面去重和更新检测。论文 的主要工作以及创新如下： 1 引入了目录型网页，提高了发现新网页的效率，采用f w k n n 算法有 效地识别了目录型网页。 2 针对m d 5 算法过于苛刻的问题，本文采取基于网页框架和规则的方法 先对网页去噪后，再对网页正文计算得出唯一的m d 5 值。此方法在一定程度上 提高了网页相似性分析的准确率。 3 在预测网页的变化频率方面，通过分析泊松模型存在的缺点，引入了更 新频率计算窗口，提出内容分析和网页隶属分析，避免了建立模型前需要大量 的训练数据，能更准确地预测网页变化频率。 4 在研究隐马尔可夫模型的基础上，改进了基于i - i m m 的信息抽取方法，对 含有固定格式的信息项采用正则表达式处理，并对未知观测值概率进行了平滑 处理。实验表明该方法获得了更好的抽取效果。 最后，通过改进的w e b 增量采集及信息提取系统的实验，分析了运行的数 据，证明系统己成功达到了预期的目标。 关键词：增量采集，w e b 信息采集，信息抽取 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r a c t ，p e o p l ea r ei n c r e a s i n g l yd e p e n d e n to n t h en e t w o r kt o g e ti n f o r m a t i o n t h el i f e t i m e o fn e t w o r ki n f o r m a t i o nr e s o u r c e s u s u a l l yo n l yd o z e n so fd a y s ，a st i m eg o e so n ，al o to ft h eo l dn e t w o r ki n f o r m a t i o n r e s o u r c e sa r eo v e r w h e l m e db yt h en e wn e t w o r ki n f o r m a t i o n h o wt om o r eq u i c k l y a n da c c u r a t e l yc o l l e c tf r o mt h eu s e f u li n f o r m a t i o no nt h ei n t e r n e ti sb e c o m i n gt h e r e s e a r c hh o ts p o t t h el a r g es c a l en o n - i n c r e m e n t a lc o l l e c t i o nh a sb e e nd e v e l o p e d v e r ym a t u r e i no r d e rt o a v o i dt h ew a s t eo ft i m eb e c a u s eo fc o l l e c t i n gt h ep a g e s w h i c hi sn o tc h a n g e ，i n c r e m e n t a lc o l l e c t i o nc o m ei n t ob e i n g i no r d e rt oi m p r o v et h e e f f i c i e n c yo fu p d a t i n gc o l l e c t i o na n da c c u r a c yo fe x t r a c t i o n ，t h i sp a p e rf o c u s e so n i n c r e m e n t a lu p d a t ew e bi n f o r m a t i o nc o l l e c t i o na n di n f o r m a t i o ne x t r a c t i o nb a s e do i l h m m t h i sp a p e ra n a l y z e st h eb a c k g r o u n d ，s i g n i f i c a n c e , p r e s e n ts i t u a t i o na n di t s d i f f i c u l t i e sa n dc h a l l e n g e sf a c e di nt h er e s e a r c ho fw e bi n f o r m a t i o nc o l l e c t i o n s y s t e m ，d e s c r i b e st h ei n f o r m a t i o nc o l l e c t i o ns y s t e mo p e r a t i o n a lp r i n c i p l ea n dt h e w e bc r a w l e rw o r kp r o c e s s e sa n do nt h eb a s i so fc o r et e c h n o l o g yo fi n f o r m a t i o n c o l l e c t i o na n di n f o r m a t i o ne x t r a c t i o nc o m b i n e dw i t ht h ei n c r e m e n t a li n f o r m a t i o n c o l l e c t i o nd e m a n d ，d e t e r m i n et h ep r o b l e m st ob es o l v e di nt h ed e v e l o p m e n to f s y s t e m ，p r o p o s es p e c i f i cd e s i g n , b u i l dag o o dp e r f o r m a n c ea n ds c a l a b i l i t yo ft h e i n c r e m e n t a li n f o r m a t i o nc o l l e c t i o ns y s t e m t h es y s t e mi n c l u d e s t h ef o l l o w i n g m o d u l e s ：p a g ec o l l e c t i o n ，p a r s i n g t h ep a g e ，r e i b _ o v ed u p l i c a t eo r e s ，r e m o v e d u p l i c a t ep a g e sa n du p d a t e dp a g e sc h e c k e r t h em a i nw o r ka n di n n o v a t i o na r ea s f o l l o w s ： 1 t h ei n t r o d u c t i o no ft h ei n d e xp a g e s ，a n di m p r o v e st h ee f f i c i e n c yo ft h e d i s c o v e r yo f n e w p a g e s ，u s i n gf w k n na l g o r i t h mc a ni d e n t i f yt h ei n d e xp a g e 2 t o oh a r s hf o rt h em d 5 a l g o r i t h m ，t h i sp a p e ra d o p t sa m e t h o db a s e do nw e b f r a m e w o r ka n dr u l e s f i r s t , r e m o v e sn o i s e ；t h e nc a l c u l a t e sm d 5 v a l u eo ft h eb o d yo f p a g e t os o m ee x t e n t , t h i sm e t h o di si m p r o v e dt h ea c c u r a c yo fp a g es i m i l a r i t y a n a l y s i s 一 3 w i t hr c s p e c tt op r e d i c tc h a n g e si nf r e q u e n c yo f t h ep a g e ，t h r o u g h 姐a l y z i n g i es h 0 c o m i n 缪o fp o i s s o nm o d e l ，t h i sp a p e ri n t r o d u c e s t h eu p d a t e 董q u 饥c y c a l c u l a t i o nw i n d o w ，觚dt h ec o n c e p t o fc o n t e n ta n a l y s i sa n dp a g eb d o n g i n g a i l a l y s l s ， 啪e s t h ef o r e c a s ta c c u r a c yo ft h ef r e q u e n c y o fp a g ec h 锄g e s 4 b a s e do nt h es m d yo fh i d d e nm a r k o vm o d e l ，t h i sp a p e rt m p r o v e s t h e i l l f o m l a t i o ne x t r a c t i o nm e t h o do nt h eb a s i so fh m m ，u s i n gr e g u l a re x p r c s s l o n t 0 e x t r a c t 恤1 c i x e df 0 觚，s m o o t h i n g t h e p r o b a b i l i t y o fu n k n o w no b s 洲a t i o n 8 e x p 幽e 1 1 t ss h o wt h a tt h ee x t r a c tm e t h o do b t a i n e d b e t t e rr e s u l t s f i n a l l y t h ei m p r o v e dm e t h o de x p e r i m e n t s a l ed o n ea n dt h ea n a l y s e s o f e x p 嘶m e 吣r 呶l l td a t a , w h i c ha l ep r o v e t h a tt h es y s t e mh a ss u c c e s s 如l l ya c l l i e v e d t h ed e s i r e dg o a l s k e y w 。r d s ：h l c r e m e n t a l c o l l e e t i 。i l ，w e b i n f o r m a t i 。nc o i l e c t i 。n ，i n f o m a t i o n e x t r a c t i o n h i 目录 摘要i a b s t r a c t 。i i 第1 章绪论l 1 1 研究背景。l 1 2 研究意义。2 1 3 研究现状2 1 4 本文安排5 第2 章w e b 信息采集相关技术研究6 2 1 信息采集系统概述6 2 1 1 搜索引擎的基本结构6 2 1 2 信息采集系统的工作原理8 2 2 爬虫工作流程。9 2 3 增量采集技术1 2 2 3 1 增量采集的定义1 2 2 3 2 增量采集策略。1 2 2 4 信息抽取技术1 4 2 4 1 信息抽取的策略。1 4 2 4 2 隐马尔可夫模型1 5 2 5 本章小结l7 第3 章改进的增量采集算法18 3 1 目录型网页识别18 3 1 1 目录型网页的定义1 8 3 1 2 目录型网页识别算法18 3 1 3 目录型网页识别的应用1 9 3 2 网页的相似性分析：19 3 2 1 基于m d 5 算法的内容变化判定2 0 3 2 2 网页去噪算法2 2 3 3 预测网页的变化频率2 3 3 3 1 泊松模型2 3 3 3 2 改进的泊松模型2 5 3 4 本章小结2 6 第4 章网页信息抽取算法2 7 4 1 网页预处理2 7 4 2 构造抽取模型。3 1 4 3 信息提取和精化3 2 4 a 本章小结3 3 第5 章系统的实现与分析3 4 5 1 系统需求分析3 4 5 2 系统设计3 4 5 3 系统实现3 6 5 3 1 页面采集模块3 6 5 3 2 页面解析模块3 6 5 3 3u r l 去重模块4 l 5 3 4 页面去重模块4 1 5 3 5 更新检测模块4 2 5 4 系统增量采集实验4 4 5 4 1 增量采集实验4 4 5 4 2 信息提取实验4 5 5 5 本章小结昱4 6 第6 章总结与展望4 7 6 1 总结：4 7 6 2 下一步的工作4 7 致谢。4 9 参考文献5 0 攻读硕士学位期间发表的学术论文5 5 武汉理工大学硕士学位论文 1 1 研究背景 第1 章绪论 随着因特网的迅猛发展，w e b 信息迅速海量地增加，用户要在信息海洋里查 找所需信息，就像大海捞针一样。而搜索引擎技术恰好解决了这一难题。根据 c n n i c 的统计，搜索是互联网上仅次于电子邮件的应用，是网民上网最重要的事 之一。搜索引擎自动从互联网上发现、搜集信息，对信息经过一定处理后，提供 给用户进行检索。互联网上的信息浩瀚万千，而且杂乱无章，搜索引擎提供的信 息搜索功能帮助用户方便快捷地查询到有用的信息，搜索引擎技术因此成为计算 机界和学术界争相研究的对象。 由于各种网络信息资源具有信息量大、寿命短、传播范围广、来源广泛、增 速快、格式及表达方式多样、内容庞杂而且质量不一的特点，因此难以完整的收 集。c n n i c 发布了第2 7 次中国互联网络发展状况统计报告。报告认为，网页的 规模反映了互联网的内容丰富程度。自2 0 0 3 年开始，中国的网页规模基本保持 翻番增长，2 0 1 0 年网页数量达到6 0 0 亿个，年增长率7 8 6 。从详细情况来看， 2 0 1 0 年动态网页增长幅度高于静态网页，静态与动态网页的比例已经从1 3 ：1 降低为1 1 4 ：l 。与此同时，平均每个网站的网页数达到3 1 4 1 4 个，年增长率达 到2 0 2 。【l l 其中企业和个人等非官方的网络信息资源难以收集，政府、新闻出版、 大学等机构的网络信息资源则相对较易收集。 网络信息资源的保存寿命通常只有几十天，随着时间的推移，大量旧的网 络信息资源正在被新的网络信息淹没。中文网络信息资源也是中华文明的成果， 隶属于中华数字文化遗产，理应得到妥善保存和保护。国家图书馆积极开展了网 络信息收集相关技术和标准的研究，于2 0 0 3 年初成立了网络信息资源整合科 研小组，其中针对表层网页信息开展了“网络信息资源收集和保存试验项( w i c p ) 目 。w i c p 试验项目是按照网站单元和网页单元对网络信息资源进行收集、整 合和保存【n j 。 当前，w e b 信息采集技术正广泛地应用于网站结构情况分析、搜索引擎技术、 用户兴趣挖掘研究、网页有效性分析、内容安全性检测、图进化、以及信息的个 性化获取等多种研究和服务中。随着互联网中信息数量的飞速膨胀和用户对搜索 服务质量要求的提高，信息采集的任务也变得越来越艰巨。虽然已有许多成功使 用的和主流的信息采集系统，但是由于商业运作的原因将许多关键技术部分匿而 武汉理工大学硕士学位论文 不宣，这种方式显然对于信息采集技术的发展非常不利。尽管如此，国内外研究 机构仍然对它进行了许多积极的研刭3 1 。 1 2 研究意义 如今，搜索引擎是我们获取信息的主要入口。在搜索页面的背后，搜索引擎 抓取网页，下载网页到硬盘并索引，以应对用户的搜索需要。从总体来看，整个 网络的数据变化非常快，使得所有已存储的网页很快就过时了，这转而导致了搜 索质量的降低。由于整个网络的数据量相当大，并且数据是动态变化的，发布网 页者在一定程度上有自主权，所以让搜索引擎维持存储的内容与网络完全同步是 不可行的。 因为信息源是随时在变化的，信息采集器就需要不停的对数据进行刷新，但 是由于每次刷新都需要对数据进行重新抓取，因此会花费大量的时间，这个时间 周期从数周到一个月不等【4 】，从而导致数据的更新产生了严重的滞后。不同的网 页来自于不同属性的网站，因此更新的频率也大不相同，比如新闻类型的站点大 多是几个小时更新一次，而其他一些教育、政府之类的机构站点也许在一个月的 时间之内也不会有什么更新和变化。所以，需要针对不同类型的网站制定不同的 更新策略，使得网站能够将本地数据库和网络数据进行及时的更新和同步。 网页采集可以分为集中式采集和增量式采集。集中式采集是在一个工作周期 内，搜索引擎对网页进行全网搜集。这种方式的优点是易于实现、数据全，不过 有明显的滞后性。增量式采集即在以前搜集网页的基础上，采用某种更新策略， 在适当的时间再去获取网页信息，并把变化的网页及新出现的网页保存到本地。 这种方式通常需要记录网页的历史变化信息，而且不同的算法效果也不尽相同。 增量式采集可以通过对网页更新度的估计，极大地减少爬虫系统更新页面的工作 量，提升页面的新鲜度。 1 3 研究现状 目前的w e b 信息采集基本上可分为以下几种：基于整个w e b 的信息采集，基 于元搜索的信息采集，基于a g e n t 的信息采集，基于主题的w e b 信息采集，基于 用户个性化的w e b 信息采集，迁移的信息采集，增量式w e b 采集。实际的采集系 统通常都是几个采集技术相结合实现的。 ( 1 ) 基于整个w e b 的信息采集 这种方式的目标是给定的种子u r l 扩展到整个w e b 的信息采集。优点：采集 数据广，速度快，对采集页面的顺序要求相对较低。缺点：采用这种方法的采集 2 武汉理工大学硕士学位论文 数量和范围的规模都非常大，因此对存储空间和采集速度的要求很高。这种类型 的w e b 信息采集器构建的搜索引擎，适合搜索广泛的主题。典型的代表有： m e r c a t o r 5 1 、g o o g l e 6 7 】和i n t e r n e t a r c h i v e 【8 1 。 ( 2 ) 基于元搜索的信息采集 元搜索是搜索引擎之后或之上的搜索引擎，元搜索可以同时查询多个搜索引 擎的站点。元搜索可以“查一个元搜索引擎就相当于查多个独立搜索引擎，可以 收到事半功倍的效果。优点：使用户避免了在多个搜索引擎系统之间的切换及查 询请求的重复输入，不需要考虑网页索引数据库的建立和维护，可以集中精力与 财力用于查询请求的分发与查询结果的处理，可检索多个索引数据库，提高检索 的效率。缺点：检索时间有时过长，有些词组和布尔检索算符不能被正确处理， 检索结果较少，不支持许多独立搜索引擎所支持的高级检索功能。典型代表有： v i v i s i m o 、i n f o s p a c e 9 、搜星搜索引擎。 ( 3 ) 基于a g e n t 的信息采集 目前智能a g e n t 技术的发展非常迅速，因此结合了a g e n t 和信息采集技术的 研究也变得越来越热门。智能a g e n t 系统是一种通过包装之后，能在一定环境下 进行灵活自主活动的计算机系统。系统在运行时能够主动控制自己的行为和内部 的状态，不需要由人或者其他的东西对它进行控制，能够协调多个a g e n t 进行相 互间的信息交换和协作，能够感知系统环境并对此产生一定的影响，而且系统还 能够拥有普通人所拥有的知识、意念、许诺等能力，因此可以说智能a g e n t 系统 拥有了人类的社会智能。智能a g e n t 系统在针对用户的个性化采集过程中，可以 自动了解到用户兴趣的改变，能够对采集策略进行智能化的调整。正是因为有了 这些优点，智能a g e n t 系统能够方便灵活的处理类似于基于主题和用户个性化等 信息采集工作。 典型的智能a g e n t 系统包括：美国爱荷华大学的a r a c h n i d 项目，该系统主 要模拟了生态系统的发展以及演化的过程，并基于此来设计建设系统的网络信息 采集器【1 0 ，1 1 】；美国麻省理工学院的a m a l t h a c a 系统【1 2 】和l e t i z i a 系统【1 3 】， a m a l t h a c a 系统是基于用户个性化的需求，采用了a g e n t 技术进行设计的元信息 采集器，l e t i z i a 系统是通过设计智能a g e n t 辅助工具，来对用户的w e b 页面浏 览进行辅助；美国斯坦福大学的基于学习a g e n t 的主题信息采集系统【1 4 】，该系 统能够通过建立向量空间模型v s m 和运用经典的t f * i d f 算法对搜索到得页面进 行评价，根据评价结果的高低并结合用户反馈的信息和系统的学习策略来不断完 善自身的启发式搜索。 ( 4 ) 基于主题的w e b 信息采集 3 武汉理工大学硕士学位论文 这种采集方法的特点是采集时不是采集所有页面，而是在事先定义好的主题 集范围内采集与主题相关的页面。主题包括样本文件和关键词。优点：由于这种 采集器不采集与主题无关的页面，因此与基于整个w e b 的信息采集方法相比，在 网络和硬件资源的节省方面起到了极大的作用，保存的页面也比较接近于当前网 络上的网页。缺点：因为主题词不能随意定义，并不是每个词都可以作为主题， 也不是每个词都适合作为主题，所以有实际意义的主题该如何定义，在采集时该 如何判定页面与主题相关，这些问题都是亟待解决的。主要代表系统有：由印度 理工大学和i b m 研究中心联合开发的一个基于主题的w e b 信息采集器，是该采集 方法的典型代表【1 5 1 ，另外一个是基于主题的w e b 信息采集方法是基于两个假设 条件由a g g a r w a l 提出l l 6 1 。 ( 5 ) 迁移的信息采集 一般采集器下载页面时是先由本地向w e b 站点服务器发送页面请求后下载 页面至本地，而迁移的信息采集先将自己上载到它需要采集的服务器中，然后在 当地进行采集信息，最后将采集结果压缩后回传到本地。优点：这种方式节少了 网络资源，由于它在网络服务器端做了大量的裁剪工作。缺点是：因为这样采集 站点会因为给访问者提供了太大权限而遭受攻击，采集器可能并不被采集对象所 信任。解决的方法就是为w e b 站点服务器建立一个信任机制。另外一种折衷的方 法是将采集器不迁移到w e b 服务器，而是迁移到离被采集站点很近的地方，同样 可以达到目标。这种思路的代表性采集器是s p h i n x 信息采集器旧。 ( 6 ) 基于用户个性化的w e b 信息采集 普通的搜索引擎满足不了不同背景，不同目的和不同时期的查询请求。个性 化的w e b 信息采集弥补了这一缺点。个性化技术的实质是用户不同，采取的服务 策略不同，同时提供的服务内容也不刚1 8 】。这种个性化信息的来源一般有两个： 一是由用户通过在系统提供的个性化设置的页面中设置个性化信息；二是系统通 过跟踪用户的浏览习惯和兴趣等自动获取。 主要代表系统有：由卡耐基一梅隆大学开发的s p h i n x 1 9 】是一个典型的个性化 网页信息采集器。它具有小巧、灵活和针对性强的优点，缺点是在实用性和有效 性方面有待提高。k r a k a t o ac h r o n i c l e 【2 0 】是一个网页上的新闻站点，它由乔治 亚理工学院开发，是一个针对翌塑：翌垫凼：凸璺主纽鲤曼q q 堡么墨主么卫垫堕q ：b 主婴! 的实验 室系统，特点是个性化，由服务器端和客户端组成。 ( 7 ) 增量式w e b 采集 增量式w e b 采集一般用于更新采集的时候。基本思想：采集器不采集没有变 化的网页，只采集新产生的网页或者已经发生变化的网页。增量式采集的理想状 况是已采集到的信息与网络中的信息完全一致，但这仅仅是理想状况，由于w e b 4 武汉理工大学硕士学位论文 的异构性、动态性和复杂性使得采集到的网页有可能在相当短的时间内就发生了 变化，所以在现实中是不可能实现的，我们能做的就是采取一切办法尽量逼近这 种理想状况。这种采集方式的优点有许多：能提高网页采集的效率，由于不采集 没有变化的网页，因此极大地减少了数据采集量从而减少了采集的时间和存储资 源的浪费。在实际采集网页的方法中，这种方法得到了广泛的使用。缺点：增量 信息采集带来了算法复杂性和难度的增加。典型代表有：w e b f o u n t a i n 、u n i v c h i l ec r a w l e r 和天网增量搜集系统。 1 4 本文安排 全文分为六章，其它章节安排如下： 第2 章：w e b 信息采集相关技术研究。 第3 章：对现有的增量采集算法改进。首先介绍了目录型网页的定义，采用 基于s v m 的特征加权k n n 的算法识别目录型网页，然后对网页进行相似性分析， 研究了将网页去噪后基于m d 5 算法判定网页是否发生改变，最后采用改进的泊松 分布方法预测了网页的变化时间。 第4 章：在研究隐马尔可夫模型的w e b 信息抽取算法基础上，着重探讨了隐 马尔可夫模型在文本信息抽取中的应用，改进了信息抽取方法，构造抽取粒度细 化的d o m 树结合正则表达式能提取细化的信息点，并对未知观测值概率进行了平 滑处理。实验表明，改进的h m m 方法的能获得更好的抽取性能。 第5 章：设计实现了一个增量式w e b 信息采集系统，并分析了实验结果。 第6 章：总结与展望。回顾了本文所做的工作，提出了下一步的工作。 5 武汉理工大学硕七学位论文 第2 章w e b 信息采集相关技术研究 2 1 信息采集系统概述 2 1 1 搜索引擎的基本结构 搜索引擎系统一般由网页爬虫、分词器、索引器、查询器组成。网络爬虫负 责从互联网上采集网页信息。分词器负责将采集的网页内容进行分词处理。索引 器负责将分词器分好的词建立对应的索引数据库。查询器接收用户输入的查询条 件并进行分词处理，然后在索引数据库中查找对应的词，最后将检索结果按照相 关度和重要性进行排序，将网页的摘要信息部分反馈给用户。 搜索引擎主要的工作流程如下：首先网络爬虫每隔一定的时间自动启动，比 如g o o g l e 一般是2 8 天，按顺序读取网页u r l 服务器上的u r l 列表，按照深度或 广度优先算法采集各u r l 对应的网页，对采集的网页进行文档预处理和信息提取 处理后，将当前页面上的所有u r l 存入网页u r l 服务器中以备采集，然后给采集 的各个网页分配一个唯一的文档i d ，存入文档数据库。在采集网页的同时，切 词器和索引器开始同步工作，对已采集的网页信息进行分词处理，并根据词语在 网页中出现的位置和频率计算权值，然后将分词结果存入索引数据库。查询器首 先将用户输入的查询条件进行分词处理，然后在索引数据库中检索出所有包含检 索词的记录，最后将检索结果排序，从文档数据库中提取各网页的摘要信息反馈 给查 图2 - 1 搜索引擎工作流程图 6 武汉理工大学硕士学位论文 从圈中可以清楚地看出搜索引擎由网页爬虫、分词器、索引器、查询器四部 分组成。 网页爬虫( 即w e bs p i d e r ) ：网页爬虫实际上是一个基于h t t p 协议的网络应 用程序。网页爬虫在网络中采集网页的时候，将整个网络上的网页看成是一个有 向图。它从给定的u r l 地址开始( 通常是首页) ，读取网页内容，提取出该网页 上所有的链接地址，按照深度或广度优先算法依次遍历所有未采集过的网页 u r l ，直到把整个网站的所有网页都下载到数据库为止。在抓取网页的时候，网 页爬虫一般有以下几种遍历算法：深度优先算法、广度优先算法、启发式搜索算 法。 分词器：是将用户输入的一段文本，分析成符合逻辑的一种工具。分词的准 确与否，常常直接影响到搜索结果的相关度排序。我们知道，在英文的行文中， 单词之间是以空格作为自然分界符的，而中文只是字、句和段可以通过明显的分 界符来简单划界，唯独词没有一个形式上的分界符，虽然英文也同样存在短语的 划分问题，但是在词这一层上，中文比之英文要复杂的多、困难的多。例如，英 文句子h ei sap r o f e s s o r ，翻译为中文即：“他是一位教授 。计算机可以很简 单通过空格识别p r o f e s s o r 是一个单词，但是不能很容易明白“教”、“授 两个 字合起来才表示一个词。把中文的汉字序列按照一定的规则切分成有意义的词， 就是中文分词。他是一位教授，分词的结果是：他是一位教授。现有的分词 算法可分为三大类：基于理解的分词方法、基于字符串匹配的分词方法和基于统 计的分词方法。 索引器：索引器的主要功能是将分词后形成的顺排档文档组织成倒排档索引 数据。倒排索引类似于书籍的目录，是目前搜索引擎最常用的索引存储方式。它 的优点是在处理复杂的多关键字查询时，可在倒排表中先完成查询的交、并等逻 辑运算，再存储得到的结果。这样不需要对每个记录随机存取，把对记录的查询 转换为地址集合的运算，从而提高搜索速度。倒排索引文件分为三个文件：一个 是各文档索引文件；另一个是倒排列表，存储了- y , j 指针，指针存放的值就是术 语出现的文档号；还有一个是字典，它存放数据库中出现的所有可能的术语。 查询器：查询器是最终和用户打交道的一个环节，属于搜索引擎系统中最后 一个部分。查询器通过网页表单接收用户输入的查询条件，然后分词器对查询条 件分词，接着根据分好的词查询倒排索引文件查询出所有符合检索条件的文档， 并对这些文档进行交、并运算和排序后，提取该文档对应的摘要信息返回给用户 查看。由于在检索过程中需要读取索引文件并进行一系列的运算，因而查询器很 难用a s p 、p h p 、j s p 等一些服务器脚本来实现，必须通过c g i 程序来完成。采用 i s a p i 来实现是一种很好的选择，它运行在w i n d o w s 平台上并配合i i s 服务器， 7 武汉理工大学硕士学位论文 是以d l l 的形式发布，用户的查询只需要提交给此d l l 处理，处理完后会自动以 h t m l 的形式反馈给用户。 2 1 2 信息采集系统的工作原理 w e b 信息采集是通过w e b 信息采集器依照网页之间的链接关系，从一个页面 上的链接不断向整个w e b 扩展，自动地从网络上下载这些链接对应的页面至本 地。具体过程如下：从给定的一个初始u r l 集出发，将这个初始u r l 集中的全部 u r l 依次放入一个有序的待采集队列中，接着w e b 信息采集系统从这个待采集队 列中按顺序取出u r l ，按照一些协议规则，下载该u r l 对应的页面，然后将已获 取页面中的未采集过的u r l 放入待采集队列中，不断重复上面的过程直到所有的 u r l 都已获取完毕。 一个w e b 信息采集系统大体上可以由以下七个部分协调起来从互联网上获 取信息：u r l 处理器、协议处理器、重复内容检测器、u r l 提取器、m e t a 信息获 取器、语义信息解析器和数据库。其结构如下图所示【2 l 】： 图2 - 2w e b 信息采集系统基本结构 ( 1 ) u r l 处理器有两个任务：一是将需要采集的u r l 进行排序，并且采 用一定的策略分配u r l 给协议处理器，二是对u r l 进行d n s 解析。根据采集系统 规模的不同，u r l 可以是多个采集队列，也可以是一个u r l 服务器。u r l 处理器 8 武汉理工大学硕士学位论文 有三个主要的数据来源，分别是：一是初始种子u r l 的集合，如图中的粗箭头所 示；二是从已经采集到的页面中提取出的u r l 集，这些u r l 集由u r l 提取器传输 至u r l 处理器；三是为排序提供依据的页面的m e t a 、主题和摘要等信息，主要 目的是显示从u r l 提取器中传输过来的u r l 的重要性。 ( 2 ) 协议处理器它处于系统的底层，主要使用各种网络协议来帮助完成 数据采集的功能。这些协议通常包括h t t p 、f t p 、g o p h e r 以及b b s 。 ( 3 ) 重复内容检测器有研究表时，网络上将近3 0 的大量镜像页面和内 容内容是重复的，这不仅降低了用户搜索的质量和系统的效率，还对网络带宽以 及存储资源造成了极大地浪费。因此，重复内容检测成为了采集系统的不可缺少 的一部分，重复内容检测的方法的选择取决于的需要。 ( 4 ) u r l 提取器主要作用是分析采集到的页面中的链接，并对这些链接 进行必要的转换，形成统一的格式以便后续处理。首先需要判别页面的类型，页 面的类型可由分析的应答头得出，只对“t e x t ，h t m l ，s h t m l 和h t m ”等类型的页 面分析链接。除此之外，由于某些网站返回的内容是不完整的应答信息格式，这 时候就需要根据对页面u r l 中的扩展名的分析来判断页面的类型。其中需要分析 的标记包括如下几种： 、 、 、 、 、 、 等。因为u r l 的格式多种多样，比如可能包括协议、站点和路 径，也有可能是相对路径的格式、或是省略了其中部分的内容。对于各种格式不 统一的情况，一般采取将其规格化为统一的格式的方法，以便后续处理。 ( 5 ) m e t a 信息获取器由于从页面中提取出来的u r l 好坏没有一个度量标 准。因此这个模块的主要用途是在对页面内容信息进行语义理解之前，尽最大的 努力挖掘出页面的m e t a 信息、页面的主题、页面的摘要等，来为提取出来的u r l 好坏给出一个评价值，并传输给u r l 处理器用于对u r l 进行排序。 ( 6 ) 语义信息解析器主要用途是对文本内容建立简单的索引。如果是大 型的信息采集器，因为采集的信息量很大程度上决定了需要较高深度的语义挖 掘，因此通常的做法是将语义挖掘与信息采集独立开来分别处理，对索引部分设 置专门的索引部件。 ( 7 ) 数据库用来存储信息采集过程中需要保留的数据信息，包括页面的 数据信息、处理流程中提取出来的页面中的m e t a 信息、主题和摘要信息，以备 其他应用使用。由于数据较多，所以在存入数据库之前，一般要进行压缩，降低 空间开销。 2 2 爬虫工作流程 9 l o 图2 - 3 网络爬虫的工作流程图 武汉理工大学硕十学位论文 网络爬虫的工作流程如下： ( 1 ) 网络爬虫读取待抓取的u r l 列表，按顺序取出一个网页的u r l 放入未 访问的u r l 列表( u v u r l 列表) 中，若待抓取的u r l 列表为空，则结束爬行，跳 转到( 4 ) ； ( 2 ) 判断u v u r l 是否为空，若不为空则从中取出一个u r l ；若为空，则结 束爬行，跳转到( 5 ) 。 ( 3 ) 在已访问的u r l 列表中查找( 2 ) 中取出的u r l 是否存在，若不存在则 下载此网页至本地，然后对其进行超链分析及内容分析，并将该网页上的所有超 链接放入未访问的u r l 列表( u v u r l 列表) 中，将此网页的u r l 放入已访问的u r l 列表( r l 列表) 中，然后将这个页面的相关内容存入文档数据库。 ( 4 ) 转到( 1 ) 。 ( 5 ) 结束。 2 3 增量采集技术 2 3 1 增量采集的定义 所谓增量采集，是指采集目标是新出现的网页、变化的网页和将消失的网页， 它能在一定程度上避免因重复采集未变化的旧网页而带来时间和存储等资源上 的浪费。 网页增量采集有以下两种方式：第一种是周期性网页采集器，这是一种传统 的采集方式，采集器依据自己采集的需要在互联网上采集一部分信息后停止采 集，当过了一段时间之后这些数据已经过时，采集器重新采集一遍所有的网页替 代原有的本地网页；另外一种方法，当第一遍采集完毕后，某些页面已经过时， 采集器不采集没有变化的页面，只采集新出现的页面或者是发生了变化的页面， 即对旧的页面采用增量式更新。 在网络信息的快速增长的今天，网页数量以前所未有的速度增长，使得搜索 引擎必须考虑采取增量式的网页搜集策略。一方面，网页数量太大，应尽量全面 地搜集最新的网页，以给用户提供最新的信息；另一方面，硬件资源有限，要优 先考虑有价值的网页加以搜集。因此，网页增量采集系统应运而生，它的搜集目 标是新出现的网页、变化的网页和将消失的网页，避免由于对未变化的网页重复 搜集而带来资源的浪费。 2 3 2 增量采集策略 武汉理工大学硕士学位论文 增量式采集系统的工作流程分为以下两个模块：一个是下载模块，负责根据