[硕士论文] 垂直搜索引擎的设计与实现.pdf

西北工业大学 硕士学位论文 垂直搜索引擎的设计与实现 姓名 吴欣茹 申请学位级别 硕士 专业 软件工程 指导教师 王庆 20061201 摘要 随着I n t e r n e t 的迅速发展 W e b 己经发展成为包含多种信息资源 站点分 布全球的海量信息服务网络 搜索引擎是一种用于帮助W e b 用户查询信息的搜索 工具 它以一定的策略在I n t e r n e t 中搜集 发现信息 对信息进行理解 提取 组织和处理 并为用户提供检索服务和信息导航 通用搜索引擎的特点是 索引 数据库的规模大 检索结果数据量特大 随着信息多元化的发展 通用搜索引擎己经不能满足主题用户的需求 用户 迫切需要一个数据分类细致 精确 全面 更新及时的面向特定主题的搜索技术 和方法来获得主题资源信息 在这种需求的推动下 垂直搜索引擎应运而生 论文研究了搜索引擎的相关技术 通过分析基于查询串方式的搜索引擎和分 类目录式搜索引擎的整体结构 设计了垂直搜索引擎的系统结构 并对其中涉及 的关键技术 W e b 搜集器 信息抽取技术 中文分词和检索技术进行了深入研究 期望对推进本领域的技术发展作一点贡献 在总体设计方面采用的是模块化思想 垂直搜索引擎被分为搜集子系统 索 引子系统和检索子系统 各子系统相对独立 实现较为方便 本文实现的垂直搜索引擎已经在实际中成功运用 具有较好的效果 很好地 满足了主题用户的需求 具有广阔的市场前景 关键词 搜索引擎 信息抽取 下推自动机 中文分词 页面距离 西北工业大学硕士学位论文 A b s t r a c t A b s tr a c t W i t ht h ep f e v a l 锄c co ft h en e t w o r ka p p l i c a t i o n s t h eI n t e r a c th a sb c c 0 蚰ea w i c en e t w o r kp r o v i d i n gm a s si n f o r m a t i o n w h i c hi n c l u d e sv a r i o u si n f o r m a t i o n r e s o u r c e sa n ds i t e sd i s t r i b u t e da l lo v e rt h ew o r l d T h es e a r c he n g i n ei sak i n do f s e a r c ht o o l s h e l p i n g w e bu s e rt ol o o ku pi n f o r m a t i o n I tc o l l e c t sa n ds e e k s i n f o r m a t i o ni nt h eI n t e r a c tw i t hc e r t a i ns t r a t e g i e sa n dp r o v i d e sr e t r i e v a ls e r v i c ea n d i n f o r m a t i o nn a v i g a t i o nO nt h eb a s i so fe x t r a c t i n g o r g a n i z i n ga n dd e a l i n gw i t ht h e i n f o r m a t i o n T h ec h a r a c t e r i s t i c so ft h eg e n e r a le n g i n em el a r g e s c a l ei n d e xd a t a b a s e a n dm a s sr e t r i e v a lr e s u l td a t a W i t ht h ed e v e l o p m e n to fd i s p a r a t ei n f o r m a t i o n t h eg e n e r a ls e a r c he n g i n ec a n t m e e tt h et o p i cc u s t o m e r s T h ec u s t o m e r sn e e da p a r t i c u l a rs u b j e c t o r i e n t e dt e c h n i q u e a n dm e t h o d w h i c hi sa c c u r a t e a l l s i d e da n du p d a t e dt i m e l yt oo b t a i nr e s o u r c e sa b o u t s o m et o p i c B yt h ep r o m o t i o no ft h i sk i n do fd e m a n d st h ev e r t i c a ls e a r c he n g i n e e m e r g e a tt h i sb a c k g r o u n d T h et h e s i ss t u d i e dt h er e l a t e dt e c h n i q u eo ft h es e a r c he n g i n e d e s i g n e dt h es y s t e m a r c h i t e c t u r eo ft h ev e r t i c a ls e a r c he n g i n eb a s e do na n a l y z i n gt h et r a d i t i o n a ls y s t e m s t r u c t u r eo ft h es e a r c he n g i n e I nt h i sa r t i c l e s o m ek e yt e c h n i q u e si n v o l v e di nt h e s e a r c he n g i n es u c ha sw e bc r a w l e r i n f o r m a t i o ne x t r a c t i o n C h i n e s ep a r t i c i p l ea n dt h e r e t r i e v i n gt e c h n i q u e sa r es t u d i e di nd e t a i l B yl u c u b r a f i n gt h e s ek e yt e c h n i q u e s t h e a u t h o re x p e c tS o m eh e l pt ot h ed e v e l o p m e n ti nt h i sf i e l d M o d u l a rt h o u g h tw a sa d o p t e di nt h es y s t e md e s i g n T h ev e r t i c a ls e a r c he n g i n ei s d i v i d e di n t ot h r e ep a r t s t h ec o l l e c ts u b s y s t e m t h ei n d e xs u b s y s t e ma n dt h er e t r i e v a l s u b s y s t e m E a c hs u b s y s t e m i s i n d e p e n d e n c eo p p o s i t e l y a n d i m p l e m e n t e d e x p e d i e n t l y T h ev e r t i c a ls e a r c he n g i n eh a sb e e np u ti n t oU S Ca n dp r o v e ds u c c e s s f u l l ya n d e f f i d e n f l yi np r a c t i c e I tc a ns a t i s f yt h en e e do ft h et o p i cc u s t o m e rp r i m l y S Oi tw i l l h a v eav a s tm a r k e ti nf u t u r e K e yw o r d s s e a r c he n g i n e t h ei n f o r m a t i o ne x t r a c t i o n t h ep u s h d o w na u t o m a t i c m a c h i n e C h i n e s ep a r t i c i p l e t h ep a g ed i s t a n c e 西北工业大学 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定 即 研究生在校攻读学位期 间论文工作的知识产权单位属于西北工业大学 学校有权保留并向国家有关部 门或机构送交论文的复印件和电子版 本人允许论文被查阅和借阅 学校可以 将本学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印 缩 印或扫描等复制手段保存和汇编本学位论文 同时本人保证 毕业后结合学位 论文研究课题再撰写的文章一律注明作者单位为西北工业大学 保密论文待解密后适用本声明 学位论文作者签名 墨 逸基 指导教师签名 学位论文作者签名 盘 迭丛 指导教师签名 D Z 年J f 月It Z 日口彳年1 1 月J 上日 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德 本人郑重声明 所呈交的学位论 文 是本人在导师的指导下进行研究工作所取得的成果 尽我所知 除文中已 经注明引用的内容和致谢的地方外 本论文不包含任何其他个人或集体已经公 开发表或撰写过的研究成果 不包含本人或他人己申请学位或其它用途使用过 的成果 对本文的研究做出重要贡献的个人和集体 均已在文中以明确方式标 明0 本人学位论文与资料若有不实 愿意承担一切相关的法律责任 学位论文作者签名 墨殛盘 口6 年c 只 B 西北工业大学硕士学位论文 第一章绪论 1 1 研究背景 第一章绪论 随着信息技术的快速发展 互联网得到了飞速的发展 成为人们学习 工作 生活中的最重要的知识和信息来源 根据C N N I C 中国互联网络信息中心 2 0 0 6 年1 月1 7 日发布的 中国互联网络发展状况统计报告 1 截止到2 0 0 5 年1 2 月3 1 日 我国的网民总人数为1 1 1 0 0 万人 上网计算机总数已达4 9 5 0 万台 我 国网站数为6 9 4 2 0 0 个 目前 整个互联网中文网页数超过2 0 亿 G o o g l e 收 录了5 亿中文网页 百度收录了8 亿中文网页嘲 I n t e r n e t 上的信息资源随着I n t e r n e t 的发展呈现出以下特点 l 信息量大而且分散 2 自治性强 3 信息资源多种多样 4 不一致和不完整 为了获取所需的信息 用户必须借助一定的工具 他们通常使用以下两类网 站 一 第一类是分类目录式搜索引擎 其典型代表是Y a h o o 它主要采用人工方式 或半自动方式收集和整理I n t e r n e t 上的信息 根据所搜集网页的内容再手工将 其网址分配到所采用的分类主题目录的不同层次级别类目之下 用户查询时 通 过逐级层层浏览这些类目 寻找自己所需的网址信息 这类搜索引擎因为加入了 人的智能 所以信息准确 导航质量高 缺点是需要人工介入 维护量大 信息 量少等 第二类是基于查询串方式的搜索引擎 也称为通用搜索引擎 这类搜索引 擎指的是一种在W e b 上应用的软件系统 它以一定的策略在W e b 上搜集和发现信 息 在对信息进行处理和组织后 为用户提供W e b 信息查询服务 从使用者的角 度看 这种软件系统提供一个网页界面 让他通过浏览器提交一个词语或者短语 然后很快返回一个可能和用户输入内容相关的信息列表 这类通过关键词匹配实 现查询的自动更新的搜索引擎优点是涵盖的网页数量巨大 因为它拥有基于关键 字的全文索引 它为所有网上冲浪的用户提供了一个入口 所有的用户都可以从 搜索引擎出发到达自己想去的网上任何地方 搜索引擎对用户是这样的重要 成 为了用户上网的常用服务 根据 中国互联网络发展状况统计报告 1 用户经 常使用的网络服务是 浏览新闻 6 7 9 9 6 搜索引擎 6 5 7 收发邮件 6 4 7 西北工业大学硕士学位论文第一章绪论 即时通讯 4 1 9 9 6 论坛 B B S 讨论组等 4 1 6 然而 事实也已经证明单纯依靠搜索引擎提供的分类目录和关键词检索 搜 索效果并不理想 分类目录所涵盖的网页资源需要人工编辑 因此数量有限 而 对于关键词检索 虽然搜索引擎技术几经完善 但是信息的查全率和查准率还是 相当低下 特别是较低的查准率使得用户得到搜索结果后还需进一步挑选 智力 负担相当重 即使比较著名的诸如G o o g l e 等搜索引擎对检索结果采用了基于超 链接的相关度排序 但它们主要依据的也只是网页被其他网页认可的程度 并非 网页与用户真实检索需求之间的关联程度 同时结果中包含了大量与用户查询请 求不相关的文档 用户在返回的动辄成千上万条记录中寻找相关文档犹如大海捞 针 造成这种现象的原因很多 从主观上讲 对于分类目录 用户通常并不一定 清楚搜索引擎提供的分类目录是否真正包含自己所需的内容 而且缺乏必要的分 类知识也会使得用户难以在庞大的 经常动态调整的类目间准确定位 1 而对于 关键词检索 用户通常键入的词语是非常简练的 而且也无法保证是否与命中记 录存在关系 从客观上讲 搜索引擎技术还有相当大的完善空间 目前的技术在 提高网页查全率和相关度排序上已经达到了较高的水平 但是对于自动网页分类 和聚类 基于概念的检索词匹配等方面仍然要求技术突破 除了这些技术原因外 产生目前问题的原因还包括一些设计方面存在的缺陷 如搜索引擎系统与用户的 接口设计存在障碍 让彼此难以通过现有的界面进行良好的表达和反馈 用户无 法有效地根据搜索引擎的提示调整检索策略 搜索引擎也无法以一种方便用户操 作的合理方式来展示查询结果 作为一项直接面对普通用户的检索技术 搜索引 擎要想实现检索的成功 一定要能在用户与检索系统之间建立良好的沟通渠道 这个渠道能使用户准确表达自己的检索需求 同时系统能够准确理解用户的检索 意图 并且能以一种用户感觉良好的方式显示结果 但事实上 孤立地使用单一 的分类目录和关键词检索 往往都使得这种愿望难以实现 在现阶段技术水平下 要提高搜索引擎的检索效果 必须从搜索引擎的基础收录入手 并采用分类目录 和主题检索相结合的方法 1 2 搜索引擎的现状分析 搜索引擎起源于传统的全文检索理论 即通过扫描每一篇文档资料中出现的 词语 建立以关键词为单位的索引文件 并通过界面让用户使用关键词进行检索 从深层次来看 搜索引擎的出现有技术的必然性 主要原因在于快速发展的网络 提供的资源极大地超出了人们能够自然有效地利用传统方法进行管理的能力范 围 传统的管理信息资源的方法主要基于人们对信息的再消化 再理解 以信息 西北工业大学硕士学位论文第一章绪论 重组的方式重构整体的信息框架 并将所得信息资源分门别类 而用户的检索显 然也要按照这种事先规定好的类目结构来进行 但由于自动分类技术的难度 基 于全文检索的方法就巧妙地绕开了这个障碍 即使人们不具备理解信息资源本身 的条件 也可以借助计算机技术快速地进行全文索引和全文检索匹配 从理论上 讲 每个词语都成为了检索的依据 以信息理解为基础的信息检索行为逐渐过渡 到以信息单纯匹配为基础的检索行为 即以关键词为主的主题检索 现代的搜索引擎在面对海量数据的时候 通过简单的全文检索匹配来返回最 终结果 但是仍然缺乏有效的手段让用户通过键入的少量关键词就能快速准确定 位到自己所需要的信息嘲 从本质上讲 这由于两方面的原因 首先 互联网信 息量巨大 哪怕用户只是搜索其中的一小部分内容 搜索引擎返回的命中页面数 量也是巨大的 从本质上看 这也是应该的 利用用户键入的词语来进行全文检 索就应该返回所有相关信息 其次 用户本身检索专业能力有限 最为普遍的关 键词检索行为中用户通常只是键入几个词语 如A S p i n k 等人曾对E x c i t e 等搜 索引擎的近3 0 0 位用户做过实验后发现人均输入的检索词为3 3 4 个 国内部分 学者也有相似的结论 发现9 0 左右的用户输入的中文检索单字为2 6 个 过 少的检索词事实上无法真正表达用户的检索需求 而且用户通常也不去进行复杂 的逻辑构造 只有相当少的用户使用布尔逻辑检索 限制性检索和高级检索等方 法 如A S p i n k 等人发现 仅有5 2 4 的检索式中包含有布尔逻辑运算符 国 内部分学者的研究结果也表明约4 0 的用户不能正确运用字段检索或二次检索 8 0 左右的用户不能正确运用高级检索功能 甚至还发现用户缺乏动力去学习复 杂的检索技能 多数用户都寄希望于搜索引擎能够自动地为他们构造有效的检索 式 1 由于缺乏过去联机检索中常常具备的检索人员 用户实际的检索行为与用 户理想的检索行为存在事实上的差距 因此信息查准率非常低 进一步提高搜索引擎的查询效率和效果 必定是下一代搜索引擎的主要目 标 从检索专业角度来看 基于关键词的主题检索一定要和基于目录的分类检索 进行有机的结合才能提高检索的成效 主要原因在于这种结合有两方面的好处 首先 在检索界面中 它可以利用主题词表达分类目录 能有效地提高类目的可 理解性 同时也可以利用类目修饰关键词 加强关键词的指向度 其次 在返回 结果界面中 通过目录和关键词的组合表达 使得用户更加易于定位所需信息 随着信息多元化的发展 通用搜索引擎己经不能满足主题用户的需求 用户 迫切需要一个数据分类细致 精确 全面 更新及时的面向特定主题的搜索技术 和方法来获得主题资源信息 在这种需求的推动下 垂直搜索引擎应运而生 西北工业大学硕士学位论文第一章绪论 1 3 选题意义 综合分类和主题的优势 垂直搜索引擎将能展示更为优秀的检索功能 它在 实际应用中 也有广阔的使用范围 具体的表现形式有三个 1 垂直搜索引擎系统检索时采用分类目录和主题检索相结合的方法有利于 专业信息的查找 同时消除无关信息 这其实正是专业搜索引擎的一种表现 专 业搜索引擎主要针对某一专业的相关网页信息进行索引和提供检索 此时分类且 录扮演着重要的角色 因为专业搜索引擎在遍历互联网的时候 通常是利用搜集 的网页索引词来给出所属类目 从而判断是否为专业的相关网页 2 垂直搜索引擎在显示时采用主题和类目结合的方法有利于结果的展示 提高了网页相关度显示能力 即结果呈现以类聚集的特点 用户以类为对象进行 整体查询 效率和查准率都能得到提高 3 用于构建中 小企业的门户网站或分类信息网 1 4 论文贡献 互联网的快速发展 对搜索引擎提出了更高的要求 巨大的使用需求推动了 搜索引擎技术的发展 各种新技术纷纷应用到搜索引擎中 搜索引擎是这些技术 的基础和平台 它决定着这些技术的开发和应用 但一般的研究机构不可能拥有 和商业搜索引擎一样规模的计算机资源 因此需要一种对资源要求低 体系开放 的搜索引擎来作为各种新技术的平台 本文在深入分析网页获取 索引生成 信息检索等搜索引擎核心技术的基础 上 设计并实现了一种新的搜索引擎一垂直搜索引擎 该搜索引擎使用网络蜘 蛛实现网页获取 通过信息抽取 中文分词和建立倒排文件等技术建立索引数据 库 信息检索返回的网页的级别使用本文定义的 页面距离 来度量 大大降低 了搜索引擎对于计算机资源的要求 论文主要贡献如下 1 提出了一种W e b 搜集器算法 并用 1 a v a 成功实现 2 在分析了H T M L 语法特点的基础上 利用C h o r a s k y 语法分析的方法 归纳 H T M L 数据的语法规则 从而达到抽取模式数据 为存储设计提供元数据的目的 这种方法不但能够快速 准确地提取元数据信息 而且容错性强 能够处理不完 整的H T M L 数据片断 3 提出了一种对H T M L 数据的检索方法 该方法吸收了信息检索领域的倒排 表索引的优点 结合H T M L 数据的结构和内容双重索引的设计 能发挥结构信息 的语义指导作用 提高了检索的查询精度 西北工业大学硕士学位论文 第一章绪论 1 5 论文的组织结构 本文中 各章的具体内容概括如下 第二章介绍垂直搜索引擎的结构 首先 介绍基于查询串方式的搜索引擎和 分类目录式搜索引擎的整体结构 然后在此基础上 设计了垂直搜索引擎的系统 结构 并介绍了各部分所完成的工作 第三章详细讨论了实现搜集器的主要类结构以及数据库设计 然后描述了本 文设计的W e b 搜集器的执行流程 最后简述了W e b 搜集器的实现难点 第四章详细介绍垂直搜索引擎采用的信息抽取技术 基于语法的信息抽 取技术 首先介绍H T M L 数据的语法特点及理论基础 然后 介绍本文所利用的 下推自动机模型 最后 详细描述了模式获取算法 E x t r a c tS c h e m a 简写为E S 的实现 第五章详细介绍垂直搜索引擎采用的中文分词技术 首先 将现有的中文分 词技术进行比较 然后 详细介绍本文所采用的中文分词技术 全二分最大匹 配快速分词算法 第六章介绍垂直搜索引擎采用的检索机制 首先介绍传统的信息检索技术 然后在此基础上 设计了垂直搜索引擎检索子系统的结构 最后介绍本文提出的 检索技术 第七章总结全文 并给出需要进一步改进的问题 西北工业大学硕士学位论文第二章垂直搜索引擎的结构 第二章垂直搜索引擎的结构 垂直搜索引擎是针对某一个行业的专业搜索引擎 是搜索引擎的细分和延 伸 是对网页库中的某类专门的信息进行一次整合 定向分字段抽取出需要的数 据 进行处理后再以某种形式返回给用户 本章首先介绍基于查询串方式的搜索 引擎和分类目录式搜索引擎的整体结构 然后在此基础上 设计了垂直搜索引擎 的系统结构 并介绍了各部分所完成的工作 2 1 基于查询串的搜索引擎 基于查询串的搜索引肇通常是由网络蜘蛛 S p i d e r 以某种策略自动地在互 联网中搜集和发现信息 并将搜集到的信息建立索引 形成索引库 由检索器根 据用户输入的关键词检索索引库 并将查询结果返回给用户 1 典型的搜索引擎 有 A l t aV i s t a E x c i t e N o r t h e r nL i g h t G o o g l e 等 2 1 1A l t aV i s t a 搜索引擎结构 A l t aV i s t a 搜索引擎结构如图2 1 所示 1 制 图2 1A l t aV i s t a 结构 A l t aV i s t a 软件结构主要包括两个部分 第一部分是用户接口和查询机制 主要实现用户所提交的查询条件在索引库中完成搜索 并将相关的检索结果反馈 给用户的过程 索引机制采用集中式的方式应答用户的请求 第二部分包含网络 蜘蛛和索引机制 网络蜘蛛运行在本地机上 通过自动将请求发送给远程W e b 服务器 获取相应服务器上的信息 经过处理后存入索引库 从而实现索引库的 动态扩充 1 9 9 8 年 A l t aV i s t a 运行在2 0 个C P U 上 1 3 0 G B 内存和5 0 0 G B 的硬盘 6 西北工业大学硕士学位论文 第二章垂直搜索引擎的结构 单查询机制就使用了7 5 以上的资源 2 1 2H a r v e s t 搜索引擎结构 H a r v e s t 结构是基于网络蜘蛛与索引机制结构的几种变种之一 其结构如图 2 2 所示阍 H a r v e s t 使用分布式体系结构获取数据与分发数据 已被 C I A N A S A U SN a t i o n a lA c a d e m yo fS c i e n c e 和U SG o v e r n m e n tP r i n t i n gO f f i c e 使用 另外N e t s c a p e 的目录服务也是H a r v e s t 的一种商业化版本 网络应用缓 存是H a r v e s t 缓存的一种商业化应用 图2 2H a r v e s t 结构 H a r v e s t 结构包含两个方面的内容 收集器 g a t h e r i n g 与B r o k e r 收集器的 任务是定期收集并从多个服务器中抽取索引信息 完成信息的搜集过程 B r o k e r 主要对搜集的数据建立索引机制 并完成用户对搜索引擎的查询过程 B r o k e r 可以从搜集器中接收信息或从其他的B r o k e r 中获取信息来更新其本身的索引 同时 B r o k e r 也可以通过过滤信息或者将所获得的信息发送给其他的未获取相 应信息的B r o k e r 来节省这些B r o k e r 的时间开销 2 I 3G o o g I e 搜索引擎结构 G o o g l e 搜索引擎主要依赖于超文本中的结构信息 利用C c 编写 运行在 S o l a r i e s L i n u x 平台 其结构如图2 3 所示 网页爬行 C r a w l i n g 指网页的下载过程 技术是由若干个分布式的网络爬 虫实现的 其中 一个叫做U R LS e r v e r 的服务器负责把需要下载的U R L 地址列 表分派给这些网络爬虫进行处理 网页数据如果被取回 将立即被送到S t o r e S e r v e r 中 S t o r eS e r v e r 对网页数据进行压缩 然后保存到R e p o s i t o r y 数据库 中 每一个文档都拥有一个与之相关的唯一的I D 编号 G o 0 9 1 e 称它为d o c I D 每当有一个新的链接从网页中破解析出来 它所指向的文档就自动获得一个 西北工业大学硕士学位论文第二章垂直搜索引擎的结构 d o c I D 建立索引的任务则交给索引器和排序器来完成 I n d e x e r 依次从R e p o s i t o r y 中取出文档 对文档解压缩 然后对文档进行解析 随后文档被解析为一组命中 在G o o g l e 中 命中是一种数据结构 用来记录单词在文档中每一次出现的信息 在命中结构中 记录了每个词 词在页面中的位置 大小写 字体相对大小写等 信息 这样 每个词都有很多不同的命中 这些命中的组合又称为该词的命中列 表 索引器把这些命中再写入一组桶中 并建立一个部分排序的前序索引 索引 器还同时把网页中所有的链接的重要信息解析出来 并记录到一个叫做A n c h o r s 的文件中 该文件包含了足够多的信息 从中可以查询出每一个链接的来源 指 向以及该链接的文本 U R LS e r v e r 卜 叫C r a w l e r 卜 叫S t o r eS e r v e R LR e s o l v e L i n k s A n c h o r s D o c I n d e xl lS o r t e r R e p o s i t 图2 3G o o g l e 结构 U R LR e s o l v e r 服务器负责从A n c h o r s 文件中读取出这些链接 把相对路径 转换为绝对路径 再转换为相应的d o c I D 通过d o c I D 的关联 锚文件的信息也 被加入到前序索引的a n c h o rh i t 结构中 U R LR e s o l v e r 同时创建了一个L i n k s 数据库 用来存放两两相互对应的d o c I D L i n k s 数据库被用来计算所有文档的 P a g e R a n k 接着排序器接管这些桶 排序器的主要任务是按照W o r d I D 重新进行排序 从而为这些桶生成一个倒排索引 这个操作是在每个桶中执行的 所以只需用很 少的临时空间 排序器还建立了一个w o r d l D 列表 列表中同时记录了该w o r d I D 在倒排索引中的偏移量大小 有一个叫做D u m p L e x i c o n 的工具 用来把w o r d l D 和由索引器产生的词典相结合 并产生一个新的词典 这个新的词典被用在最终 8 西北工业大学硕士学位论文第二章垂直搜索引擎的结构 的搜索程序中 连同P a g e R a n k 和倒排索引一起 为用户提供查询服务 2 2 分类目录式搜索引擎 分类目录式搜索引擎是互联网上最早提供唧资源查询的工具 分类目录式 搜索引擎 也称为目录型检索工具 或目录搜索引擎 它主要包含 网页采集 网页分类 网页索引 搜索器等旧 其中网页的采集过程一般需要由编辑人员查 看信息后人工生成信息摘要 并将信息置于事先确定的分类框架中m 网页的分 类过程分为人工和自动两种 由于一个分类目录式搜索引擎一般要采集数亿个网 页 因此 信息的分类是个非常繁琐的工作 用户查询时 通过逐级层层浏览这 些类目 寻找自己所需的网址信息 这类搜索引擎因为加入了人的智能 所以信 息准确 导航质量高 缺点是需要人工介入 维护量大等 国外具有代表性的目 录搜索引擎有 Y a h o o L o o k S m a r t O p e nD i r e c t o r y 6 0G u i d e 等 国内具有代 表性的目录搜索引擎有 搜狐 新浪 中文雅虎等 2 3 垂直搜索引擎的结构 根据搜索引擎设计的复杂度不同 搜索引擎的设计框架也不一样 简单的基 于查询串的搜索引擎如A l t a V i s t a 等 只包含两部分的功能 搜索与用户查询服 务 复杂的搜索引擎提供目录服务以及其他的内容 本文根据常用的搜索结构 有机地将分类目录式搜索引擎和基于查询串的搜索引擎结合起来 设计了一个垂 直搜索引擎的体系结构 如图2 4 所示 其各部分功能简述如下 l 爬虫软件 也称为s p i d e r c r a w l e r 和r o b o t 等 定向搜索各类信息前 十名的网站 并负责将这些W e b 文档搜集到原始数据库中 2 索引器 负责对原始数据库的文档构造索引 并且存储在索引数据库中 索引是检索的有利工具 好的索引机制会导致检索效率的提高 3 检索器 是垂直搜索引擎的核心 检索器利用索引数据库中的索引来查 找与用户查询相匹配的文档 计算各个文档和查询关键词的相关度 并将相关度 大于阈值的文档按照相关度递减的顺序排列 返回给用户 4 用户接口 提供可视化的查询输入和结果输出界面 一般来说 在输出 界面中 垂直搜索引擎将检索结果展示为一个线形的文档列表 其中包含了文档 的标题和超链等信息 从图2 4 可以看出 垂直搜索引擎系统包括搜集子系统 索引子系统和检索 子系统三个组成部分 9 西北工业大学硕士学位论文第二章垂直搜索引擎的结构 2 3 1 搜集子系统 罔圜国 闰 爬虫软件 L 上 3 原始数据库 丁厂一 索引器 上 C 1 1 e n q u e u e t o p i c u r l q u e u e u 1 2 e l s e 13 e n q u e u e u r l q u e u e u 西北工业大学硕士学位论文第三章W e b 搜集器 1 4 r e o r d e r q u e u e u r l q u e u e 1 5 r e o r d e r q u e u e t o p i c u r l q u e u e 功能说明 e n q u e u e q u e u e e l e m e n t 将元素e l e m e n t 添加到队列q u e u e 的尾部 d e q u e u e q u e u e 删除队列q u e u e 的第一个元素并将其返回 d e q u e u e 2 q u e u e l q u e u e 2 如果队列q u e u e l 不空 执行d e q u e u e q u e u e l 否 则执行d e q u e u e q u e u e 2 c l a s s i f i e r a n c h o ra n ds u r r o u n d i n ga n du r lt e x to fu 用分类器分析链接 u 的元数据 计算其与特定主题的相关性权值 如果权值大于设定的门槛值C 那么认为链接u 主题相关 否则不相关 r e o r d e r q u e u e q u e u e 根据链接的权 值重新排列q u e u e 3 2 主要类 接口与数据库设计 表3 1C r a w l e r 的状态 C L E A R E D C r a w l e r 处于消除状态 P A U S E D C r a w l e r 处于暂停状态 R U N N I N G C r a w l e r 处于运行状态 S T O P P E D C r a w l e r 处于停止状态 图3 1C r a w l e r 状态转化图 1 6 西北工业大学硕士学位论文 第三章W e b 搜集器 W e b 搜集器负责从种子网页开始收集主题相关的网页 该模块的执行效率决 定了垂直搜索引擎的效率 为提高垂直搜索引擎的执行效率 W e b 搜集器采用多 线程并行地进行网页的下载和分析 本节详细介绍了W e b 搜集器的主要类 接口 与数据库设计 1 C r a w l e r S t a t e 类 状态类C r a w l e r S t a t e 管理W e b 搜集器的状态 其状态设计如表3 1 所示 各状态之间的转化关系如图3 1 所示 2 P a g e 类 P a g e 类封装了网页的属性和操作 当发现一个新的链接 U R L 时将其存 入数据库中等待下载 下载完毕后创建一个P a g e 对象 等待C r a w l e r 线程进行 分析 P a g e 类的主要数据成员如下 U R L b a s e 网页的U R L 地址 比如w w w y a h o o c o l n 皿 S t r i n gt i t l e 网页的标题 S t r i n g c o n t e n t 网页的主要内容 R e g i o n t o k e n s T e x t w o r d s T a g t a g s l 网页中的所有标签 E l e m e n t e l e m e n t 网页文档结构树中的所有节点 E l e m e n tr o o t 网页文档结构树的根 L i n k l i n k s 网页中的所有链接 3 l i n k 类 l i n k 类封装了网页之间链接的属性和操作 包括链接的父网页对应的P a g e 对象 链接的地址以及链接的A n c h o r 文字等元数据 l i n k 类的主要数据成员如下 p r i v a t eP a g ep a g e 链接的父网页对应的P a g e 对象 p r o t e c t e dU R Lu r l 链接的U R L 地址 p r i v a t ef l o a tp r i o r i t y 链接的主题相关性权值 p r i v a t eD o w n l o a d P a r a m e t e r sd p 链接的下载参数 4 C r a w l e r 类 W e b 搜集器的核心是C r a w l e r 类 它实现了收集主题相关网页的功能 C r a w l e r 类的主要数据成员如下 p r o t e c t e d1 w o r k l o a d S t o r a b l ew o r k l o a d 数据库接口 管理C r a w l e r 搜集到的链接 U R L 等待C r a w l e r W o r k e r 线程池中的线程下载分析 西北工业大学硕士学位论文 第三章W e b 搜集器 p r i v a t eL i n k r o o t s n u l l 网页搜集的种子U R L p r o t e c t e dC r a w l e r W o r k e rp o o l 口 用于下载分析网页的线程 p r i v a t ei n ts t a t e C r a w l e r E v e n t C L E A R E D C r a w l e r 的状态 p r i v a t eS t r i n gn a m e g e t C l a s s g e t N a m e0 p r i v a t eD o w n l o a d P a r a m e t e r sd p n e wD o w n l o a d P a r a m e t e r s c h a n g e U s e r A g e n t n a m e 页面下载参数 D o w n l o a d P a r a m e t e r s 为封 装下载参数信息的类 记录了下载超时的时问 下载页面同时开启的线程数 最 大页面大小 是否接受的M I M E 类型等 P r i r a t eR o b o t E x c l u s i o nr o b o t E x c l u s i o n P r i v a t eV e c t o rc l a s s i f i e r s n e wV e c t o r 注册到C r a w l e r 的分类器 P r i v a t et r a n s i e n tV e c t o rc r a w l e r L i s t e n e r s 注册到C r a w l e r 的状态 监听器 实现C r a w l L i s t e n e r 接口 当C r a w l e r 状态发生改变时 向所有的 C r a w l e r 状态监听器发送消息 监听器完成相应的操作 P r o t e c t e dC r a w l e r D o n ed o n e n e wC r a w l e r D o n e0 决定C r a w l e r 运行是 否终止 5 I W o r k e r l o a d S t o r 8 b l e 接口 I W o r k e r l o a d S t o r a b l e 接口定义了链接队列管理器的功能 它保存W e b 搜集 器搜集到的链接及其元数据 还定义了W e b 搜集器在下载分析链接过程中链接所 可能经历的状态 I W o r k e r l o a d S t o r a b l e 接口的主要属性和方法如下 p u b l i cs t a t i cf i n a lc h a rR U N N I N G R 链接正在进行下载分析 p u b l i cs t a t i cf i n a lc h a rE R R O R E 链按在下载过程中出错 p u b l i cs t a t i cf i n a lc h a rW A I T I N 6 w 链接已经保存 正在等待下 载分析 p u b l i cs t a t i cf i n a lc h a rC O M P L E T E C 链接已经下载分析完毕 p u b li cs t a t i cf i n a lc h a rU N K N O W N U 未知链接 p u b l i cS t r i n ga s s i g n w o r k l o a d 0 从链接队列中找出一个链接进行分析 它将返回一个权值最大的状态为W A I T I N G 的链接 并把此链接状态改为R U N N I N G p u b li cv o i da d d W o r k l o a d S t r i n gu r l d o u b l er e l e v a c e 将链接及其 主题相关性权值存入队列 p u b l i cB o o l e a na d d l i n k L i n k1 S t r i n gp a r e n t U R L 保存链接及其元 数据 p u b l i cc h a rg e t U R L S t a t u s S t r i n gu r l 返回队列中链接的状态 如果 链接不存在 返回U N K N O W N 西北工业大学硕士学位论文 第三章W e b 搜集器 p u b l i cv o i dc o m p l e t e W o r k l o a d S t r i n gu r l B o o l e a ne r r o r 链接下载 分析完毕 如果准确无误 将链接状态设为C O M P L E T E 否则为E R R O R p u b l i cv o i dc l e a r 将链接队列清空 6 C r a w l e r W o r k e r 类 C r a w l e r W o r k e r 类设计为线程类T h r e a d 的子类 用于在后台多线程地进行链 接的下载分析 关于C r a w l e r W o r k e r 类实现的细节将在3 4 3 节详细论述 7 数据库设计 在W e b 搜集器搜集网页的过程中 它抽取页面的链接及其相应的链接元数据 并将其存入数据库中 此数据库主要包括两个表 详细如下 U r l l o a d u r lv a r c h a r 2 5 0 u r l i db i g i n t 2 0 A u t oI n c r e m e n tP r i m a r yK e y s t a t u sv a r c h a r 1 r e l e v a n c ed o u b l e m e t a d a t a u r l i db i g i n t 2 0 P r i m a r yK e y p a r e n tu r li db i g i n t 2 0 P r i m a r yK e y t y p ev a r c h a r 1 m e t a d a t av a r c h a r 2 5 0 A l l o wN u l l u r l l o a d 表中包含了种子页面和W e b 搜集器运行过程中所搜集到的网页的链 接 对于每一个链接 u r l l o a d 表包含链接地址 u r l 链接的标示号 u r l i d 链接的下载状态 s t a t u s 链接的主题相关性权值 其中链接的下载状态主要包 括链接正在等待下载 W A I T I N G 链接正在下载 R U N N I N G 链接