（计算机应用技术专业论文）面向领域的关系数据库全文检索系统的优化设计.pdf

枞靴学位敝 摘要 摘要 在互联网飞速发展的背景下，数据库应用体现出了不同以往的新特点，新的 需求应运而生。海量数据及数据孤岛的产生，严重阻碍了科学数据的有效共享。 从这一背景出发，d a r t g r i d 在传统的数据集成解决方案基础上引入了语义技 术和网格技术，提出了基于语义的数据库网格的概念，作为异质异构数据库集成 的一种解决方案。作为d a r t g r i d 内核的一个主要应用平台，d a r t s e a r c h 全文搜索 系统已经伴随着d a r t g r i d 发展到了第三个版本，本文主要介绍了d a r t s e a r c h v 3 系 统的设计和实现。 首先，本文简要的介绍了d a r t g r i d 平台和搜索引擎技术的发展现状，然后介 绍l u c e n e 的实现机制。并通过分析d a r t s e a r c h v 2 版本所存在的问题，提出了 d a r t s e a r c h v 3 所要解决的问题和系统的架构设计。 本文的重点是对d a r t s e a r c h v 3 系统中中文分词方法、索引机制、r a n k 机制这 三个核心模块所采用的技术、架构、算法思想、核心模块、优化结果等多个方面 进行了分析。此外，本文还介绍了d a r t s e a r c h v 3 系统所开发的v m l 语义图工具包 和相关图文聚合工具包。总之，探讨的重点始终围绕d a r t s e a r c h v 3 面向数据库的 全文搜索系统的功能性、实用性、易用性进行。 最后，本文还扼要的分析了d a r t s e a r c h v 3 系统将来可能面临的问题，提出了 d a r t s e a r c h 系统的发展方向。 关键词：d a r t g r i d ，中文分词，索引机制，r a n k 机制，v m l 矢量图，l u e e n e 姒学硕士学位论文 a b s t r a c t a b s t r a c t a st h ei n t e m e ti n d u s t r yg r o w sf a s t e ra n df a s t e r , v a r i o u sk i n d so fn e w r e q u i r e m e n t sh a v ea p p e a r e di nt h ea p p l i c a t i o n so fd a t a b a s es y s t e m s p a r t i c u l a r l y , t h e a p p e a r a n c eo fl a r g e s c a l ed a t a b a s e sa n dd a t ai s l a n d sm a k et h es h a r i n ga n di n t e g r a t i n g o fd a t a b a s e s ，e s p e c i a l l ys c i e n t i f i cd a t a b a s e s ，b e c o m em o r ed i 伍c u l t t os o l v et h i sp r o b l e m d a r t g r i dw a sd e v e l o p e db a s e do nt h et r a d i t i o n a ls o l u t i o n o fd a t a b a s ei n t e g r a t i o n i tt o o k 觚1a d v a n t a g eo ft h ec o n e 印to f “d a t a b a s eg r i da n d s e m a n t i c 溉6 ”a n db e c a m eas u c c e s f u ls o l u t i o no fd a t ai n t e g r a t i o nb e t w e e np h y s i c a l l y o rl o g i c a l l yd i f f e r e n td a t a b a s e s d a r t s e a r c hf u l l t e x ts e a r c he n g i n es y s t e mw a sg e n e r a t e df r o mt h ed a r t g r i dc o r e p l a t f o r m n o wd a r t s e a r c hh a sd e v e l o p e dt oi t st h i 。r dv e r s i o n , a n dt h i st h e s i si sa b o u t t h ed e s i g n o p t i m i z a t i o na n di m p l e m e n t a t i o no fd a r t s e a r c h v 3s y s t e m a tf i r s t w eb r i e f l yi n t r o d u c e dt h el a t e s td e v e l o p m e n ti nt h ea r e ao fl a r g e - s c a l e s c i e n t i f i cd a t as h a r i n ga n ds e a r c he n g i n et e c h n o l o g y , a n dt h e ni n t r o d u c e ds o m eb a s i c k n o w l e d g eo fl u c e n e t h e nw e d 1 i k et o a n a l y s e t h ee x i s t i n gp r o b l e m so f d a r t s e a r c h v 2 ，a n db e g i nt op u tf o r w a r dt h ek e yp r o b l e m st h a td a r t s e a r c h v 3h a v et o s o l v ea n dm es t r u c t u r ea n ds y s t e md e s i g no fd a r t s e a r c h v 3 t h ef o c u so ft h i st h e s i si sa b o u tt h ec 1 1 i n e s ew o r ds e g m e n t a t i o na l g o r i t h r n ，t h e i n d e xm e c h a n i s m ，t h er a n km e c h a n i s m ，w h i c ha r et h et h r e ec o r em o d u l e so f d a r t s e a r c h v 3s y s t e m ，a n ds p e c i a l l yi n t r o d u c e dt h et e c h n o l o g y , a r c h i t e c t u r e ，a l g o r i t h m ， t h ec o r ei m p l e m e n t a t i o n ，a n dt h er e s u l t so ft h e s em o d u l e s i na d d i t i o n ，w ea l s o i n t r o d u c e dav m lb a s e ds e m a n t i ct o o lk i ta n dar e a l a t e dp i c t u r es e a r c h i n gt 0 0 1 w h l e t a l k i n ga b o u tt h ed e s i g na n do p t i m i z a t i o n ，w ea l w a y sf o c u so ns y s t e mf u n c t i o n a l i t y , p r a c t i c a l i t y , e a s et ou s eo ft h ef u l l t e x td a t a b a s e - o r i e n t e ds e a r c he n g i n es y s t e m i nt h e1 a s tp a r to ft h i st h e s i s w eb r i e f l ya n a l y s e ds o m ep r o b l e m st h a t d a r t s e a r d l v 3s y s t e ms h o u l df a c e i nt h ef u t u r e a n dp o i n t e do u tt h ed e v e l o p m e n t d i r e c t i o n k e y w o r d s ：d a r t g r i d ，c h i n e s es e g m e n t a t i o n ，i n d e x ，r a n k ，v m ls e m a n t i c g r a p h , l u e e n e n 掀黜学位做图目录 图目录 图1 1d a r t g r i d 系统架构图2 图2 1 系统模块图1 6 图2 2 基于语义的数据库全文检索系统架构图1 8 图3 1 常用中文分词算法2 0 图3 2d a r t s e a r h v 2 分词结果2 4 图3 3 百度上搜索“将军”2 5 图3 4 中医药领域词库2 8 图3 5 基于动态规划的最大匹配分词算法3 1 图3 6 基于互信息的新词识别算法3 2 图3 7 分词效果3 3 图3 8d a r t s e a r c h v 3 词频统计结果3 4 图3 9d a r t s e a r c h v 3 新词识别结果3 4 图3 1 0d a r t s e a r c h v 2 输入“李时珍 的搜索结果3 5 图3 1 1d a r t s e a r c h v 3 输入“李时珍的搜索结果- 3 5 图4 1l u c e n e 索引示意图3 7 图4 2 互关联后继树示意图4 1 图4 3i n d e x 算法实现类图4 4 图5 1d a r t s e a r c h v 3r a n k 算法流程5 0 图6 1 基于v m l 的语义展示图6 1 图6 2 图片聚合工具包类图6 3 图6 3 图片聚合6 4 v 掀靴学位做 表目录 表目录 表1 1l u e e n e 和数据库的比较7 表1 2l u c u c e 全文搜索和数据库的模糊查询9 表1 3自动切分和基于词表的分词方法比较1 0 表3 1t c m l s 已经收录的中医药领域词条2 7 表4 1 索引块文件结构3 8 表4 2 域信息文件结构3 8 表4 3 索引项信息文件结构。3 9 表4 4 频率文件的结构一3 9 表4 5 位置文件的结构3 9 表5 1l u c e n e 评分公式中的因子5 1 v i 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝婆盘茔或其他教育机构的学位或证书而使用过的材料。与我 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 学位敝储繇多隧欲签字魄彬年多月夕日 学位论文版权使用授权书 本学位论文作者完全了解澎姿盘堂 有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权澎姿盘堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位敝储虢糖歙 签字眺纱诉多月夕日 翮弥p 暑f 爸 签字日期洲年( 月q 日 浙江大学硕士学位论文第1 章绪论 第1 章绪论 1 1d a r t g r i d 与d a r t s e a r c h 1 1 1d a r t g r i d 简介 d a r t g r i d 是浙江大学开发的利用语义技术和网格技术来共享异质异构数据库 的解决方案。它于2 0 0 3 年底完成了第一版，现在已经发展到了第三个版本。 d a r t g r i d 的目标是在特定的虚拟组织( v o ) 1 里集成数据。数据的来源可来自 于不同的逻辑结构与物理属性。但d a r t g r i d 的用户却可以在不知道这些特定数据 源的详细的情况下查询数据。它们只需要知道被虚拟组织( v o ) 管理员或领域专 家定义的本体模式。具体地说，在我们的特定的环境里，虚拟组织指的是关系数 据库存放的一个逻辑概念。而我们查询的数据源则是数据库。 d a r t g r i d 在语义查询时包含了以下的信息 2 ： 1 领域专家定义的用来描述特定领域的标准词汇的本体模式 2 数据源的注册信息，它描述了这些领域的成员提供的数据来源信息。 3 本体的语义注册信息，它用来描述数据源和本体模式的对应关系。 d a r t g r i d 会在初始化时读入这些信息，当我们运行一个查询时，d a r t g r i d 会做一下事情 3 ： 1 解析语义查询请求。 2 利用本体模式和语义注册信息将查询请求转化成一个s q l 的查询计划。 3 获取数据来源的信息并将查询计划分配到不同的数据源上。 4 汇集查询结果，形成一个新的语义查询结果。 5 将查询结果包装成用户定义的形式。 以下的d a r t g r i d 的整体架构图，在整个架构图里描述了d a r t g r i d 的组成部件 及查询的整个过程： 瓤煳舯黼沦文 第l 章绪论 图1 1d ar t g ri d 系统架构图 1 1 2d a r t s e a r c h 简介 d a r t s e a r c h 4 ，又称为基于语义的全文搜索系统，是一个基于d a r t g r jd 基础 框架丌发的而阳i 各义网络的集成异质异构火系数据库的全文搜索引擎系统。 d a r t s e a r c h 足个通用甲台，可以应用j 二任何领域，本文以在中医药领域中 的应用为例。d a r t s e a r c h 是基于d a r t g r i d 内核的全文搜索引擎，它与通用搜索引 擎具有显著的区别 5 ： 首先，d a r t s e a r c h 是而向领域的，它是适用t i 任何领域的通用搜索引擎。 其次，1 ) a r t s e a r c h 的数据是米源于关系数据库而不是通常的网页。系统从数 浙江大学硕士学位论文 第l 章绪论 据库中读取记录建立索引，同时根据内核的语义注册信息对每一个索引项进行语 义标注。 此外，d a r t s e a r c h 本身并不关注海量信息的处理，因为它的数据来源毕竟有 限。d a r t s e a r c h 真正关心的是如何提供高质量的搜索服务，如何创造颇具领域特 点的搜索方式，让领域内的用户能迅速有效地查找到有用信息。 d a r t s e a r c h 是一个用s p r i n g 框架开发的通用的b s 结构查询工具，支持全文搜 索、专题搜索、标准次关联搜索等多种搜索方法，且通过x m l 文件对系统进行配 制，为用户在最短时间内部署平台提供了捷径。 d a r t s e a r c h 在本文之前已经开发了两个版本。 1 2 搜索引擎技术简介 迅速膨胀的超大规模的科学数据为信息的整理和检索带大了越来越到的技 术压力，就是在这种情况下搜索引擎技术应运而生。众所周知，搜索技术现在已 经成长为互联网应用中最热门的技术。 搜索引擎的大量使用是近几年的事，是随着互联网的普及逐渐发展起来的一 种服务方式。搜索引擎这个名称是由其英文名s e a r c he n g i n e 直译而来的，实际上 是w e b 上的一种超文本信息查询工具。早期的搜索引擎是将互联网中资源服务器 的地址收集起来，按其提供资源的类型不同而分成不同的大类，大类下再细分小 类。人们按照目录一层层进入，最后找到自己想要的信息。这种方式只适用于网络 信息并不多的时候。随着y a h o o 的出现，搜索引擎的发展也进入了黄金时代。搜 索引擎从不同的角度可以分为不同的种类。如按搜索方式可分为范畴层次式“分 类目录搜索引擎 ( 1 i s t - b a s e ds e a r c h e n s n e ) 和利用关键词查询的“词语搜索引擎 ( w o r d s - b a s e ds e a r c he n g i n e ) 两大类：如按覆盖范围可以分为通用搜索引擎和专业 搜索引擎：按功能可分为常规搜索引擎和多元搜索引擎。我们这里将搜索引擎按 工作原理分为基于蜘蛛程序的机器人搜索引擎、目录式搜索引擎以及元搜索引擎 三类。 3 浙江大学硕十学位论文 第l 章绪论 1 基于蜘蛛程序的机器人搜索引擎 这种搜索引擎由一个称为蜘蛛( s p i d e r ) 的机器人程序自动访问w e b 站点，提 取点上的网页，并根据网页中的链接，进一步提取其它网页。索引器为搜索到的 信息建立索引，由检索器根据用户的查询输入检索索引库，并将查询结果返回给 用户。这种搜索引擎的优点是信息量大，更新及时，毋需人工干预。缺点是返回 信息过多，有很多无关信息，用户必须自己从中筛选。比较典型的有g o o g l e 、y a h o o 、 a s k 等，国内的有b a i d u 、中搜等。 2 引擎目录式搜索引擎 这种搜索引擎是以人工或半自动方式搜集信息，由编辑人员查看信息之后。人 工形成摘要，并将信息置于事先确定的分类框架中。信息大多面向网站，提供目 录浏览服务和直接检索服务。该类搜索引擎因为加入了人工智能，所以信息准确， 导航质量高。这类搜索引擎的缺点是需要人工介入，维护量大，信息量少，信息更 新不及时。比较典型的有y a h o o 、o p e n d i r e c t o r y , 国内的有s i n a 、s o h u 。 3 元搜索引擎 元搜索引擎自身没有建立任何数据库，而是将用户的提问同时传送至多个包 含数据库的搜索引擎，然后对各搜索引擎返回的结果进行去重、排序等整理，最终 响应给检索用户。目前，没有一个搜索引擎能涵盖整个i n t e m e t , 各搜索引擎的收 录范围又有所差异，因此这类元搜索工具受到了一定程度的关注，特别适合于对 查全率要求高的查询。但是，不同的搜索引擎之间，建立索引数据库和执行提问 检索的具体方法或规则并不相同，因此，大大影响了元搜索工具的检索效果。 搜索引擎的原理，可以看做三步：从互联网上抓取网页一建立索引数据库一 在索引数据库中搜索排序。从互联网上抓取网页利用能够从互联网上自动收 集网页的s p i d e r 系统程序，自动访问互联网，并沿着任何网页中的所有u r l 爬 到其它网页，重复这过程，并把爬过的所有网页收集回来。建立索引数据库一 由分析索引系统程序对收集回来的网页进行分析，提取相关网页信息( 包括网页 所在u r l 、编码类型、页面内容包含的关键词、关键词位置、生成时间、大小、 4 浙江大学硕士学位论文 第l 章绪论 与其它网页的链接关系等) ，根据一定的相关度算法进行大量复杂计算，得到每 一个网页针对页面内容中及超链中每一个关键词的相关度( 或重要性) ，然后用 这些相关信息建立网页索引数据库。在索引数据库中搜索排序一当用户输入关 键词搜索后，由搜索系统程序从网页索引数据库中找到符合该关键词的所有相关 网页。因为所有相关网页针对该关键词的相关度早已算好，所以只需按照现成的 相关度数值排序，相关度越高，排名越靠前。最后，由页面生成系统将搜索结果 的链接地址和页面内容摘要等内容组织起来返回给用户。 搜索技术是当今世界的热点技术，全世界的很多大公司在这个领域展开了激 烈的竞争。它的难点有以下几个： l 、需要对海量数据有极快的查询速度。对于海量的互联网数据来说，速度就是 生命。g o o g l e 可以在几百毫秒之内将所有查询的数据返回，它所需要的技术不仅 仅是高效的搜索算法，它需要大量并行技术，需要使操作系统适应搜索的要求， 甚至需要调整磁盘阵列等等。 2 、数据来源的获取。我们会看到从g o o g l e 与b a i d u 上搜出来的结果经常会是完全 不一样的，这说明了它们获取数据的来源是完全不同的。 3 、搜索结果的排序。搜索结果的排序是极其重要的，一般用户最关心的都是前 几页的数据，g o o g l e 发明的p a g er a n k 使它立刻变成了全世界最流行的搜索引擎。 然而我们要设计的系统需求与g o o g l e 或b a i d u 还是有很大的不同的，主要表 现在以下几点： l 、我们查询的数据量虽然很大，但比起g o o g l e 或b a i d u 来，仍然是有限的。整个 中医药数据库的数据加起来有2 0 多g ，称得上是海量的数据库，但是比起g o o g l e 来还是差得太多了。这种数据量的情况下，我们不需要考虑太多操作系统或并行 计算，只要使用在单机上优秀的全文检索算法就足够了，全文检索算法。 2 、数据来源的抽象才是本系统设计的难点。系统的目标是将异质异构的数据厍 用语义来集成，这就意味着数据的结构是完全没有规律的，字段的名称、大小、 类型都是完全不同的。而所有全文检索内核所要求的数据来源恰恰都是结构化的 5 浙江大学硕士学位论文第l 章绪论 数据，事实上已有的全文检索系统也都是基于结构化的数据来做的。例如 t h e s e r v e r s i d e 上的全文检索是针对数据库里的文章、新闻或b l o g 等文本内容， 这些数据都有统一的结构，它们有标题、作者、内容摘要、相应链接，全文检索 引擎建索引时会把这些看成一些f i d d 。g o o g l e 与b a i d u 的查询内容事实上也是结 构化的，无外乎网页标题、内容摘要、相应链接。而我们面对的数据库来源则完 全没有这样清楚的界定，因此我们需要统一的机制将非结构化的数据转换成可被 全文检索引擎接受的结构化的数据。 3 、中文分词是系统的另一个难点。全文检索的关键是利用关键词来建立索引。 而这些关键词的来源正是通过中文分词得到。目前开源最多的最大匹配法在效率 和精确性上相差比较大，而且由于与词库的紧绑定使我们很难找到一个可用的分 词库。 4 、我们的搜索引擎并不是面向互联网的通用搜索工具，而主要面向某个特定的 领域的全文检索工具。 5 、我们的搜索不是面向网页的搜索，而是面向关系型数据库的 1 3l u c e n e 开源包介绍 d a r t s e a r c h 数据库全文检索系统中使用了全文检索技术、中文分词技术，并 使用了著名的全文检索开源项目l u e e n e ，因此下面我们将对全文检索技术与 l u c e n e 进行了简要的介绍。 1 3 1l u c e n e 的基本情况 l u c e n e 是一个用j a v a 写的全文索引引擎工具包，它可以方便的嵌入到各种应 用中实现针对应用的全文索引检索功能。l u c e n e 不是一个完整的全文索引应用。 l u c e n e 的作者：l u c e n e 的贡献者d o u gc u t t i n g 是一位资深全文索引检索专 家，曾经是v t w i n 搜索引擎( a p p l e 的c o p l a n d 操作系统的成就之一) 的主要开发 者，后在e x c i t e 担任高级系统架构设计师，目前从事于一些i n t e r n e t 底层架构的 6 浙江大学硕士学位论文第l 章绪论 研究。他贡献出的l u c e n e 的目标是为各种中小型应用程序加入全文检索功能。 l u c e n e 的发展历程：早先发布在作者自己的嗍1 u c e n e c o m ，后来发布在 s o u r c e f o r g e ，2 0 0 1 年年底成为a p a c h e 基金会j a k a r t a 的一个子项目 6 ： h t t p ：j a k a r t a a p a c h e o r g l u c e n e 已经有很多j a v a 项目都使用了l u c e n e 作为其后台的全文索引引擎，比较著名 的有： j i v e ：w e b 论坛系统； e y e b r o w s ：邮件列表h t m l 归档浏览查询系统，本文的主要参考文档 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 r 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 的开放开发平台，帮助部分的全文索引使用了l u c e n e 对于中文用户来说，最关心的问题是其是否支持中文的全文检索。但通过后 面对于l u c e n e 的结构的介绍，你会了解到由于l u c e n e 良好架构设计，对中文的支 持只需对其语言词法分析接口进行扩展就能实现对中文检索的支持。 1 3 2 全文检索的实现机制 l u c e n e 的a p i 接口设计的比较通用，输入输出结构都很像数据库的表= = 记录 = = 字段，所以很多传统的应用的文件、数据库等都可以比较方便的映射至u l u c e n e 的存储结构接口中。总体上看：可以先把l u c e n e 当成一个支持全文索引的数据 库系统。 表1 1l u c e n e 和数据库的比较 索引数据源：索引数据源： ：l o c ( f i e l dl ，f i e l d 2 ) r e c o r d ( f i e l dl ，f i e l d 2 ) 5 0 c ( f i e l d l ，f i e l d 2 )r e c o r d ( f i e l d l ) i n d e x e r is q l ：i n s e r ti 7 浙江大学硕士学位论文 第l 章绪论 l u c e n e i n d e xi d bi n d e x l s e a r c h e r ls q l ：s e l e c ti 结果输出：结果输出： h i t s ( d o c ( f i e l d l ，f i e l d 2 ) d o c ( f i e l d l ) )r e s u l t s ( r e c o r d ( f i e l di ，f i e l d 2 ) r e c o r d ( f i e l dl ) ) d o c u m e n t ：一个需要进行索引的“单元” r e c o r d ：记录，包含多个字段 一个d o c u m e n t 由多个字段组成 f i e l d ：字段f i e l d ：字段 h i t s ：查询结果集，由匹配的d o c u m e n tr e c o r d s e t ：查询结果集，由多个r e c o r d 组成 组成 全文检索1ik e ”k e y w o r d 通常比较厚的书籍后面常常附关键词索引表( 比如：北京：1 2 ，3 4 页，上海： 3 ，7 7 页) ，它能够帮助读者比较快地找到相关内容的页码。而数据库索引能 够大大提高查询的速度原理也是一样，想像一下通过书后面的索引查找的速度要 比一页一页地翻内容高多少倍而索引之所以效率高，另外一个原因是它是排 好序的。对于检索系统来说核心是一个排序问题。 由于数据库索引不是为全文索引设计的，因此，使用l i k e k e y w o r d 。时， 数据库索引是不起作用的，在使用l i k e 查询时，搜索过程又变成类似于一页页翻 书的遍历过程了，所以对于含有模糊查询的数据库服务来说，l i k e 对性能的危害 是极大的。如果是需要对多个关键词进行模糊匹配：l i k e k e y w o r d l ”a n dl i k e ”k e y w o r d 2 ”其效率也就可想而知了。 所以建立一个高效检索系统的关键是建立一个类似于科技索引一样的反向索 引机制，将数据源( 比如多篇文章) 排序顺序存储的同时，有另外一个排好序的 关键词列表，用于存储关键词= = 文章映射关系，利用这样的映射关系索引： 关 键词= = 出现关键词的文章编号，出现次数( 甚至包括位置：起始偏移量，结束 偏移量) ，出现频率 ，检索过程就是把模糊查询变成多个可以利用索引的精确 查询的逻辑组合的过程。从而大大提高了多关键词查询的效率，所以，全文检索 问题归结到最后是一个排序问题。 8 浙江大学硕士学位论文 第l 章绪论 由此可以看出模糊查询相对数据库的精确查询是一个非常不确定的问题，这 也是大部分数据库对全文检索支持有限的原因。l u c e n e 最核心的特征是通过特殊 的索引结构实现了传统数据库不擅长的全文索引机制，并提供了扩展接口，以方 便针对不同应用的定制 7 。 表1 2l u c u c e 全文搜索和数据库的模糊查询 对于l i k e 查询来说，数据传统的索 将数据源中的数据都通过全文索引一一 引是根本用不上的。数据需要逐个便 索引利记录进行g r e p 式的模糊匹配， 建立反向索引 比有索引的搜索速度要有多个数量 级的下降。 匹配效 通过词元( t e m l ) 进行匹配，通过语言分析 使用：l i k e ”n e t ”会把n e t h e r l a n d s 接口的实现，可以实现对中文等非英语 也匹配出来，多个关键词的模糊匹 果 配：使用l i k e ”c o m n e t ”：就不 的支持。 能匹配词序颠倒的x x x n e t x x x t o m 有匹配度算法，将匹配程度( 相似度) 没有匹配程度的控制：比如有记录中 匹配度n e t 出现5 词和出现1 次的，结果是 比较高的结果排在前面。 一样的。 结果输 通过特别的算法，将最匹配度最高的头返回所有的结果集，在匹配条目非常 1 0 0 条结果输出，结果集是缓冲式的小多的时候( 比如上万条) 需要大量的 出 批量读取的。 内存存放这些临时结果集。 可定锟 通过不同的语言分析接口实现，可以力 便的定制出符合应用需要的索引规她没有接口或接口复杂，无法定制 性 ( 包括对中文的支持) 高负载的模糊查询应用，需要负责的模使用率低，模糊匹配规则简单或者需 结论 糊查询的规则，索引的资料量比较大要模糊查询的资料量少 全文检索和数据库应用最大的不同在于：让最相关的头1 0 0 条结果满足9 8 以上用户的需求。 1 3 3 亚洲语言的切分词问题 对于中文来说，全文索引首先还要解决一个语言分析的问题，对于英文来说， 语句中单词之间是天然通过空格分开的，但亚洲语言的中日韩文语句中的字是一 9 浙江大学硕士学位论文第l 章绪论 个紧挨着另一个，所有，首先要把语句中按“词”进行索引的话，这个词如何切分 出来就是一个很大的问题。 首先，肯定不能用单个字符作( s i - g r a m ) 为索引单元，否则查“上海”时，不能 让含有“海上”也匹配。但一句话：“北京天安门”，计算机如何按照中文的语言习 惯进行切分呢? “北京天安门”还是“北京天安门”? 让计算机能够按照语言习 惯进行切分，往往需要机器有一个比较丰富的词库才能够比较准确的识别出语句 中的单词。 另外一个解决的办法是采用自动切分算法：将单词按照2 元语法( b i g r a m ) 方式 切分出来，比如：”北京天安门”- - ”北京京天天安安门”。这样，在查询的 时候，无论是查询”北京”还是查询”天安门”，将查询词组按同样的规则进行切 分：”北京”，”天安门”，多个关键词之间按与a n d ”的关系组合，同样能够正确 地映射到相应的索引中。这种方式对于其他亚洲语言：韩文，日文都是通用的。 基于自动切分的最大优点是没有词表维护成本，实现简单，缺点是索引效率 低，但对于中小型应用来说，基于2 元语法的切分还是够用的。基于2 元切分后的 索引一般大小和源文件差不多，而对于英文，索引文件一般只有原文件的3 0 - 4 0 不同。 表1 3自动切分和基于词表的分词方法比较 薹 实现实现非常简单 实现复杂 查询增加了查询分析的复杂程度，适于实现比较复杂的查询语法规则 索引冗余大，索引几乎和原文 存储效率索引效率高，为原文大小的3 0 左右 一样大 词表维护成本非常高：中同韩等语言需 维护成本无词表维护成本要分别维护。还需要包括词频统计等内 容 嵌入式系统：运行环境资源有 限分布式系统：无词表同步问对查询和存储效率要求高的专业搜索引 适用领域 题多语言环境：无词表维护成擎 本 l o 浙江大学硕士学位论文第1 章绪论 1 4 论文结构 本文的第二章从需求的角度，分析了基于关系数据库的全文检索系统存在的 问题以及优化设计的目标。 第三章分析了当前的中文分词常用算法，并重点介绍t d a r t s e a r c h v 3 中文分 词的核心算法。 第四章分析了l u c e n e 的索引机制，并重点介绍了d a r t s e a r c h v 3 对索引方法的 优化和实现。 第五章分析了l u c e n e 的r a n k 机制，并重点介绍了基于l u c e n e 的面向关系型数 据库的排序机制的优化方法。 第六章主要介绍了在d a r t s e a r c h v 3 系统的设计过程中为了优化展示效果所专 门设计的的两个工具包，一个用来展示语义结果图，一个用来搜索相关的图片和 文章。 第七章是对d a r t s e a r c h 系统的总结与展望。 浙江大学硕士学位做第2 章d a r t s c a r c h v 3 系统设计目标 第2 章d a r t s e a r c h v 3 系统设计目标 2 1d a r t s e a r c h v 2 问题分析 现在正在使用的d a r t s e a r c h v 2 系统在基于语义本体的异质异构数据库集成方 面体现出良好的性能，但是在实际使用过程中也暴露了一些问题，主要体现在以 下几个方面： 中文分词 d a r t s e a r c h v 2 系统采用的是l u c e n e 中自带的基于最大匹配的中文分词算法， 这个算法能够对普通的汉语进行分析，但是分析效率比较低下。而且，而且不能 对特定领域的汉语词语进行有效的识别。例如在中医药领域，“大黄是一种非 常常见的单味药，“将军 在中医药领域是蟋蟀的一种别名，在中医药领域，这 些词是标准词汇。但是用普通的搜索引擎，如百度和谷歌，会将“大黄 和大黄 狗联系起来，而且无论如何无法将“将军 和蟋蟀联系在一起。在d a r t s e a r c h v 2 中也存在同样的问题。 尽管最大匹配法分词是常用的解决的方案，但是无疑它存在很多明显的缺陷， 这些缺陷也限制了最大匹配法在大型搜索系统中的使用频率。最大匹配法的问题 主要问题有以下几点： 一、长度限制 由于最大匹配法必须首先设定一个匹配词长的初始值，这个长度限制是最大 匹配法在效率与词长之间的一种妥协。我们来看一下以下两种情况： ( 1 ) 词长过短，长词就会被切错。例如当词长被设成5 时，也就意味着它只 能分出长度为5 以下词，例如当这个词为“中华人民共和国 长度为7 的词时，我 们只能取出其中的5 个字去词库里匹配，例如“中华人民共，显然词库里是不 可能有这样的词存在的。因此我们无法下确的划分出“中华人民共和国 这样的 1 2 i 浙江大学硕士学位论文第2 章。a n s 例曲v 3 系统设计目标 词长大于5 的词。 ( 2 ) 词长过长，效率就比较低。也许有人会认为既然5 个字无法满足我们的 分词要求，何不将词长加大，例如加到1 0 或者1 0 0 ，毕竟这个世界超过1 0 0 个字长 的词还是很少见的，我们的词长问题不就解决了? 然而当词长过长时，我们却要 付出另一方面的代价：效率。效率是分词算法、甚至是整个算法理论体系的关键， 毕竟算法书里所有的高深的查询或排序算法都是从效率出发的，否则任何笨办法 都可以解决分词效率低的问题。设想到我们把字长设成1 0 0 个词时，我们必须将 词从1 0 0 开始一直往下匹配直到找到要查的字为止，而我们大多数词的字长却只 有两三个字，这意味着前9 7 次的匹配算法是徒劳的。 因此我们必须要在词长与效率之间进行妥协，既要求分词尽量准确，又要求 我们的词长不能太长。尽管我们可能找到这样一个比较优化的字长值使两者都达 到比较满足的状态，但是毕竟不管我们怎么设定，总会有些太长词分出来，或者 带来效率问题。 二、效率低 效率低是最大匹配法分词必然会来的问题。即便我们可以将字长设成相当短， 例如5 ( 注意，我们不能再缩短字长了，毕竟字长为5 以上的词太多了，我们不能 牺牲分词的准确) ，然而当我们的大数词长为2 时，至少有3 次的匹配算法是浪费 掉的。回想一下算法书里提到的最简单的字符匹配与k i v i p 算法之间天差地别的效 率，我们知道通过某种方法，这些浪费的掉的匹配时间是可以补回来的。 三、掩盖分词歧义 中文是如此复杂的语言，它的表达方式如此之多，语法文法如此精妙，机械 的电脑是很难理解这么复杂的语言，因此它必然会带来歧意性，以下是两个简单 的例子： a “有意见分歧( 正向最大匹配和逆向最大匹配结果不同) 韦意7 觅7 分唆7 奄7 意见f 分歧 1 3 浙江大学硕士学位论文第2 章。a i t s 向v 3 系统设计目标 b “结合成分子时”( 正向最大匹配和逆向最大匹配结果相同) 结合成分子时由于词的歧义性使我们在使用最大匹配法分词会产生错 误的结果，而且使用正向分词与逆向分词往往会产生截然不同的结果。尽管使用 回溯法或计算计算词的使用频率，可以使出现歧义的可能性减少，但是我们知道， 这样的结果是不可避免的，因为中文的变化实在太多了。 四、最大匹配的并不定是想要的分词方式 最大匹配法基于的理念是找到最大的匹配词，但有的时候除了最大匹配词外， 我们也可能只需要这个词的一部分。例如“感冒解毒胶囊 是一个完整的词，按 照最大匹配法我们无法对它进行拆分了，这样我们输入“感冒的时候就根本搜 不到我们需要的词。这是我们需要的吗? 做为生产这种药的厂商，它肯定希望用 户输入“感冒 甚至“解毒”，我们都能查到对应的内容。 索引效率问题 d a r t s e a r c h v 2 中使用的索引器是采用了l u c e n e 开源工具包自带的索引器，这 种索引器在针对大量的网页语料库进行一次性索引时能体现出良好的性能。而 d a r t s e a r c h 系统主要是应用于领域数据库中，语料相对较少，一般只有几百船到 几个g b 的数据。l u c e n e 自带的s t a n d a r t i n d e x e r 不能很好的支持增量索引，当语 料发生变化时，如预料增加时，就需要花费大量的时间重新建立索引。 r a n k 机制 d a r t s e a r c h v 2 中使用的结果集r a n k 机制是采用了l u c e n e 工具包自带的r a n k 公 式，这个r a n k 机制在结果集相关性上有比较良好的性能，因面d a r t s e a r c h v 3 系统 将继续采用这个公式作为结果集的排序机制。但是d a r t s e a r c h v 2 系统没有考虑到 关系数据库自身的特征，因而在d a r t s e a r c h y 3 系统开发时，将会重点考虑关系型 数据库的特征，重写l u c e n er a n k 公式的一些接口实现。 展示界面不够美观 d a r t s e a r c h v 2 系统的用户界面设计不够美观，没有充分利用w e b 2 o 环境下网 络应用系统的开发模式以及各种网络资源，在用户搜索接口和搜索结果的展示方 1 4 浙江大学硕士学位论文第2 章d a r t s e a r c h v 3 系统设计目标 面存在较大的改进空间。 2 2d