（计算机应用技术专业论文）基于p2pkm的桌面搜索优化的研究.pdf

基于p 2 p k m 的桌面搜索优化的研究 摘要 随着计算机技术的日益发展和网络的迅速普及，电子文档数目急剧膨 胀，从大量的信息里面快速、全面、准确地查找所需要的资料信息已经成 了人们关注的焦点，也成了研究领域内的一个热门课题。目前，信息检索 技术的最新应用是国内外公司相继推出的桌面搜索引擎。桌面搜索的特点 在于不需要通过浏览器来进行搜索，并且将搜索方位延伸到自己电脑硬盘 中所存储的各种文档，能够让用户快速搜索他们的硬盘并且在不到一秒的 时间里得到相关的搜索结果。 桌面搜索引擎是集成信息检索技术的典型代表，信息检索的核心技术 是全文检索技术。在基于p 2 p k m 的学习支持平台系统下，我们需要一个更 加完善的桌面搜索引擎，本文通过对全文检索技术、l u c e n e 全文检索引擎 工具包和近似镜像文本检测算法的分析和研究，对学习支持平台系统的桌 面搜索引擎进行了扩展和完善：改进了l u c e n e 的中文分词技术，支持多种 文档格式文件的搜索，并提出应用m d 5 指纹的近似镜像文本检测算法对本 学习支持平台中索引前的文档进行消重处理的方法。经过本文的扩展，使 得学习支持平台的桌面搜索引擎能满足用户更多的需求。 关键词：l u c e n e 搜索引擎正向最大匹配算法近似镜像文本检测算法 全文检索 r e s e a r c hb a s e do np 2 p k m d e s k t o p s e a r c h i n g o p t i m i z a t i o n a b s t r a c t c o m p u t e rt e c h n o l o g yi n e r e a s i n g i yd e v e l o p e da n dt h ei n t e r a c t d i s t r i b u t e dr a p i d l y , e l e c n d m c a ld o c u m e n tq u a n t i t ye x p a n d e ds u d d e n l y p e o p l ep a ya t t e n t i o nt os e a r c hn e e d e d i n f o r m a t i o ns p e e d l y , r o u n d l y , t r u l yf r o ml a r g en m b e r so fi n f o r m a t i o n s ，a n dt h ea t t e n t i o ni s t h er e s e a r c h i n gp r o j e e ti nt h er e s e a r c h i n gf i e l d a tp r e s e n t , n e wa p p l i c a t i o no fi n f o r m a t i o n s e a r c hi st h ed e s k t o ps e a r c l l i n ge n g i n et h a tr e l e a s e di ns u c c e s s i o ni n t e r i o r l ya n do v e r s e a s 1 1 1 e d e s k t o ps e a r c h i n g s c h a r a c t e r i s t i ch a sn ou 辩f o rb r o w s e rw i t l ls e a r c h i n g a n de x p e n dt h e s e a r c h i n go b j e c tt ok i n d so fs t o r e dd o c u m e n t s i no u rp e r s o n a lh a r dd i s k 1 1 1 e d e s k t o p s e a r c h i n gp r o v i d e su s e r st os e a r c ht h e i rh a r dd i s kr a p i d l ya n dr e c e i v et h es e a r c h i n gr e s u l tl e s s as e c o n d d e s k t o ps e a r c h i n ge n g i n ei s t h et y p i c a lr e p r e s e n t a t i v eo f i n t e g r a t i n gi n f o r m a t i o n s e a r c h i n gt e c h n o l o g y f u l l - t e x ts e a r c h i n gt e c h n o l o g yi st h ec o r eo ft h ei n f o r m a t i o ns e a r c h i n g b a s e do np 2 pk n o w l e d g em a n a g e m e n ts t u d ys y s t e m ，w en e e dam o r ec o n s u m m a t ed e s k t o p s e a r c he n g i n e t 1 l i sd i s s e r t a t i o ns t u d i e da n da n a l y s e dt h ef o i l - t e x ts e a r c h i n gt e c h n o l o g y , t h e l u e e n e 剐l - t e x ts e a r c h i n ge n g i n e st o o lp a c k a g ea n dt h ea p p r o x i m a t em i r r o rt e x ta l g o r i t h m 1 1 圮p a p e re x p e n d e da n dc o m p l e t e dt a b l e t o ps e a r c he n g i n e i m p r o v e do nc h i n e s es y n c o p a t i n g w o r dt e c h n o l o g y , s u p p o r t e dt os e a r c hm o r ek i n d so fd o c u m e n t s ，a n db r o u g h tf o r w a r da m e t h o dt h a te l i m i n a t e st h er e p e a t e dd o c u m e n tw i t hm d 5f i n g e r p r i n ta p p r o x i m a t em i r r o rt e x t a l g o r i t h m b e f o r e b u i l d i n g i n d e x a f t e rt h ed i s s e r t a t i o n s e x p a n d e r , p 2 pk n o w l e d g e m a n a g e m e n ts t u d ys y s t e mc a ns a t i s f yo u ra s e r sm o r er e q u i r e m e n t s k e yw o r d s ：l u c e n es e a r c he n g i n e ；f o r w a r d sm a x i m u mm a t c ha l g o r i t h m ：a p p r o x i m a t e m i r r o rt e x ta l g o r i t h m ；f u l l - t e x ts e a r c h i n g 玎 广西大学学位论文原创性声明和使用授权说明 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的 成果和相关知识产权属广西大学所有，本人保证不以其它单位为第一署名单位 发表或使用本论文的研究内容。除已注明部分外，论文中不包含其他人已经发 表过的研究成果，也不包含本人为获得其它学位而使用过的内容。对本文的研 究工作提供过重要帮助的个人和集体，均己在论文中明确说明并致谢。 论文作者签名 学位论文使用授权说明 年月日 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 口即时发布口解密后发靠 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：导师签名年 月同 7 - - 西大掌硕士掌位论文 基于p 2 p k m 的桌面搜索优化的研究 第一章绪论 本文是基于广西教育厅科研项目：桂教科研 2 0 0 5 】4 7 号基于p 2 p k m 的学 习支持平台的研究提出的。本章对基于p 2 p k m 的学习支持平台作了全面的概述，从 而引出本文研究的主要内容。 1 1 研究基础 广西教育厅科研项目：桂教科研【2 0 0 5 】4 7 号基于p 2 p k m 的学习支持平台 的研究1 1 j ，该项目是一个用j a v a 开发的远程教育学习支持平台“基于p 2 p k m 的 学习支持平台”。系统的主要功能为：将p 2 p 技术与个人知识管理整合起来，搭建了一 个分布式学习支持平台，解决了传统的集中式远程教育学习支持平台的可维护性差、无 法支持群体学习和协同工作的缺陷；通过联系人管理和知识库管理的功能，能搜索特定 人群所掌握的资料，保证了搜索的针对性和精确度；扩展了一个功能更完善的桌面搜索 引擎，能够对指定的目录进行搜索，并在此基础之上保证了本地资料的安全；扩展了 x m p p 协议，使其能支持远端用户的知识库全文搜索服务。 p 2 p 技术能很好的适用于协同工作和内容管理，这正是知识管理两个主要的方面。 因为p 2 p 计算模型的目的就是为了共享和充分利用资源，从而很好的满足了知识管理 市场的要求1 2 , 3 1 。 基于p 2 p 技术的知识管理( p 2 p k m ) 可以看成是知识管理向个人角度的一个扩展， 个人同时可以在组群中共享资源。p 2 p k m 主要有3 个特点：1 p 2 p k m 、p k m 都是以 用户为中心；2 形成的组群的拓扑结构是可以动态变化的；3 在p 2 p k m 环境中，协同 工作不再受限于各类网络的边界，个人知识管理( p k m ) 可以看成是节点数只有1 的 p 2 p k m 。而且p 2 p 通讯应用对象不只是人，还可以在多终端( 比如p c 、手机、p d a ) 上，与多个人共同实现知识( 信息) 的捕捉、获取、分类、定位和分发。 p 2 p 技术与个人知识管理这样结合起来能充分利用的网络边缘的资源，让更多的个 人知识和经验得到整理和共享。个人面对的就是一个有n 个人维护的知识库，在提供 足够的搜索能力的支持下，可以让人们很迅速的找到自己关心的内容，同时还有利于互 联网上小团队的协同工作方式。 当i ；i 桌面搜索引擎的功能都仅仅针对本地的内容进行搜索，主要是被利用来查找自 己的资料。而该项目考虑将桌面搜索引擎与p 2 p 通讯平台整合起来，将这种搜索的能 力扩展到整个p 2 p 通讯平台所覆盖的网络，即通过p 2 p 通讯平台发送搜索的请求，而 各个节点接收到搜索请求之后，在各自的本地目录进行搜索，再将搜索结果通过p 2 p 通讯平台反馈给发出搜索请求的节点。 广西大掌碛士掌位论文a g - 3 pp 2 p k h 的桌面搜棠优化的研究 p 2 p 通讯平台都提供了功能完备的即时通信协议，用户通过即时通信协议束j l 十t l 联 系。为了通过p 2 p 通讯平台来处理搜索请求，需要在即时通信的内容中加入一些搜索 功能必须的元素，例如搜索请求中的搜索关键字、搜索反馈的结果列表等等。这些元素 本身并不被即时通信协议所支持，必须针对协议中的消息体进行扩展彳能满足要求。 该项目当前仅仅是初步建立了架构，实现了关键的一些功能，也验证了整个系统的 技术可行性。但距离一个真正成熟的软件，还有一定的距离。从完善系统的角度出发， 还有以下几个方面的工作需要进行： 搜索引擎的完善：当前本地搜索引擎模块搭建了主要的框架，可以对t x t 、h t m l 、 x m l 文本格式的文档进行全文搜索。而实际工作中，我们有相当数量的资料是更复杂一 些的格式，包括d o c 、p d f 、e x c e l 等。搜索引擎需要进一步扩展对这些格式的支持。 搜索结果的优化处理：当从多个联系人处搜索资料时，为了避免过多重复内容的搜 索结果影响到使用者的效率，可以对搜索结果进行一定程度的优化，合并那些明显重复 的结果。 软件的易用性：当前的系统实现的界面还相对比较简单，基本以完成功能为目标， 对易用性考虑不够。为了这个系统能更容易被人接受，在易用性上还有较多的工作要做。 要完成搜索引擎的完善和搜索结果的优化处理的改进工作，主要是在桌面搜索引擎 与p 2 p 通讯平台的整合这一模块进行。 1 2 研究内容 对于已经建立好的基于p 2 p k m 的学习支持平台的架构，我们进行了多项实验。其 中包括： 1 ) 进行了中文检索的实验，此平台的桌面搜索引擎在建立索引和查询中文关键字 时，对中文是进行单字切分的，我们查询的关键字是“上海”，但是“海上”的 相关信息也显示在了查询结果中。 2 ) 在测试数据中，加入除t x t 、x m l 和h t m l 格式的文档，如：口d f 、w o r d 、e x c e l ， 基于p 2 p k m 的学习支持平台对这些文档建立索引，并对p d f 、w o r d 、e x c e l 文档 的内容进行关键字查询，都没有相应的返回结果。 3 ) 在测试数据中，加入一个文档d o c i ，并对它进行了三份复制( d o c 2 、d o c 3 、 d o c 4 ) ，另外还放入了二份文档d o c 5 和d o c 6 ，d o c 5 的信息与d o c i 的信 息有4 0 的重复，d o c 6 与d o c l 的信息则有7 5 的重复。这六个文档在同一 知识包中，我们对知识包建立索引并查询关键字，返回结果分别为( d o c l 、 d o c 2 、d o c 3 、d o c 4 、d o c 5 、d o c 6 ) 。 以上实验表明，基于p 2 p k m 的学习支持平台还需要进一步的扩展和完善。上述实 验主要由基于p 2 p k m 的桌面搜索引擎来完成，平台中已把桌面搜索引擎与p 2 p 即时通 2 广西大掌硕士掌位论文 叁于p 2 p k m 的桌面搜囊优化的研究 讯进行了整合，进行搜索并在本地进行操作，本文提出对此平台的桌【旬搜索0 l 擎进 j ：扩 展和完善： 1 ) 对中文信息建立检索时，本文提出改进它的中文切分词技术，让用户能够更准 确地进行关键字的查询。 2 ) 基于p 2 p k m 的桌面搜索引擎已实现了对h f i i l l 、t ) ( t 、x m l 格式文档的全文搜索， 本文为了完善这方面的不足，提出实现对其它文本格式( d o c 、p d f 、e x c e l ) 文 档的全文检索，并分析检索数据库中各种格式文档的特点，应用一个通用的文 档模型，以方便搜索引擎的处理。 3 ) 为了避免过多重复内容的搜索结果影响到用户的使用效率，本文提出通过一种 近似镜像文本检测算法的方法对含有重复内容的文档进行消重处理，这样可以 对搜索速度进行一定程度的优化，合并那些明显重复的文档。 1 3 本文组织 第一章，绪论。主要介绍了本文的研究基础和研究内容。 第二章，相关技术研究现状。首先总结了桌面搜索引擎技术的研究现状，并对桌面 搜索引擎的构建基础i 眦e n e 搜索引擎开源包作了简要概述；接着总结了近似镜像网 页检测算法的背景和近似镜像网页检测算法的两种类型：基于全文分段签名的近似镜像 算法和基于关键词匹配的近似镜像算法。 第三章，基于p 2 p ：m 的桌面搜索引擎。首先总结了基于p 2 p k m 的桌面搜索引擎， 并对本文所涉及的索引模块和搜索模块进行了说明；对桌面搜索引擎的关键基础 l u c e n e 搜索引擎开源包进行了分析和研究。 第四章，对l u c e n e 搜索引擎的中文支持进行了分析，应用正向最大匹配算法对基 于p 2 p k m 学习支持平台的中文切分词技术进行改进。 第五章，实现对d o c 、p d f 、e x c e l 文档的全文检索关键在于要把它们转成本文设定 的通用的文档模型( t x t 文本格式文件) ，本章实现了这三种文档的文本转换。 第六章，近似镜像文本检测算法。在近似镜像网页算法的基础上，本文具体化了此 算法，并把本文具体化的算法定义为近似镜像文本检测算法。在应用算法之前，我们需 对文档信息进行预处理，让不同格式的文档都转换为“t x t ”文本格式的文档。在这些 “1 x t ”文本格式文档的基础上，应用我们所定义的m d 5 指纹的近似镜像文本检测算 法对基于p 2 p k i v l 的学习支持平台的重复文档信息进行消重处理，并用实验验证了它的 可行性。 第七章，总结和展望。对本文的具体工作做了全面的总结，并说明了下一步要继续 的研究。 基于p 2 p k m 的桌面搜索优化的研究 第二章相关技术研究现状 2 1 桌面搜索引擎研究现状 2 1 1 概述 桌面搜索引擎技术是从互联网搜索引擎发展而来。 在互联网搜索引擎发展如火如茶的同时，p c 机上的本地文件搜索技术则一直发展 缓慢，在主流操作系统w i n d o w s 系列上，微软一直以来都仅仅提供了以文件央遍历形 式方式来搜索本地的文件，由于实现的技术手段太过原始，搜索的效率非常低下。随着 p c 机用户个人电子文档的积累，单台p c 机上的文件数量已经开始上升到l o 万这个数 量级，操作系统自带的搜索功能已经无法满足要求了。在这样一个背景之下，开始有个 人和组织考虑将互联网搜索引擎发展多年累积下来的技术，应用到p c 机的本地文件搜 索，以提高本地文件搜索的效率1 4 6 】。 2 0 0 4 年，g o o g l e 作为互联网搜索业的巨头，推出其桌面搜索引擎的测试版，这标 志着桌面搜索引擎的产品开始进入可用状态。通过该搜索引擎，用户可以搜索自己p c 上面的各种格式的文档，包括o f f i c e 系列、o u t l o o k 邮件，i c q m s n 聊天记录等等。人 们发现，通过桌面搜索引擎，在短短数秒之内，即可从大量的硬盘文件中，找到自己关 心的文件。在一些技术密集型的行业，例如i t 、生物技术、高等教育等等，开始有越 来越多的人使用这款工具来帮助管理本地的电予文档，提高对已有资料的使用效率1 7 】。 桌面搜索引擎发展自互联网搜索引擎，其核心实现原理也基本类似，主要的差别在 于桌面搜索引擎搜索的对象主要是本地硬盘存储的文件【g l 。 一个桌面搜索引擎由本地文件采集模块、索引创建模块、搜索模块、用户接口组成： 本地文件采集模块：此模块的功能是在本地硬盘中漫游，发现和搜集本地文件。 它是一个或者多个后台运行的计算机进程，在p c 机启动之后不停地运行。它要尽可能 多、尽可能快地搜集各种格式的文件，还要定期更新已经搜集过的1 日文件，以避免无效 的文件。 索引创建模块：索引创建模块的功能是理解本地文件遍历模块所搜集的信息， 从中抽取出索引项，用于表示文档以及生成文档库的索引表。索引项有客观索引项和内 容索引项两种：客观项与文档的语意内容无关，如作者名、文档路径、更新时间、长度 等等；内容索引项是用来反映文档内容的，如关键词及其权重、短语、单字等等。内容 索引项可以分为单索引项和多索引项( 或称短语索引项) 两种。单索引项对于英文来讲 4 g - 西大掌司l 士掌位论文基于p 2 p k 、! 的橐面搜索优化的研究 是英语单词，比较容易提取，因为单词之b j 有天然的分隔符( 空格) ：时j il j 文等连续 书写的语言，必须进行词语的切分。在搜索引擎中，一般要给单索引项赋与一个权值， 以表示该索引项对文档的区分度，同时用来计算查询结果的相关度。使用的方法一般有 统计法、信息论法和概率法。短语索引项的提取方法有统计法、概率法和语寺学法。索 引表一般使用某种形式的倒排表( i n v e r s i o nl i s t ) ，即由索引项查找相应的文档。索引 表也可能要记录索引项在文档中出现的位置，以便搜索模块计算索引项之订j 的相邻或接 近关系( p r o x i m i t y ) 。 搜索模块：此模块的功能是根据用户的查询在索引库中快速检索出文档，进行 文档与查询的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机 制。 用户接口：用户接口的作用是输入用户查询、显示查询结果、提供用户相关性 反馈机制。主要的目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到 有效、及时的信息。用户接口的设计和实现使用人机交互的理论和方法，以充分适应人 类的思维习惯。用户输入接口可以分为简单接口和复杂接口两种。简单接口只提供用户 输入查询串的文本框；复杂接口可以让用户对查询进行限制，如逻辑运算( 与、或、非) 、 相近关系( 相邻、n e a r ) ，域名范围( 如e d u 、c o r n ) 、出现位置( 如标题、内容) 、信 息时间、长度等等。 市面上各个主流的桌面搜索引擎基本都是由上述四个模块构成，四个模块协同工作 完成对p c 机本地文件的搜索工作1 9 1 。其中，前两个模块负责根据文件内容生成索引库， 后面两个模块则让用户完成对索引库的搜索。实际搜索的时候，搜索模块仅仅对索引库 进行搜索，因此，索引库创建的结构好坏，直接决定了搜索的质量。 2 1 2l u c e n e 搜索引擎 l u c e n e 搜索引擎工具包是基于p 2 p k m 的桌面搜索引擎建立的基础，l u c e n e 是一个全 文检索引擎工具包，可以跨平台使用，通过调用其接口引入到工程中。通过使用l u c e n e ， 可以为一个企业或者个人的应用增加信息检索功能，包括文档搜索、网页搜索、站点搜 索、邮件搜索、出版物搜索等，它可以作为桌面搜索引擎的开发基础i l o j 。 基于l u c e n e 的全文检索实现较为简单，可扩展性很强，很容易被引用。由于l u c e n e 数据库是完全开放源代码的，这有3 个好处：可以掌握先进的数据库技术，打破国外 公司对我国数据库产品的垄断控制，促进我国情报检索收集工作的发展。可以确保代 码的安全性，防止国外商业软件由于源代码无法检查，造成黑客程序侵入国家重要数据 库，从而保障国家信息安全。我国研究支持中文的全文检索，可以很好地发挥对中文 理解的独到之处，开发出更好的支持中文的全文检索程序l t m 2 1 。 广西大掌硕士掌位论文 , l k - - 于f 2 1 k 的橐面搜索优化的研究 l u c e n e 不是一个完整的全文检索系统，而是一个用j a v a1 ；的令义搜索引譬工具包， 它提供了灵活的a p i 函数和可以定制的数据存储结构，可以方便地嵌入到各种应用中实 现具体的全文检索系统。l u c e n e 本身只是一个组件，而非完整的系统，所以在集成到应 用程序中时，须根据应用程序的需要设计索引数据结构，调用l u c e n e 提供的各种接口 实现全文检索功能。 已经有很多j a v a 项目都使用了l u c e n e 作为其后台的全文索引引擎，比较著名的有： j l i v e ：w e b 论坛系统； e y e b r o w s ：邮件列表h t m l 归档浏览查询系统，本文的主要参考文献【8 1 “t h e l u c e n es e a r c he n g i n e p o w e r f u l ，f l e x i b l e ，a n df l e e ”，作者就是e y e b r o w s 系统的主 要开发者之一，而e y e b r o w s 已经成为目前a p a c h e 项目的主要邮件列表归档 系统。 c o c o o n ：基于x m l 的w e b 发布框架，全文检索部分使用了l u c e n e 。 e c l i p s e ：基于j a v a 的开放式开发平台【1 3 】，帮助部分的全文索引使用了l u c e n e 。 对于中文用户来说，最关心的问题是其是否支持中文的全文检索。但通过后面对于 l u c e n e 的结构的介绍，将会了解到由于l u e e n e 良好架构设计，对中文的支持只需对其 语言词法分析接口进行扩展就能实现对中文检索的支持。 l u c e n e 的确是一个面对对象设计的典范： 所有的问题都通过一个额外抽象层来方便以后的扩展和重用：你可以通过重新 实现来达到自己的目的，而对其他模块而不需要； 简单的应用入口s e a r c h e r 、i n d e x e r ，并调用底层一系列组件协同的完成搜索任 务； 所有的对象的任务都非常专一：比如搜索过程：q u e r y p a r s e r 分析将查询语句转 换成一系列的精确查询的组合( q u e r y ) ，通过底层的索引读取结构i n d e x r e a d e r 进 行索引的读取，并用相应的打分器给搜索结果进行打分，排序等。所有的功能模 块原子化程度非常高，因此可以通过重新实现而不需要修改其他模块。 除了灵活的应用接口设计，l u e e n e 还提供了一些适合大多数应用的语言分析器 实现( s i m p l e a n a l y s e r , s t a n d a r d a n a l y s e r ) ，这也是新用户能够很快上手的重要原 因之一。 这些优点都是非常值得在以后的开发中学习借鉴的。作为一个通用工具包，l u c e n e 的确给予了需要将全文检索功能嵌入到应用中的开发者很多的便利。 此外，通过对l u c e n e 的学习和使用，本文也更深刻地理解了为什么很多数据库优 化设计中的要求，比如： 尽可能对字段进行索引来提高查询速度，但过多的索引会对数据库表的更新操 作变慢，而对结果过多的排序条件，实际上往往也是性能的杀手之一。 6 广西大掌硕士掌位论文基于p 2 p k 、i 的桌面搜索优化的研究 很多商业数据库对大批量的数据插入操作会提供些优化参数，这个作用和索 引器的m e r g ef a c t o r 的作用是类似的。 1 4 原则：查的结果多并不等于质量好，尤其对于返回结果集很大，如何优化 这头几十条结果的质量往往才是最重要的。 尽可能让应用从数据库中获得比较小的结果集，因为即使对于大型数据库，对 结果集的随机访问也是一个非常消耗资源的操作。 2 2 近似镜像网页检测算法的研究现状 随着互联网的不断发展，人们越来越多地在互联网上发布和获取信息。w e b 已经成 为信息制造、发布、加工和处理的主要平台。w e b 上存在网页内容转载的情况，我们把 转载的网页称为原始网页的镜像，如果是热门话题、重大新闻经典文章，则转载的频率 会很高。因此，w e b 上存在大量的镜像网页。并且整个网页集会经常被各个服务器备份， 以提供更快的本地访剐1 。大量的镜像网页并不是对原始网页的简单拷贝，而是将要转 载的内容放在新的模板中再提供服务。称这样的网页为近似镜像网页。相同的文档可能 在网上存在不同格式的版本。这样大量的重复网页信息的存在，必然会造成索引的负担， 影响检索服务的效果。 近似镜像网页检测算法，它就是在给定大数据量的随机文件( 即网页) 的数据集， 从中发现近似镜像网页的算法。在搜索引擎中，如果我们能将搜集到的网页中的近似镜 像网页去掉，而后再建索引提供服务，这样用户查询时就不会出现大量内容重复的网页。 这个去除镜像网页的过程被称为消重l ”j 。 国际上对近似镜像网页检测算法的研究最初主要是针对大型文件系统的，后来又被 拓展应用于数字化图书馆项目和搜索引擎系统【1 6 博1 。美国a r i z o n a 大学的研究人员采用 计算文档重叠程度的方法来发现一个大型文件系统中的相似文件。斯坦福大学的研究人 员开发了s c a m 原型系统，用于发现近似文档，后来在对其近似镜像检测算法作了改 进之后被应用于g o o g l e 系统。几乎所有的上述近似镜像检测技术都基于这样一个基本思 想：为每个文档计算出一组指纹( f i n g e r p r i n t ) ，若两个文档拥有一定数量的相同指纹， 则认为这两个文档的内容重叠性较高，也即二者是近似镜像的 1 9 1 。接下来，介绍现有 的两类方法1 2 0 , 2 2 , 2 3 1 。 2 2 1 基于全文分段签名的近似镜像网页检测算法 基于分段签名的近似镜像算法，比如文献【“1 采用了一种对全文分段签名的算法。这 种算法把一篇网页按一定的原则分成n 段( 如每n 行作为一段) ，然后对每一段进行签名( 即 计算指纹) ，于是每一篇文档就可以用n 个签名后的指纹来表示。对于两篇文档，当它们 7 广西大掌硕士掌位论文- - 1 k - 予p 2 1 1 k 的桌面搜索优化的研究 的n 个签名中有m 个相同时( m 是系统定义的闽值) ，则认为它们足互为近似镜像的。该算 法通过对三元组 b 表示“若a 成立 则b 成立”1 3 i 】。 2 3 本章小结 本章对相关的研究技术桌面搜索引擎和近似镜像网页检测算法做了全面的概 述。l u c e n e 搜索引擎工具包可以用来做桌面搜索引擎的进一步开发，对近似镜像网页检 测算法的两类：基于全文分段签名的近似镜像算法和基于关键词匹配的近似镜像算法作 了介绍和简要分析，为后续工作的开展奠定了基础；本文所定义的近似镜像文本检测算 法是对近似镜像网页检测算法的具体化，本文将在第四章做详细说明。 9 广西大掌硕士掌位论文 基于p 2 p k m 的嘉面搜索优化的研究 3 1 引言 第三章基于p 2 p k m 的桌面搜索引擎 基于p 2 p 技术的知识管理( 简称p 2 p k m ) 的学习支持平台，它已构建了一个分布 式知识库，并实现在这个分布式知识库中进行全文检索的能力。具体特性如下所述1 3 2 i ： 整个平台由多个节点组成，每个节点互相独立，互不影响； 每个节点都有一个本地的知识库，节点与节点之间通过p 2 p 协议互相通信； 每个节点由各用户自己维护，分别按照其知识体系结构和工作习惯来组织本地 知识库： 各用户可以把整个系统当作一个分布式的知识库，通过p 2 p 的搜索技术来查找 所需要的资料。 基于p 2 p k m 的学习支持平台系统( 图3 - l 为其总体架构图) ，是一种基于p e e r - t o p e e r 技术的知识管理的远程教育平台，构建了一个分布式资源库，实现了在这个分布式资源 库中进行全文检索的能力。作为基于p e e r - t o p e e r 知识管理的远程教育平台，整个系统 可以部署在互联网、广域网、局域网内。从物理部署上，可以分为客户端和服务器端两 部分。 图3 - l 总体架构图 f i g 3 1s y s t e ma r c h i t e c t u r ed i a g r a m 客户端：直接面向最终的用户，部署在最终用户的个人计算机上。让最终用户可以 进行本地的知识管理、联系人管理、知识库搜索等操作。( 见图3 2 所示) x m p p 服务器端：作为p e e r - t o p e e r 通讯的中心服务器，负责完成用户的注册、消 息的路由等功能。( 见图3 - 3 所示) 1 0 基于p 2 p k m 的桌面搜索优化的研究 一蓼卜q 坦 鱼吲黑 图3 - 2 客户端逻辑架构图 f i g 3 2l o g i ca r c h i t e c t u r ed i a g r a mo f c l i e n t 擞务豁端 图3 3 服务器端逻辑架构图 f i g 3 - 3l o g i ca r c h i t e c t u r ed i a g r a mo f s e r v e r 在此平台中，用户先注册，再通过中心服务器成为一个或者多个联系人组中的一员， 用户可添加文件到知识包中，当用户需要进行信息检索时，除了对本地知识库的搜索之 外，还能够对远端联系人组的联系人共享的知识包进行搜索，并接收远端搜索的反馈结 果( 2 , 3 1 。 从客户端看，搜索引擎应用于图4 - 2 中的知识库搜索模块中，为了支持多种不同的 搜索引擎，在设计搜索模块的时候，遵循接口和实现分离的原则，根据搜索模块的主要 广西大掌硕士掌位论文基于p 2 p k m 的集面搜索优化的研究 功能，首先定义了索引创建和搜索眄个接li 。创建l u c e n e 的索引相当简单，只需指出 索引的目录和索引文件存放位置即町。基于l u c e n e 对索引生成器接口的实现，在l u c e n e 核心的基础之上对其进行扩展，使之可以针对不同的本地目录创建索引，从而满足平台 对搜索这块的要求【3 3 】。 3 2 基于p 2 p k m 的桌面搜索引擎 3 2 1 本地知识库的组织结构 3 2 1 1 知识库的两级分类结构设计 基于p 2 p k m 的学习支持平台系统提供了一个组织上比较灵活的知识库结构，方便 用户，根据需要对知识库进行管理。为此，在这个平台里实现知识包和知识库两级的分 类结构。 知识包：例如可以按照资料的专业领域进行分类的文件目录。比如说j a v a 语言的 资料、c 语言资料、l u c e n e 的资料都可以分别划分成一个个知识包，分别对应到文件系 统的一个目录，在这些目录下，存储了实际的文档。 知识库：例如可以按照对这些资料的使用来进行分类，这个分类是在知识包的基础 上，根据资料使用上的需要，把多个知识包组织到一起，则成为了一个知识库。例如为 某个毕业设计的课题定义一个知识库，其中包含了j a 、，a 语言、l u c e n e 的知识包。表3 1 和表3 2 说明了知识包和知识库是如何定义的。 广西大掌硕士掌位论支 基于p 2 p k m 的橐面搜索优化的研究 表3 - lp a c k a g e s 表结构 t a b l e 3 1s t r u c t u r eo f p a c k a g e st a b l e 字段名类型主键允许为空 说明 p a c k a g e - i dv a c h a r ( 3 2 ) 是 否 知识包的i d 。在系统中 唯一标识一个知识包 p a c k a g e _ n a m ev a c h a r ( 2 5 5 ) 否 知识包名称。用户根据 自己的需要给特定的知识包 命名。 u r l v a c h a r ( 2 5 5 ) 是知识包的路径：如果是本 地的知识包，则记录在本地 的路径。如果是远端知识包， 则只记录一个名字，这个字 段就为空 o w n e r v a c h a r ( 1 2 8 ) 否如果是本地的知识包， 这个字段记录“l o c a l 如果是某个远端联系人 的所拥有的知识包，则记录 该联系人的唯一名称，例如 t e r r y ! p 2 p k m 表3 一l 包含了知识包表结构的定义，系统中的所有知识包的信息都记录在这个表中。 表3 - 2l i b r a r y s 表结构 t 曲l e 3 2s t r u c t u r eo f l i b r a r i e st a b l e 字段名 类型 主键允许为空说明 l i b r a r y i d v a e h a t ( 3 2 ) 是否 知识库的i d 在系统中 唯一标识一个知识库 l i b r a r y v a e h a t ( 2 5 5 ) 否 知识库名称用户根据 n a m 匣 自己的需要给特定的知识库 命名。 表3 - 2 包含了知识库的定义，系统中的所有知识库的信息都记录在这个表中。 3 2 1 2 知识库两级分类之间映射关系的存储 基于p 2 p k m 的学习支持平台中知识库的存储除了包括文档资料的存储之外，还包 括知识库分类结构映射关系的存储。 表3 3 包含了知识库和知识包关联的定义，系统中的所有知识库和知识包的关联的 广西大掌硕士掌位论文基于p 2 p k m 的橐面搜索优化的研究 信息都记录在这个表中。 表3 - 3p a c k a g e _ l i b r a r y 表结构 t a b l e 3 3s t r u c t u r eo f p a e k a g e _ l i b r a r yt a b l e 字段名类型主键允许为空说明 i d v a c h a r ( 3 2 ) 是否 l i b r a r yi d v a c h a r ( 3 2 ) 否 知识库的i d 在系统 中唯一标识一个知识库。 p a c k a g e - i dv a c h a r ( 3 2 ) 否 知识包的i d 在系统 中唯一标识一个知识库。 一个知识库可以包含多个知识包，而一个知识包也可以从属于多个知识库。通过表 3 3 反映了知识包和知识库之白j 多对多的映射关系。 此系统按照知识包来分别创建独立的索引库，从物理上保证了不同知识包的索引库 都是完全独立的，成为整个系统安全性的基础，任何对知识库的搜索范围都可以被限定 在指定的知识包之内，只有那些被共享出来的知识包才能被其他联系人搜索。通过在不 同目录下建立索引库，并在搜索时指定搜索所使用的索引库，系统可以做到指定目录进 行搜索，以满足远程教育平台的使用需要。 3 2 2 索引模块结构 在基于p 2 p k m 的学习支持平台的知识库组织结构中，包含了两级的分类结构，第 一级是知识包，对应到实际的文件系统目录：第二级是知识库，对应到多个知识包。 知识包是最小粒度的分类，为了做到尽可能小的粒度的搜索，索引的结构也必须跟 知识包的结构进行对应。由于l u c e n e 是每一个索引库都独立使用一个目录，因此，对 应到每个知识包，设计上都会有一个l u c e n e 的索引库目录与之对应，对应的规则就是 以p a c k a g en a m e + “i d x ”作为索引库目录名。 整个系统各个知识包的索引目录都会放在一个根目录下，表3 - 4 举例说明了索引目 录的结构： 1 4 广西大掌硕士掌位论支基于p 2 p k m 的桌面搜索优化的研究 表3 - 4 索引目录结构表 t a b l e 3 4s t r u c t u r eo f i n