（计算机应用技术专业论文）垂直搜索引擎的研究.pdf

摘要 随着网页信息量越来越大，采用通用搜索引擎搜索某一个方面的信息时覆 盖率和准确率低，回馈的内容不够详细，噪音过多，维护庞大的网页索引库特 别困难，在信息的采集和存储面临着严峻的挑战。由于通用搜索引擎存在以上 的缺点垂直搜索引擎正好弥补了这些不足，它最大的特点是精，准，深。 论文的主要工作如下： 1 介绍了垂直搜索引擎，包括网络蜘蛛，索引器，检索器，用户接口的体系 构架和主题页面分布特征、倒排序索引的建立和中文分词等基本技术。 2 分析并研究了页面的解析和抓取、与主题相关性判定、网页收集和净化等 基本工作原理，优化并且实现了一种页面消重算法。 3 利用l u c e n e 开发包实现了一个小型垂直搜索引擎。用网络蜘蛛实现对各种 类型的文档的解析，包括文本、h t m l 、w o r d 、p d f 等格式，通过解析文档来 提取与主题有关的信息，同时实现了中文分词、索引器和检索器等模块。 4 论文对内容重复的网页消重算法进行了改进和实现，它是对传统基于特征 串的页面消重算法的一种改进。 由于转载导致网址不同而网页内容相同，这样会有大量的重复页面出现， 论文页面消重算法改进算法利用了主码和辅码来实现，特征码能够较好反映网 页内容和方便计算。主码表示网页文本的段落结构信息，辅码用来标识网页文 本的内容信息，这样就能够利用网页文本的结构和内容信息消除重复网页，在很 大程度上提高了消重的效率。 关键词：中文分词，l u c e n e ，特征串，网页消重 a b s t r a c t w i t ht h eg r o w i n ga m o u n to fi n f o r m a t i o np a g e sw h e ns e a r c h i n gf o rap a r t i c u l a r i n f o r m a t i o no ng e n e r a ls e a r c he n g i n e sa c c u r a c ya n dc o v e r a g ei sl o w ，p a i db a c kt h e c o n t e n ti sn o td e t a i l e de n o u g ha n dt o om u c hn o i s e ，m a i n t a i nah u g ei n d e xl i b r a r yo f w e bp a g e si se s p e c i a l l yd i f f i c u l t ，i ni n f o r m a t i o nc o l l e c t i o na n ds t o r a g ei s f a c i n g s e v e r ec h a l l e n g e s b e c a u s et h e r ei sm o r et h a ng e n e r a ls e a r c he n g i n e sd i s a d v a n t a g e s o fv e r t i c a ls e a r c he n g i n e so f f s e tt h es o r t a g ea n di t sg r e a t e s tf e a t u r ei st h ep r e c i s e ， a c c u r a t e ，d e e p m a i nw o r ko f p a g ea sf o l l o w s ： 1 d e s c r i b i n gc o m p l e t i l yv e r t i c a ls e a r c he n g i n e ，i n c l u d i n gs y s t e ma r c h i t e c t u r e w h i c hi n c l u d i n gaw e bs p i d e r , i n d e x e r , c r a w l e r , a n du s e ri n t e r f a c ea n dt h e m e s d i s t r i b u t i n gf e a t u r e s ，i n v e r t e ds o r ti n d e xc r e a t i o na n db a s i ct e c h n i q u e ss u c ha s c h i n e s es e g m e n t a t i n gw o r d 2 a n a l y s i s i n ga n ds t u d y i n gt h ep a r s i n ga n dc r a w l i n gw e b ，a n dt h es u b j e c to f d e t e r m i n a t i o n ，c o l l e c t i o na n dp u r i f i c a t i o no ft h eb a s i cw e ba n da l s os oo p e r a t i n g p r i n c i p l e ，o p t i m i z ea n di m p l e m e n ta na l g o r i t h mf o re l i m i n a t i o no fd u p l i c a t e d p a g e s 3 i m p l e m e n t i n gas m a l lv e r t i c a ls e a r c he n g i n e ，m a i n l yi m p l e m e n t i n gl u c e n e d e v e l o p m e n tk i t ，w e bs p i d e rt oa c h i e v er e s o l u t i o no ft h ev a r i o u st y p e so f d o c u m e n t s ，i n c l u d i n gt e x t ，h t m l ，w o r d , p d fa n do t h e rf o r m a t s ，b yp a r s i n gt h e d o c u m e n tt oe x t r a c tt h et o p i c - r e l a t e di n f o r m a t i o n , a n dt h ep a g ea c h i e v em o d u l e s i n c l u d i n gt h ec h i n e s ew o r ds e g m e n t a t i o n , t h ei n d e x e ra n dt h es e a c h e r 4 t h i sp a g ee l i m i n a t ei m p r o v i n ga n di m p l e m e n t e i n gw e bi n c l u d i n gd u p l i c a t i n g c o n t e n t i ti saa ni m p r o v e m e n t f o rt r a d i t i o n a lf e a t u r e - b a s e dw o r d sa l g o r i t h m a st h er e s u l tp a g e s ，r e p r o d u c e dl e dt os u c ha st h ee m e r g e n c eo ft h es a m ec o n t e n t a td i f f e r e n tw e bu r l ，s ot h e r ew i l lb eal o to fd u p l i c a t ec o n t e n t ，t h ei m p r o v e d a l g o r i t h mo ft h i sp a p e ru s et h em a i nc o d ea n ds e c o n d a r yc o d et oa c h i e v e ，t h ef e a t u r e e x p r e s s i o ns i g n a t u r e c a nr e f l e c tt h e p a g e c o n t e n ta n dt h ec o n v e n i e n c eo f c a l c u l a t i o n m a s t e rc o d ep a r a g r a p ho ft e x ts i g n a t u r ew e bp a g es t r u c t u r ei n f o r m a t i o n ， s e c o n d a r yc o d ei d e n t i f yt h ec o n t e n t so ft h ew e bp a g e ，s ot h a tt h et e x tc a nu s et h e s t r u c t u r ea n dc o n t e n to fi n f o r m a t i o nt oe l i m i n a t ed u p l i c a t ep a g e s t h ea l g o r i t h mh a s g r e a t l yi m p r o v e dt h ee f f i c i e n c yo fe l i m i n a t i n gd u p l i c a t ep a g e s i i k e y w o r d s ：c h i n e s es e g m e n t a t i n gw o r d , l u c e n e ，f e a t u r es e r i e s ，e l i m i n a t i o n o f d u p l i c a t e dp a g e s i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名_ 至盟鸟日期：堡：日 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：七哺导师( 签名) ：日弱乙日期5 , z j 武汉理工大学硕士学位论文 第1 章绪论 1 1 研究的背景和意义 随着i n t e r n e t 的迅速发展，随着网络信息资源的急剧增长，然而w e b 信息的 急速膨胀，一方面网上的信息多种多样、丰富多彩，而另一方面用户不能精确 地快速的找到他们所需要的信息。在这个背景下搜索引擎就是在这样的背景下 产生了，并且已经发挥出因特网咽喉要道的的作用，获取信息的入口绝大部分 是搜索引擎。它的好坏直接关系到搜索的准确性。但如何更快速、更精确、更 有效地挖掘网页信息，并提供更便捷的检索服务已经变得十分的迫切。伴随着 信息更加的细化和专业化，更加需要了解具体的领域的详细情况，而普通搜索 引擎却不能做到对每个领域的信息都那么完备，在这个背景下垂直搜索引擎产 生了。垂直搜索引擎也称专业搜索引擎或主题搜索引擎，它们只针对特定主题 信息进行搜索，信息详细并且精确。通用搜索引擎的信息量大、查询不准确、 深度不够而垂直搜索引擎的特点就是专、精、深，且具有行业特点，能够对具 体的领域的问题具体处理，从而得到该方面的更加深入的搜索信息。由于只是 就某一个领域进行搜索，网页的收集周期更加的小，并且对网页更新更加的快， 减少的噪音，等等一些普通搜索引擎不可以比拟优点。 1 2 国内外的发展情况 国内百度有关于新闻、m p 3 、图片、文档等专业的领域有成熟的搜索产品， 特别是在中文搜索支持方面，百度具有一定的技术优势。在中文分词、检索器、 爬抓器、和索引器等等几个关键技术都走在世界搜索引擎的前列是目前的天网 搜索。达到了国外中型搜索引擎系统的技术水平。在垂直搜索国内出现了以火 车票，房地产，旅游为代表的搜索产品，其中论坛搜索有奇虎网，生活搜索有 酷讯网，商业搜索有音速网，旅游搜索有趣那儿，招聘搜索有搜职网，比价搜 索有顶九网，娱乐搜索有视频搜索网。在国内的垂直搜索做的越来越细，国外 有以h e r i t r i x 、n u t c h 、l a r b i n 、l u c e n e 为工具的垂直搜索引擎，代表网站有 h e a l t h c a t e 、m e d i c a lw o r l ds e a r c h 等。在开源社区出现了关于搜索的项目， 武汉理工大学硕士学位论文 l u c e n e 是j a k a r t a 项目的子项目，是开放源代码的全文检索引擎工具包，拥有完 整的索引引擎和查询引擎。n u t c h 基于l u c e n e 的增加数据采集的功能软件。 h e r i t r i x 是开源的w e b 信息采集项目。l a r b i n 是能够多线程同时从不同的站点采 集页面，但是就目前网络爬虫的编写并不是很成熟。 1 3 本文的主要工作和组织结构 本文对搜索引擎的总体构架进行了详细的分析，并且部分实现构架里的一 些功能。对垂直搜索引擎进行详细的讲解。第一章进行背景的阐述，第二章垂 直搜索引擎的基础知识介绍。第三章介绍了搜索引擎开发包l u c e n e 的基本知识 和内部结构，第四章介绍了网络蜘蛛的原理，第五章是系统实现。第六章对全 文工作的总结。前面几章的基本内容介绍是为后面的实现系统做铺垫，本文所 用到的技术在前几章都有所介绍，后面实现系统体现了理论到实践的过程。 所做的主要工作：实现各个系统功能，提出了主码加辅码的理论对网页消 除算法进行了改进，并进行实验证明改进算法的有效性。对内容重复的网页消 重算法进行了改进和实现，它是对传统基于特征串的页面消重算法的一种改进。 由于利用网页文本的结构和内容信息消除重复网页所以对于转载导致页面等一 些噪音的出现导致网址不同而网页内容相同的情况非常有用。 2 武汉理工大学硕士学位论文 第2 章垂直搜索引擎基本知识介绍 2 1 通用搜索引擎分类 通用搜索引擎分为三类：目录式的搜索，全文搜索，元搜索。基于人工维 护索引方式的目录式搜索引擎的典型代表是y a h o o 。它用人工浏览各站点的方式 来对网站分类。优点是结构清晰、错误较少，而缺点是需要人工干预，建立分 类的速度慢。2 ) 全文搜索引擎是从网上提取网页信息建立索引数据库，按照用户 要求检索得到的返回给用户。3 ) 元搜索引擎本身没有自己的数据库，而是调用 其它独立搜索引擎而完成搜索。元搜索在一定程度上弥补单个搜索引擎的不足。 2 2 通用搜索引擎的不足 通用搜索由于没有正对某一个方面进行搜索，虽然内容的广度很大，但是 在内容的详细程度和准确程度都会有所降低，这有它的本身的结构是分不开的， 比如自身的搜索策略，存储方式，研究对象，最小化单元的划分等等，但是大 体上的不足有以下三点： 1 实时性差：由于信息量大难以保证不会出现大量无效或过时的链接。 2 精确度不够：反馈的结果信息量很多，但是部分可用。 3 对数据源种类处理不足：网页上的格式也各种各样，进行信息提取时将会 出现问题，多语种需要根据语言的特征建立符合语言特征的分词技术。 2 3 垂直搜索引擎的优势 由于专业搜索引擎只关注于某一方面的网页，一般是抓取的网页数量和通 用搜索比较少了很多，在这个意义上讲很多在通用搜索领域由于时间复杂度等 问题而不能使用的算法模型在专业搜索中变得可行。通过进行一些复杂的数据 挖掘和分析，可以发现页面内容中蕴涵的更深层次的信息。同时由于信息量相 对较小，网页的更新周期较短，能够较好的保证信息的时效性，而为体现出更 好的搜索质量。 武汉理工大学硕士学位论文 2 4 垂直引擎与通用搜索引擎的差别 由于垂直搜索与通用搜索的结构的差异性他们之间存在许多差别。不管从 工作原理上，还是发展的目标上，还是从对硬件的要求上都存在差别。他们分 别如下： ( 1 ) 爬抓策略不同略1 ：通用搜索引擎图遍历整个w e b 爬抓网页，而垂直搜 索引擎只是爬抓与主题有关的网页，并且则采用预测相关的方法来调整爬行方 向，与主题相关的网页集中的地方爬行会提高爬抓信息的精度。 ( 2 ) 不相同目的：一般搜索可以搜索任何的方面的信息，范围非常的广， 主要体现在全面上。而垂直也就是基于主题搜索在某一方面提供非常详细的信 息，特别是很具有深度的网页。 ( 3 ) 不相同的硬件要求：通用搜索要求专业的服务器才能完成认为，而垂 直型搜索一般的p c 机器就可以完成要求的，这是因为两者的规模是完全不一个 数量级。 2 5 垂直搜索整体框架 垂直搜索按照功能不同，主要由检索器，用户接口，索引器，爬抓器，四 部分相互配合有机的构成。爬抓器的功能是在互联网搜集信息。通过不停地运 行在因特网上抓取各种信息来作为搜索引擎的来源，这点与通用搜索引擎一样。 爬抓器的设计标准是要多、要快、要准、要全的爬抓各式各样的关于某个主题 的网页，因为在网上的网页更新的速度也是非常的快速的，所以还要对已经搜 刮在服务器的网页进行不定期的跟新才能保证有最新的网页和去掉一些死连接 等等。查找与主题相关的网页一般有两种方式：第一个方式是在开始的u 】 也集合 的存放的顺序已经他们的包含的超链接，以深度方式爬行和宽度方式爬行循环 往复地在网上查找所需要的网页。这些起始u r l 可以是任意的u r l ，也可以是 特定的。第二种将w e b 按照域名、口地址的范围划分，在每个范围内进行搜索。 搜集的信息类型多种多样，包括多媒体、文本文件、图片、f t p 文件等等。爬抓 器一般利用基于基于多线程的爬行和分布式的并行计算方式等等来提升查找有 用网页和更新它们的内容的速度。索引器的解析爬抓到的与主题相关的网页， 然后再里面提取一些索引的集合来表示组织成为索引表的数据库。索引器的职 责是解析网页信息、提取网页里有用的内容和建立关于主题的索引库等等几个 4 武汉理工大学硕士学位论文 内容。它包含有主观索引和客观索引项两种：主观索引和网页的内容没有关 系，比如网页所有权、网页更新方面的消息、网页内嵌的脚本语言、网页的大 小，被连接的网页数量等等；客观索引用来表示网页里面的内容，如关于网页 提取的关键词向量和它们的权重等等。客观索引项是有单和多索引两者方式1 。 单索引就英文来说是单词，由于有空格来区分分析它们是非常方便的；但是对 于传统的中文来说必须使用中文分词来完成词语切分。中文分词根据语言的特 点和使用习惯来切分它们，把一句话分成若干个词语。基于倒排表的索引用来 方便的查找某个信息。索引表包含从网页提取出来的文档在磁盘里的地址和找 出索引项的相互关系。索引器首先解析提取网页信息，提取有用信息，去掉没 用信息，比如页面内的广告，这就是需要对网页信息进行提取分解；提取有关 于主题的相关的网页信息，其中有网页应该归属的u r l 、关键词及它们的地址、 它们的长短、和其他网页的链接关系等等，接下来按照关键字的来完成索引的 建立，建立的方式是基于倒排序的方式来完成。基于全文的检索是搜索引擎的 基石，中文分词质量的高低直接关系到搜索结果的质量的高低。用户打入关键 词后检索器通过中文分词来分解关键词，构建一个关键词向量在根据它从数据 库查找与主题相关的网页来反馈给用户：在这个过程中还要涉及到关键词向量 和与网页提取的关键词向量的值，也就是它们的关系度。1 4 1 高低与排名直接挂 钩的；中文分词技术和网页的关键词与用户输入的关键词的相关度计算是关键。 用户接口的作用是把搜索系统计算得出的结果，也就是关于主题相关的链接和 它们的摘要清晰地有结构的反映给使用者，要有较高的效率方式提供给用户区 使用它们，并且要要给使用者简单的查询和复杂查询接口，其中有选定查找词 的范围，关系和逻辑运算符的利用、关键词位置比如内容、标题。垂直搜索引 擎的系统结构如图2 1 i 图2 1 垂直搜索引擎的系统结构图 5 武汉理工大学硕士学位论文 2 6 主题页面分布特征 因特网虽然网页的数量巨大，并且是呈几何级数量的增长，但是主题页面 分布还是有一定规律的。页面包含四个特征巧1 ：t u n n e l 特性、h u b 特性、主题 关联特性和站点主题特性。链接预测和页面过滤正是利用了这些特性。( 1 ) t u n n e l 特性：主题页面聚族之间有时要经过很多与主题没有关系的链接才能相互到达。 这些无关链接就像一个隧道。t u n n e l 会影响爬行的覆盖率、页面质量和准确度。 ( 2 ) h u b 特性：h u b 页面是指向相关主题页面的一个中心，这些页面的链接都是 指向同一个主题。许多页面是相关于某一主题的有价值的页面为权威页面也可 以叫中心页面。好的h u b 页面一般指向多个权威页面，并且所指向的权威页面 的h u b 页面的质量会越好。反过来，h u b 页面的质量越好，它所指向的每个页 面也趋向于权威页面。( 3 ) 站点主题特性：站点趋向于包含若干个主题，同一 主题的页面较紧密地在此站点内部链接成聚族，聚族之间的链接很少。根据主 题聚族的特性，为每一类的链接和页面赋予不同的权重，然后通过向量空间模 型算法为每个页面分类，站点页面可以构成一个棵树，树按照自底向上进行主 题聚类。( 4 ) 主题关联特性：指页面所包含的链接趋向于指向和该页面具有相同 主题的其它页面，对于链接到某主题的页面它所包含的链接也趋向于该主题。 t u n n e l 特征表明了主题聚族的分布不稠密。h u b 特性表明了主题易成聚族；主 题关联特性进一步扩展聚族特性；站点主题特性表明了主题团所在的位置：四 大特性为网络蜘蛛提供了策略指导 2 7 中文分词技术 中文分词技术在搜索引擎有举足轻重的地位，分词的好坏直接关系到搜索 引擎的准确率。在决定与主题相关系数方面和建立索引数据库都吏部开中文分 词的使用，汉语独立活动的有意义的语最小单元是词1 2 1 , 词的切分是中文分词 技术的基础，与英语不同的是汉语的词之间没有用空格隔开，也没有明显的区 分标记，所以词划分的好坏直接影响意思的表达，近一步影响搜索引擎的结果。 早期的搜索引擎当用户搜索一个词的时候，会把词语里面的字搜索出来，往往 会出现词语里面的字分开的情况，这样表达的意思就完全错误。中文分词根据 中文语言的习惯和特点对汉语的音、形、义进行理解，中文分词有三种，分别 是：统计、理解、字符串匹的方法。其中，字符串匹配的分词方法也称机械分词 6 武汉理工大学硕士学位论文 方法，是以词典为支持的，优点是有效率高，算法简单，但容易产生的歧义， 准确率较差；基于统计的分词方法根据词的频度来判断是否为词，优点是可以识 别新词，但是效率不高，时间空间代价比较大；基于理解的分词方法通过让计算 机模拟人对句子的理解，达到识别词的效果，但是语言本身的复杂性，模拟的 难度很大。分词的好坏直接影响了搜索引擎的质量。下面来详细介绍着三种方 法 9 1 ： ( 1 ) 基于字符串匹配的方法是以照词典里的词曲词库为基础，在划分词语 的时候，将字符串与词典里的词进行对照，符合字典库中的词条进行匹配，若 在词库中找到相应的词条，则匹配成功。然后将字符串按词进行切词。根据扫 描的方向，正向匹配和逆向匹配，按照优先匹配的长度，为最大匹配法和最小 匹配法。但是在匹配的方法中可以结合其他的方法一起使用，比如多种分词方 法结合会形式一些新的分词方法，比如设立切分标志法、双向扫描法、最佳匹 配法和二次扫描法等等。 ( 2 ) 基于统计的分词方法： 基于统计的分词方法是不需要切分词典，这是与字符串匹配的方法的最大 的区别。词是稳定的字的组合，如干个字同时出现的次数越多，就越有可能构 成一个词 3 1 1 0 对字组合的频度进行统计，共同出现的频率能够较好地反应成词 的可信度。当如干个字同时出现概率高于的阀值时，就构成了一个词。但共同 出现频度高不一定构成词，例如“我是”，“你是”，“他是”等。如果结合分词词典 效果更好。结合的优点有很多可以识别新的词，又有机械分词切分速度快、效 率高的特点。所以在实际的中文分词中经常是结合起来使用。统计模型的分方 法中。 ( 3 ) 基于理解的分词方法 3 7 1 ： 基于理解的分词方法包括三个部分：分词子系统、句法语义子系统，总控部 分。基本的步骤就是分析句子的语法以及所要表达的语言的意思来分词，然后 用它们来消除句子的歧义，这点非常重要。计算机按照一定的算法来分析句子 来认识词语的目的。这样的方式要对语言有很彻底的了解。语言本身是非常复 杂的，光靠计算机去识别是很困难的，以及本身存在歧义，因此该方法也只是 在研发阶段，还不够成熟。 综合以上三种分词方法的优点和缺点如表2 1 有： 7 武汉理工大学硕士学位论文 算法名称复杂度效率需词库发现新词是否常用 机械分词易低需否是 统计分词难 中等 需 能是 理解分词难高不需能否 表2 1 三种分词方法的优点和缺点3 2 1 每种分词方法都有其优点和不足，使用那种分词方法效果最好目前还没有 定论，使用单一的分词方法来进行分词比较少，综合不同的方法是最好的选择。 8 武汉理工大学硕士学位论文 2 8 倒排索引的建立 在介绍倒排序的时候首先介绍索引的由来，索引的最终的目的是为了加快 查找的速度。当数量固定并且数量也很庞大的时候索引可很大程度上提高检索 时的效率。倒排索引结构由词典和出现情况两部分组成，每一个单词对应一个 词汇列表，列表上面包含文档在磁盘的地址，地址就是单词的位置，说明在提 取的网页中词语是到了那个一个了，如果是字符是到了那一个了1 2 2 1 0 但是索引 结构的一个缺陷是不支持快速更新信息，完成索引建立后文档中的信息发生变 化的时候，也必须更新索引进行。通常是这样处理的：通过定期更新索引，把 新的索引替换旧的索引。查找索引进行时预处理索引的文档，建立文档对应的 索引结构。顺排序索引文档到单词的映射，而倒排索引是单词到文档的映射关 系。假设有两篇文档：文档x 和文档y 。文档x 的内容是：h ei sag o o ds t u d e n t 文档 y 的内容是：t h e r ei sn o ta n ys t u d e n th e r e 。如果建立的是一般的索引结构，那么会 有如表2 2 所示的关系： 文档编号出现单词出现次数 xs t u d e n t1 ys t u d e n t1 y a n y 1 y h e r e1 表2 - 2 一般索引 从中可以看出，普通的索引结构是以文档为中心建立索引结构来记录文档 中出现的单所有词。比如在文档y 中s t u d e n t ，h e r e ，h e r e 各出现一次。对于每个关 键字都要遍历所有的文档，倒排索引按关键字建立索引。例如单词s t u d e n t 在文 档x 和文档y 中分别出现了一次，而单词a n y 只在文档y 中出现了一次，如表 2 3 ： 武汉理工大学硕士学位论文 单词出现的文档出现次数 s t u d e n t x ，y 2 h e r ex1 a n y y1 h e r ey1 表2 3 倒排序搜索 在建立倒排序文件先预处理网页，包括提取正文信息( 指过滤网页标签， s c r i p t s ，c s s ，j a v a ，e m b e d d e d o b j e e ，c o m m e n t s 等信息) 和把正文信息切分为索 引“索引词载体信息”( 网页与文档是不加以区分的，但是网页中包含普通文档所 没有的h t m l 标签信息，这些分析网页两个阶段。形成的结果是文档号到索引 词的对应关系表。每条记录中包括文档编号，索引词编号，索引词在文档中的 位置信息，信息标识了文档中索引词的字体和大小写等信息，或称载，是搜索 引擎的信息。服务阶段提供更好的结果排序所需要的) 。一般只保存编号和索 引词信息。 每个网页由两行信息组成，第一行是文档编号，第二行是使用切分模块将 文档正得到网，调用切词模块，获得正向索引，格文信息划分成索引词后的集 合。建立倒排文件：搜索引擎面临大量的用户检索需求( 几十几千点击秒) ， 要求搜索引擎在检索程序的设计上要高效，尽可能的将大运算量的工作在索引 建立时完成，使检索时的运算尽量的少。一般的数据库系统不能快速响应如此 大量的用户请求，在搜索引擎中通常采用倒排索引技术。由正向索引建立反向 索引如图2 2 ： 网赁1 咧炙2 网炙k 网炙m a ) 特征项1 特征颇2 特征项i 特征项2 图2 2由正向索引建立反向索引 1 0 嘲贞l 嘲炙2 晒炙1 阿页2 网贞3 竺一 墨一 武汉理工大学硕士学位论文 创建倒排索引包括建立正向索引和反向索引。分析完网页后，得到以网页 编号为主键的得到图a 。当反向索引建立完成后的图b ) 。这是一个表的重组的过 程，正向索引表，如图a ) 所示，为了加快速度全过程需要在内存中完成。在小数 据量时，有足够的内存保证该创建过程可以一次完成。数据规模增大后，可以 采用分组索引，然后再归并索引的策略。该策略是，建立索引的模块根据当时 运行系统所在的计算机的内存大小，将索引分为k 组，使得每组运算所需内存 都小于系统能够提供的最大使用内存的大小。按照倒排索引的生成算法，生成k 组倒排索引。然后将这k 组索引归并，即将相同索引词对应的数据合并到一起， 就得到了以索引词为主键的最终的倒排文件索引，即反向索引。真正的搜索引 擎，倒排文件很大，无法直接调入内存，通常在内存中存储以索引词和倒排表 项偏移位置组合的信息。 2 9 主题预测算法的介绍 预测算法是指不下载网页来预测所指向的网页与主题的相关的方向，主题 相关的网页相互联系往往更加紧密。以便所指向的方向是与主题尽可能相关来 提高网络爬虫的精确性。网页汇聚性是一个比较新的概念，网页拓扑结构图是 一个带权重的网页之间的连接的有向图。拓扑图的节点集合会表现出汇聚性， 也可以叫做页面团特性，网页的页面团组织成有向图，链接关系在图来体现。 页面团是大规模统计分析拓扑结构得出的，网页之间的聚类特性并不直观。汇 聚性的出现为基于链接结构的网页相关度预测提供指导，优先下载与主题相关 度高的网页来依据主题相关度进行排序，下载网页的时间比预测网页页面团的 方向的时间长，故预测网页页面团方向很重要，它可以大大减少无关网页的下 载时间。x 为将要下载的网页，定义其中九表示影响参数，九在0 到1 范围。s i m ( t i ) 表示页面t i 的实际相关度值，t i 表示下载链接指向x 的页面；s i m ( x ) 表示预测 页面与主题相关度的值；n 表示页面的入度。x 入度高则与主题相关就大。x 的入度并不高而它链接的网页与主题相关度高则x 的主题相关度高。预测与主 题相关度的页面团的公式： s i r e ( x ) = ( 1 2 ) ( 1 - 矿一) + a 武汉理工大学硕士学位论文 第3 章l u c e n e 的介绍 l u c e n e 具有源代码开源，跨平台，功能强大等优点，l u c r e 是检索引擎工 具包，它需要把包里的类组织起来，然后利用包里提供的框架，才能搭建成有 一定功能的程序。l u c e n e 提供了简单的函数调用接口来用作数据访问和管理， 可以混合到具体应用的中。l u c r e 在检索领域己经有了很多成功的例子。比如 e c l i p s e 的帮助文档采用l u c r e 作为检索引擎t 2 3 1 。 3 1l u c e n e 的特征与优点 l u c r e 以系统架构合理、索引结构优异、代码开源等优点：1 无需自己编写 代码就可获得强大的查询能力，并且查询实现中实现了布尔操作、分组查询、 模糊查询等1 2 4 1 02 l u c e n e 以八位字节为基础的索引文件格式独立于不同平台的 并且可以很容易共享建立的索引文件。3 拥有不依靠语言种类的文件格式的文本 分析接口，加上创立t 0 k e i l 流完成的索引文件1 6 1 扩展新的语言和文件格式只 需要实现文本分析的接口即可。4 利用倒排序可以比较方便的分块，可以在引入 了新的网页或者文档的时候可以建立一个小规模的索引，甚至可以建立二级索 引，也可以把小索引进行合并，可以提高索引的质量达到搜索的速度。5 不改变 l u c r e 索引文件格式就能够让l u c r e 能够运行在各种各样的平台上。6 面向对 象架构拥有一个合理而极具扩充能力，很大方便在l u c r e 的基础上扩充各种功 能，扩展的功能的编写不复杂7 l u c r e 系统抽象恰当和合理，跨平台的功能的 扩展非常容易做到。 3 2l u c e n e 的结构 l u c r e 的系统结构拥有了与平台无关的索引文件格式，是一个低耦合并且 效率高，二次开发容易的引擎。利用中心组件以抽象类的方式来结合具体操作 系统来具体实现组件，系统结构是面向对象的全文检索引擎，经过层层的面向 对象式的处理。与具体平台相关的部分比如文件存储也封装为类l u c r e 系统结 构与源码组织关系如图3 1 ： 1 2 武汉理工大学硕士学位论文 圈3 - 1 系统结构与源码组织关系 l u c e n e 的将所有源码分为了7 个模块2 5 1 po r g a p a c h e l u c e n e u t i l ，o r g a p a - c h e l u c e n es e a r c h ，i n d e x o r g a p a c h e 1 u c c n cs t o t e o r g ，a p a c h e l u c e n e q u e r y p a r s e r , o r 8 a p a e h el u c e n ei n d e x ，o r ga p a c h el u c r eo r gl u c e n e a n b l s i s 。l u c e n e 的系统由对外接 口、索引核心、基础结构封装组成。其中索引核心是直接操作索引文件的，也是 整个系统的重点。模块是虬包表示，各个模块所属的系统部分也如上图所示。 各个包的的功能如表3 - 1 ： 包名功能 o r g , a p a c h e 1 u c e u e m , , a l y s i s 语言分析，切词支持中文的主要 扩展这个类 o r ga p a c h e i n c 自l cd o c u m e n t文档结构管理 o r g , a p a e h e 1 u c e n ei n d e x索引管理，包括建立，删除等 o r sa p a c h e 1 u c e es e a r c h检索管理，根据查询条件得到 o r s a p a c h e 1 u n es t o r e 数据存储管理，主要是底层f o o r g a p a c h e 1 u e e n eq u 6 t y p a r s c r 查询分析器，实现查询关键词的 运算 o r ga p a c h e 1 u c e n e u t i l 一些公用类 武汉理工大学硕士学位论文 表3 - 1 各包的的功能 l u c e n e 不是作为一个单独的索引服务器存在，可以作为一个运行库被包含 进入应用程序中去。l u c e n e 提供一个全文索引引擎的架构，而不是具体实现。 抽象层来减少组件的耦和来达到组件之间不会互相的影响。加入操作处理索引 文件的包来的封装组件记们来完成索引核心的实现。在每一个局部细节上，比如 数据结构与算法，也是引入额外的抽象层以降低耦合性，在高度的面向对象使 得l u c c n e 的实现容易理解，易于扩展。 通过对l u c e n e 源码包的分析，可以发现l u c e n e 的核心类包主要有3 个1 2 7 1 ： o r g a p a c h e 1 u c e n e i n d e x 、o r g a p a c h e 1 u c e n e a n a l y s i s 和o r g a p a c h e 1 u c e n e s e a r c h 。 1 语言分析包o r g a p a c h e 1 u c e n e a n a l y s i s 内部结构如图3 2 ： a n n l ) z e r ( f r o ma a a b s i s ) t o k c n s t r c a r n t j 咄c n s t r c a m ( 1 t o k e n ( f r o ma n a l y s i s j - t cr m t c x i ：s t r i n g - 囊a f t o f f s e t ：i n t - c n d o f f s c t ：i n t - t y i x ：醴妇= w o r d 。 i x 3 s it i o n i c r c r n cn t ：in t = 1 “o k e n ( j + t o k c n ( ) + g c t p o s i t i o n l c r e r n e n t ( ) + g c t p o s i t i o n l c r c m e a t ( ) + t c r m t e x t ( j + s t a r t o f f 譬t ) + c n d o f f s c kj + t y l x ( s i m p l e a n a l z e r c f r o ma t a l y s i s ) o k cn s t r c a m ( 图3 - 2 o r g a p a c h e 1 u c e n e a n a l y s i s 内部结构 o r g a p a c h e 1 u c e n e a n a l y s i s 的作用就是按照切词规则，把一篇文章从开头到结 尾分成一个个的与实际情况尽量相符的词组。对英文，其分词规则很简单，按 1 4 武汉理工大学硕士学位论文 空格取单词即可，以一个合理的完全统计的词库为基础将短语作为一个单位来 切分的话提高英文检索的的速度和准确度。a n a l y z e r 是对文本内容的切分词的抽 象类，切分后返回一个t 0 k e n s t r e a m ，t o k e n s t r e a m 的n e x t 0 取到下一个词。对中 文而言，文字之间都是没有空格，相连的，同样在词库前提下，按照词库的标 准分割文字，这样会更加符合语言的习惯。词库的规模和准确度是影响分词效 果的重要的原因。l u e e n e e 不支持中文切词，需要扩展a n a l y z e l 类。 2 索引管理包o r g a p a c h e 1 u c e n e i n d e x 内部结构如图3 3 和图3 4 ： i n d e x wr t e i t ( f r o mi n d e x ) + g e t u s e c 0 m p o u n d f i l e ( ) + s e t u s e c 0t r t p o u n d f i l e0 + s e t si m i l a r i t yo + g e t si t n i l a 。i t y ( ) + i j l d e x w r i t e r ( ) + i n d e x w r i t e r ( ) + i n d e x w r i t e r ( ) + l n d e x w r i t e r ( ) + c l o 始( ) + f i n a l i z e ( ) 十g e t g n a l y z e r ( ) + d o c c o u n t 0 + a d d d o c ur n e n t ( ) + a d d d o c ur n e n t 0 + g e t s e g m e n t s c o u n t e ro - h l e w s e g m e n t n a m e o - t o p t i l n i z eo + a d d i n d e x e s o + a d di n d e x e s ( ) + f l u s h ra m s e g m e n t so + m a y b e m e r g e s e g m e n t so d o c u m e n t w r i t e r ( f r o mi n d e x ， - m l l x f i e i dl e n g ! h ：i n t - p o s t i n g t a b l e f i e l d l e n g t h s 口：h a t n e l d p o s i t i o n s 【】：i n t n e i d b o o s t s ：n o a t d o c uj n e n t wr i t e ro t e r m l n f o s w r i t e r ( f r o mi n d e x ) 一f o r m a t ：i n t = 2 一s i z t ：k ) n g20 一i n d e x i n t e r v a l ：j n t = l2 8 一s k i p i n t e r v a l ：i n t = 16 一二a s t i r d e x p o i n t e r ：i o r l g = o f i d d s w r i t e r ( f r o mi n