[毕业设计论文]文件快速搜索引擎.doc

沈阳航空工业学院学士学位论文 摘 要文件快速搜索引擎院 系 北方软件学院 专 业 计算机科学与技术 班 号 4233302 学 号 200427333207 姓 名 胡启良 指导教师 张 恒 沈阳航空工业学院2006年6月摘 要众所周知，我们生活在信息大爆炸时代，每天的信息量太大了，足以将所有人湮没。在如此庞杂的新鲜信息与海量信息面前，人们如何找到适时有用或急需的信息，搜索引擎如此应运而生。本文主要论述了使用倒排文件的方法建立一个文件快速搜索引擎。详细阐述了整个应用系统的设计思路，及毕业设计课题的选题意义。给出了研究开发的过程，以及对设计思路和实现细节的考虑，并对各部分周期进行了详尽的分析和描述，最终达成一个完整的设计方案。系统开发工具为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 utilized 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 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 platform 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 查找算法分析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 本课题的研究背景社会发展到今天，已经进入了计算机的时代。在各行各业的发展中，只要是涉及到信息管理范围的领域，都需要由计算机来完成。原因当然很简单，因为计算机处理速度快，可靠性高，而且易于维护。人们对计算机如此依赖，主要是因为近年来计算机硬件的发展水平飞速增加。对硬件方面了解的人都知道，计算机硬件的发展基本上是一年乘一个倍数的增长，但是这种发展势头会一直这样持续吗？答案是肯定的，不。因为任何事物都是有极限的。计算机也一样。CPU的运算速度现在来讲基本上已经快到极限了，但人们对它的速度要求还远远不仅如此。这就出现了一个问题，既然硬件无法提高，而人的要求又无法满足，那应该怎么办呢？办法是有的，运用好的算法，可以节约硬件资源，提高运算效率，一个很优秀的算法可以大大提升这些。文件内容查找是目前人们经常做的操作，很多软件都提供了文件内容查找的功能，如：Offcie办公软件、记事本、浏览器软件、写字板软件等。但是这些软件本身所带的查找功能多数是基于模式匹配（逐个字符比较）的方式制作的，当处理大规模文件时查询效率很低。在这样的背景下，我们提出了本课题，希望通过本题的研究，开发出一种文件内容快速查找工具，从而提高查找效率。如果要提高查找效率，必须对原文件建立索引文件，下面简单介绍一下索引文件的信息。1.1.1 索引文件构成1索引文件 索引文件由主文件和索引表构成。主文件：文件本身。索引表：在文件本身外建立的一张表，它指明逻辑记录和物理记录之间的一一对应关系。2索引表组成 索引表由若干索引项组成。一般索引项由主关键字和该关键字所在记录的物理地址组成。索引表必须按主关键字有序，而主文件本身则可以按主关键字有序或无序。3索引顺序文件和索引非顺序文件（1）索引顺序文件(Indexed Sequential File) 主文件按主关键字有序的文件称索引顺序文件。 在索引顺序文件中，可对一组记录建立一个索引项。这种索引表称为稀疏索引。（2）索引非顺序文件(Indexed NonSequentail File) 主文件按主关键字无序的文件称索引非顺序文件。 在索引非顺序文件中，必须为每个记录建立一个索引项，这样建立的索引表称为稠密索引。 通常将索引非顺序文件简称为索引文件。 索引非顺序文件主文件无序，顺序存取将会频繁地引起磁头移动，适合于随机存取，不适合于顺序存取。 索引顺序文件的主文件是有序的，适合于随机存取、顺序存取。 索引顺序文件的索引是稀疏索引。索引占用空间较少，是最常用的一种文件组织。 最常用的索引顺序文件：ISAM文件和VSAM文件。1.1.2 索引文件的存储1索引文件的存储 索引文件在存储器上分为两个区：索引区和数据区。索引区存放索引表，数据区存放主文件。2 索引文件的建立 建立索引文件的过程：（1） 按输入记录的先后次序建立数据区和索引表。其中索引表中关键字是无序的（2） 待全部记录输入完毕后对索引表进行排序，排序后的索引表和主文件一起就形成了索引文件。1.1.3 索引文件的操作 1检索操作 检索分两步进行： 将外存上含有索引区的页块送入内存，查找所需记录的物理地址 将含有该记录的页块送入内存 需要注意的是： 索引表不大时，索引表可一次读入内存，在索引文件中检索只需两次访问外存：一次读索引，一次读记录。 由于索引表有序，对索引表的查找可用顺序查找或二分查找等方法。2更新操作（1） 插入： 将插入记录置于数据区的末尾，并在索引表中插入索引项；（2） 删除： 删去相应的索引项；需要注意的是：在修改主关键字时，要同时修改索引表。1.1.4 利用查找表建立多级索引 1查找表 对索引表建立的索引，称为查找表。查找表的建立可以为占据多个页块的索引表的查阅减少外存访问次数。2多级索引 当查找表中项目仍很多，可建立更高一级的索引。通常最高可达四级索引： 数据文件 一 索引表 查找表 第二查找表 第三查找表。 多级索引是一种静态索引 多级索引的各级索引均为顺序表，结构简单，修改很不方便，每次修改都要重组索引。3 动态索引 当数据文件在使用过程中记录变动较多时，利用二叉排序树(或AVL树)、B_树(或其变型)等树表结构建立的索引，为动态索引。（1）树表特点 插入、删除方便 本身是层次结构，无须建立多级索引 建立索引表的过程即为排序过程。（2）树表结构选择 当数据文件的记录数不很多，内存容量足以容纳整个索引表时，可采用二叉排序树(或AVL树)作索引； 当文件很大时，索引表(树表)本身也在外存，查找索引时访问外存的次数恰为查找路径上的结点数。采用m阶B-树(或其变型)作为索引表为宜（m的选择取决于索引项的多少和缓冲区的大小）。（3）外存的索引表的查找性能评价 由于访问外存的时间比内存中查找的时间大得多，所以外存的索引表的查找性能主要着眼于访问外存的次数，即索引表的深度。 1.2 设计目标本课题最终成果是一个可以实现快速文件内容查找的工具。基本功能如下：1、系统支持多文本文档的导入，是对多文件进行操作。2、为了提高查询效率，必须建立索引文件。本系统采用倒排文件的方法对原文件建立索引，索引文件与原文件之前用指针链接，查询时先在由键盘输入查找关键字，然后到索引文件的词文件中查找与查找关键字相同的字段，如果两者相同，通过链接的指针，可给出该词在原文中的位置，并将其前后约20个字符显示出来。并给出该词在原文件中出现的频率。3、本系统是英文类别的查找工具。处理时词与词之间用空格与回车换行符做为隔符。4、本系统是对常用词表进行查找的工具，因此词库文件由手动添加。这样可以过滤一些没有意义的词。5、由于是常用词表查找，所以本系统查找算法采用顺序查找算法实现。 6、如时间充裕，可考虑扩充词库文件为跟据导入文件自动建立，并分别建立顺序查找，折半查找及二分查找，比较其查询效率，择优用之。第二章 关键问题分析2.1 索引算法分析2.2.1 散列文件的组织方式 散列文件是利用散列存储方式组织的文件，亦称直接存取文件。即根据文件中关键字的特点，设计一个散列函数和处理冲突的方法，将记录散列到存储设备上。散列表与散列文件比较如表2.1比较项目散列表散列文件存储单位若干记录为一组桶处理冲突办法开放地址法、拉链法拉链法表2.11、基桶和溢出桶 在散列文件的存储单位叫桶(Bucket)。假如一个桶能存放m个记录，则当桶中已有m个同义词的记录时，存放第m+1个同义词会发生溢出。需要将第m+1个同义词存放到另一个桶中，通常称此桶为溢出桶。相对地，称前m个同义词存放的桶为基桶。 (1)溢出桶和基桶大小相同，相互之间用指针相链接。 (2)当在基桶中没有找到待查记录时，就沿着指针到所指溢出桶中进行查找，因此，希望同一散列地址的溢出桶和基桶，在磁盘上的物理位置不要相距太远，最好在同一柱面上。2、散列文件的查找操作在散列文件中查找的过程：（1） 根据给定值求出散列桶地址（2） 将基桶的记录读人内存，进行顺序查找（3） 若找到关键字等于给定值的记录，则检索成功；否则，读人溢出桶的 记录继续进行查找。3、散列文件的删除操作 在散列文件中删去一个记录，仅需对被删记录作删除标记即可。4、散列文件的特点 1）散列文件的优点（1） 文件随机存放，记录不需进行排序。（2） 插入、删除方便。（3） 存取速度快；不需要索引区，节省存储空间。 2）散列文件的缺点（1） 不能进行顺序存取，只能按关键字随机存取（2） 询问方式限于简单询问（3） 在经过多次插入、删除后，可能造成文件结构不合理，需要重新组织文件。2.2.2 多关键字文件1多关键字文件 包含有多个次关键字索引的文件称为多关键字文件。 2多关键字文件和其他文件的区别如表2.2多关键字文件其他文件包含的关键字主关键字外还有多个次关键字只含一个主关键字索引建立的索引建立主关键字索引和多个次关健字索引只有（没有）主关键字索引查询查询对主关键字索引或次关键字索引查询只能顺序存取主文件记录进行比较，效率低文件组织方式四种基本组织方法都可以四种组织方法都可以表2.22.2.3 多重表文件1、多重表文件的组织方式 多重表文件是将索引方法和链接方法相结合的一种组织方式。具体组织方式： 对每个需要查询的次关键字建立一个索引，同时将具有相同次关键字的记录链接成一个链表，并将此链表的头指针、链表长度及次关键字，作为索引表的一个索引项。通常多重表文件的主文件是一个顺序文件。2、多重表文件的查询操作（1） 单关键字简单查询基本思想 据给定值，在对应次关键字索引表中找到对应索引项，从头指针出发，列出该链表上所有记录。（2） 多关键字组合查询基本思想 在查找同时满足两多个关键字条件得记录时，可先比较两（多）个索引链表的长度，然后选较短的链表进行查找。 3、多重表的更新操作 1插入新记录 相同次关键字链表不按主关键字大小链接时，在主文件中插入新记录后，将记录在各个次关键字链表中插在链表的头指针之后即可。 2删除记录 在删去一个记录的同时，需在每个次关键字的链表中删去该记录。 2.2.4 倒排文件 1倒排文件的组织方式和特点 倒排文件和多重表文件不同。在次关键字索引中，具有相同次关键字的记录之间不进行链接，而是列出具有该次关键字记录的物理地址。 倒排文件中的次关键字索引称做倒排表。倒排表和主文件一起就构成了倒排文件。2倒排文件的查询 倒排表的主要优点是：在处理复杂的多关键字查询时，可在倒排表中先完成查询的交、并等逻辑运算，得到结果后再对记录进行存取。这样不必对每个记录随机存取，把对记录的查询转换为地址集合的运算，从而提高查找速度。3倒排文件的更新 在插入和删除记录时，还要修改倒排表。4列出主关键字的倒排表列出主关键字的倒排表的特点：(1) 存取速度较慢(2) 主关键字可看成是记录的符号地址，对于存储具有相对独立性。5倒排文件与一般文件组织的区别在一般的文件组织中，是先找记录，然后再找到该记录所含的各次关键字；而倒排文件中，是先给定次关键字，然后查找含有该次关键字的各个记录，这种文件的查找次序正好与一般文件的查找次序相反，因此称之为倒排。6倒排算法描述倒排文件索引结构：该结构及相应的生成算法如下：(0）设有两篇文章1和2 文章1的内容为：Tom lives in Guangzhou,I live in Guangzhou too. 文章2的内容为：He once lived in Shanghai. (1) 此索引结构是基于关键词索引和查询的，首先我们要取得这两篇文章的关键词，通常我们需要如下处理措施 a.我们现在有的是文章内容，即一个字符串，我们先要找出字符串中的所有单词，即分词。英文单词由于用空格分隔，比较好处理。 b.文章中的”in”, “once” “too”等词没有什么实际意义，中文中的“的”“是”等字通常也无具体含义，这些不代表概念的词可以过滤掉 c.用户通常希望查“He”时能把含“he”，“HE”的文章也找出来，所以所有单词需要统一大小写。 d.文章中的标点符号通常不表示某种概念，也可以过滤掉 经过上面处理后 文章1的所有关键词为：tom lives guangzhou i live guangzhou 文章2的所有关键词为：he lived shanghai (2) 有了关键词后，我们就可以建立倒排索引了。上面的对应关系是：“文章号”对“文章中所有关键词”。倒排索引把这个关系倒过来，变成：“关键词”对“拥有该关键词的所有文章号”。文章1，2经过倒排后变成 关键词 文章号 guangzhou 1 he 2 i 1 live 1 lives 1 lived 2shanghai 2 tom 1 通常仅知道关键词在哪些文章中出现还不够，我们还需要知道关键词在文章中出现次数和出现的位置，通常有两种位置：a)字符位置，即记录该词是文章中第几个字符（优点是关键词亮显时定位快）；b)关键词位置，即记录该词是文章中第几个关键词（优点是节约索引空间、词组查询快）。加上“出现频率”和“出现位置”信息后，我们的索引结构变为： 关键词 文章号出现频率 出现位置 guangzhou 12 3，6 he 21 1 i 11 4 live 11 5 lived 11 2lives 11 2shanghai 21 3 tom 11 1 以“live” 这行为例我们说明一下该结构：live在文章1中出现了2次，文章2中出现了一次，它的出现位置为“2,5,2”这表示什么呢？我们需要结合文章号和出现频率来分析，文章1中出现了2次，那么“2,5”就表示live在文章1中出现的两个位置，文章2中出现了一次，剩下的“2”就表示live是文章2中第 2个关键字。 以上此索引结构中最核心的部分。我们注意到关键字是按字符顺序排列的，因此可以用二元搜索算法快速定位关键词。 实现时将上面三列分别作为词典文件（Term Dictionary）、频率文件(frequencies)、位置文件 (positions)保存。其中词典文件不仅保存有每个关键词，还保留了指向频率文件和位置文件的指针，通过指针可以找到该关键字的频率信息和位置信息。 下面我们可以通过对该索引的查询来解释一下为什么要建立索引。 假设要查询单词 “live”，搜索引擎先对词典二元查找、找到该词，通过指向频率文件的指针读出所有文章号，然后返回结果。词典通常非常小，因而，整个过程的时间是毫秒级的。 而用普通的顺序匹配算法，不建索引，而是对所有文章的内容进行字符串匹配，这个过程将会相当缓慢，当文章数目很大时，时间往往是无法忍受的。2.2 查找算法分析2.2.1 顺序查找 在表的组织方式中，线性表是最简单的一种。顺序查找(Sequential Search)是一种最简单的查找方法。1、顺序查找的基本思想 基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。2、顺序查找的存储结构要求顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作存储结构时，扫描必须从第一个结点开始）。3、基于顺序结构的顺序查找算法（1）类型说明 typedef struct KeyType key； InfoType otherinfo； /此类型依赖于应用 NodeType； typedef NodeType SeqListn+1； /0号单元用作哨兵（2）具体算法 int SeqSearch(Seqlist R，KeyType K) /在顺序表R1.n中顺序查找关键字为K的结点， /成功时返回找到的结点位置，失败时返回0 int i； R0.key=K； /设置哨兵 for(i=n；Ri.key!=K;i-)； /从表后往前找 return i； /若i为0，表示查找失败，否则Ri是要找的结点 /SeqSearch（3）算法分析 算法中监视哨R0的作用 为了在for循环中省去判定防止下标越界的条件i1，从而节省比较的时间。成功时的顺序查找的平均查找长度： 在等概率情况下，pi=1/n(1in)，故成功的平均查找长度为 (n+2+1)/n=(n+1)/2 即查找成功时的平均比较次数约为表长的一半。 若K值不在表中，则须进行n+1次比较之后才能确定查找失败。表中各结点的查找概率并不相等的ASL 若事先知道表中各结点的查找概率不相等和它们的分布情况，则应将表中结点按查找概率由小到大地存放，以便提高顺序查找的效率。 为了提高查找效率，对算法SeqSearch做如下修改：每当查找成功，就将找到的结点和其后继(若存在)结点交换。这样，使得查找概率大的结点在查找过程中不断往后移，便于在以后的查找中减少比较次数。顺序查找的优点 算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。顺序查找的缺点查找效率低，因此，当n较大时不宜采用顺序查找。2.2.2 二分查找1、二分查找(Binary Search) 二分查找又称折半查找，它是一种效率较高的查找方法。 二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。2、二分查找的基本思想 二分查找的基本思想是：（设Rlow.high是当前的查找区间）（1）首先确定该区间的中点位置： （2）然后将待查的K值与Rmid.key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下： 若Rmid.keyK，则由表的有序性可知Rmid.n.keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R1.mid-1中，故新的查找区间是左子表R1.mid-1。 类似地，若Rmid.keyK，则要查找的K必在mid的右子表Rmid+1.n中，即新的查找区间是右子表Rmid+1.n。下一次查找是针对新的查找区间进行的。 因此，从初始的查找区间R1.n开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空(即查找失败)时为止。3、二分查找算法 int BinSearch(SeqList R，KeyType K) /在有序表R1.n中进行二分查找，成功时返回结点的位置，失败时返回零 int low=1，high=n，mid； /置当前查找区间上、下界的初值 while(lowK) high=mid-1; /继续在Rlow.mid-1中查找 else low=mid+1； /继续在Rmid+1.high中查找 return 0； /当lowhigh时表示查找区间为空，查找失败 /BinSeareh4、 二分查找算法的执行过程 先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。如图2.1，2.2。图2.1二分查找算法的执行过程1图2.2二分查找算法的执行过程25、二分查找判定树 二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)。 判定树的形态只与表结点个数n相关，而与输入实例中R1.n.keys的取值无关。（1）二分查找判定树的组成圆结点即树中的内部结点。树中圆结点内的数字表示该结点在有序表中的位置。外部结点：圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。树中某结点i与其左(右)孩子连接的左(右)分支上的标记、)表示：当待查关键字KRi.key)时，应走左(右)分支到达i的左(右)孩子，将该孩子的关键字进一步和K比较。若相等，则查找过程结束返回，否则继续将K与树中更下一层的结点比较。（2）二分查找判定树的查找 二分查找就是将给定值K与二分查找判定树的根结点的关键字进行比较。若相等，成功。否则若小于根结点的关键字，到左子树中查找。若大于根结点的关键字，则到右子树中查找。 由此可见，成功的二分查找过程恰好是走了一条从判定树的根到被查结点的路径，经历比较的关键字次数恰为该结点在树中的层数。若查找失败，则其比较过程是经历了一条从判定树根到某个外部结点的路径，所需的关键字比较次数是该路径上内部结点的总数。（3）二分查找的平均查找长度设内部结点的总数为n=2h-1，则判定树是深度为h=lg(n+1)的满二叉树(深度h不计外部结点)。树中第k层上的结点个数为2k-1，查找它们所需的比较次数是k。因此在等概率假设下，二分查找成功时的平均查找长度为： ASLbnlg(n+1)-1二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为： 二分查找的最坏性能和平均性能相当接近。6、二分查找的优点和缺点虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找。 2.2.3 分块查找分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。1、 二分查找表存储结构 二分查找表由分块有序的线性表和索引表组成。（1）分块有序的线性表 表R1.n均分为b块，前b-1块中结点个数为 ，第b块的结点数小于等于s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是分块有序的。（2）索引表 抽取各块中的最大关键字及其起始位置构成一个索引表IDl.b，即：IDi(1ib)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。2、分块查找的基本思想 分块查找的基本思想是：（1）首先查找索引表 索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。（2）然后在已确定的块中进行顺序查找 由于块内无序，只能用顺序查找。3、算法分析（1）平均查找长度ASL分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。以二分查找来确定块，分块查找成功时的平均查找长度 ASLblk=ASLbn+ASLsqlg(b+1)-1+(s+1)/2lg(n/s+1)+s/2以顺序查找确定块，分块查找成功时的平均查找长度 ASLblk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s) 当 s= 时ASLblk取极小值 +1 ，即当采用顺序查找确定块时，应将各块中的结点数选定为 。（2）块的大小在实际应用中，分块查找不一定要将线性表分成大小相等的若干块，可根据表的特征进行分块。（3） 结点的存储结构各块可放在不同的向量中，也可将每一块存放在一个单链表中。（4）分块查找的优点分块查找的优点是：在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。沈阳航空工业学院学士学位论文 第三章 系统设计第三章 系统设计3.1 程序的总体框架图3.1程序的总体框架图3.2 索引建立模块分析如果使用基于模式匹配（逐个字符比较）的方式制作，查询效率非常低，因此需要一种高效的查询算法。本题使用的方法为倒排文件索引方法，既对导入的文本文件先按照词库文件建立倒排索引。例如：“there is no such thing as motion over and above the things”先按照词库文件建立索引，如表3.1所示：词库表aboveasmotionoversuchtherethingthings表3.1 词库文件表建立倒排索引后如表3.2所示：词所在文件所在位置 出现频率aboveBook01.txt101asBook01.txt61motionBook01.txt71overBook01.txt81suchBook01.txt41thereBook01.txt11thingBook01.txt51thingsBook01.txt121表3.2 倒排索引表这样在查找的时候只要找到相应的词，即可获该词所在文件名与该词在文件中的位置以及该词的出现频率。即可直接显示该词前后的一些相关信息。从而达到快速搜索的目的。3.3 程序总体模块图图3.2 程序总体模块图沈阳航空工业学院学士学位论文 第四章 详细设计第四章 详细设计4.1 深入剖析倒排文件索引算法一个搜索引擎的灵魂就是索引数法，只有好的算法才能完成快速搜索的任务。以下函数为该题目最核心的函数。struct files_info /该结构为倒排索引结构char word32;/词文件char *filename;/所在文件名long place; /首次出现的位置long frequency;/出现频率file10000;void Index(char *inname, char *outname)char a32=0;char b32=0;char d8=0;char e8=0;int n = 0;int i;int m;FILE *in,*out,*fp;if(in = fopen(inname,r) = NULL)printf(in,cantn);if(out = fopen(outname,w+) = NULL)printf(out,cantn);if(fp = fopen(Term Dictionary.txt,r) = NULL)printf(fp,cantn);while(!feof(fp)/到词库中取词d0 = fgetc(fp);if(d0 != 10)strcat(a,d);if(d0 = 10)while(!feof(in) & a0 != NULL)/到待查找文件中取词e0 = tolower(fgetc(in);/大写转小写if(feof(in)m = strlen(a);for(i=0;im;i+)ai = 0;rewind(in);/除去空格与换行的非字母字符转换为空串