（计算机应用技术专业论文）移动中文新闻搜索引擎的设计与实现.pdf

六 七s t r a c t ab s t r a c t w i t h t h e r a p i d d e v e l o p m e n t o f t h e i n t e r n e t , t h e i n t e rn e t h a s b e c o m e a n i m p o r t a n t w a y t o a c c e s s t o n e w s a n d i n f o r m a t i o n . h o w t o a c c e s s r e l e v a n t i n f o r m a t i o n m o r e c o n v e n i e n t l y , m o r e c o m p r e h e n s i v e l y a n d m o r e a c c u r a t e l y h a s b e c o m e a n i s s u e . a s t r a d i t i o n a l n e t w o r k m e d i a w i t h d e d i c a t e d w e b s i t e s n o l o n g e r s t a t i s f y t h e n e e d s o f u s e r s , t h e n o t i o n o f n e w s s e a r c h e n g i n e e m e r g e s . w i t h g r o w i n g p o p u l a r i t y o f m o b i l e p h o n e s a n d c o n t i n u a l i m p r o v e m e n t o f i t s u s a b l i l i t y , m o b i l e n e w s s e a r c h i s b e c o m i n g a t r e n d. i n t h i s p a p e r , . n u m b e r o f k e y t e c h n o l o g i e s o f t h e m o b i l e s e a r c h e n g i n e o n c h i n e s e n e w s h a v e b e e n d e e p l y a n a l y z e d a n d r e s e a r c h 喊 a n d a p r o t o t y p e s y s t e m h a s b e e n r e a l i z e d . t h e s t u d y i n c l u d e s t h e f o l l o w i n g m a i n p o i n t s : 1 ) d e s i g n a n d i m p l e m e n t a t i o n o f a t e x t e x t r a c t i o n a l g o r i t h m f o r h t m l n e w s p a g e s b a s e d o n t h e c h a r a c t e r i s t i c s o f h u m a n v i s i o n . t h e a l g o r i t h m i s b a s e d o n t h e j u d g m e n t o f t e x t . a c c o r d i n g t o f a c t o r s i n c l u i n g t h e c o u n t o f c h i n e s e c h a r a c t e r s , t h e c o u n t o f h o t w o r d s , t h e c o u n t o f h y p e r l i n k s , c e r t a i n p a r a g r a p h p a tt e r n s o f t e x t c a n b e d e t e r m i n e d . t h e n b y u s i n g t h e r e l a t i o n s h i p o f h t m l n o d e s , t h e t e x t o f t h e n e w s p a g e s c a n b e e x t r a ct e d . e x p e r i m e n t s i n d i c a t e t h a t w i t h t h i s m e t h o d , t e x t o f t h e n e w s p a g e s c a n b e a c c u r a t e l y e x t r a c t e d , a n d o t h e r r e d u n d a n t s e c t i o n s s u c h a s a d v e r t i s e m e n t s c a n b e r e m o v e d a s w e l l , u n l i k e t ra d i t i o n a l e x t r a c t i o n me t h o d s , w i t h o u t p r e - l e a rn i n g , t h a t u n n e c e s s a r i l y a d j u s t c o n f i g u r a t i o n a c c o r d i n g t o d i ff e r e n t w e b s i t e s a nd d i ffe r e nt c ha n r e l s . 2 ) d e s i g n o f a m o b i l e s e a r c h e n g i n e o n c h i n e s e n e w s , a n d t h e a c t u a l r e a l i z a t i o n o f t h i s p r o g r a m a n d a p r o t o t y p e w i t h a n u m b e r o f i m p r o v e m e n t s m a d e a c c o r d i n g t o u s e r s e x p e r i e n c e i n t h e s e c o n d w o r k p h a s e . k e y w o r d : m o b i l e s e a r c h e n g i n e o n c h i n e s e n e w s ; h t m l t e x t e x t r a ct i o n ; l u c e n e 内容目录 图目 录 图2 .1搜索引攀工作流程图. _:.“ :.” ” ” . ” 二 ; . . .; .; . . . . . 8 图3 .1系统架构图二 _ - - .- - . - ” . _ . . 一 “ . .一 ” ; . . .; .; . 2 3 图4 .1 采集模块工作流程图_ 一_“ _. ” . _ 二 一 - . 2 8 图4 .2 r s s 的x m l示例_ _二 -3 3 图4 3加工模块工作流程图_ _ _ _. _二_ 3 5 图4 .4 h t ml新闻页面正文提取流程图二 _. _ _ ” 3 ， 图4 .5 h t ml 页面实例._二 _ . _._. _- . .- 4 1 图4 .6 d o m树实例” 二_一_-4 2 图4 . 7数据库中 各表关系图 一_ _ _ _ _s o 图 4 .8 l u c e n e的结构组织. . 一 _- - 一 _ _ _ -5 2 图4 .9 l u c e n e 索引 文件概念结构一 _. _. _一 5 3 图4 . 1 0移动中文新闻 搜索首页. 二 ” . ” . _. 二 - -.- .- . -. 6 3 图4 . ll 点击 “ 更多”后的“ 焦点新闻” 效果图. ” 一 _ .- . - . - - . 6 4 图4 . 1 2搜索 “ 物权法，后 的结果页面 . . . 一“ ” . 一 ” _” ” . 二 6 5 内容目录 表目 录 表3 .1元搜索方式与全文搜索方式的比 较- - - - - - - - - - - - - 2 2 表 4 . 1频道定义表 . - - - - - - - - - - - - - - - - - - - - - - - - 一 ， 一 ， 一 个 ， 一 ， 一 。 tt tt ， 一 ” 一 ” . . . . - - - - - - . . - - * * . 2 6 表4 .2数据源定义表- - - 一- - - - - - - - 一，一 ， . . . . . . . . . . . . . . . 2 6 表 4 3 频道表 一 + 一 ， - - - - - - 一一- - 一 ， - - - - 一 一 一 ，一 - - - - - - - - - - 一 :. . . 2 6 表 4 . 4频道视图- - - - 一一 一 - 一 _一+， 一 ， * * * * * * * * * * * * * * * * * * * * . . . . . . . . . . . . 2 7 表 4 . 4 h t ml转义字符- - 一一， 一一 一 _ ，一 ， ，一 :. . . . 3 7 南开大学学位论文版权使用授权书 本人完全了 解南开大学关于收集、保存、使用学 位论文的规定， 同意如下各项内容:按照学校要求提交学 位论文的印刷本和电子版 本;学校有权保存学位论文的印 刷本和电 子版， 并采用影印、 缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以 及提供 本学位论 文全文或者部分的阅 览服务; 学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电 子版; 在不以赢利为目 的的 前 提下，学校可以 适当 复制论文的部分或全部内 容用于学术活动。 学 位 论 文 作 者 签 名 : 幻3 立 2 刃 年工 月 2 8 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名: 愧一 t . 学位论文作者签名 : n k 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: !一.一 ! :内部5 年 ( 最长5年，可少于5 年) 一 秘 密 i 。 年( 最 长 ;。 年 ， 可 少 于 ; 0 年 ) ! 机 密 2 。 年( 最 长 : 。 年 ， 可 少 于 2 0 年 ) (_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文， 是本人在导师指导下， 进行 研究工作所取得的 成果。 除文中已 经注明引用的内容外， 本学位论文 的 研究成果不包含任何他人创作的、 己公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体， 均己 在文中以明 确方式标明。 本学位论文原 创性声明的法律责任 由本人承担。 学 位 论 文 作 者 签 名 : 月 弓 立 “ 。 夕 年i 月。 : 日 绪论 第一章 绪论 第一节 研究背景 随着互联网技术的不断发展， 越来越多的新闻在互联网上发表， 人们越来越 依赖网络以获得相关的新闻资讯。d c c i互联网数据中心发布的 i i f m r et g u i d e 2 0 0 7 中国 互联网 调查 报告 显示， 2 0 0 6 年使 用过新闻 这项互联网 服务的 用户总人数为 1 . 1 7 亿，占整个中国互联网用户的比例为 8 5 . 6 7 %。面对如此规模 的用户需求，传统的网络媒体为网民获取新闻提供了相当的便利。而随着信息 的爆炸式增长， 信息量越来越大，某一单个网络媒体很难网罗 全部新闻。垂直 搜索引擎的出 现和发 展给新闻带来了 新的发展契机，用户可以 在单一入口 处浏 览多家媒体的新闻内容，同时也可以利用关键词查找感兴趣的新闻。 传统的互联网有其 自身的固定性， 即必须通过网络插线才能接入。 如何让用 户能够更便捷地获 取新闻 信息成为一个鱼待解决的问 题. 手机作为使用率最高 的移动终端， 它无 须上网设备，只要一部普通手机就可以 随时随 地入网而不必 受网络插线的限制。 根据著名手机企业诺基亚的 预测， 到2 0 1 0 年， 全球手机用 户将突破3 0亿。而全球电脑用户只有手机用户十分之一，其中还有相当一部分 不能上网。中国手 机用户现已 超过 4亿人，随 着手 机的 普及， 利用手机获取新 闻自然成了一种趋势，移动中文新闻搜索引擎应运而生。 第二节 研究意义 目 前对于搜索引擎的关注点已 经从如何找到更多的信息转移到如何更便捷 地找到准确、有用的信息，提高便捷性与准确率已经成为众多搜索引擎的首要 目 标。 垂直搜索引擎是一种专用领域的搜索引擎，它从某一专题出发， 有针对性的 搜集互联网 上的 专题信息， 采用优化后台信息集 合、 优化用户查询界面等措施， 以高效的检索到所需信息。移动搜索技术，由于其无法比拟的便捷性，被越来 越多的消费者所接受，其发展空间是有无限潜力的。两种技术的结合无疑会为 绪论 用户获 取信息 带来更大的便 利。 移动 搜索引 擎是信息时 代崭新的 指路人， 通过对移 动中 文新闻 搜索引 擎的 研 究与 应用，必然会对搜索引擎的发展产生影响， 必然会更好的方 便用户获得所 需信息。 第三节 应用现状 现今新闻 服务的竞争己经 不仅仅是在新闻网站之间， 搜索引 擎在新闻 搜索领 域的竞争也越来越激烈。移动中文新闻搜索引擎作为一个新的研究领域，目前 已经有一些较好的 w a p 应用出现: 1 ) 百度新闻 搜索 i 百度新闻搜索提供两种方式查看新闻:关键字搜索、焦点新闻分类浏览。 新闻源较多，内容较丰富。关键字搜索为按全文搜索，未提供按标题搜索.每 条新闻只能浏览部分内容，不能浏览全文。 2 ) 爱问新闻 搜索冈 爱问 新闻 搜索提供两 种方式查看新闻: 关键字搜索、 最热新闻浏览。 关键字 搜索提供了 按标题搜索 和按 全文搜索两种方式。 最 热新闻 按照频道分类， 每类3 条。 3 ) 搜狗新闻 搜索 3 搜狗新闻搜索提供两种方式查看新闻:关键字搜索、最热新闻浏览.关键 字搜索提供了按标题搜索和按全文搜索两种方式.默认为标题方式。最热新闻 显示在首页，共 1 0 条，未按频道分类. 第四节 本文内 容组织 移动中文新闻搜索引擎是当今各 wa p中文网站竞争的热点之一。本文从搜 索引擎基本技术开始，逐步研究了垂直搜索引擎的构造，结合新闻的特点，设 计了移动中文新闻搜索引擎的系统架构，并实现了移动中文新闻搜集引擎的基 本功能。 本文的结构和内容如下: 第一章:重点介绍了本文的研究背景、研究意义及应用现状。 绪论 第二章: 首 先介绍了 搜索引 擎的分 类和发展历程， 然后分析搜索引擎的组 成、 工作流程，阐 述了 搜索引擎的相关技术， 介绍了 搜索引擎中的重要分支 一 垂 直搜索引 擎， 对垂直搜索引擎的产生原因 及特点 进行了分析，进而引出 移动 新 闻搜索引 擎，阐 述了 新闻搜索引擎的 产生背景、移 动搜索的特点及移 动新闻 搜 索引擎的 发展前景。 第三章: 重点 对移动中 文新闻 搜索引擎 进行了 系统分析， 建立了 系统的基 本 架构. 第四 章: 实现了 一个系统原型， 详细 介绍了 系统各组成部分的实现工作， 重 点介绍了本文提出的基于视觉特征的 h t ml新闻页面正文提取算法。 第五章:对本文所做工作进行了总结和展望。 最后是参考文献、致谢及个人简历。 搜索引擎 第二章 搜索引擎 第一节 搜索引擎的概述 2 . 1 . 1搜索引擎的概念 搜索引擎是指以一定的策略搜集互联网上的信息， 在对信息进行组织和处理 后，为 用户提供检索服务的系统。搜索引擎实际上就是在用户 ( 搜索引 擎的使 用者) 和互联网资源 ( 搜索引擎的搜索对象) 这两者之间建立起一 个联系， 将 用户真正 想要的内 容呈现给用户，同时用户不想要的内 容不呈现给用户。 我们 称这一要求为 “ 所得即所需，( wh a t y o u g e t i s wh a t y o u w a n t ) 。 从使用者的 角 度看， 搜索引擎提供一个包含搜索框的页面， 在搜索框输入词语，通过浏览器 提交给搜索引擎后，搜索引擎就会返回与用户输入内容相关的信息。 2 . 1 . 2 搜索引擎的分类 搜索引擎按其工作方式主要可 分为三种， 分别是全文搜索引擎 ( f u ll t e x t s e a rc h e n g in e ) 、目 录 索 引 类 搜 索引 擎 ( s e a rc h in d e x / d ir e c to ry ) 和 元 搜 索 引 擎 ( m e ta s e a r c h e n g in e ) 14 1 . 1 ) 目 录索引 类搜索引 擎 基于目 录的 搜索引擎以人工 分类的目 录为主。 互联网 发展早 期， 以y a h o o 为 代表的网站分类目录查询服务非常流行。现在这种方式依然还在采用。 它的 工作原理是: 网站分类目 录由 人工整理维护， 精选互联网 上的 优秀网 站， 并简要描述，分类放置到不同目录下，允许用户通过各种方式找到想要的网站， 这类搜索引擎一般提供目录导航和关键词检索两种方式。 优点:由于目录的构建一般由人工完成， 所以分类比较准确， 被收编的网站 质量也较高，用户搜索出来的结果往往比较准确。 缺点:由于目录分类、 网站收录大都由人工完成， 因此收集的网页是有限的， 而且更新的周期也比较长，维护代价较大。 搜索引擎 2 ) 全文搜索引擎 全文搜索引擎是名副其实的搜索引擎， 人们一般所说的搜索引擎都是指全文 搜 索引 擎， 这 是目 前 主 流 的 搜 索 引 擎 ， 典 型 代 表如 百 度、 g o o g l e 、 搜 狗等 。 工 作原 理: 使 用 网 络 蜘 蛛s p id e r 程 序 从 互 联 网 上 抓 取 各网 站 信 息 ( 以 网 页 文 字 为 主 ) ， 放 到 本 地 的 数 据 库 中 ， 然 后 对 这 些 原 始 的网 页 进 行 加 工处 理 ， 并 且 建 立网页内容的索引。通过检索索引，查询与用户查询条件匹配的网页，按一定 的 排列规则进行排序处理，然后将结果返回给 用户。 优点:全文搜索引擎信息量大，更新及时、无需人工干预。 缺点: 返回信息 较多， 查全率 有所提高， 但有很多无用信息， 查准率很难 保 证， 用户必须从结果中 进行筛选。 3 )元 搜 索 引 擎 元搜索引 擎也被成为搜索引擎的 搜索引擎。 它通过一个统一用户界面帮助 用 户 在多 个 搜 索引 擎中 选 择 和 利 用 合 适的 ( 甚 至 同 时 利 用若 干 个 ) 搜 索 引 擎 来实 现 检 索操作， 是对分布于网络的多 种检索工具的 全局控制机制。 工作原 理: 一个真正的元搜索引 擎由 三部分 组成，即: 检索请求提交机制、 检 索接口 代理机制、检索结果显 示机制。 “ 请求 提交，负 责实现用户 “ 个性化” 的检索设置要求， 包括调用哪些搜索引擎、 检索时间限制、 结果数量限制等。 “ 接 口 代理” 负责将用户的检索请求 “ 翻译”成满足不同搜索引 擎 “ 本地化”要 求 的 格式。 “ 结果 显示” 负责所有 源搜索引 擎检 索结果的 去重、 合并、 输出 处理等。 著 名的 元 搜 索引 擎 有in f o s p a c e , d o g p i le , y v is im 。 等 优点:一般不需存储索引库，硬件与技术的代价比较小，而且由于它返回的 结果是由多个独立搜索引擎提供的， 所以信息的查全率较高。 缺点:这类搜索引擎的检索结果很大程度上依赖于其它搜索引擎。同时，由 于 搜索建立在多个独立的搜索引擎之上， 所以检索响应速度没有独立搜索引 擎 快。 第二节 搜索引擎的发展 搜索引擎是伴随着互联网的发展而产生和不断发展的， 互联网已经成为人们 学习工作和生活中不可缺少的平台，几乎每一个上网的人都会使用搜索引擎。 搜索引 擎大约经历了三代的发展l i1 5 1 ，下面逐一介 绍。 搜索引擎 1 ) 第一代搜 索引 擎 目 录索引 类搜索引 擎， 现在这种方式依然还在采 用。 2 ) 第二代 搜索引 擎 随 着网 络应用技术的发展， 客户不再满足于对网站分类 和摘要的 简单查找， 更希望 对内容 进行查找，于是就出 现了 关键字查询，即 第二 代搜索引擎。 最成 功的、 最有代表性的 是 g o o g l e .该搜索引擎不 仅使用关键字搜索网 页，内 容 可 以 覆盖 互联网的 大量网页内容，并且它将自 身建立在网 页链接分析技术之 上， 这项技术可对网页的重要性进行较客观的分析，将最重要的搜索结果首先呈现 给用户。 3 )第 三 代 搜 索引 擎 随着网 络信息的急 骤膨胀， 人们希望 在大而全的基础上， 为信息减肥， 使信 息查找更加精炼、 准确和快捷。 在此基础上第三 代搜索引 擎应运而生。 第三代搜索引 擎的 主要特征是智能 化、 个性化、 专业化。 相对前两 代， 第三 代搜索引擎主 要关 注的是如何为用户提供更便捷的有效搜索， 更注重智能 化和 个性化，采用自 动分类、自动聚类等人工智能技术，使用内容分析技术以及区 域智能识别技 术， 增强了搜索引擎的查询能力。它的最大特点是大量采取 人工 介入， 实现人工 和技 术的 完美结合，以 提高搜索水 平。 第三节 搜索引擎的组成及工作流程 前面介绍了搜索引擎的分类及各自的原理， 下面重点介绍一下全文搜索引擎 的系统构架和关键技术。为 叙述方便， 下文中提到的搜索引 擎如无特殊说明 都 是指全文检索搜索引擎。 2 .3 . 1 搜索引擎的 组成 搜索引擎由 搜索器( r o b o t ) 、 索引器( i n d e x e r ) 、 检索器( s e a r c h e r ) 和用户接口 ( ul) 等四个部分组 成s 6 . 系统首先由 搜索器收集网页的内 容; 然后索引器分析收 集的 内容， 建立索引; 再由 检索 器响应用户的检索请示，用户输入关键字后， 搜索 器用关键字与建立的索引器匹配，作相关性排序后通过用户接口将结果返回给 用户。 搜索引擎 2 . 3 . 1 . 1 搜索器 搜索器在 互联网 中漫游， 发现和搜集信息。 它是一 个计算机程序，日 夜 不停 地运行。它要尽可能多、可能快地搜集各种类型信息，同时由于互联网信息更 新很快，还要定期更新已搜集过的旧信息，以避免死连接和无效连接。搜索器 常 用分布式并 行计算技术，以提高信息发 现和更新的速度【6 2 . 3 . 1 . 2 索引器 索引器理解搜索器所搜集的信息，从中抽取出索引项， 用于表示文档以及生 成文 档库的 索引 表6 。 索引器读入待索引的全 文， 首先进行分词处理生成索引 项， 并作归并排 序， 生成i n v 和i n d e x 文件 6 . i n v 文件为倒排表， 即由 索引项查找 相 应的 文档; i n d e x 文件存储分词与倒排表的对 应关系，内容为分词 在倒排表中 相 应的文档块起始地址，含有该词的文档数量等信息。索引器使用集中式索引算 法或分布式索引算法。当 数据量很大时必须实现及时 索引，否则将跟不 上信息 量急剧增加的速度。索引算法对索引器的性能 ( 如大规模峰值查询时的响应速 度) 有很大的 影响， 一个搜索引擎的性能在很 大程度上取决于索引器的质量 i 气 2 .3 . 1 .3 检索器 检索器根据用户的查询在索引库中快速检索出文档， 进行文档与查询的相关 度评价，对要输出的结果进行排序。 检索器通 常支持多种语法规则， 如 逻辑 操作符“ a n d . o r . n o t . + , 气” 、 连接号、 通配 符、 逗号、括号或引号等。 对于每个索引项，匹配i n d e x 文 件，查询倒排表中包含该索引项的文档，并对所有找出的文档进行集合运算， 结果集基于内容和链接分析的方法进行相关度评价并排序，最大限度保证检索 结果与用户查询串的高相关性，将最终形成的有序文档结果集合返回给用户接 口。 2 .3 . 1 .4 用户接口 用户接口的作用是输入用户查询、 显示查询结果、 提供用户相关性反馈机制。 主要目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、 及时的信息。 用户接口的 设计和实 现使用人机交互的理论和方法，以充 分适应 人类的思维习惯。 搜索引擎 2 . 3 .2 搜索引擎的工作流程 搜索引擎的 工作流程一般由抓取网页、 加工整理、 查 询服务 三个阶段构成【 6 抓取网页阶段:网 络蜘蛛程序每隔一定时间自 动启动， 从 u r l数据库中 取 得 u r l列表， 在蜘 蛛规则的控制下按照抓取 策略抓取各u r l所指定的网 站， 将抓回的网页 存入网 页数据库，并将新发现的u r l 放入u r l 数据库。 加工整理阶段: 网页 抓回 后， 通过分词等预先处理， 对网 页文档建立 倒排索 引，并将索引 更新 至大的 索引 数据库。同时，提取网页中的链接信息， 存入链 接数据库，为网页评级做好准备。 查询服务阶段: 查 询服务器接受用 户的查 询请求， 对用户 输入的 信息 进行分 词处理，检索索引数据库，找到满足条件的记录，通过网页评级对结果记录进 行排序处理，最后将 排序后的记录反 馈给用 户。 图2 . 1 给出了一般搜索引擎的处理流程。 图 2 . 1搜索引擎工作流程图 搜 索引攀 第四节 搜索引单若干关键技术概论 2 .4 . 1 网络蜘蛛 把互联网比 喻成一个蜘蛛网， 那么 专门 用于抓取网 页信息的搜索 器程序就象 蜘蛛一样在网络间爬来爬去。因此，搜索引擎的搜索器程序又被称为网络蜘蛛 ( w e b s p i d e r ) . 网 络蜘蛛， 实际上是一个基于h t t p 协议的网 络应用程序， 其功能是自 动搜 索 i n t e r n e t 上的网站或网 页。 该程 序在 i n t e r n e t 上漫游，通过网页间 链接顺序地 搜索新的 地址，当遇到新的网页 时， 就给该页上的某些字或全部字作上索引并 把它加到搜索引擎的数据库中，从而搜索引擎的数据库得以添加和更新。 网 络蜘蛛在搜索引 擎中占 有重要 地位， 对搜索引 擎的 查全、查 准都有影响， 决定了搜索引擎的数据容量，而且网络蜘蛛的好坏直接影响搜索结果页中的死 链接 ( 即链接所指向的网页已经不存在)的个数。 2 .4 . 1 . 1 网页抓取策略 将互联网作为一个有向图 处理， 将 页面看 作图中的 节点， 页面中的 超链接看 作图中的 有向 边，可以 使用有向图 遍历算法 ( 深度优先算法、宽度优先算法、 启发式方式)对其进行遍历。在抓取网页的时候，网络蜘蛛一般有以下几种策 略: 1 ) ip 地 址 搜 索 策 略 先赋予网络蜘蛛一 个起始的ip地址， 然后根据i p 地址递增的方 式搜索 本 ep 地址段后的每一个1 : 1 : 1 : 9 地址中 的文档，它完全不考 虑各文档中 指向 其它w e b 站点的超级链接地址。优点是搜索全面，能够发现那些没被其它站点引用的信 息源;缺点是不适合大规模搜索。 2 ) 深 度优先搜索策略 深度优先搜索是一种在网 络蜘蛛 早期使 用较多的 方法。 它的目 的是要达到被 搜索结 构的叶结点， 即 那些不包含任何超链接的h t m l 文档。 在一个h t m l文 档中， 当一个超链接被选择后，对 被链接的h t m l 文档执行深度优先 搜索，即 在搜索其余的超链接结束之前必须先完整地搜索单独的一条链。深度优先搜索 沿着h t m l 文档上的超链 接走到 不能再深入为止， 然后返回到 某一个h t m l文 搜索引擎 档，再 继续选择该 h t m l 文档中的 其他超链。当不再有其他超链 接可选择时， 说明搜 索已 经结束。 该策略的 优点 是能 遍历一个w e b 站点或深层嵌 套的 文档集 合; 缺点 是w e b 结构可能 相当 深，造成一旦 进去， 再也出不 来的 情况发生。 3 )宽 度 优 先 搜 索 策 略 在宽 度优先搜索中 ，先搜 索完一个 w e b页面中所有的超级链接， 然后再继 续搜索下一层，直到底层为止。例如，一个 h t ml文档中有三个超链，选择其 中 之一并处理相应的h t m l 文档， 然后不再选择其下h t m l 文档中的 任何超链， 而是返回 并选择第二个超链，处理 相应的h t m l文档，再返回， 选择第三个超 链并处理相应的 h t ml文档。一旦一层上的所有超链都己被处理，就可以开始 在刚才处理过的 h i ml文件中搜索其余的超链。这就保证了最浅层的首先处理。 当遇到一个无穷尽的深层分支时，不会导致陷进 1 : 1 : 1 : 9 中的深层文档中无法出 来的 情况发生。宽度优先搜 索策略 还有一个 优点，即它能在两个h t m l文档之 间找到最短路径。宽度优先搜索策略通常是实现网络蜘蛛的最佳策略，因为它 容易实现，而且具备大多数期望的功能。但是如果要遍历一个层次很深的站点， 用宽度优先搜索策略则需要花费比较长的时间才能到达深层的h t ml文档。 2 .4 . 1 . 2 功能模块 根据抓取过程，网 络蜘蛛主要分为 三个功能模块， 一个是网 页读取模块， 主 要是 用来读取远程w e b 服务 器上的网 页内 容，另一 个是超链分 析模块，这个模 块主要是分析网页中的超链接，将网页上的所有超链接提取出来，放入到待抓 取 u r l列表中，再一个模块就是内容分析模块，这个模块主要是对网页内容进 行分析，将网页中所有超标志去掉，只留下文字内容。 2 .4 . 1 . 3 r o b o t 协议 w e b站点管理员和网页作者 采用 r o b o t e x c l u s i o n p ro t o c o 】 协议或 r o b o t me t a t a g 指 令 来 控 制网 络 蜘 蛛 对 站点 网 页 的 访 问 . 1 ) r o b o t e x c l u s i o n p r o t o c o l 协 议 w e b 站点 管理员 可以 使用ro b o t s . t x t 文件为 来访的网 络蜘 蛛提供一个标准的 访问 策略，指出站点的 哪一部分可以 被访问。 这个 文件存储在 w e b 站点的 根目 录。 所以当网 络蜘蛛访问一个站点时，应该首先 检查 ro b o t s .t x t ，如 果这个文件 存在，它便会按照这样的记录格式去分析: 搜索引攀 u s e r - a g e n t : . d i s a l lo w : / c g i - b i n / d i s a ll o w: a m 训 u s e r a g e n t 开头的 行: 指出 下面的 禁止行适用的网络蜘蛛， . 意味着该网 站适 用于所有的网 络蜘蛛。 d i s a ll o w开头的 行: 指出 禁止访问的目 录或 子目 录， 列出 的路径以 及它下面的子路径都对网络蜘蛛关闭， d i s a ll o w :/ 表示整个站点对外关 闭。如果该 站的r o b o t s . t x t 文件限 制网 络蜘蛛的访问，则网 络蜘 蛛应不 对该 站点 进行处理。 刀r o b o t me t a t a g r o b o t m e t h ta g 允 许h t m l 网 页 作 者 指 出 某 一 页 面 是否 可 以 被 索 引， 或 是 否 可 以 用 来查 找 更多 的h t m l 文 档。 该m e t a ta g 放 在h t m l 文 档的h e a d 中 . 其格式如 下: r o b o t m e t h t a g 指 令 使 用 逗号 隔 开 ， 可 以 使 用的 指 令包 括【n o i n d e x和 n o f o l l o w. i n d e x 指令指出网络蜘蛛是否可以对本网页进行索引: f o l l o w 指令指出网络蜘蛛是否可以跟踪本网页的链接。 网络蜘 蛛应该 遵守 这些协议，避免访问r o b o t s .t x t 以 及r o b o t m e t a t a g 内 禁 止访问的网页。 2 . 4 . 2 信息的预处理 信息的 预处理 包括信息的 格式支持、转换以 及信息过滤。目 前， 加 抚 功 d上 的信息发布格式多种多样，这就要求搜索引擎支持多种文件格式。从实际的情 况看，所 有的 搜索引 擎都支持h t m l格式，而对于 其他 文件格式的 支持则有所 不同，最多的能 支持 2 0 0多种文件格式。同时搜索引擎 还应具 备信息格式转换 功能，以保证不同格式的数据均能在网络中流通。信息过滤也是搜索引擎的一 项重要技 术。 在i n t e r n e t 上， 存在着大量无用信息，一个 好的 搜索引 擎应该尽量 减少垃圾站点的数量，这是信息过滤要着重解决的问题。 搜索引擎 2 . 4 . 3 中文分词 2 .4 .3 . 1概念 词是 最小的 能够独立活动的有意 义的语言 成分。 众所周知， 英文 是以 词为单 位的，词和词之间是靠空格隔开， 而中 文是以 字为单 位，句子中所有的字连起 来才能 描述一个意思，词语之间没 有明显的区 分标记。 例如，英文 句子勺a m a s t u d e n t ，用中文则为: “ 我是一个学生” 。计算机可以很简单通过空格知道 s t u d e n t ” 是一 个单词， 但是 不能 很容易明白“ 学” 、 “ 生” 两个字 合起来才表示 一个词。 把中文的汉字序列切分 成有意义的 词， 就是中文分词， 也 称为 切词。 “ 我 是一个学生”的分词的结果是:“ 初 卿 一个/ 学生” 。 2 .4 . 3 . 2 中文分词与搜索1 1 . 目 前的搜索引擎， 大多是 基于一种称为 倒排索引的结构 门 .以何 作为索引的 键值直接影响到整个搜索引擎的准确度、召回率、速度。下面我们先看看不使 用中文分词的情况。 如果不使用中文分词， 可以 采用单个汉字索引方 式。 例如， “ 网络” ， 先索引 “ 网” 字，然后再索引 “ 络”字。对于一篇文 档， 把所有的汉字都单独索引一 次，并记录他们的位置。搜索过程中，也是先找包含 “ 网”字的所有文档，再 找包含 “ 络”字的所有文档，然后做交叉与运 算，即 包含这两个字，并且只有 位置连续的文档才符合查询要求。这种方式是最基本的索引方式，现在有些小 引擎还在使用。但这里存在一个问题:对于访问频繁的大数据量搜索引擎来说， 进行与操作的计算量会相当大，这无疑是对硬件和算法的极大挑战。 考虑到速度问题， 如果不使用分词， 还有另外一种选择: n 元组合索引方式， 如2 元、 3 元等。 拿2 元来说， 中国人， 先索引“ 中国” ， 再索引“ 国 人” 。同 样， 对于一篇文章，以2为 单位， 把所有相邻的 汉字都索引 起来， 并记录他们的位 置。 搜索过程中，也是先找包含 “ 中国”的 所有文档， 再找 “ 国人”的所有文 档， 然后做交 叉与运算，即包含这两个单元， 而且位置连续的文 档。这样以两 个字做为索引单元， 大大减少了 搜索过程中的计算量。 以 上两种方式， 都不需要分 词， 也实现了 搜索引 擎的 索引和检索。 但这里存 在一个不可忽视的问题:准确度。一个很常见的例子:和服，如果按照上面两 种方式，都会查到包含 “ 主板和服务器” 的文档: “ 北大” 也会得到“ 东北大学气 搜索引擎 对于大 数据量的搜索引擎来说， 每次搜索一般都会有成千上万的结果， 用户己 经很难挑 选真正想要的信息，如果这里还要增加许多 错误，用户体验会极差。 所以，中文搜索引擎需要进行中文分词处理。 以词为单位做为搜索引擎的索引键值，会大大提高搜索引擎结果的准确度， 同时保证了搜索过程中较少的计算量。同时，对于搜索引擎来说，最重要的并 不是找到 所有结果，因为在上百亿的网 页中 找到所有结果没有太大意义，最重 要的是把最相关的结果排在最前面，这也称为相关度排序。中文分词的准确与 否，常常直接影响到对搜索结果的相关度排序。 2 . 4 . 3 3 中文分词 技术 现有的分词算法可 分为 三大类: 基于字符串匹配的分词 方法、 基于理解的分 词方法和基于统计的分词方法。 1 )基 于 字 符 串 匹 配 的 分 词 方 法参 这种方法又叫做机 械分词方法， 它是按照一定的策略 将汉 字串与 一个充分大 的机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功 ( 识别 出一个词) 。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹 配; 按照不同 长 度优先匹 配的 情况， 可以 分为最大 ( 最长)匹配 和最小 ( 最短) 一 匹配;按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标 注相结合的一 体化方 法。 常用的 几种机械分词方法如下: 正向 最大匹配 法 ( 由 左到右的方向) 逆向 最大匹配 法 ( 由 右到左的方向 ) 最少切分 ( 使 每一句中 切出 的词数最小) 还可以 将上 述各 种方法相互组合， 例如， 可以 将正向 最大匹 配方法和逆向 最 大匹 配方法结 合起来构成双向匹配法。由 于汉语单字成词的 特点，正向 最小匹 配和逆向 最小 匹配一 般很少使用。一般说来， 逆向匹 配的 切分精度略高于正向 匹配， 遇到的 歧义现象也较少。统计结果表明 ，单纯使用正向最大匹配的错误 率为 1 / 1 6 9 ，单纯 使用逆向 最大匹配的错误率为 1 / 2 4 5 。 但这种精度还远远不能 满足实际的 需要。 实际使用的分词系统，都是把机械分词作为一种初分手段， 还需利用其它的 语言 信息来进一步提高分词的准确 率。 一种方法是改 进扫描方式， 称为特征扫描 或标志 切分， 优先在待分析的字符 串中识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串 搜索引擎 分为较小的串后再进行机械分词，从而减少匹配的错误率。另一种方法是将分 词和词类标注结合起来，利用丰富的词类信息对分词决策提供帮助，并且在标 注过程中 又反 过来对分词结果 进行检验、 调整， 从而极大 地提高 切分的 准确率。 对于 机械分词方法， 可以建 立一个一 般的 模型， 在这方 面有专业的 学术论文， 这里不做详细论述。 2 ) 基于理解的分词 方法 这种分词方法是通过让计 算机模拟人对句子的理 解， 达到识别 词的效果。 其 基本思想就是在分词的同 时进行句法、 语义分析，利用句法信息 和语义 信息 来 处理歧义现象。它通常包括三个部分: 分词子系统、 句法语 义子系统、总 控部 分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义 信息来 对分词歧义进行判断，即它模拟了 人对句子的理解过 程。 这种分词 方法 需要使 用大量的语言知识和信息。由 于汉语语言知识的笼统、复杂 性， 难以 将 各种语言 信息组织成机器可直接读取的 形式， 因此目 前基于 理解的 分词系统还 处在试验阶段。 3 ) 基于统计的 分词方法 从形式上看， 词是稳定的字的组合， 因此 在上下文中， 相邻的字同时出 现的 次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较 好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统 计， 计 算它们的互现信息。 定义两个 字的互 现信息， 计算两个汉字x , y的相 邻 共现概率。互现信息体现了 汉字之间结合关系的紧 密程度。当紧密 程度高 于某 一个闭值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字 组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法. 但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常 用字组，例如 “ 这一” 、“ 之一” 、“ 有的” 、 “ 我的” 、 “ 许多的”等，并且对常用 词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的 分词词典 ( 常用词词典)进 行串匹 配分词，同时使 用统计方法识别一些新的词， 即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点， 又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。 到底哪种分词算法的准 确度更高， 目 前并无定 论。 对于任何一个 成熟的 分词 系统来说，不可能单独依靠某一种算法来实现，都需要综合不同的算法。 搜索引攀 2 .4 .4 倒排索引 倒排索引源于实际应用中需要根据属性的值来查找记录。 这种索引表中的每 一项都包括一个属性值和具有该属性值的各记录的地址，由于不是由记录来确 定属性值， 而是由 属性值来确定记录的位置， 因