（计算机应用技术专业论文）桌面搜索引擎的研究与实现.pdf

北京化工大学硕士研究生学位论文 桌面搜索引擎的研究与实现 摘要 随着搜索技术的发展，纯粹的w e b 搜索由于受到i e 的束缚，因而 表现出应用能力偏低，而基于桌面的搜索则相当于一个“客户端+ 数 据库”这样的应用模型，尤其加入了划词搜索的功能，这也使得搜索 功能的多样化、个性化成为可能。 针对传统意义上的搜索引擎和新近提出的桌面搜索的概念，本课 题提出一整套的搜索引擎从客户端到服务端的实现方案，并予以实现。 此方案包括网络蜘蛛、多线程下载器、u n i c o d e 文件存储模块、 h t m l ) ( m l 语法解析器、分词系统、散列二级索引数据库、w e bs e r v i c e 、 p a g e r a n k ( 网页排名) 、划词搜索。 网络蜘蛛也就是s p i d e r ，负责将网络上的各种链接信息，包括普 通网页信息、办公资源、图片资料和音乐视频资源和n a s h 动画，网络 蜘蛛把它们的u i 也地址及相关信息( 如更新时间、来源网站) 存进数 据库，并将所有u i u 的链接情况记录下来，以等待后面的p a g e r a n k 模块调用。 多线程下载器将u 也下载为文件后，用u 1 蛆c o d e 更名机制存到 本地硬盘。 h r m 【，) ( m l 语法解析器负责将已经存好的h n 见文档解析，剔 i v 北京化工大学硕士研究生学位论文 除无用的h n l 标识，并根据有用的h n l 标识将文本重新组织为 x 几。 分词则负责将英文和中文段落进行词分割。 散列二级索引数据库是根据分词的结果，建立从词到u u 和从 u i 也到词的两个查询数据库。 而w 曲s e i c e 则是用于用户交互的网络服务，负责响应用户的 查询请求，并调用已经建立好的索引数据库返回查询结果。 p a g e r m k 利用网络蜘蛛创建好的链接信息，采用被二维线性收敛 方法增强的幂法，计算每个u r l 的网络排名。 划词搜索是运行在客户端，能够监视用户的划词动作并快速返回 其要搜索的关键词查询结果。 论文首先介绍了课题涉及到的主要理论和技术，然后介绍了本搜 索引擎系统的总体设计以及主要模块的详细设计，最后对搜索引擎进 行了总结和展望。 关键词：搜索引擎，中文分词，网页排名，索引数据库，解析器 北京化工大学硕士研究生学位论文 r e s e a r c ha n dim p l e m e n t0 fd e s k t o ps e a r c he n gln e b s t r a c t a st l l e d e v e l o p i n go fs e a r c ht e c h n o l o g y ，o r i g i l l a lw e bs e a r c hw a s r e s 乜a i n e db yi e ，s om a t 廿1 ec 印a b i l i t ya b o u t 印p l i c a t i o ni sn o t v e 叮w e l l 。 d e s l ( t 叩s e a r c he n g i n ee q u a l s 协e 印p l i c a t i o nm o d ec o m b i n e do fc l i e ma 1 1 d d a t a b a s e ，e s p e c i a l l yf o rt 1 1 en e w 如n c t i o nc a l l e dd r a gs e a r c h ，h e n c e ，i t m a k et h ev a r i o u sa n dp e r s o n a ls e a r c hp o s s i b l e 。 a c c o r d i n gt 0m ec o n c e p t i o no f 镪a d i t i o n a ls e a r c he n 百n ea n dt h e r e c e n t l yc o m i n gd e s k t o ps e a r c he n g i n e ，t l l i sm e s i sp o s tas o l u t i o nf o r w h o l es e r i e so fs e a r c h 丹o mc l i e n tt os e e ra l l di m p l e m e mm o s e 。t h i s s o l u t i o ni 1 1 c l u d e ss p i d e r 、m u l 娃t 圭_ l r e a dd o w n l o a d e r 、u n i c o d ef i l es t o r a g e 、 h m ) ( m l p a r s e r 、t 0 k e n i z a t i o n 、h a s h2i n d e x e dd a t a b a s e 、w 曲s e i c e 、 p a g e r a n k 、d r a gs e a r c h 。 s p i d e ri sc h a r g eo fg a t h e f i n ga ut h el i n ki n f o n i l a t i o n 疔o mi n t e m e t ， i n c l u d 洒gn o n n a lw e bp a g e 、o f f i c ed o c u m e m 、p i c t u r e 、m u l t i m e d i a 、n a s h a i l i m a t i o n 。s p i d e rp u tm e i rl i n ki 1 1 f o m l a t i o na i l di m e r r e l a t e d 洒f o m l a t i o n ( u p d a t et i m e 、s o u r c ew e b s i t e ) i n t 0d a t a b a s e ，a n dr e c o r dt h el i n k 行o m u i u t ob ep r e p i i e df o rp a g e “m k 。 v i 北京化工大学硕士研究生学位论文 m u l t i t l _ i r e a dd o w n l o a d e fi sd o ，i l l o a da l lu r lt ol o c a lf i l e sa n dt l l e n s t o r ei n t oh a r dd r i v e ra r e rr e n a m eb yu n i c o d ef i l es y s t e m 。 h t m l x m lp a r s e ri sr e s p o n s i b l et os t o r e dh n n lf i l e s 。f i l t e ra ut h e u s e l e s sh t m l t a ga n do 珞a n j z et l l et e x tt o ) ( i t l lb a s e do nu s e m lh t m l t a g 。 1 b k e n i z a t i o ni st od i v i d e 廿l ee n g l i s hp a r a g r a p ho rc h i n e s ep a 镩印h i n t ow o r d s 。 h a s h2i n d e x e dd a t a b a s ei sa c c o r d i n gt ot 1 1 er e s u l t6 o mt o k e n i z a t i o n t ob u i l d2q u e r yd a t a b a s e s ，o n ei s 疗o mw o r d st ou r l ，t 1 1 eo 也e ro n ei s 丘o mu r l t ow o r d s 。 w 曲s e r v i c ei su s e df o ru s e ri n t e r f a c ew h i c hi st or e s p o n dm eu s e r q u e a n da l s oi tc “lm ei n d e x e dd a t a _ b a s et h a tw a sa l r e a d yd o n et or e n m l 也eq u e r yr e s u l t 。 p a g e r a n ki sa c c o r d i n gt o 也el i n ki n f o r m a t i o nf o ms p i d e r ，c a l c u l a t e 也ep a g er a n kv a l u eb ym ep o w e rm e m o dc n h a l l c e db yp l a n a rl i n e 酎 c o l l v e r g e n c em e m o d 。 d r a gs e a r c hi sr u n n i n go nc l i e n t ， i tc a no v e r s e ed r a go p e r a t i o n 矗o m u s e ra 1 1 dm e nr e t 啪血eq u e 哆r e s u l ta b o u tw h a tu s e rw a n ti m m e d i a t e l y 。 t h et 1 1 e s i si n 仃o d u c e sm em a i nm e o r i e sa n dt e c h n o l o g i e su s e di nt l l e d e s i g n ，a n dt h e np r e s e n t st 1 1 eo v e r a l ld e s i g no f 也es y s t e ma n dd e t a i l e d c o n s t n l c t i o no fe v e 叮i m p o r t a l l tm o d u l e l a s ti ts u m m a r i z e st h ed e s l ( t o p s e a r c he r 培i n ea n dd e s c r i b e si t sb r i g h tm t u r e 北京化工大学硕士研究生学位论文 k e yw o r d s ：s e a r c he n g i n e ，c h i n e s et o k e n i z a t i o n ，p a g e r a n k ，i n d e x d a t a b a s e ，p a r s e r i 北京化工大学硕上研究生学位论文 北京化工大学位论文原刨性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 作者签名：丝塑日期： 智 关于论文使用授权的说明 刀。5 、i 千 学位论文作者完全了解北京化工大学有关保留和使用学位论文的 规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京 化工大学。学校有权保留并向国家有关部门或机构送交论文的复印件 和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学 位论文。 保密论文注释：本学位论文属于保密范围，在l 年解密后适用本 授权书。非保密论文注释：本学位论文不属于保密范围，适用本授权 书。 作者签名：丛鱼 导师签名：盗鱼皇 1 1 日期：竺! ：鱼堡 日期：! 丝! ：! ：壁 北京化工大学硕士研究生学位论文 符号说明 c h m m ：c c a d e dh i d d e nm a r k o vm o d e l ，层叠隐马尔可夫模型 c o m ：c o m p o n to b j e c tm o d e l 组件对象模型 h m m ：h i d d e nm a r k o vm o d e ，隐马尔可夫模型 m v c ：m o d e l e wc o 虹o l l e f ，模型视图控制器 d t d ：d o c u m e m1 卯ed 嘶诚i o n ，文档类型定义 x m l ：c x t 锄s i b 】em a r k u pl 8 n g l 】a g e ，可扩展标记语言 o o p ：o 均e c to r i e 1 ：e l lp m g r a i t i ，面向对象编程 s v m is u p p o r t t o rm a c l i e ，支持向量机 l o d ：l a wo f d e m e t e r ，迪米特原则 l o d ：l a wo f d 啪e t e r ，迪米特原则 北京化工大学硕士研究生学位论文 1 1 正则匹配 第一章绪论 正则表达式最早由数学家s t e p h e n 日e e n e 于1 9 5 6 年提出【l 】他在对自然语言 的递增研究成果的基础上提出来的。正则表达式并非一门专用语言，但它是可用 于在一个文件或字符里查找和替代文本的一种标准。许多程序中都使用了正则表 达式，并可以被很多语言采纳，如h n 他和m 。，而这些采纳通常只是整个标 准的一个子集。正则表达式在字符串匹配问题上，具有很广的应用。 下面列出一些最常用的匹配规则： 表1 1 正则匹配规则集 n b l c1 1r u l eo f r e g e xm 抓m 匹配前面的子表达式零次或多次。例如，z o 能匹配“z ”以及”z o o ”。等 价于 o ，) 。 上 匹配前面的子表达式一次或多次。例如，+ i 能匹配”z o ”以及”z o o ”， 但不能匹配”z 。+ 等价于 1 ，) 。 ? 匹配前面的子表达式零次或一次。例如，”d o ( e s ) ? ”可以匹配”d o ”或 ”d o e s ”中的”d o ”。? 等价于 o ，1 ) 。 x 1 ) |匹配x 或y 。例如，z | f b o d l 能匹配”z ”或”f o o d ”。( z i d o o d t 则匹配”z o o 扩 或”f o o d 。 咖】字符集合。匹配所包含的任意一个字符。例如，【妇】可以匹配”p l a i n ”中 的a i 。 【勺翻负值字符集合。匹配未包含的任意字符。例如， 。 “a b c 】可以匹配”p l a i n ” 中的i p t 。 【叫字符范围。匹配指定范围内的任意字符。例如，【a - z 】可以匹配a i 到掣范 围内的任意小写字母字符。 在搜索引擎中，需要利用正则匹配识别链接信息及图片锚链接等信息，所 以需要构造各种正则表达式，在本文的s p i d e r 中，采用开源b o o s t 正则匹配库， b o o s t 库是由开源组织b o o s t o r g 提供的跨平台c + + 标准库，包括比如智能指针 ( s m a r tp o i n t e r ) 、多维数组、图库、正则库、线程库，计时系统等。正则匹配比 6 北京化工大学硕士研究生学位论文 传统的字符串匹配更快并具灵活性，因为正则库在底层用状态转换机实现。 匹配网页中的链接的正则表达式为： “+ h r e f 恬= + + 奉( 【 埘 】+ ) ” 匹配网页中的图片链接的正则表达式则为： “i m g + s p c s + 武s + ”( 【，、s 】) ” 选取多媒体文件包括图片文件的热点值的正则表达式是： “s + a l t s = 、s 扎”( 【 s 】) ”，所谓热点h o t 【5 州就是h t i i l l 代码中的a l t 标签，这里选取a l t 值，主要是为了能提前知道链接中的有用的信息。 1 2 递推下降分析 自顶向下分析算法通过最左推导中描叙出各个步骤来分析记号串输入，一般 用递推下降分析和l l ( 1 ) 分析，其中递推下降在形式上要比l l ( 1 ) 简单，因为它把 状态栈的处理隐藏到递推的过程中。主要原则是在处理完上层的符号，然后将后 面的符号交给下层的过程去处理，这样层层下降，直到最低层的原子符号【1 0 1 。 下面分析h f m l 标识的语法： a - c 硼 b = aj t d ：= e li e 2j e 3i e 4 e = f g = h f = f j n t ls t y l e 卜 g = s i z e l l i n k k h = = n u m b e r i n a m e t _ s n 证g 通过简单分析其文法，得出该文法是3 型上下文无关文法，所以大体上可以 用自顶向下或者自底向上文法分析。在这里采用自顶向下递推下降的方法构造语 法分析树1 1 1 ，是因为： l ，结构清晰，容易实现。 2 ，扩展方便。由于每一步骤都需递交给下面过程来处理，所以如果扩展某 7 北京化工大学硕士研究生学位论文 一步骤，只需要增加一个下一层递归就可。而自底向上在扩展时需要重新扩充表 结构，并没有自顶向下在结构上方便【1 2 】。 3 ，性能可靠。一般来说自顶向下因为层层递归，空间消耗大，但是网页解 析可以在允许的栈范围内解决，并且由于不存在解析回测13 1 ，所以解析速度还是 非常快。 1 3 隐马模型 隐马模型【1 4 l 是经典的描述随机过程的统计方法，在自然语言处理中得到了广 泛的应用。然而，相对于复杂的自然语言现象来说，传统的 m o 讧仍然略显简单， 为此，需要采用多个层次的隐马模型对汉语词法分析中遇到的不同情况进行分别 处理。 层次隐马模型( h i e r a r c h i c a lh i d d e nm a 血0 vm o d e l ，简称h h m m ) ：在h h m m 中，有多个状态层和一个输出层。每一个上一层状态都对应于若干个下一层的子 状态，而每个状态的予状态的分布都是不同的，由一个隶属于该状态的初始子状 态概率矩阵和子状态转移概率矩阵所决定。最底层状态通过一个输出概率矩阵输 出给观察值。m m o 订实际上是一种不同于h m m 的更复杂的数学模型，并且具有 比h m m 更强的表达能力，不过使用起来时空开销也比较大。h h m m 的解码问题 求解的时间复杂度是0 ( n f ) ，而h m m 的解码问题求解的时间复杂度只有o ( n d ， 与句子长度成线性关系，速度非常快。本文采用的也是一种多层隐马尔可夫模型， 称为层叠隐马尔可夫模型( c 嬲c a d e dh i d d e nm 盯k o vm o d e l ，简称c h m m ) 。不同 于h h m m 的是，c h m m 实际上是若干个层次的简单h m m 的组合，各层隐马尔 可夫模型之间以下述几种方式互相关联，形成一种紧密的耦合关系： 各层m n t 之间共享一个切分词图作为公共数据结构； 每一层隐马尔可夫模型都采用n - b e s t 策略，将产生的最好的若干个结果送到 词图中供更高层次的模型使用； 低层的h m m 在向高层的 叮“m 提供数据的同时，也为这些数据的参数估计 提供支持。整个系统的时间复杂度与脚m 相同，仍然是o ( n t ) 。 现在给定一个分词原子序列s 的某个可能的分词结果记为阡t ( w 如， 矿对应的类别序列记为乒( c ，同时，这里把概率最大的分词结果矿作为最 北京化工大学硕士研究生学位论文 终的分词结果。则： = a r g m np ( 聊 利用贝叶斯公式进行展开，得到： = a r g m “p ( 碉c ) p ( c ) 形 将词类看作状态，词语作为观测值，利用一阶 蹦m 展开得： 矿# = a r g m a x 最p ( w fi q ) p ( 。fi c f 1 ) f = 1 ( 其中印为句子的开始标记b e g ，下同) 为计算方便，常用负对数来运算，则： 矿；a r g m i n 兰卜l t i p ( w f | 日) 一l i l p ( q q i ) 】 矽i - 1 这样就可以利用动态规划算法进行计算，选出概率最大的n 个词组合，然后 再交到下一层当中处理【1 6 】。 1 4 索引数据库 用户在使用搜索引擎时，往往是通过输入关键词来查找相关网页，这实际就 是索引的第一个目的：即建立从关键词到u r l 地址的映射。同时程序在找到一篇 u r l 对应的本地文件时，也应该能快速知道哪些词在这个文件中出现过，出现过 几次，出现的权重是多少( 权熏根据一些h t m l 标签的一些特征来输出，比如字 体大的关键词其权重就大) ，这样就形成了索引的第二个目的：建立从u r l 地址 到关键词的映射。上面的两个目的形成了两张相互对应的表【1 7 1 ，一个表储存每个 关键词对应哪些u r l ，另一个表储存每个u r l 对应哪些关键词。 如果应用现有的数据库产品，比如m y s q l ，o r a c l e 等，解决这样双对应的问 题是建立第三个表来储存前面两个表的笛卡尔积。假设有m 个u i 也和有n 个关 键词，那么在第三个表的主键中就会出现m n 个记录，而每一条记录又表示着 对应关系，如果没有对应存在就保留为空值。可以想象的是，由于不是每篇u r l 都出现了所有的词，所以在这张表中会有很多空项，从而浪费了大量的空间。问 题并不止空间效率，时间效率才是真正的弱点。因为m 和n 都可能是非常大的 北京化工大学硕士研究生学位论文 数字。比如中文、英文、数字等常用符号组合加起来可能就达到数十万，而这正 是n 的数目。比起n 来，m 则更大，g o o 酎e 声称他们已经收集了8 0 亿张网页， 哪怕是小型的搜索引擎，网页也要在百万以上，这么算来，m n 会是一个令数据 库系统运行很慢的数字，尤其在其插入和删除的时候。 时间效率是搜索引擎最重要的要求，比如g o o g l e ，一般情况下搜索一篇文章 的速度不会超过2 秒钟【m 。也就说明了这种情况下，不便使用通常的数据库系统， 而必须自己建立网页存储结构。而将关键词和其对应的u r l 或者将u r l 和其对 应的关键词顺序存放在文件中也是不明智的，因为顺序查找的效率是o ( n ) ，这 样的效率不能忍受，因此在这里，本文选择了建立索引表文件的倒排表原理的数 据库的办法。 索引的完整意义是对关键词索引，其目的是用二分查找代替顺序查找来提高 速度，然后通过索引数据库里记录的该关键词在真正数据文件中的偏移地址来快 速定位到需要的数据。众所周知，二分查找在最坏情况下的效率还可以达到了 l o ( n ) 【1 9 】，所以几万级数目的关键词甚至几亿数目的网页u r l 都可以在几十 次内就完成查找，这样的查找速度正是搜索引擎所需要的。不过需要注意的是， 使用二分查找有两个很重要的前提： a ：在线性结构中关键词有序 b ：数据记录定长 a 前提比较好理解，因为必须在线性结构中保持元素有序排列才能比较，就 像s t l 中要求对对象进行b 妇町s e a r c h 前一定要实现附带o p e r a t o r = ) ( x i ( t _ a + x k 1 7 e n o f o x k - x k 1 | | k _ 】k + 1 ) 1 6m v c 模式 m v c 英文即m o d e l v i e w c o n 呐l l e r ，即把一个应用的输入、处理、输出流程 按照m o d e l 、e w 、c o i l 仃o l l e r 的方式进行分离，这样一个应用被分成三个层 模型层、视图层、控制层。 视图( e w ) 代表用户交互界面，对于w 曲应用来说，可以概括为h 瑚l 界面， 但有可能为 t m l 、x m l 和a p p l e t 。随着应用的复杂性和规模性，界面的处理 也变得具有挑战性。一个应用可能有很多不同的视图，m v c 设计模式对于视图 北京化工大学硕士研究生学位论文 的处理仅仅限于视图上数据的采集和处理，以及用户的请求，而不包括在视图上 的业务流程的处理。业务流程的处理交给模型( m o d e l ) 处理。比如一个订单的视图 只接受来自模型的数据并显示给用户，以及将用户界面的输入数据和请求传递给 控制和模型。 模型( m 0 d e l ) ：就是业务流程，状态的处理以及业务规则的制定。业务流程的 处理过程对其它层来说属于黑箱操作，模型接受视图请求的数据，并返回最终的 处理结果。业务模型的设计可以说是m v c 最主要的核心。目前流行的e j b 模型 就是一个典型的应用例子，它从应用技术实现的角度对模型做了进一步的划分， 以便充分利用现有的组件，但它不能作为应用设计模型的框架。它仅仅告诉你按 这种模型设计就可以利用某些技术组件，从而减少了技术上的困难。对一个开发 者来说，就可以专注于业务模型的设计。m v c 设计模式告诉开发者，模型按一 定的规则抽取出来，抽取的层次很重要，这也是判断开发人员是否优秀的设计依 据。抽象与具体不能隔得太远，也不能太近。m v c 并没有提供模型的设计方法， 而只告诉你应该组织管理这些模型，以便于模型的重构和提高重用性。这点对编 程的开发人员非常重要。 控制( c o n 血o l l 神：理解为从用户接收请求，将模型与视图匹配在一起，共同 完成用户的请求。划分控制层的作用也很明显，它清楚地告诉你，它就是一个分 发器，选择什么样的模型，选择什么样的视图，可以完成什么样的用户请求。控 制层并不做任何的数据处理。例如，用户点击一个连接，控制层接受请求后，并 不处理业务信息，它只把用户的信息传递给模型，告诉模型做什么，选择符合要 求的视图返回给用户。因此，一个模型可能对应多个视图，一个视图可能对应多 个模型。 s t r u t s 的体系结构实现了m o d e l v i e w c o n t r o l l e r 设计模式的概念，它将这 些概念映射到w e b 应用程序的组件和概念中。 基于m v c 的系统中的m o d e l 部分可以细分为两个概念一系统的内部状态和 能够改变状态的行为。用语法术语来说，这里可以把状态信息当作名词( 事物) ， 把行为当作动词( 事物状态的改变) 。 基于s t r u t s 的应用程序中的v i e w 部分通常使用j s p 技术来构建。j s p 页面 包含称为“模版文本”的静态h t m l ( 或) ( m l ) 文本，加上插入的基于对特殊行为 标记解释的动态内容。j s p 环境包括了其用途由j s p 规范来描述的一套标准的行 北京化工大学硕士研究生学位论文 为标记，例如 。另外，还有一个用来定义标记的标准机制，这些 自定义的标记组织在“定制标记库”中。s t r u t s 包括了一个广阔的便于创建用 户界面，并且充分国际化的定制标记库，与作为系统m o d e l 部分一部分的 a c t i o n f o r mb e a n s 美妙地相互配合。 应用程序的c o n t r o l l e r 部分集中于从客户端接收请求( 典型情况下是一个 运行浏览器的用户) ，决定执行什么商业逻辑功能，然后将产生下一步用户界面的 责任委派给一个适当的v i e w 组件。在s t r u t s 中，c o n t r o l l e r 的基本组件是一个 a c t i o n s e r v l e t 类的s e r v l e t 。这个s e r v l e t 通过定义一组映射( 由j a v a 接口 a c t i o n m a p p i n g 描述) 来配置。每个映射定义一个与所请求的u r i 相匹配的路径 和一个a c t i o n 类( 一个实现a c t i o n 接口的类) 完整的类名，这个类则负责执 行预期的商业逻辑，然后将控制分派给适当的v i e w 组件来创建响应。 s t r u t s 也支持使用包含有运行框架所必需的标准属性之外的附加属性的 a c t i o n m a p p i n g 类的能力。这允许用户保存特定的应用程序的附加信息，同时仍 可利用框架其余的特性。另外，s t r u t s 允许用户定义重定向到的逻辑名，这样一 个行为方法可以请求“主菜单”页面，而不需要知道相应的j s p 页面的实际名字 是什么。这个功能极大地帮助分离控制逻辑和显示逻辑，从而达到了后台与前台 独立的效果。 w j n d o s 系统中，各个进程独立享有自己的内存空间，在w i n 3 2 中这个空 间达到了4 g 大小，这种各自隔离的内存访问机制使得各个进程之间的通信变得 不太容易。进程通信有很多种方式，比如剪贴板、注册表、拷贝消息等等，但可 以说最根本也是最快的是应用内存文件映射。 如果用户程序要自己使用虚拟内存，那么首先是在进程地址空问中保留 ( r e s e r v e ) 一块地址( 在4 m _ _ 2 g 中) ，然后再把这块空间提交( c o 衄i t ) 给真正的内 存。但这种做法在大块空间分配时会变得很慢。 而内存文件映射正是克服了这个缺点，内存映射文件提供了一个统一的内存 管理特征，使得应用程序能够通过内存指针象访问动态内存一样对磁盘上的文件 进行访问。通过内存映射文件，可以将磁盘上文件的全部和部分映射为到进程的 1 4 北京化工大学硕士研究生学位论文 虚拟地址空间的某个位置。一旦完成了映射视图，对文件内容的访问就如同在该 地址区域内直接对指针取值一样简单。这样，如果对文件写入数据就可以直接对 指针进行赋值，如： p m e m = 2 3 ； 同样，从文件的某个特定位置读取数据也一样非常的简单： n t o k e n l e n = + p m e m ； 在这个例子中，指针p m e m 代表映射到文件视图的进程地址空间的某个区域 中任何一个地址。事实上，当内存映射文件提供了对文件某个特定位置的直接读 写时，真正的对磁盘文件的读写是由底层处理的。而且，数据也并非在每次操作 时都即时写入到磁盘，而是大量的文件i ，o 通过缓冲处理来提高系统的整体性能。 当然，可以通过调用内存映射文件函数f l 岫h e 、v o 球i l e 强制立即执行磁盘事务处 理以重载这种缓冲处理方式。 使用内存映射文件i o 的好处是系统对所有的数据的传输都是通过4 k 的数 据页面来实现的。内部的所有内存页面都是有虚拟内存管理器来管理的，它决定 内存的页面何时被分页对应到磁盘，哪些页面应被释放以提供给其它的应用程序 使用，以及每个应用程序可以拥有超出实际分配的物理内存之外多少个页面空间。 因为虚拟内存管理器以统一的方式处理所有磁盘i o 一一次以一个页面为单位 读写内存，这种优化使它能够以足够快的速度处理内存操作。限制所有的磁盘的 读写操作以4 k 大小的页面为单位进行，意味着一些小的i o 操作将被缓冲入一 次大的操作之中，也就是说次i ，o 操作以后的其它操作所需的数据已经被前一 次的页面操作读入到内存，从而无需再进行一次磁盘i 0 ，这样将大幅度地减少 硬盘读写头的移动，从而提高了系统的性能。 内存文件映射在保留一块内存地址空间的同时，还将这块内存地址空间提交 给物理内存，这样的做法主要有两个特点： a 直接用内存映射文件来访问磁盘上的数据文件，无需再进行文件的i o 操 作。 b 用来在多个进程之间共享数据。内存映射文件的位置在3 g 一4 g 的空间中， 这部分是w i n 3 2 所有进程都看的到并且共享的，自然可以用来传输数据，比如各 个进程所共享的d l l 等也是映射在这个空间范围。 内存映射文件的使用可以分为以下三步： 北京化工大学硕士研究生学位论文 1 c r e a t e f i l e p p i n g 创建一个文件映射内核对象 2 m a p v i e w o f f i l e 将文件数据映射到其进程地址空间 3 u n m a p v i e w o f f i l e 从其进程地址空间解除这个映射 这样，就可以为需要的各个进程分配出一片共享区域，通过m a p e w o f f i l e 函数，可以得到指向此共享区域首地址的指针，那么各个进程都可以根据文件映 射的标识号得到词指针，从而对该区域进行读写操作。 1 6 北京化工大学硕士研究生学位论文 2 1 问题的提出 第二章系统总体设计 在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网爆 炸性的发展，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大 众信息检索需求的专业搜索网站便应运而生了。现代意义上的搜索引擎的祖先， 是1 9 9 0 年由蒙特利尔大学学生a 1 a ne m t a g e 发明的a r c h i e 。虽然当时w o r l dw i d e w e b 还未出现，但网络中文件传输还是相当频繁的，而且由于大量的文件散布在 各个分散的f t p 主机中，查询起来非常不便，因此a 1 a ne m t a g e 想到了开发一个 可以以文件名查找文件的系统，于是便有了a r c h i e 。a r c h i e 工作原理与现在的搜 索引擎已经很接近，它依靠脚本程序自动搜索网上的文件，然后对有关信息进行 索引，供使用者以一定的表达式查询。由于| r c h i e 深受用户欢迎，受其启发，美 国内华达s y s t e mc o m p u t i n gs e r v i c e s 大学于1 9 9 3 年开发了另一个与之非常相似 的搜索工具，不过此时的搜索工具除了索引文件外，已能检索网页。 当时，“机器人”一词在编程者中十分流行。电脑“机器人”( c o m p u t e r r o b o t ) 是指某个能以人类无法达到的速度不问断地执行某项任务的软件程序。由 于专门用于检索信息的“机器人”程序像蜘蛛一样在网络间爬来爬去，因此，搜 索引擎的“机器人”程序就被称为“蜘蛛”程序。世界上第一个用于监测互联网 发展规模的“机器人”程序是m a t t h e wg r a y 开发的w o r l dw i d ew e bw a n d e r e r 。 刚开始它只用来统计互联网上的服务器数量，后来则发展为能够检索网站域名。 与w a n d e r e r 相对应，m ”t i nk o s t e r 于1 9 9 3 年1 0 月创建了a l l w e b ，它是a r c h i e 的h t t p 版本。a l l w 雎不使用“机器人”程序，而是靠网站主动提交信息来建立 自己的链接索引，类似于现在大家熟知的y a h 0 01 。 随着互联网的迅速发展，使得检索所有新出现的网页变得越来越困难，因此， 在m a t i l l e wg f a y 的w 删e 砌。基础上，一些编程者将传统的“蜘蛛”程序工作原理 作了些改进。其设想是，既然所有网页都可能有连向其他网站的链接，那么从跟 踪一个网站的链接开始，就有可能检索整个互联网。到1 9 9 3 年底，一些基于此原 理的搜索引擎开始纷纷涌现，其中以j u m p s t a t i o n ，1 1 l ew 叫dw i d ew - e bw b 衄和 r 印o s i t o r y - b 必e ds o f h a r ee n g i i l e e 血g ( r b s e ) s p i d e r 最负盛名。 1 7 北京化工大学硕士研究生学位论文 最早现代意义上的搜索引擎出现于1 9 9 4 年7 月。当时m i c h l m a u l d i n 将j o l l n l e a v i t t 的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的l y c o s 。同年4 月，斯坦福( s t a l l f o r d ) 大学的两名博士生，d 州d f i l o 和美籍华人杨致远( g e r r y y h g ) 共同创办了超级目录索引呦o o ，并成功地使搜索引擎的概念深入人心。 从此搜索引擎进入了高速发展时期。目前，互联网上有名有姓的搜索引擎已达数 百家，其检索的信息量也与从前不可同日而语。比如最近风头正劲的g o o g l e ，其 数据库中存放的网页已达8 0 亿之巨。到现在，搜索引擎已经深入到人们的日常生 活中，可以说人们已经离不开搜索，所以就更需要对目前的搜索引擎技术进行研 究并完善和提高。 随着搜索技术的发展，纯粹的w e b 搜索由于受到i e 的束缚，因而表现出应 用能力偏低，而基于桌面的搜索则相当于一个“客户端+ 数据库”这样的应用模 型，这也使得搜索功能的多样化，个性化成为可能。作为目前尚未完全成熟的技 术，想完全准确定义桌面搜索比较困难。不过可以肯定的是首先桌面搜索基于w e b 搜索引擎，其次桌面搜索由于加载了客户端使的用户搜索更加方便更加快捷，也 就是它是一个更好的搜索引擎。桌面搜索技术的推出改变了传统的搜索规则，它 不同于以往的“地址栏”搜索，用户可以在不打开任何浏览器的情况下，随时搜 索自己需要的数据：不管是在浏览新闻，还是在编辑文件，收发b m a i l ，或是玩 游戏，听m p 3 ，只要用户有需求，就可以随时完成搜索。桌面搜索真正实现了“以 用户为中心”的网络服务方式，它使用户可以在不知道复杂网址，不打开i e 浏览 器，也不用传统搜索方式的情况下，实现搜索的“无处不在”。正是因为桌面搜索 技术能够提供直接搜索的重要功能，因此在业界倍受瞩目。可以说，搜索功能走 进桌面任务栏是一个相当重要的发展，因为这意味着一种网络搜索的新方式正浮 出水面，也意味着搜索将不再是网络浏览器的专利。今后，网络搜索将会逐步地 脱离浏览器，慢慢成为个人电脑通用的桌面应用。“搜索的方式已经不再是先打开 浏览器，然后登陆搜索网站，然后键入关键字才能进行搜索，今后搜索就直接内 建在你工作的一部份。” 桌面搜索作为搜索领域的新生力量，在技术上比较复杂，综合了多门计算机 学科，其中搜索排名和建立索引数据库的部分至今还是各大公司研发机构的重点。 综上所述，桌面搜索引擎是一项很有挑战性的课题，其涉及面很广，包含数 学、算法、人工智能、编译原理等多个领域，作为研究目标，很有必要建立一套 北京化工大学硕士研究生学位论文 能够适合中文英文文献的，运行服务端和客户端的桌面搜索引擎系统。 2 2 系统总体结构 搜索引擎的技术基础是全文检索技术，从2 0 世纪6 0 年代，国外对全文检索 技术就开始有研究。全文检索通常指文本全文检索，包括信息的存储，组织，表 现，查询，存取等各个方面，其核心为文本信息的索引和检索，一般用于企事业 单位。随着互联网信息的发展，搜索引擎在全文检索技术上逐渐发展起来，并得 到广泛的应用，但搜索引擎还是不同于全文检索。搜索引擎和常规意义上的全文 检索主要区别有以下几点【2 4 】： a 数据量：传统全文检索系统面向的是企业本身的数据或者和企业相关的数 据，一般索引库的规模多在g b 级，数据量大的也只有几百万条；但互联网网页 搜索需要处理几十亿的网页，搜索引擎的策略都是采用服务器群集和分布式计算 技术。 b 睡容相关性：信息太多，查准和排序就特别重要，g o o g l e 等搜索引擎采 用网页链接分析技术，根据互联网上网页被链接次数作为重要性评判的依据；但 全文检索的数据源中相互链接的程度并不高，不能作为判别重要性的依据，只能 基于内容的相关性排序。 c 安全性：互联网搜索引擎的数据来源都是互联网上公开的信息，而且除了 文本正文以外，其它信息都不太重要；但企业全文检索的数据源都是企业内部的 信息，有等级，权限等限制，对查询方式也有更严格的要求，因此其数据一般会 安全和集中地存放在数据仓库中以保证数据安全和管理的要求。 d 个性化和智能化：搜索引擎面向的是互联网访问者，由于其数据量和客户 数量的限制，自然语言处理技术，知识检索，知识挖掘等计算密集的智能计算技 术很难应用，这也是目前搜索引擎技术努力的方向；而全文检索数据量小，检索 需求明确，客户量少，在智能化和个性可走得更远。 搜索引擎与全文检索除了以上的区别外，还结合互联网信息的特点形成了三 个不同的类型： 全文检索搜索引擎： 全文搜索引擎是名副其实的搜索引擎，国外具代表性 的有( 沁o g l e ( h 郇：价n w g o o g l e c o m ) ，y a h o o ( h t i p ：s e a r c h y a h o o c o m ) ， 1 9 北京化工大学硕士研究生学位论文 a 1 l t h e w e b ( h 即：， w v a l l t l l e w e b c o n l ) 等，国内著名的有爱问 ( h n p ：n v w 认s k c o m ) ，中搜( m p ：， n z l l o n g s o u c o m ) 。它们都是通过 从互联网上提取的各个网站的信息( 以网页文字为主) 而建立的数据库，检索与 用户查询条件匹配的相关记录，然后按一定的排列顺序将结果返回给用户，也是 目前常规意义上的搜索引擎。 目录搜索引擎： 目录索引虽然有搜索功能，但在严格意义上算不上是真正 的搜索引擎，仅仅是按目录分类的网站链接列表而已。用户完全可以不用进行关 键词查询，仅靠分类目录也可找到需要的信息。国外比较著名的目录索引搜索引 擎有y a h o o ( h t t p ：肌删w y a l l o o c o m) o p e nd i r e c t o r yp r o j e c t ( d m o z ) ( 1 帅： ，d m o z c o m ) ，l 0 0 k s m a r t ( 胍p ：，n _ 啊1 0 0 k s m r t c o m ) 等。国 内的搜狐( h t t p ：、删