《[毕业设计论文]文件快速搜索引擎.doc》由会员分享，可在线阅读，更多相关《[毕业设计论文]文件快速搜索引擎.doc（41页珍藏版）》请在金锄头文库上搜索。
1、沈阳航空工业学院学士学位论文 摘 要文件快速搜索引擎院 系 北方软件学院 专 业 计算机科学与技术 班 号 4233302 学 号 200427333207 姓 名 胡启良 指导教师 张 恒 沈阳航空工业学院2006年6月摘 要众所周知，我们生活在信息大爆炸时代，每天的信息量太大了，足以将所有人湮没。在如此庞杂的新鲜信息与海量信息面前，人们如何找到适时有用或急需的信息，搜索引擎如此应运而生。本文主要论述了使用倒排文件的方法建立一个文件快速搜索引擎。详细阐述了整个应用系统的设计思路，及毕业设计课题的选题意义。给出了研究开发的过程，以及对设计思路和实现细节的考虑，并对各部分周期进行了详尽的分析和描
2、述，最终达成一个完整的设计方案。系统开发工具为Visual C+6.0，平台为WINDOWS XP Professional。关键字:倒排文件，搜索引擎- 36 -沈阳航空工业学院学士学位论文 AbstractAbstractAs everyone knows, we live in an era of information explosion, the daily volume of information is too great, to be all lost. In the case of fresh information and stock information utilize
3、d before, people need to find timely and useful information, which can search it. Search engines such came into being.This article discusses the use of the main methods of creating a document would platoon rapid document search engines. Detailed design of the entire application system, the selection
4、 of subjects and topics from design significance. Given the research and development process, and to consider the details of the design and realization of ideas and the cycle of a detailed analysis and description, the ultimate goal of a complete design.VC+6.0 tools for system development, the platf
5、orm for Windows XP Professional.Key words: opposing platoon documents, the search engine沈阳航空工业学院学士学位论文 第二章关键问题分析目 录摘 要Abstract目 录第一章 引 言11.1 本课题的研究背景11.1.1 索引文件构成11.1.2 索引文件的存储21.1.3 索引文件的操作31.1.4 利用查找表建立多级索引31.2 设计目标4第二章 关键问题分析52.1 索引算法分析52.2.1 散列文件的组织方式52.2.2 多关键字文件62.2.3 多重表文件72.2.4 倒排文件72.2 查找算法
6、分析102.2.1 顺序查找102.2.2 二分查找112.2.3 分块查找15第三章 系统设计173.1 程序的总体框架173.2 索引建立模块分析183.3 程序总体模块图19第四章 详细设计204.1 深入剖析倒排文件索引算法204.2查询的实现234.3界面设计25第五章系统性能分析及测试305.1系统性能分析305.1.1系统稳定性分析305.1.2系统安全性分析305.1.3系统实用性分析305.2系统测试315.2.1测试环境315.2.2测试数据的建立31第六章 结论与展望326.1 结论326.2 展望32致 谢33参考文献34第一章 引 言1.1 本课题的研究背景社会发展到
7、今天，已经进入了计算机的时代。在各行各业的发展中，只要是涉及到信息管理范围的领域，都需要由计算机来完成。原因当然很简单，因为计算机处理速度快，可靠性高，而且易于维护。人们对计算机如此依赖，主要是因为近年来计算机硬件的发展水平飞速增加。对硬件方面了解的人都知道，计算机硬件的发展基本上是一年乘一个倍数的增长，但是这种发展势头会一直这样持续吗？答案是肯定的，不。因为任何事物都是有极限的。计算机也一样。CPU的运算速度现在来讲基本上已经快到极限了，但人们对它的速度要求还远远不仅如此。这就出现了一个问题，既然硬件无法提高，而人的要求又无法满足，那应该怎么办呢？办法是有的，运用好的算法，可以节约硬件资源，
8、提高运算效率，一个很优秀的算法可以大大提升这些。文件内容查找是目前人们经常做的操作，很多软件都提供了文件内容查找的功能，如：Offcie办公软件、记事本、浏览器软件、写字板软件等。但是这些软件本身所带的查找功能多数是基于模式匹配（逐个字符比较）的方式制作的，当处理大规模文件时查询效率很低。在这样的背景下，我们提出了本课题，希望通过本题的研究，开发出一种文件内容快速查找工具，从而提高查找效率。如果要提高查找效率，必须对原文件建立索引文件，下面简单介绍一下索引文件的信息。1.1.1 索引文件构成1索引文件 索引文件由主文件和索引表构成。主文件：文件本身。索引表：在文件本身外建立的一张表，它指明逻辑
9、记录和物理记录之间的一一对应关系。2索引表组成 索引表由若干索引项组成。一般索引项由主关键字和该关键字所在记录的物理地址组成。索引表必须按主关键字有序，而主文件本身则可以按主关键字有序或无序。3索引顺序文件和索引非顺序文件（1）索引顺序文件(Indexed Sequential File) 主文件按主关键字有序的文件称索引顺序文件。 在索引顺序文件中，可对一组记录建立一个索引项。这种索引表称为稀疏索引。（2）索引非顺序文件(Indexed NonSequentail File) 主文件按主关键字无序的文件称索引非顺序文件。 在索引非顺序文件中，必须为每个记录建立一个索引项，这样建立的索引表称为
10、稠密索引。 通常将索引非顺序文件简称为索引文件。 索引非顺序文件主文件无序，顺序存取将会频繁地引起磁头移动，适合于随机存取，不适合于顺序存取。 索引顺序文件的主文件是有序的，适合于随机存取、顺序存取。 索引顺序文件的索引是稀疏索引。索引占用空间较少，是最常用的一种文件组织。 最常用的索引顺序文件：ISAM文件和VSAM文件。1.1.2 索引文件的存储1索引文件的存储 索引文件在存储器上分为两个区：索引区和数据区。索引区存放索引表，数据区存放主文件。2 索引文件的建立 建立索引文件的过程：（1） 按输入记录的先后次序建立数据区和索引表。其中索引表中关键字是无序的（2） 待全部记录输入完毕后对索引
11、表进行排序，排序后的索引表和主文件一起就形成了索引文件。1.1.3 索引文件的操作 1检索操作 检索分两步进行： 将外存上含有索引区的页块送入内存，查找所需记录的物理地址 将含有该记录的页块送入内存 需要注意的是： 索引表不大时，索引表可一次读入内存，在索引文件中检索只需两次访问外存：一次读索引，一次读记录。 由于索引表有序，对索引表的查找可用顺序查找或二分查找等方法。2更新操作（1） 插入： 将插入记录置于数据区的末尾，并在索引表中插入索引项；（2） 删除： 删去相应的索引项；需要注意的是：在修改主关键字时，要同时修改索引表。1.1.4 利用查找表建立多级索引 1查找表 对索引表建立的索引，
12、称为查找表。查找表的建立可以为占据多个页块的索引表的查阅减少外存访问次数。2多级索引 当查找表中项目仍很多，可建立更高一级的索引。通常最高可达四级索引： 数据文件 一 索引表 查找表 第二查找表 第三查找表。 多级索引是一种静态索引 多级索引的各级索引均为顺序表，结构简单，修改很不方便，每次修改都要重组索引。3 动态索引 当数据文件在使用过程中记录变动较多时，利用二叉排序树(或AVL树)、B_树(或其变型)等树表结构建立的索引，为动态索引。（1）树表特点 插入、删除方便 本身是层次结构，无须建立多级索引 建立索引表的过程即为排序过程。（2）树表结构选择 当数据文件的记录数不很多，内存容量足以容
13、纳整个索引表时，可采用二叉排序树(或AVL树)作索引； 当文件很大时，索引表(树表)本身也在外存，查找索引时访问外存的次数恰为查找路径上的结点数。采用m阶B-树(或其变型)作为索引表为宜（m的选择取决于索引项的多少和缓冲区的大小）。（3）外存的索引表的查找性能评价 由于访问外存的时间比内存中查找的时间大得多，所以外存的索引表的查找性能主要着眼于访问外存的次数，即索引表的深度。 1.2 设计目标本课题最终成果是一个可以实现快速文件内容查找的工具。基本功能如下：1、系统支持多文本文档的导入，是对多文件进行操作。2、为了提高查询效率，必须建立索引文件。本系统采用倒排文件的方法对原文件建立索引，索引文
14、件与原文件之前用指针链接，查询时先在由键盘输入查找关键字，然后到索引文件的词文件中查找与查找关键字相同的字段，如果两者相同，通过链接的指针，可给出该词在原文中的位置，并将其前后约20个字符显示出来。并给出该词在原文件中出现的频率。3、本系统是英文类别的查找工具。处理时词与词之间用空格与回车换行符做为隔符。4、本系统是对常用词表进行查找的工具，因此词库文件由手动添加。这样可以过滤一些没有意义的词。5、由于是常用词表查找，所以本系统查找算法采用顺序查找算法实现。 6、如时间充裕，可考虑扩充词库文件为跟据导入文件自动建立，并分别建立顺序查找，折半查找及二分查找，比较其查询效率，择优用之。第二章 关键问题分析
