（计算机应用技术专业论文）垂直搜索引擎数据分析技术的研究与实现.pdf

华北电力大学硕士学位论文 摘要 针对通用搜索引擎的信息量大、查询不准确、深度不够等问题，本文采用垂直 搜索引擎技术和电子商务服务相结合的新的服务模式，设计了一个电子商务垂直搜 索引擎系统。论文重点研究了系统的数据分析模块中对页面数据信息抽取方式和数 据索引的关键技术和实现算法；设计实现了数据展示模块的用户查询接口，同时对 检索结果做了相关性分析。在对各类信息抽取技术进行分析和比较后，设计了本系 统的信息抽取方案；针对该方案本文设计了独有的索引结构，在数据索引过程中应 用了基于词库的最大匹配分词算法，采用顺排和倒排索引相结合的文件索引方式建 立索引。经过试验证明，本文设计和实现的电子商务搜索引擎能够满足用户结构化 查询需求，该系统具有较好的实用价值和应用前景。 关键词：垂直搜索引擎，信息抽取，中文分词，倒排索引，相关性排序 a b s t r a c t a i m e dt ot h es o l v i n gt h ep r o b l e m so ft o o m a s s i v ed a t a ，l o ws e a r c ha c c u r a c y a n dp r o f u n d i t yi nc o m m o ns ea n db a s e do nt h en e ws e r v i c em o d e lo fv e r t i c a ls e a r c h e n g i n ec o m b i n e dw i t he - c o m m e r c e ，t h i sp a p e rd e s i g n sae - c o m m e r c ev s es y s t e m ， w i t hf o c u so nt h ek e yt e c h n i q u e sa n da r i t h m e t i co fw e bp a g e s i n f o r m a t i o n e x t r a c t i o na n dd a t ai n d e xo ft h ed a t aa n a l y s i sm o d u l e ，a n di m p l e m e n t a t i o no fu s e r q u e r yi n t e r f a c ea n dr e s u l t sa n a l y s i so ft h ed a t ap r e s e n tm o d u l e b a s e do nt h e a n a l y s i sa n dc o m p a r i s o no fi et e c h n o l o g y , t h i sp a p e rp r o p o s e sa na p p l i c a b l ei e s o l u t i o n ；a p p l yt h em ma r i t h m e t i co fc h i n e s es e g m e n t a t i o n b a s e d o nw o r d s d a t a b a s ea n dc o o p e r a t i o no fs e q u e n c ei n d e xa n di n v e r t e di n d e xa n dt h es p e c i a li n d e x s t r u c t u r e a f t e rs y s t e mt e s t i n g ，t h ee - c o m m e r c es e a r c he n g i n ef u l f i l l st h eu s e r s q u e r yn e e do fs t r u c t u r e di n f o r m a t i o n i tp r o v e st ob ew i t hp r a c t i c a l i t yv a l u ea n d a p p l i c a t i o nf o r e g r o u n d j i a n gj u a n ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yv i c ep r o f z h e n gl i n g k e yw o r d s ：v e r t i c a ls e a r c he n g i n e ，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 e s e g m e n t a t i o n ，i n v e r t e di n d e x ，r e l e v a n c er a n k i n g 华北电力大学硕士学位论文 摘要 针对通用搜索引擎的信息量大、查询不准确、深度不够等问题，本文采用垂直 搜索引擎技术和电子商务服务相结合的新的服务模式，设计了一个电子商务垂直搜 索引擎系统。论文重点研究了系统的数据分析模块中对页面数据信息抽取方式和数 据索引的关键技术和实现算法；设计实现了数据展示模块的用户查询接口，同时对 检索结果做了相关性分析。在对各类信息抽取技术进行分析和比较后，设计了本系 统的信息抽取方案；针对该方案本文设计了独有的索引结构，在数据索引过程中应 用了基于词库的最大匹配分词算法，采用顺排和倒排索引相结合的文件索引方式建 立索引。经过试验证明，本文设计和实现的电子商务搜索引擎能够满足用户结构化 查询需求，该系统具有较好的实用价值和应用前景。 关键词：垂直搜索引擎，信息抽取，中文分词，倒排索引，相关性排序 a b s t r a c t a i m e dt ot h es o l v i n gt h ep r o b l e m so ft o o m a s s i v ed a t a ，l o ws e a r c ha c c u r a c y a n dp r o f u n d i t yi nc o m m o ns ea n db a s e do nt h en e ws e r v i c em o d e lo fv e r t i c a ls e a r c h e n g i n ec o m b i n e dw i t he - c o m m e r c e ，t h i sp a p e rd e s i g n sae - c o m m e r c ev s es y s t e m ， w i t hf o c u so nt h ek e yt e c h n i q u e sa n da r i t h m e t i co fw e bp a g e s i n f o r m a t i o n e x t r a c t i o na n dd a t ai n d e xo ft h ed a t aa n a l y s i sm o d u l e ，a n di m p l e m e n t a t i o no fu s e r q u e r yi n t e r f a c ea n dr e s u l t sa n a l y s i so ft h ed a t ap r e s e n tm o d u l e b a s e do nt h e a n a l y s i sa n dc o m p a r i s o no fi et e c h n o l o g y , t h i sp a p e rp r o p o s e sa na p p l i c a b l ei e s o l u t i o n ；a p p l yt h em ma r i t h m e t i co fc h i n e s es e g m e n t a t i o n b a s e d o nw o r d s d a t a b a s ea n dc o o p e r a t i o no fs e q u e n c ei n d e xa n di n v e r t e di n d e xa n dt h es p e c i a li n d e x s t r u c t u r e a f t e rs y s t e mt e s t i n g ，t h ee - c o m m e r c es e a r c he n g i n ef u l f i l l st h eu s e r s q u e r yn e e do fs t r u c t u r e di n f o r m a t i o n i tp r o v e st ob ew i t hp r a c t i c a l i t yv a l u ea n d a p p l i c a t i o nf o r e g r o u n d j i a n gj u a n ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yv i c ep r o f z h e n gl i n g k e yw o r d s ：v e r t i c a ls e a r c he n g i n e ，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 e s e g m e n t a t i o n ，i n v e r t e di n d e x ，r e l e v a n c er a n k i n g 声明尸明 本人郑重声明：此处所提交的硕士学位论文垂直搜索引擎数据分析技 术的研究与实现，是本人在华北电力大学攻读硕士学位期间，在导师指导 下进行的研究工作和取得的研究成果。据本人所知，除了文中特别加以标注 和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得华北电力大学或其他教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 学位论文作者签名： 至三妫 e l期：型堕：垒：垡 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学 校有权保管、并向有关部门送交学位论文与复印件；学校可以采用影印、 缩印或其它复制手段复制并保存学位论文：学校可允许学位论文被查阅或 借阅；学校可以学术交流为目的，复制赠送和交换学位论文；同意学校可 以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：主呈童圣导师签名： e l期：塑哩：三：! 皇 日期：兰塑墅：至：! f 华北电力大学硕士学位论文 1 1 选题背景及意义 1 1 1 搜索引擎的兴起和发展 第一章引言 w e b 作为信息技术的载体己成为人们重要的工作、学习、生活、娱乐工具。 w c b 的发展给人类生活带来了巨大的方便，人们可以跨越时间和空间界限来共享大 量信息。但是面对w e b 上如此丰富的内容，人们同时也感到无所适从，太多的内容 使得迅速定位真正需要的信息变得更困难，跟随一个一个链接在w e b 上漫游则会浪 费大量的时间，而且很可能徒劳无功人们迫切需要有效的信息发现工具来为他们 在w e b 上进行导航，这时为满足大众信息检索需求的专业搜索网站便应运而生了。 现代意义上的搜索引擎的祖先，是1 9 9 0 年由蒙特利尔大学学生a l a ne m t a g e 发 明的a r c h i e 。虽然当时w o r l dw i d ew e b 还未出现，但网络中文件传输还是相当频繁 的，而且由于大量的文件散布在各个分散的f 】限主机中，查询起来非常不便，因此 a l a ne m t a g e 想到了开发一个可以以文件名查找文件的系统，于是便有了a r c h i e 。 最早现代意义上的搜索引擎出现于1 9 9 4 年7 月。当时m i c h a e lm a u l d i n 将j o h n l e a v i t t 的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的l y c o s 。同年4 月， 斯坦福大学的两名博士生，d a v i df i l o 和美籍华人杨致远共同创办了超级目录索引 y a h o o ，并成功地使搜索引擎的概念深入人心。从此搜索引擎进入了高速发展时期。 目前，互联网上有名有姓的搜索引擎已达数百家，其检索的信息量也与从前不可同 日而语。比如最近风头正劲的( 3 0 0 9 l e ，其数据库中存放的网页已达3 0 亿之多，还 有百度其存放的网页也有6 亿多。 搜索引擎以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、 组织和处理，并为用户提供检索服务，从而起到信息导航的目的【1 1 。搜索引擎提供 的导航服务己经成为互联网上非常重要的网络服务，搜索引擎已经成为人们在网络 中的“导游。搜索引擎技术因而成为计算机工业界和学术界争相研究、开发的对 象。 1 1 2 搜索引擎目前存在的问题 尽管搜索引擎帮助人们从因特网获取所需信息起到了很大的作用，但也应该看 到搜索引擎技术的发展不可能跟上因特网上呈几何级数爆炸性增长的信息的速度， 因而搜索引擎也就无法满足人们越来越高的期望值。总的来说，当前搜索引擎主要 存在着以下几方面不足【2 】： 1 华北电力大学硕士学位论文 1 检索精度差 这主要是现有的搜索引擎几乎都只提供关键词接口，关键词不能符合人们日常 用语的习惯，因而用户不能用它来准确表达自己检索的需求。关键词不但不能用来 描述文档的内容信息，也使得用户无法准确自由地表达自己的兴趣。只有提供自然 语言接口或其它更加科学的方法才能让用户更好地表达自己的需求，使检索的结果 更加精确。 2 没有有效地适应信息源变化的机制 由于因特网的开放性和动态性，新的信息在不断增加，旧的信息也在不断地更 新变化，而再快的搜索引擎其更新和维护都难以跟得上信息源的变化。无效链接经 常出现在检索结果列表中。如何提供有效的信息源变化机制也是一个值得研究的问 题。 3 不能访问动态网页 搜索引擎只能访问“可索引”网页，对于动态网页就无能为力了。然而，随着 应用等网站越来越多，网站使用动态网页生成工具是大趋势，大量的这些动态网页 中蕴涵着丰富的有用的信息。如果不能索引这些网页，将使得搜索引擎丢失很多可 用的信息。 4 检索结果显示方式过于简单 当前搜索引擎对于用户提交的每一个查询请求，都只是顺序性的返回上百个或 上千个页面，对检索结果缺乏必要的组织，视图单一。不能动态地显示检索结果， 或者根据用户的需要重新进行层次性的聚类、组合，让用户多层次多视角来浏览选 择检索结果，以达到进一步改善检索结果排序的目的。 5 人机交互较为简单，没有考虑用户的反馈 一方面- 由于缺乏良好的查询接口，用户不能准确地表达自己的查询请求，而 搜索引擎也都没有提供边查询边修正关键词的功能，用户无法通过不断细化或精确 化自己的查询词来达到准确表达自己需求的目的。另一方面，系统只负责返回结果 给用户，并不关心用户对返回结果的选择和评价，没有充分利用用户的反馈来提高 系统的检索精度。 6 个性化能力太差 现有的搜索引擎对所有的用户都是一个模式，查询相同的关键词，得到的结果 也一样，不参考用户的背景知识、兴趣特征，不具有对单个用户或某一特定用户群 的浏览模式和浏览行为进行分析的功能，因而不具有提取用户兴趣的能力。一句话， 只能面向公共用户，而不能适应特定用户的查询需求。 7 不具备主动性信息服务功能 目前的搜索引擎只满足于信息的发现，即只注重系统对信息“拉”的功能，而 不注重在搜索引擎加装信息“推送”功能，使系统能够在了解用户需求的基础上主 2 华北电力大学硕士学位论文 动把某一领域的信息推送给某一特定用户或某一群相关的用户。 1 2 垂直搜索引擎的国内外现状 专业化的垂直搜索引擎在提供专业信息方面有着大型综合引擎无法比拟的优 势，它面向某一特定专业领域，专注于自己的特长与核心技术，保证了对该领域信 息的完全收录与及时更新1 3 1 。因此，基于专业领域的垂直搜索引擎开始成为搜索引 擎发展的一个新趋势，同时，这也正符合了因特网发展的一个趋势，因特网将更专 业化、分工更细。与大型综合型搜索引擎相比，垂直性的专题搜索引擎具有以下几 个特点： 1 采集的学科领域小，信息量相对较少，可以保证用专家分类标引的方法对 采集到的信息进行组织整理，进一步提高信息的质量，建立起一个高质量、专业信 息收录全、能够实时更新的索引数据库。 2 只涉及某一个或几个领域，词汇和用语的一词一字多义的可能性降低，而 且利用专业词汇表进行规范和控制，从而大大提高了查全率与查准率。 3 信息采集量小，网络传输量小，有利于网络带宽的有效利用。 4 索引的数据库规模小，有利于缩短查询响应的时间，可以采用复杂的查询 语法，提高用户的准确查询精度。 5 数据规模的降低，可以节省搜索引擎的投资成本，用普通的硬件投资即可 建立高质、高效的专题搜索引擎。 当然，专题搜索是针对某一专业领域的知识搜索，面向的是某一专业领域的用 户群。而对于广大的互联网用户，存在大部分的对于日常生活领域中的搜索需求， 如购物、求职等。这就需要专门的面向购物或者求职信息的搜索引擎，为用户提供 专业化的搜索服务。 2 0 0 7 年，中国互联网搜索领域已是风声水起，各类垂直搜索引擎正悄悄地圈地 发展，乃至壮大。我们可以看出这些有各类背景的垂直搜索引擎的发展，不但将影 响搜索的市场，更将影响中国广大用户的习惯和发展。他们分别是【4 】： 1 以奇虎w v c w q i h o o c o r n 为代表的论坛搜索； 2 以酷讯w w w k o o x o o c o r n 为代表的生活搜索； 3 以音速w w w 2 5 8 t o m 为代表的商业搜索； 4 以去哪儿w w w q u n a r e o m 为代表的旅游搜索； 5 以搜职v c v c n v g l o b e h r c o m 为代表的招聘搜索； 6 以顶九w w w d i n 9 9 t o m 为代表的比价搜索： 7 以视频搜索w v d w o p e n v t v 为代表的娱乐搜索。 可以看出，搜索已经不再只是单纯地搜索网站页面，而是越来越细化，越来越 3 华北电力大学硕士学位论文 有针对性。专业搜索服务越来越受到用户的欢迎，也成为了学术研究的热门项目。 1 3 本文主要工作 针对通用搜索引擎存在的信息量大、查询不准确、深度不够等问题，垂直搜索 引擎能够在数据的准确性、专业性、结构性等方面满足用户的需求。另一方面，网 络购物的逐渐流行，成为消费者购买的主要途径之一，因此对电子商务的服务需求 也越来越迫切。基于这些背景，本文研究的基于电子商务的垂直搜索引擎旨在建立 一个便捷、一目了然的信息检索服务，为用户提供各类商品的结构化信息，使用户 能够在一个搜索服务下就能“货比三万家。 本文所作的主要工作有以下几点： 1 在查阅了国内外大量文献资料的基础上，了解了当前通用搜索引擎现状和 存在的问题，确定了垂直搜索引擎的研究方向和主题。 2 对通用搜索的系统架构和工作原理进行了深入的学习和理解；提出了以图 书为主题的电子商务垂直搜索引擎系统的设计方案，包括系统的结构设计和数据结 构的设计，研究了系统实现中存在的问题和拟解决方案。 3 深入学习了解了垂直搜索引擎数据分析模块的页面分析和信息抽取并且数 据结构化的技术，针对图书信息的特点设计实现了本系统特有的基于包装器的信息 抽取方式。 4 对数据的索引模块应用到的分词技术进行了深入的研究；在通用搜索引擎 的数据索引技术的基础上进行索引方式的改进，经过试验，改进方式为系统提供了 良好的索引结构和检索效果。 5 实现了用户查询接口，对查询请求提供检索服务，并对检索结果进行相关 度分析和排序输出。 6 在研究了当前流行的软件开发技术的基础上，选择了j a v a 程序设计开发语 言，利用了一些开源项目的资源，开发出了一个可供使用的、可跨平台的图书主题 垂直搜索引擎的数据分析和展示系统。 4 华北电力大学硕士学位论文 2 1 搜索引擎的分类 第二章搜索引擎综述 搜索引擎面向的是互联网访问者，由于其数据量和客户数量的限制，自然语言 处理技术、知识检索、知识挖掘等计算密集的智能计算技术很难应用，这也是目前 搜索引擎技术努力的方向。互联网上的搜索引擎种类很多，但是它们的技术基础都 是互联网技术和数据库技术，以及一些人工智能技术和多媒体技术。根据它们所基 于的技术原理，按照信息搜集方法和服务提供方式的不同，搜索引擎系统可以分为 四大类【5 j 。 2 1 1 基于机器人的搜索引擎 基于机器人的搜索引擎也称为基于r o b o t 的搜索引擎。这种搜索引擎的特点 是利用一个称之为机器人的程序自动访问w e b 站点，提取站点上的网页，并根据网 页中的链接进一步提取其他网页，或转移到其他站点上。这种机器人程序也称之为 s p i d e r 或w e bc r a w l e r 等。机器人搜集到的网页被加入到搜索引擎的数据库中，供用 户查询使用。i n t e r n e t 上最早出现的搜索引擎就是利用机器人来建立数据库。 基于机器人的搜索引擎的优点是信息量大、更新及时、无需人工干涉，缺点是 返回的信息过多，有很多无关信息，用户必须从结果中进行筛选。这类搜索引擎的 代表是：a l t av i s t a 、n o r t h e r nl i g h t 、e x c i t e 、i n f o s e e k 、i n k t o m i 、f a s t 、l y c o s 、 ( 3 0 0 g l e ；国内代表为：天网、悠游、o p e n f i n d 等。 2 1 2 目录式搜索引擎 目录与基于机器人的搜索引擎所不同的是，目录的数据库是依靠专职编辑或志 愿人员建立起来的。这些编辑人员在访问了某个w e b 站点后撰写一段对该站点的描 述，并根据站点的内容和性质将其归为一个预先分好的类别，把站点的u r l 和描述 放在这个类别中，当用户查询某个关键词时，搜索软件只在这些描述中进行检索。 很多目录页接受用户提交的站点和描述，当目录的编辑人员认可该网站和描述后， 就会将之添加到合适的类别中。 目录搜索引擎因为加入了人的智能，所以信息准确，导航质量高。缺点是需要 人工介入，维护量大，信息量少，信息更新不及时。这类搜索引擎的代表是：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 、g og u i d e 等。事实上，现在很多搜索站点 都同时提供目录搜索引擎和基于机器人的搜索引擎两种服务，以便尽可能的为用户 华北电力大学硕士学位论文 提供全面的查询结果。 2 1 3 元搜索引擎 元搜索引擎也叫多元搜索引擎，即m e t a 搜索引擎( m u l t i p l es e a r c h e n g i n e ) 。它的特点是本身并没有存放网页信息的数据库，当用户查询一个关键词 时，它把用户的查询请求转换成其他搜索引擎能够接受的命令格式，并行地访问数 个搜索引擎来查询这个关键词，并把这些搜索引擎返回的结果进行重复排除、重新 排序处理后，作为自己的结果返回给用户。元搜索引擎向其提交查询请求的搜索引 擎称为目标搜索。由于采用了一系列的优化运行机制，能够在尽可能短的时间内提 供相对全面、准确的信息，而且即使不能完全满足用户需求，仍可以作为相对可靠 的参考源进行扩展搜索。 严格意义上来讲，元搜索引擎只能算是一种用户代理，而不是真正意义上的搜 索引擎。大部分搜索引擎在处理其它搜索引擎的返回结果时，只提取出每个搜索引 擎的结果中前面1 0 , - - - - 5 0 条，并将这些条目合并在一起返回给用户，因此最后结果 的数量可能会远少于直接在一个搜索引擎上进行查找所得到的数量，这就是为什么 很多i n t e m e t 用户都喜欢使用元搜索引擎来查找信息的原因。元搜索引擎实现起来 也比较简单，但是它也有一定的局限性，例如多数元搜索引擎都只能访问少数几个 搜索引擎，并且通常不支持这些搜索引擎的高级搜索功能，在处理逻辑查询时也常 常会出现错误。这类搜索引擎的代表是：w e b c r a w l e r 、i n f o m a r k e t 等。 2 1 4 垂直搜索引擎 另外目前出现的垂直搜索引擎也以一种新的概念全面发展起来。垂直搜索是针 对某一个行业的专业搜索引擎，是搜索引擎的细分和延伸，是对网页库中的某类专 门的信息进行一次整合，定向分字段抽取出需要的数据进行处理后再以某种形式返 回给用户。 垂直搜索引擎和普通的网页搜索引擎的最大区别是对网页信息进行了结构化 信息抽取，也就是将网页的非结构化数据抽取成特定的结构化信息数据，好比网页 搜索是以网页为最小单位，基于视觉的网页块分析是以网页块为最小单位，而垂直 搜索是以结构化数据为最小单位。然后将这些数据存储到数据库，进行进一步的加 工处理，如：去重、分类等，最后分词、索引再以搜索的方式满足用户的需求。整 个过程中，数据由非结构化数据抽取成结构化数据，经过深度加工处理后以非结构 化的方式和结构化的方式返回给用户。 垂直搜索引擎的应用方向很多，比如企业库搜索、供求信息搜索引擎、购物搜 索、房产搜索、人才搜索、地图搜索、r a p 3 搜索、图片搜索等等，几乎各行各业各 6 华北电力大学硕士学位论文 类信息都可以进一步细化成各类的垂直搜索引擎。 本文以图书为主题研究的垂直搜索引擎，整体流程大致如下：抓取网页后，对 网页商品信息进行抽取，抽取出商品名称、价格、描述等，甚至可以进一步将笔记 本商品描述细分成“品牌、型号、c p u 、内存、硬盘、显示屏 等，然后对信息进 行清洗、去重、分类、分析比较、数据挖掘，最后通过分词索引提供用户搜索。 2 2 搜索引擎的评价指标 一个互联搜索引擎的优劣，与以下几个因素相关【6 】： 1 网页覆盖率。一个搜索引擎网页数据库包含的网页越多，它就有可能为提 供更全面的网页检索。 2 网页检索速度。一个搜索引擎网页数据库的检索速度赶快，它就越有可能 为更多用户提供检索查询服务。 3 网页检索质量。描述搜索引擎检索质量指标分别是p r c c i s i o n 和r e c a l l ，前 者描述检索查询的准确性，即所检索出的相关文档占全部检索出文档的比例；后者 是描述检索结果的完全性，即检索到的相关文档占全部相关文档的比例。 4 网页更新率。由于互联网是一个动态的信息源，因此一个好搜索引擎的网 页数据库内容也应能及时反映这种变化。 由于互联网信息搜索引擎大多是采用基本关键词的信息处理技术，因而随着搜 索引擎覆盖网页数量的急剧增加，也将会导致搜索检索返回结果的急剧增加，这就 使得用户面临着这样的一种尴尬局面：“或许所需要的网页就在检索结果中，但依 然无法将这它们寻找出来 2 3 通用搜索引擎的系统结构 搜索引擎一般由搜索器( r o b o t ) 、索引器( i n d e x e r ) 、检索器( s e a r c h e r ) 和用户接 口( u i ) 等四个部分组成i _ 丌。系统首先由搜索器收集网页的内容；然后由索引器分析 收集内容，建立索引；再由检索器响应用户的检索请示，用户输入关键词后，搜索 器要用这个检索词与建立的索引器匹配，匹配后作相关性排序；最后通过用户接口 将排序结果返回给用户。 1 搜索器 一 搜索器的功能是在互联网中漫游、发现和搜集信息。它常常是一个计算机程序， 日夜不停地运行。它要尽可能快的搜集各种类型的新信息，同时因为互联网上信息 更新很快，所以要定期更新已经搜集过的旧信息，以避免死链接和无效链接。目前 有两种搜集信息的策略： 7 华北电力大学硕士学位论文 a 从一个起始u r l 集合开始，顺着这些u r l 中的超链( h y p e r l i n k ) ，以宽度优 先、深度优先或启发式方式循环地在互联网中发现信息。这些起始u r l 可以是任意 的u r l ，但常常是一些非常流行、包含很多链接的站点，如y a h o o ! 。 b 将w e b 空间按照域名、i p 地址或国家域名划分，每个搜索器负责，个子空间 的穷尽搜索。 搜索器搜集的信息类型多种多样，包括h t m l 、x m l 、n e w s g r o u p 文章、f r p 文件、字处理文档、多媒体信息。搜索器的实现常常用分布式、并行计算技术，以 提高信息发现和更新的速度。商业搜索引擎的信息发现可以达到每天几百万网页。 2 索引器 索引器的功能是理解搜索器所搜索的信息，从中抽取出索引项，用于表示文档 以及生成文档库的索引表。索引项有客观索引项和内容索引项两种：客观项与文档 的语意内容无关，如作者名、u r l 、更新时间、编码、长度、链接流行度等等；内 容索引项是用来反映文档内容的，如关键词及其权重、短语、单字等等。内容索引 项可以分为单索引项和多索引项两种。单索引项对于英文来讲是英语单词，比较容 易提取，因为单词之间有天然的分隔符( 空格) ；对于中文等连续书写的语言，必须 进行词语的切分。在搜索引擎中，一般要给单索引项赋与一个权值，以表示该索引 项对文档的区分度，同时用来计算查询结果的相关度。使用的方法一般有统计法、 信息论法和概率法。短语索引项的提取方法有统计法、概率法和语言学法。索引表 一般使用某种形式的倒排表( i n v e r s i o nl i s t ) ，即由索引项查找相应的文档。索引表 也可能要记录索引项在文档中出现的位置，以便检索器计算索引项之间的相邻或接 近关系。 索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必须实 现即时索引( i n s t a n ti n d e x i n g ) ，否则不能够跟上信息量急剧增加的速度。索引算法 对索引器的性能( 如大规模峰值查询时的响应速度) 有很大的影响。一个搜索引擎的 有效性在很大程度上取决于索引的质量。 3 检索器 检索器的功能是根据用户的查询在索引库中快速检出文档，进行文档与查询的 相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。检索 器常用的信息检索模型有集合理论模型、代数模型、概率模型和混合模型。 4 用户接口 用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。 主要的目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、 及时的信息。用户接口的设计和实现使用人机交互的理论和方法，以充分适应人类 的思维习惯。 用户输入接口可以分为简单接口和复杂接口两种。简单接口只提供用户输入查 r 华北电力大学硕士学位论文 询串的文本框；复杂接口可以让用户对查询进行限制，如逻辑运算( 与、或、非) 、 相近关系( 相邻、n e a r ) 、域名范围( 如e d u 、c o m ) 、出现位置( 如标题、内容) 、信 息时间、长度等等。目前一些公司和机构正在考虑制定查询选项的标准。 2 4 搜索引擎的工作流程 上一节介绍的搜索引擎四个组成部分分别负责搜索引擎系统流程上的四个主 要的核心工作，这四个核心任务分别为： 1 从互联网上抓取网页 利用能够从互联网上自动收集网页的网络蜘蛛程序，自动访问互联网，并沿着 任何网页中的所有u r l 爬到其它网页，重复这过程，并把爬过的所有网页收集到服 务器中。 2 建立索引数据库 由索引系统程序对收集回来的网页进行分析，提取相关网页信息( 包括网页所 在u r l 、编码类型、页面内容包含的关键词、关键词位置、生成时间、大小、与其 它网页的链接关系等) ，根据一定的相关度算法进行大量复杂计算，得到每一个网 页针对页面内容中及超链中每一个关键词的相关度，然后用这些相关信息建立网页 索引数据库。 3 在索引数据库中搜索 当用户输入关键词搜索后，分解搜索请求，由搜索系统程序从网页索引数据库 中找到符合该关键词的所有相关网页。 4 对搜索结果进行处理排序 所有相关网页针对该关键词的相关信息在索引库中都有记录，只需综合相关信 息和网页级别形成相关度数值，然后进行排序，相关度越高，排名越靠前。最后由 页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户。 图2 1 是一个典型的搜索引擎系统架构图，搜索引擎的各部分都会相互交错相 互依赖。其处理流程按照如下描述。 华北电力大学硕士学位论文 图2 - 1 搜索引擎的系统结构图 “网络蜘蛛 从互联网上抓取网页，把网页送入“网页数据库 ，从网页中“提 取u r l ，把u r l 送入“u r l 数据库，“蜘蛛控制 得到网页的u r l ，控制“网 络蜘蛛 抓取其它网页，反复循环直到把所有的网页抓取完成。 系统从“网页数据库中得到文本信息，送入“文本索引 模块建立索引，形 成“索引数据库 。同时进行“链接信息提取，把链接信息( 包括锚文本、链接本 身等信息) 送入“链接数据库一，为“网页评级 提供依据。 “用户力通过提交查询请求给“查询服务器一，服务器在“索引数据库一中进 行相关网页的查找，同时“网页评级 把查询请求和链接信息结合起来对搜索结果 进行相关度的评价，通过“查询服务器 按照相关度进行排序，并提取关键词的内 容摘要，组织最后的页面返回给“用户 。 1 0 华北电力大学硕士学位论文 第三章图书主题垂直搜索引擎系统的总体设计 随着网络的发展；通过网络可以做到的事情也越来越多，网络购物就是其中一 个发展迅猛的现象之一。随着e b a y ，淘宝等大型购物网站的出现，网络带来了一次 前所未有的购物狂潮。而互联网上海量的网络商品信息多而且庞杂，如何能在巨大 的商品海洋中得到用户真正需要而且实惠的信息成为本文研究的初衷。本文以图书 这个商品为例，重点在于构建一个图书搜索引擎，将采集到的图书购物信息页面进 行信息抽取和结构化，利用分词技术对数据进行有效的索引，提供基本的检索功能 给用户查询。 3 1 系统的设计 3 1 1 系统结构设计 如图3 - 1 是系统的结构设计图，系统模块主要包含了数据的采集，数据分析和 数据展示模块。 数据采集 数据分析 数据展示 图3 - 1 系统的总体结构设计图 华北电力大学硕士学位论文 数据的采集模块应用s p i d e r 网络蜘蛛爬行器。网络蜘蛛是搜索引擎采集数据的 主要工具。由于垂直搜索引擎索引的信息内容仅限于特定主题或专门领域，故其网 络蜘蛛在采集数据的过程中无需对整个w e b 进行遍历，只需访问与主题相关的页 面。经s p i d e r 采集下来韵页面可以按照网站结构存储在服务器上，为数据的分析模 块提供数据基础。 数据分析模块主要是对采集后的页面进行分析，过滤掉一些无用的广告信息和 与主题无关的垃圾信息，利用分装器的信息抽取方式将图书的主要信息提取出来， 以结构化的数据格式存储在系统文件中，为数据的索引做好准备；接着对这些结构 化的数据建立起索引，提供给用户接口的检索服务。数据分析模块的工作流程如图 3 2 所示。 抽取规则 页面库 信 息 抽 取 图3 - 2 数据分析模块流程图 倒排档索引库 顺捧档索引库 分词、建立索引 x m l 结构化数据 数据的展示模块首先对用户的查询输入进行分词，按照关键字在索引文件中检 索，并对检索结果作合并操作和排序分析，最后返回结果给用户。数据展示模块的 具体工作流程如图3 3 所示。 图3 - 3 数据展示模块流程图 1 2 华北电力大学硕士学位论文 3 1 2 数据结构设计 以图书这个商品为例，系统涉及到的结构化数据是对图书信息的页面进行信息 抽取后建立的，本文在对大量的商品信息页面进行分析后得出图书的必要信息，针 对这些信息建立起数据的结构，数据以文件形式存储。图3 - 4 为系统涉及到的数据 结构图。 s t r i n gb o o k _ n a m e ； s t r i n ga u t h o r ； s t r i n gb o o k _ p i c ； f l o a tb o o k _ p r i c e ； s t r i n gp u b l i s h e r ； s t r i n gb o o k _ i n t r o ； s t r i n gw e b s i t e ； s t r i n gb o o k _ u r l ； 图书名称 图书作者 图书图片 图书价格 出版社 图书简介 商家网站名称 图书链接地址 图3 - 4 图书信息数据结构图 对数据索引文件的记录结构的设计分为顺排档结构和倒排档结构，如图3 5 和 图3 6 所示。 id o c i d w b r d l d 出现次数 h i th i t l w b r d i d 出现次数 h i th i t 一级索引 图3 - 5 顺排档索引记录结构图 二级索引 图3 - 6 倒排档索引记录结构图 1 3 华北电力大学硕士学位论文 3 2 系统面临的问题和解决方案 3 2 1 数据源的确定 通用搜索引擎对采集的页面不分大小，地理位置，一律进行下载，因此关注点 在于采集的广度和深度。与此不同的本系统关注的是互联网络的商品信息页面，页 面内容具有主题性和专一性。因此数据源的确定是一个问题。 本文采用的数据是从各大购物门户网站采集而来，包括淘宝网，易趣购物等大 型的个体买卖集合网站，也包括像当当网等商业网站。数据采集的目的是为了给用 户提供足够丰富和多样的商品信息。 3 2 2 信息抽取和数据的结构化 信息抽取的主要任务是对采集到的页面采用一定的策略将页面文本组织成有 结构的数据信息。由于数据的来源不同，如何设计一个自动抽取系统使之能对不同 的数据进行抽取，成为一个问题。 本文采用基于包装器的抽取方式，对不同的数据源定义不同的抽取规则。在这 个基础上对包装器进行了改进，利用样本学习方式，设计系统具有自动生成的包装 器的功能。 3 2 3 分词词库的组织 针对图书主题的作者信息，分词系统对人名的识别存在一些困难。通用的分词 词库包含足够多的日常词语，但是专用的人名词库需要手工录入。对人名的智能识 别成为需要解决的问题。系统对这个问题的解决采用的方法是，数据库存储用户查 询输入的某个在词库中无法找到的词，这个词需要以某个姓氏开头，当词出现概率 超过一定的比例时，认为是一个人名，再加入专用词库里。 3 2 4 数据的索引设计 用户在使用搜索引擎时，往往是通过输入关键词来查找相关网页。为了提高检 索的效率，必须对文档进行分词和索引。检索过程主要是在倒排档的索引数据库查 找，但是倒排档索引的建立比较复杂，需要依靠顺排挡索引结构。建立顺排档数据 库虽然占用存储空间，但是易于实现而且快速，而且为倒排档的索引的建立准备了 基础，使索引效率大大提高。本文对数据的索引设计就是采用顺排挡和倒排档结合 的方式。基于图书主题信息结构的特点，系统对索引中词的位置信息进行了改进， 能更快更准的确定词的位置。 1 4 华北电力大学硕士学位论文 第四章页面分析和页面信息抽取方式的应用 w e b 结构化信息抽取就是将网页中的非结构化数据按照一定的需求抽取成结 构化数据，这是垂直搜索引擎和通用搜索引擎最大的差别。信息抽取之前需要对页 面进行一些分析和处理，过滤掉一些无用的信息，得到页面的主题正文结构。 4 1 页面的分析和预处理 页面内容结构分析在信息抽取中有着重要的作用。从页面布局和内容之间关系 出发，根据页面中标记之间关系，用标记树表示页面文件，采用自底向上的算法， 抽取出具有不同语义的页面内容，利用树形层次结构表示它们之间关系。 4 1 2 页面的预处理 为了方便预处理结果的使用，我们用一个统一的结构化的模型表示预处理的结 果，这个网页表示模型称为d o c v i e w 引。它包括：网页标识、网页类型、内容类别、 标题、关键词、摘要、正文、相关链接等要素。其中正文和相关链接要素属于网页 的内容数据，而其他6 项则属于网页的元数据。下面将对模型中的各个要素作详细 描述。 网页标识是对w e b 上网页的唯一性标识，在d o c v i e w 模型中使用网页的u r l 作为网页标识。 网页类型是根据网页内容的表现形式进行划分的，在本文中将网页分为三类： 有主题网页、目录网页、图片网页。 1 有主题网页：网页中通过文字描述了一件或多件事物，是有一定主题的。 一张具体的新闻网页就是典型的有主题网页。 2 目录网页：专门用来提供网页导向的网页，因而是超链聚集的网页。门户 网站的首页就是典型的目录网页。 3 图片网页：网页的内容是通过图片的形式体现的，其中文字很少，仅仅是 对图片的一个说明。某个机构的人员介绍网页就是典型的图片网页。 将网页分为上述三个类型是因为三类网页在用途和处理方法上存在较大的差 别。其中目录网页与其它两类网页的区别在于网页在w e b 上发挥的作用不同，目录 网页通常不会具体的讲述一件事物，而是提供关于相关信息的链接集。而图片网页 与其它两类网页的区别在于处理的方法不同，由于图片网页的内容是通过图片表达 的而不是通过文字，因而，传统信息处理领域的方法对图片网页是不够有效的。三 1 5 华北电力大学硕士学位论文 类网页问的区别导致很多应用领域都会对它们作适当的区别。 内容类别是对网页的内容进行分类的结果，它是计算机获取网页语义信息的一 个直接手段，在w e b 上的研究领域中有着广泛的应用。它是通过特定的分类器对网 页内容分类得到的，依赖于一定的分类体系。d u b l i nc o r e 中推荐用内容类别作为其 中s u b j e c t 元素的值【9 1 。 标题、关键词和摘要是概括描述w e b 文档内容的重要的元数据，对于w c b 信 息检等领域的工作有非常重要的作用。 正文是原始网页中真正描述主题的部分，可以看作是净化后的网页，因此，在 某些具体应用中用正文代替原始网页更为合理。 相关链接是指在本网页中指向与正文内容相关的网页的链接，而非广告等噪音 链接。可以看出，将正文和相关超链重新组合可以得到另外一个净化尺度的净化后 的网页。 4 1 2 页面的表示