（系统工程专业论文）桌面搜索引擎的设计与实现.pdf

大连理工大学硕士学位论文 摘要 随着互联网的普及，搜索引擎得到了快速的发展，对人们的生活产生了巨大的影响。 现在随着个人电脑中硬盘容量的越来越大，硬盘里所包含的文件的数量也越来越多，于 是如何在海量文件中快速准确的找到自己需要的文件，成为p c 用户的一个重要需求， 因此桌面搜索引擎的设计与开发变得极其重要。基于此，本文设计与实现了一款桌面搜 索引擎，具体如下： 首先设计了桌面搜索引擎的整体框架，将整个桌面搜索引擎分为四个模块：文件解 析模块，中文分词模块，查询模块和用户界面模块。 其次设计了文件解析模块，用来实现文件格式的转化。该模块针对多种文件格式进 行解析，可解析的文件格式除了常用的o f ! f i c e 文件，文本文件，c p p 文件，h 文件，还 包括p d f 文件，c h m 文件，h l p 文件，x m l 文件，i n f 文件，c s v 文件等，并且对 于p d f 文件本文改进了其解析算法，对其加入了解密处理。通过本模块的设计可以满 足公司对多种文件格式进行查询的需求。 再次设计了中文分词模块。该模块主要是对解析后的文件加入中文分词处理，采用 的是基于层叠隐马尔可夫模型的汉语词法分析系统，通过本模块的设计桌面搜索引擎提 高了其查询的准确性和查询的速度。 然后设计了查询模块和用户界面模块。查询算法为k m p 算法，其搜索速度快，搜 索结果准确。用户界面模块为用户提供了多个结果输出界面，可以使用户从多角度查看 搜索结果，通过本模块的设计桌面搜索引擎提高了其方便性和实用性。 最后通过实例验证了本文所设计的桌面搜索引擎的优良性能，通过实例可以看出本 文所设计的桌面搜索引擎是绿色版的，具有体积小，搜索速度快，搜索结果准确等特点， 用户可以通过本桌面搜索引擎实现对多个关键字进行搜索，并可以在结果显示对话框中 查看搜索结果。 关键词：桌面搜索引擎；文件解析；文件解密；中文分词 桌面搜索引擎的设计与实现 d e s i g na n di m p l e m e n t a t i o no fd e s k t o ps e a r c he n g i n e a b s t r a c t n e t 、o r ks e a r c he n 酉n e ( e 召，t r a d i t i o n a ls e a r c he n 百n e s ) h a sg o tah u g ed e v e l o p m e n tw i t h t h ep o p u l a r i t yo ft h ei n t e m e t i tm a d eat r e m e n d o u si i i l p a c t0 np e o p l e sl i f c m e a i l w h i l e ，i tm a d e t h ec a p a c i t yo f h a r dd i s ki np e r s o n a lc o m p u t e ri n c r e a s e do b v i o u s l y t h e r ea r el o t so ff i l e s ( e g ， o 施c e ，e - m a i l ，c h m ，p d f a n dh l p ) i i lt h ep cd i s k t h e nh o w t os e a r c hf i l e si nt h eh u g ed j s k b e 姗eas e r i o u sp r o b l e m s ot h ed e s k t o ps e a r c he n g i n ei sr e q u i r e dt 0r e s o l v et h ep r o b l e m f i r s to fa l l ，t h ew h o l ef r a m e w o r ko ft h ed e s k t o ps e a r c he n 西n eh a sb e e nd e s i g n e di nt l l i s p a p e r t h ed e s k t o ps e a r c he n 酉n ei sd i v i d e di n t of o u rm o d u l e s ：t h ed o c l l m e n t 扑a l y s i sm o d u l e ， t h ec h i n e s ew o r ds e 肿e n t a t i o nm o d u l e ，t h es e a r c hm o d u l e 锄dt h eu s e ri n t e r l i a c c ； s e c o n d ，m 锄yk i n d so ff i l e sh a v eb e e nr e s o l v e di nt h i sp a p e r ( e g ，o 仃i c e ，e - m a i l ，c h m ， p d f ，h l p ，x m l ，d 疆a n dc s v ) t h ed e s k t o ps e a r c he n 垂n ec a nm e e tt h ec o m p a n y sn e e d s f o rav a r i e t yo ff i l ef o 彻a t st h r o u g ht h i sm o d u l e n i r d t h ec h j n e s ew o r ds e g m e n t a t i o nw h i c hb 硒e d 伽h i e r 盯c h j c a lh j d d e nm a r k o v m o d e lh a sb e e na d d e di n t od e s k t o ps e a r c he n 酉n e nc 孤i m p r 0 v et h ed e s k t o ps e a r c he n 百n e s s e a i c hs p e e da n ds e a r c hr e s u l tt h r o u g l lt h i sm o d u l e ； f b r t h ，t h es e a r c hm o d u l ew h i c hb a s e do nk m pa l g o r i t h mh a sb e e nd e s i g n e di nt h i sp a p e r a n d 柚o p t i m i z e du ih a sb e e nd e s i 印e df o ru s e r s n eu ic 觚b e d i v i d e di n t os e v e r a ls e c t i o n s n eu s e f sc 卸1 0 0 kf o rt h er e s u l t s 劬md i 胝r e n ta n 百e s p nl a s t ，t h ed e s k t o ps e a f c hs o f f w a f ec a nt e s t 锄dv e r i f yi t sf i i n c t i o nb y 姐e x a m p l ew h i c h i n t h i sp a p e r ni ss m a l l 觚dd o e sn o tn e e dt 0i n s t a l l 1 1 h es e a r c hs p e e d 锄ds e a r c hr e s u l t so f t h ed e s k t o ps e a r c he n g i n ea r eb o t hv e r yg o o d t h eu s e r sc 锄s e a r c hm u l t i p l ek e y w o r d s ，锄d f i n dt h es e a i h r e s u l t si i lt h ed i a l o gb o x 】s 对w o r d s ：d e s k t o ps e a r c he n g i n e ；d o c u m e n ta n a i y s i s ；f i l ed e c r y p t j o n ；c h i n e s e w 0 r ds e g m e n t a t j o n 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 作者签名：j j 警，_ 一日期：率年必斗日 大连理- t 大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 大连理工大学硕士学位论文 1 绪论 1 1 桌面搜索引擎简介 桌面搜索引擎也称为个人桌面引擎或个人硬盘搜索引擎，是对个人电脑上存储的信 息进行查找的检索工具i l j 。 随着互联网的普及，网络搜索引擎对人们的生活产生了巨大的影响【2 1 。同时，现在 个人电脑的硬盘容量越来越大，已经达到t b ，硬盘里包含的0 艏c e 文档、电子邮件、 保存的网页、p d f 文档、c h m 文件、h l p 文件等的数量都非常大，在如此多的文件中 查找某个文件变的非常困难，因此能够准确快速的查找到需要的信息成为现在电脑用户 的一个重要要求【3 l 。 桌面搜索与网络搜索不同，首先从技术上看1 4 j ，只有桌面搜索才算是全方位的搜索。 它方便快捷，不用登录网络，就能找到用户要查找的内容。它将搜索业务深入到个人电 脑中，除了能找到用户所需要的网络信息之外，还可以帮助用户从个人电脑的海量资料 中快速地查找到想要的信息，包括文件、电子邮件、即时通讯信息以及网页浏览历史记 录等【5 j 。其次，由于在电脑硬盘上的文档之间几乎没有什么联系，因此关于网页排名的 算法不适用于桌面搜索【引，所以对桌面搜索的结果进行排序就不太重要。最后从市场发 展来看，桌面搜索市场的发展潜力最大。尽管搜索市场竞争非常激烈，但桌面搜索市场 的增长潜力被普遍看好。有关市场研究数据显剩1 7 j ：中国的搜索引擎市场2 0 0 3 年达到了 5 2 亿元人民币，比2 0 0 2 年的2 3 亿一年增长了1 2 7 ，2 0 0 4 年中国搜索引擎市场达8 8 亿元，2 0 0 6 年达2 4 亿元。而全球搜索引擎产业，在2 0 1 1 年将有望达到7 0 亿美元。事 实上，各大搜索公司近来的业绩都在高速提高，各大搜索引擎厂商纷纷推出了自己的桌 面搜索引擎。 1 2 主流桌面搜索引擎介绍 现在桌面搜索的开发已经成为了互联网领域的最大亮点，也为搜索领域带来了新的 发展机会，随着众多厂商的加盟。桌面搜索引擎的竞争日趋激烈。目前最流行的桌面搜 索引擎有以下几款：g o o 舀ed e s k t o ps e a r c h ，百度硬盘搜索，网络猪，微软桌面搜索。 ( 1 ) g o o 甜ed e s k t o p s e a - c h 2 0 0 4 年1 0 月5 日，g o o 酉e 发布了自己的桌面搜索工具：g o o 酉ed e s k t o ps e a r c h ， 简称为g d s ，这是一款强大的计算机硬盘搜索工具。目i j 的最新版本是5 7 0 8 0 2 2 2 4 3 8 ， 使用的系统环境为w i n d o w sv i s t a x p 2 0 0 0s p 3 + ，另外g d s 也有u n u x 版和m a c 版。 g d s 的特点主要有1 8 】： 桌面搜索引擎的设计与实现 g d s 会自动保留即时通讯的谈话记录，还能复制历史记录，通过g d s 可以查找 自己的电子邮件、媒体文件、网页历史记录、文档、g m a i l 等内容； 拥有先进的搜索技术； 不用上网就可以查看浏览过的网页； 可以直接通过桌面栏进行搜索； 通过快速查找项启动应用程序并立即开始搜索，还可以补充工具栏，将个性化 信息集中放置； 可以通过开发人员编写的插件补充工具栏。 ( 2 ) 百度硬盘搜索 百度硬盘搜索是世界上第一款中英文桌面搜索工具。它可以在电脑中快速的查找信 息；还可根据文件的类型和属性信息，自动生成目录。百度硬盘搜索目前的版本：2 7 ， 大小：1 9 3 m b 。 百度硬盘搜索的功能特点主要有以下几点1 9 】： 可以通过添加高级搜索，使查找的结果更准确； 可以支持语法搜索； 可以给搜索结果页面增加细分目录，进一步的缩小搜索范围； 增加了很多小功能，方便实用： 可以支持o f f i c e 2 0 0 7 文件格式； 优化了搜索性能，减小了安装文件的体积； 可以支持很多浏览器中。 ( 3 )网络猪 2 0 0 4 年2 月，中国搜索推出了一款桌面搜索产品：网络猪，网络猪是一款基于搜索 引擎并能整合多项功能( 如：m p 3 点歌、视频点播下载电影、聊天、短信、天气预报、 定制最新新闻等) 的桌面软件。它不需要打开i e ，只要输入关键词，就可以在桌面上实 现搜索。网络猪的搜索框可以进行网页、新闻、网站、行业、图片、m p 3 、论坛、词典、 下载等9 项搜索。 网络猪的主要功能特点如下1 1 0 1 ： 越过传统的搜索模式，可以实现划词搜索； 可以订制专题新闻，设置自己的新闻中心； 设有m p 3 点歌台，可以通过笔画、字数和拼音多方位搜索自己喜欢的音乐； 设有办公小秘书，为用户提供日程提醒、即时贴、常用软件快捷方式等服务； 大连理工大学硕十学位论文 集合型聊天工具，可以将q q 、m s n 和网络猪的即时通讯起应用； 设有天气预报功能。 ( 4 ) 微软桌面搜索 2 0 0 4 年1 2 月微软m s n 推出了桌面搜索软件的测试版。这个m s n 搜索工具的主要 功能是快速搜索计算机硬盘的文件，w i n d o w s 的桌面搜索集成在m s nt c l o l b a r 里。2 0 0 8 年6 月，微软推出了其桌面搜索工具w i n d o w ss e a r c h4 o 的最终正式版，此版本支持多 种操作系统和包括简体中文在内的多国语言川。w i n d o w ss e a r c h4 0 可以即时搜索整台 电脑，查找文档、电子邮件、音乐、照片、视频等各种内容。 微软桌面搜索的主要功能特点为1 1 2 j ： 拥有桌面、浏览器、资源管理器三种搜索工具栏，可以在这些工具栏中直接输 入文字搜索； 可以搜索在系统中已注册的所有文件类型，也可手动添加未知的文件类型； 可以通过选项卡式浏览提高网页浏览效率； 设有弹出窗口阻止程序可以有效的阻止弹出窗口； 可以在搜索结果页中突出显示搜索的文字： 可将搜索结果与系统操作高度集成，可直接对搜索结果进行系统右键菜单操作， 比如重命名、复制和删除等，支持批量操作，处理搜索结果相当方便。 以上介绍的都是非常出色的桌面搜索工具，受到了广大使用者的好评，但是他们也 存在这一些不足，例如： ( 1 ) 它们都是需要安装的软件，虽然安装文件不是很大，但是需要的安装目录比 较大，例如g o o 西ed e s k t o ps e a r c h 安装时要求所在分区要有1 g b 的剩余空间； ( 2 )索引文件很大，g 0 0 甜ed e s k t o ps e a r c h 等默认对全盘进行索引，因此随着时 间的增长，硬盘里的索引文件会越来越大，就会影响系统运行速度；虽然w i n d o w ss e a r c h 默认不进行全盘索引，只对“我的文挡 和“d o c u m e n t s 锄ds e t t i n g s 等常用文件夹进 行索引，但是它没有给出明确的索引设置说明，增加了操作难度： ( 3 ) 除了微软的桌面搜索以外，其他的桌面搜索工具都不可对加密的p d f 文件进 行检索； ( 4 ) 安全性不够。这也是企业最在意的问题，由于桌面搜索引擎功能的强大，对 用户的整个硬盘信息进行索引，如果个人计算机接入互联网，就存在着个人隐私暴露 及知识产权泄露的相关问题。因为当我们利用这些桌面搜索工具进行搜索时，搜索引 擎将查询请求发送给两个不同的程序。以g 0 0 酉ed e s k t o ps e a r c h 为例【1 3 】，一个请求发送 到网络，进行网页搜索；另一个将相同的查询请求发送到本地运行的桌面搜索程序，在 桌面搜索引擎的设计与实现 事先建立的索引中进行查询。另外g d s 还会自动的保留用户的o u t l 0 0 k 里的电邮信 息、即时通讯的谈话记录( 即使用户已经删除，它也会自动恢复) 、用户的上网浏览记 录( 即使是网上银行等保密网站的内容) ，g d s 还能复制历史记录，永远把它保留下 来，这就意味着即使你已经将一些机密的文件删除了，通过g d s 还是能将他们一一搜 索出来，将所有的机密暴露无疑。 因此现在很多公司都致力于开发自己的桌面搜索工具，本文就是一款为公司设计的 桌面搜索工具。 1 3 本文的工作 本文以实现对电脑硬盘里的所有文档( 特别是公司常用到的文档) 进行全文搜索为 目标，使用户可以快速的找到所要查找的关键字。 本文设计的是一款绿色版的桌面搜索软件，其体积很小，为了方便用户对多个关键 字进行查询，本文提供了关键字文件，即将所有要查询的关键字放入一个文件罩；通过 本软件用户还可以对多个文件夹进行搜索。最后在结果显示对话框中对搜索到的文件建 立超链接，并可生成专门的保存结果文件，在这些文件中用户可以看到搜索的关键字在 搜索到的文件中的位置，使用户可以从多角度查看搜索结果。 本文的具体安排如下： 第一章绪论 本章主要介绍了桌面搜索引擎的定义，发展现状，并介绍了几款现有的常用的桌面 搜索引擎。 第二章桌面搜索引擎的总体设计 本章主要根据公司的具体要求设计了本文开发的桌面搜索引擎的框架结构。 第三章p d f 文件结构的解析与文本内容提起 本章实现了对p d f 文件的格式转换，并可对加密的p d f 文件进行解析。 第四章帮助文件和w o r d 文件解析模块 本章主要对c h m ，h l p ，w o r d 格式的文件主要结构特点进行了分析，然后分别实 现了对它们的解析。 第五章中文分词 本章首先分析了中文分词的原理，然后介绍了i c t c l a s 的分词原理、使用特点以 及使用接口。 第六章桌面搜索引擎的设计与实现 一4 一 大连理t 大学硕士学位论文 本章首先介绍了本文所设计的桌面搜索引擎的具体设计框架，然后通过实例分析了 其性能。 结论 对本篇论文所做的工作和研究进行了总结，并对后续研究给予了展望。 桌面搜索引擎的设计与实现 2 桌面搜索引擎的总体设计 由于现有的桌面搜索引擎的不足，现在很多公司致力于开发自己的桌面搜索引擎， 本文就是一款为公司设计的桌面搜索工具，关于公司的相关要求如下： ( 1 ) 保证信息安全； ( 2 ) 保证查询速度，将查询限制在本地文件中； ( 3 ) 保证查询结果的准确性。 对于客户的第一点要求，解决方案为将查询的文件夹限制在电脑硬盘中，不自动保 留用户的即时通讯的谈话记录、用户的o u t l o o k 电邮信息、用户的上网浏览记录， 不复制历史记录。 对于客户的第二点要求，在现有的桌面搜索工具中，基本都有建立索引的模块，通 过建立索引可以提高搜索速度，特别是当电脑硬盘空间很大，文件数量很多时【1 4 1 。但是 这同时也存在一个问题，即当电脑硬盘空间很大，文件数量很多时，索引也会很大，因 此所占的空间也很大，随着时间的增长，索引文件会越来越大，就会严重影响系统运行 速度。并且它们都是针对全盘进行搜索，不能满足用户想对特定文件夹进行搜索的要求。 在本次开发中，公司要求只是针对公司的项目文件进行查询，其数据量不大，但是要限 定文件夹，因此本次设计的桌面搜索引擎中将不包含对硬盘中所有文件进行建索引的模 块，但是增加了用户可以对多个文件夹进行查询的要求。另外针对用户提出对多个关键 字进行查询的要求，本文提出将所有的关键字写入到一个t x t 文件中，当开始查询时， 从用户选定的关键字文件中读取关键字。 对于客户的第三点要求，由于公司提出查找的关键字必须实现完全匹配的要求，因 为他们所要查找的关键字都是在项目中需求的，需要百分之百的匹配，于是查询算法选 用字符串比较算法。 针对用户的以上需求，设计了整个桌面搜索引擎的框架，将全文分为：文件解析模 块，中文分词模块，查询模块，用户界面四部份。 其中文件解析模块用于将要搜索的文件格式转换为文本文件格式。本文可以搜索的 文件格括t x t ，h t m ，h t m l ，x m l ，c p p ，c ，h ，r c ，i n f ，c s v ，c h m ，h l p ，d o c ，p p t ，x l s ，p d f 以及二进制文件等。通过文件解析模块可以使这些不能直接由程序读取的文件变为可以 直接读取的格式。 中文分词模块采用了中科院的分词系统i c t c l a s ，i c t c l a s 的主要功能包括：中 文分词，词性标注，命名实体识别，新词识别，同时支持用户词典。在本模块中用户可 大连理t 大学硕士学位论文 以按照搜索的需求，将要搜索的关键词添加到用户字典中，提高了搜索效率以及搜索的 准确性。 查询模块处理的是经过文件解析模块和中文分词模块处理后的文件，由于用户要求 查找到的结果必须是和关键字完全匹配的，因此这里采用k m p 算法，k m p 算法是对模 式匹配算法的一种改进算法，具有比较速度快，正确性高的优点。 用户界面包括查询界面，查询结果显示界面，在查询结果显示界面中用户可以直接 查看搜索到的文件设置，也可以查看整个结果输出文件。 本文设计的桌面搜索引擎的框架如图2 1 所示。 用户界面( 查询界面) 上 文件解析模块 土上j上上r i 二进制文件p d f 文件解c h m 文件h l p 文件解w o r d 文件具他义伞义 i 解析模块析模块解析模块析模块解析模块 件解析模块 l上1 l上 一 r11 - 中文分词模块 查询模块 上 用户界面 ( 查询结果显示界面) 图2 1 桌面搜索引擎的总框架 f i g 2 1 t h ew h o l ef r a m e w b r ko ft h ed e s k t o ps e a r c he n g i 舱 桌面搜索引擎的设计与实现 3p d f 文件解析模块 3 1p d f 文件简介 p d f 是a d o b e 公司创建的用于进行全球电子文档存储与分发的一种电子文件格式。 它可以不依赖操作系统的语言和显示设备，保留原文件的包括字符、字体、版式和色彩 在内的所有信息。加之它对文字图像的高压缩，使得p d f 文件的尺寸很小，非常适合 网络传输、共享和打印【1 5 j 。 p d f 主要由三项技术组成：p o s t s c r i p t ( 一种页面描述语言) 、字型嵌入系统、资料 压缩及传输系统。 p d f 格式的主要特点f 1 6 】如下： ( 1 ) 高兼容性 p d f 是对文字图像数据都兼容的文档格式，它独立于各种计算机平台和应用程序， p d f 文档可以使用二进制( b i n a r v ) 或a s c i l 编码，实现跨平台作业。 ( 2 ) 高压缩性 p d f 文件是文字、图像的压缩文档格式。它使用多种方法来达到缩减原p o s t s c r i p t 文档的目的，文档的存储空间很小，适合网上传输。 ( 3 ) 设备独立性 p d f 文件具浏览不受操作系统、网络环境、应用程序版本、字体的限制。p d f 文档 是为整合多种输出选项的网络所设计的，它是设备独立的最佳输出格式。 ( 4 ) 页面独立性 p d f 文档与p o s t s c r i p t 文档不同，p d f 文档中的每一页与其它页是互不相关的，它 以单页为单位。 ( 5 ) 可扩充性 p d f 有p l u g i n 的接口结构，可通过p l u g i n 方便集成，增加新功能。同时可使用 l 0 t u s n o t e s 数据库建立p d f 文档数据库和有效进行电子文档数据管理。 ( 6 ) 保护性 p d f 文档允许设定密码，可以防止非法使用。例如必须使用密码才允许阅读、打印、 复制、注释或修改。 p d f 文件是由一个p d f 文档和其它的支持数据组成。一个p d f 文档可以包含一个 或多个页面，每个页面都是由文字、图形和图像的任意组合成的。p d f 文档还可以包含 大连理工大学硕士学位论文 一些超文本链接、声音和动画等信息。p d f 文件还包含一些p d f 版本号、文件中重要 结构的位置等其它信息。为了更好地理解p d f 文件，可把p d f 文件分解成三个部分： p d f 的对象，p d f 的物理结构，p d f 的逻辑结构。 3 1 1p d f 的对象 p d f 的对象是一组基本数据类型，这些基本的数据类型有八种【1 7 l ：布尔型( b 0 0 1 ) 、 数字( n u m e r i c ) 、字符串( s t r i n g ) 、名字( n a m e ) 、数组( a r r a y ) 、字典( d i c t i o n a r y ) 、 流( s t r e 锄) 、空对象( n u l l ) 。 b 0 0 l ：用关键字t n l e 或f a l s e 表示，可以是a 玎a y 对象的一个元素，或d i c t i o n a r ) r 对 象的一个条目。 加m e r i c ：包括整形和实型，不支持非十进制数字，不支持指数形式的数字。 s t 血g ：由一系列0 - 2 5 5 之间的字节组成，一个s t r i n g 总长度不能超过6 5 5 3 5 。s t r i n g 有以下两种方式： 由( ) 包含起来的一个字串，中间可以使用转义符“”。 由 包含起来的一个1 6 进制串，两位表示一个字符，不足两位用0 补齐。 n 锄e ：由一个前导和后面一系列字符组成，最大长度为1 2 7 。n 锄e 是不可分割的、 唯一的。 蚴y ：用【】包含的一组对象，可以是任何p d f 对象( 包括a 玎a y ) ，可以通过a m y 的嵌套实现任意维数的锄y ( 但是一个a n a y 的元素不能超过8 1 9 1 ) 。 d i c t i o n a 巧：用“ 包含的若干组条目，每组条目都由k e y 和v a l u e 组成， 其中k e y 必须是n 锄e 对象，并且是唯一的，v a l u e 可以是任何p d f 的合法对象( 包括 d i c t i o n a r v 对象) 。例： s t r c a m ：由关键字s t r e a m 和e n d s t r e 锄包含一系列字节。例： 50 o b j s t i e 锄 b t f 12 4 t f 2 3 4 2 3 5t d ( h e l l ow o f l d ) 1 ：i e t e n d s t r e a m 一9 一 桌面搜索引擎的设计与实现 d o b j 说明s t r e a m 对象的字节数，从b t 开始，e t 结束，包括中间的行 结束符。 s t r c a m 说明一个流对象的开始。 b t 说明一个文字对象的开始。 f 12 4t f ：字体信息。 2 3 4 2 3 5t d ( h e l l ow o r l d ) t j ：2 3 42 3 5 说明这一行文字放置的位置，t d 代表当前x ， y 坐标分别加上2 3 4 和2 3 5 就是文本的位置，因为在该例子中只有一个对象，那么它的 位置就是( 2 3 4 ，2 3 5 ) ，如果下个对象位置信息为1 9 ，1 4t d ，那么它的位置应该就是 ( 2 3 4 + 1 9 ，2 3 5 + 1 4 ) 也就是( 2 5 3 ，2 4 9 ) 。( h e l l ow o r l d ) t j 说明文本的内容，如果这里 是文本的内容可以写成1 6 进制，用 包含。e t 说明文字对象的结束，e n d s t f e a m 流对 象的结束。 n u l l ：用n u u 表示，代表空。如果一个k e y 的值为n u l l ，则这个k e y 可以被忽略。 另外，p d f 对象可以分成直接对象( d i r e c t0 b j e c t ) 和间接对象( i n d i r e c tb j e c t ) 。 p d f 文档中使用了大量的间接对象和间接引用。 3 1 2p d f 的物理结构 p d f 的物理结构决定了对象在p d f 文件中的存储方式、访问方式和更新方式。p d f 的物理结构( 见图3 1 ) 包括四个部分：文件头、文件体、交叉引用表和文件尾【1 8 l 。 文件头 ( h e a d e r ) 文件体 ( b o d v ) 交叉引用表 ( c r o s sr e f e r e n c et a b i e ) 文件尾 ( t r a i l e r ) 图3 1p d f 文件的物理结构 f 嘧3 1 t h ep h y s i c a ls t m c t u r eo fp d ff i l e ( 1 ) 文件头( h e a d e r ) p d f 文件的第一行，格式：p d f _ 1 5 ，表示当前文件的版本是1 5 。 ( 2 ) 文件体( b o d y ) 大连理工大学硕士学位论文 p d f 文件中用到的所有对象，包括文本图象音乐视频字体馏连接加密信息等等， 格式如下： 2 0 o b j e n d o b j 第一个数字称为对象号，标识一个对象，第二个是产生号，是来表明它在被创建后 的第几次修改，所有新创建的p d f 文件的对象号应该都是0 ，即第一次被创建以后没有 被修改过。上面的例子就说明该对象的对象号是2 ，而且创建后没有被修改过。对象的 内容应该是包含在 之间的，以关键字o b j 开始，最后以关键字e n d o b j 结束。其中 省略号部分是p d f 规定的任意合法对象( 一共8 种) 。 ( 3 ) 交叉引用表( c r o s s r e f e r e n c et a b l e ) 所有p d f 对象的引用表，其格式如下： x r e f 1 1 0 2 6 o ( ) 0 0 0 0 0 0 1 60 0 0 0 0n 0 1 ) 0 | 0 0 0 】3 0 7o ( 。) 0 0 0n 其中x r e f 是开始标志，表示以下为引用表内容；1 1 02 6 表示从对象号为1 1 0 开始连 续有2 6 个对象( o ，1 ，2 5 ) ，分别用2 6 行来表示。每行的前1 0 个数字代表这 个对象相对文件头的偏移地址，后面5 个数字只有当这个对象被删除的时候才有用，表 示这个对象被删除后又被重新生成后的对象号最后一位f 或n 表示对象是否被使用( n 表示使用，f 表示被删除或没有用) 。 ( 4 ) 文件尾( t r a i l e r ) t r a i l e f 是整个p d f 文件的入口点，文件尾中主要包含了交叉引用表的地址、文件 体的根对象c a t a l o g 的地址以及加密等信息。形式如下： t 1 a i l e r s t a n x r e f 5 5 3 e o f 桌面搜索引擎的设计与实现 t r a i l e r 后面紧跟一个字典，包含若干的键值对。 具体含义如表3 1 所示： 表3 1 文件尾的键值 t a b 3 1n e k e ya n dv a l u eo f n e t r a i l e r s t a n x r e f 后面的数字表示交叉引用表的开始位置； e o f ：文件结束符。 3 1 3p d f 的逻辑结构 p d f 的逻辑结构【w 】指定了基本对象类型表示p d f 的文档的方式，包括：页面、注 解、超文本链接、字体等。p d f 的逻辑结构反映了文件体中间接对象间的等级层次关系。 p d f 的逻辑结构是一种树型结构。 文件尾包含了文件体的c a t a l o g 的地址。c a t a l o g 是该p d f 文档的根对象，根节点 下有四棵子树【驯如下： ( 1 ) 页面树( p a g e st r e e ) ：所有的页面对象都是树的叶节点。每一页包含了对 该页的内容( c o n t e m s ) ，注释( a m n o t a t i o n s ) ，缩略图( t h u m b n a i l ) 的引用。其中， c o n t e ms t r e 锄( 内容流) 描述的是该页的文本内容。 ( 2 )目录树管理书签( b 0 0 k m a r k ) ：p d f 文档中的o u t l i n et r e e ( 大纲) 是一个 树型层次结构。其中每个节点都是一个书签b o o k m a r k 。书签名( b o o k m a r kn a m e ) 和 具体的页面位置一一对应。应用程序能够按照书签名访问文档的内容。 ( 3 ) 线索树( n f e a d st r e e ) ：按树型结构组织文章的线索和线索下的文章块。 大连理工大学硕士学位论文 ( 4 ) 名字树( n a m et r e e ) ：建立了一个字符串和页面区域之间的关联。 一个p d f 文档的层次关系如图3 2 所示： 图3 2p d f 文件的逻辑结构 f 远3 2 7 n l el o g i c a ls t m c t u r eo fp d ff i l c s 3 2p d f 文件解析 根据上面的关于文件结构的分析可以看出，解析p d f 文件时应用程序应首先访问 文件尾，从文件尾中读取交叉引用表的地址和p d f 文件的c a t a l o g 根节点。根据交叉引 用表进而访问p d f 文档中的间接对象，从而读取整个p d f 文档。所以整个处理流程将 从寻找文件尾的t r a i l e r 关键字开始。 3 2 1p d f 文件解析流程介绍 根据以上介绍，本文将p d f 文件的解析过程设计( 见图3 3 ) 如下： ( 1 )首先查找文件尾t r a i l e r ，查找关键字“r ( o t ，r o o t 后的值即为c a t a l o g 字 典( 文件的逻辑入口点) 的对象号【捌。查找关键字“e n c r y p t ”，e n c r y p t 后的值即为加 密字典的对象号，如果没有找到说明此p d f 没有被加密。 ( 2 ) 通过c a t a l o g 根节点( 标签为厂r y p e c a t a l o g ) 找到页树节点p a g e s 。如果在第 一步中找到关键字“e n c r y p t ”，则转入其加密字典处，利用m d 5 ，r c 4 算法获得其加 密密钥。 ( 3 ) 转入p a g e s 里，查找关键字鼬d s ，其后的对象号标志着页对象p a g e 的位置， 也有可能仍是页树节点。 桌面搜索引擎的设计与实现 ( 4 ) 转入到页对象p a g e 中，查找关键字“c o n t e n t s ”，如果没有，则说明这是一 空页。查找关键字“f o n t ，读取其字体信息。 ( 5 ) 转入到c o n t e n t s 里，读取s t r e a m 和e n d s t r e a m 之间的内容存放到一个数组中， 如果在( 2 ) 中获得了加密密钥，则用获得的密钥对数组中的内容通过m d 5 和r c 4 算 法进行解密，否则直接进行下一步。 ( 6 ) 读取关键字“f i l t e r 后的解码名，对解密后的内容流进行解码，然后进行 解压缩。 图3 3p d f 文件的解析过程 f i g 3 3 t h er e s o l v i n gp r o g r e s so fp d ff i l e 大连理丁大学硕十学位论文 p d f 用过滤器( f i l t e r ) 来表示内容流所采用的压缩算法。常见的过滤器有a s c h e x 、 a s c i l 8 5 、n a t e 、l z w 、r u n k n 舀h 、c c t f a x 等，必须实现对过滤器的解码才能够从 内容流中提取出正确的信息。本文实现了压缩算法是a s c l l 8 5 的解压缩，首先检查是否 是此压缩算法，如果是进行解码，获得解码后的内容流。 3 2 2p d f 文件解密流程 a d o b e 开发的p d f 格式通过添加p d f 口令来增强文档的安全性，p d f 有两种口令： 权限口令和打开口令。权限口令用来设置控制权限，打开口令是用来控制用户打开p d f 文件的。如果对一个p d f 文件同时设置了打开口令和权限口令，那么在打开p d f 文件 时候只要输入任何一个口令就可以打开加密的p d f 文档。对这种加密过的p d f 文档仍 然可以对权限口令进行破解，p d f 格式的权限控制是通过为p d f 格式的正文部分加上 操作允许口令来实现的。如果操作允许口令为空，则没有权限控制。经过权限控制的 p d f 文档的内容虽然也是加密的，但是加密密钥可以通过文体本身包含的加密字典对象 计算得到，因此可以通过加密字典对象和p d f 生成加密密钥的规则来得到加密密钥， 从而对内容进行破解1 2 。 p d f 文件采用的加密算法为r c 4 算法，加密长度为( 4 0 1 2 8 ) 位。本文将针对用 r c 4 加密算法进行加密的p d f 文件进行解密。另外p d f 文件支持的比较成熟的单向散 列h a s h 算法：m d 5 算法。 m d 5 的全称是m e s s a g e d i g e s t 越g o r i t h m5 ，用于确保信息的传输完整一致。m d 5 最广泛被用于各种软件的密码认证和钥匙识别上【2 2 1 。m d 5 的典型应用是对一段信息 ( m e s s a g e ) 产生信息摘要，以防止被篡改，m d 5 被广泛用于加密和解密技术上。 m d 5 算法可以概括为【2 2 j ：将输入的信息进行5 1 2 位分组处理，然后将每个分组再 分为1 6 个3 2 位子分组，经过处理后，算法最终的输出为由四个3 2 位分组组成的字符 串，将这些分组组合后生成一个1 2 8 位散列值。 m d 5 算法的初始化步骤为：首先将信息填充为字节长度满足对5 1 2 求余的结果为 4 4 8 。此时信息的字节长度为n 宰5 1 2 + 4 4 8 ( n 为一个正整数) ，填充的方法为：将信息 用一个1 和多个0 填充，直到满足字节长度的要求。然后在上面得到的结果后面附加一 个填充前信息长度( 以6 4 位二进制表示) 。经过以上的处理后的信息字节长度为n 搴5 1 2 + 4 4 8 + “，即( n + 1 ) 幸5 1 2 ，这样就可以满足后面处理中对信息长度的要求。 初始化结束后，首先设置m d 5 算法中四个被称作链接变量的3 2 位整数参数【2 2 】： a = 0 】【0 1 2 3 4 5 6 7 ，b = 0 x 8 9 a b c d e f ，c = 0 x f e d c b a 9 8 ，d = o x 7 6 5 4 3 2 1 0 。然后进入算法的四轮 桌面搜索引擎的设计与实现 循环运算，循环的次数为原信息进行5 1 2 位信息分组的组数。将a ，b ，c ，d 分别复制 到a ，b ，c ，d 中。 m d 5 算法的主循环有四轮【2 2 】，第一轮进行1 6 次操作，每次的操作为对a 、b 、c 、d 中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子 分组和一个常数。然后再将上面得到的结果向右移动一个不确定的数，加上a 、b 、c 、d 中之一。最后用得到的结果取代a 、b 、c 、d 中的一个。 以下是每次操作中用到的四个非线性函数( 每轮一个) 。其中& 是与，i 是或，是 非， 是异或。 f ( x ，y ，z ) ；( x y ) i ( 一x ) z ) ( 3 1 ) g ( x ，y ，z ) = ( x & z ) l ( y & ( z ) ) ( 3 2 ) h ( x ，y ，z ) ix “y “z ( 3 3 ) ，伍，】，z ) = y “伍i ( _ z ) ) ( 3 4 ) 通过上面的公式可以看出1 2 2 1 ：若参数的对应位是独立的、均匀的，则结果的每一位 也是独立的、均匀的。 假设m j 表示消息的第j 个子分组( 从0 到1 5 ) 1 2 2 】， s 表示向右移动的位数，循 环算法可表示为： ，f ( 口，6 ，c ，d ，m f ，s ，) ：口t 6 + ( ( 口+ ( f ( 厶，c ，d ) + m f + ) s ( 3 5 ) g g ( 口，6 ，c ，d ，m f ，s ，) ：口- 6 + ( ( 口+ ( g p ，c ，d ) + m f + ) s ( 3 6 ) 删( 口，6 ，c ，d ，mj ，s ，) ：口= 6 + ( ( 口+ ( 日( 6 ，c ，d ) + 肘j + f j ) s ( 3 7 ) 口( 口