文件快速搜索引擎本科论文

沈阳航空工业学院学士学位论文摘要PAGEPAGEIV文件快速搜索引擎院系北方软件学院专业计算机科学与技术班号4233302学号200427333207姓名胡启良指导教师张恒沈阳航空工业学院2006年6月摘要众所周知，我们生活在信息大爆炸时代，每天的信息量太大了，足以将所有人湮没。在如此庞杂的新鲜信息与海量信息面前，人们如何找到适时有用或急需的信息，搜索引擎如此应运而生。本文主要论述了使用倒排文件的方法建立一个文件快速搜索引擎。详细阐述了整个应用系统的设计思路，及毕业设计课题的选题意义。给出了研究开发的过程，以及对设计思路和实现细节的考虑，并对各部分周期进行了详尽的分析和描述，最终达成一个完整的设计方案。系统开发工具为VisualC++6.0，平台为WINDOWSXPProfessional。关键字:倒排文件，搜索引擎沈阳航空工业学院学士学位论文AbstractAbstractAseveryoneknows,weliveinaneraofinformationexplosion,thedailyvolumeofinformationistoogreat,tobealllost.Inthecaseoffreshinformationandstockinformationutilizedbefore,peopleneedtofindtimelyandusefulinformation,whichcansearchit.Searchenginessuchcameintobeing.Thisarticlediscussestheuseofthemainmethodsofcreatingadocumentwouldplatoonrapiddocumentsearchengines.Detaileddesignoftheentireapplicationsystem,theselectionofsubjectsandtopicsfromdesignsignificance.Giventheresearchanddevelopmentprocess,andtoconsiderthedetailsofthedesignandrealizationofideasandthecycleofadetailedanalysisanddescription,theultimategoalofacompletedesign.VC++6.0toolsforsystemdevelopment,theplatformforWindowsXPProfessional.Keywords:opposingplatoondocuments,thesearchengine沈阳航空工业学院学士学位论文第二章 关键问题分析目录TOC\o"1-3"\u摘要 Ⅰ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）索引顺序文件(IndexedSequentialFile)

主文件按主关键字有序的文件称索引顺序文件。

在索引顺序文件中，可对一组记录建立一个索引项。这种索引表称为稀疏索引。

（2）索引非顺序文件(IndexedNonSequentailFile)

主文件按主关键字无序的文件称索引非顺序文件。

在索引非顺序文件中，必须为每个记录建立一个索引项，这样建立的索引表称为稠密索引。

①通常将索引非顺序文件简称为索引文件。

②索引非顺序文件主文件无序，顺序存取将会频繁地引起磁头移动，适合于随机存取，不适合于顺序存取。

③索引顺序文件的主文件是有序的，适合于随机存取、顺序存取。

④索引顺序文件的索引是稀疏索引。索引占用空间较少，是最常用的一种文件组织。

⑤最常用的索引顺序文件：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多关键字文件其他文件包含的关键字

主关键字外还有多个次关键字只含一个主关键字索引建立的索引建立主关键字索引和多个次关健字索引只有（没有）主关键字索引查询查询对主关键字索引或次关键字索引查询只能顺序存取主文件记录进行比较，效率低文件组织方式四种基本组织方法都可以四种组织方法都可以表多重表文件

1、多重表文件的组织方式

多重表文件是将索引方法和链接方法相结合的一种组织方式。

具体组织方式：

对每个需要查询的次关键字建立一个索引，同时将具有相同次关键字的记录链接成一个链表，并将此链表的头指针、链表长度及次关键字，作为索引表的一个索引项。通常多重表文件的主文件是一个顺序文件。

2、多重表文件的查询操作

（1）单关键字简单查询基本思想

据给定值，在对应次关键字索引表中找到对应索引项，从头指针出发，列出该链表上所有记录。

（2）多关键字组合查询基本思想

在查找同时满足两多个关键字条件得记录时，可先比较两（多）个索引链表的长度，然后选较短的链表进行查找。

3、多重表的更新操作

1．插入新记录

相同次关键字链表不按主关键字大小链接时，在主文件中插入新记录后，将记录在各个次关键字链表中插在链表的头指针之后即可。

2．删除记录

在删去一个记录的同时，需在每个次关键字的链表中删去该记录。2.2.4倒排文件

1．倒排文件的组织方式和特点

倒排文件和多重表文件不同。在次关键字索引中，具有相同次关键字的记录之间不进行链接，而是列出具有该次关键字记录的物理地址。

倒排文件中的次关键字索引称做倒排表。倒排表和主文件一起就构成了倒排文件。

2．倒排文件的查询

倒排表的主要优点是：在处理复杂的多关键字查询时，可在倒排表中先完成查询的交、并等逻辑运算，得到结果后再对记录进行存取。这样不必对每个记录随机存取，把对记录的查询转换为地址集合的运算，从而提高查找速度。

3．倒排文件的更新

在插入和删除记录时，还要修改倒排表。

4．列出主关键字的倒排表

列出主关键字的倒排表的特点：

(1)存取速度较慢

(2)主关键字可看成是记录的符号地址，对于存储具有相对独立性。

5．倒排文件与一般文件组织的区别

在一般的文件组织中，是先找记录，然后再找到该记录所含的各次关键字；而倒排文件中，是先给定次关键字，然后查找含有该次关键字的各个记录，这种文件的查找次序正好与一般文件的查找次序相反，因此称之为"倒排"。6．倒排算法描述

倒排文件索引结构：

该结构及相应的生成算法如下：

(0）设有两篇文章1和2

文章1的内容为：TomlivesinGuangzhou,IliveinGuangzhoutoo.

文章2的内容为：HeoncelivedinShanghai.

(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经过倒排后变成

关键词文章号

guangzhou1

he2

i1

live1lives1lived2

shanghai2

tom1通常仅知道关键词在哪些文章中出现还不够，我们还需要知道关键词在文章中出现次数和出现的位置，通常有两种位置：a)字符位置，即记录该词是文章中第几个字符（优点是关键词亮显时定位快）；b)关键词位置，即记录该词是文章中第几个关键词（优点是节约索引空间、词组查询快）。

加上“出现频率”和“出现位置”信息后，我们的索引结构变为：

关键词文章号[出现频率]出现位置

guangzhou1[2]3，6

he2[1]1

i1[1]4

live1[1]5lived1[1]2

lives1[1]2shanghai2[1]3

tom1[1]1以“live”这行为例我们说明一下该结构：live在文章1中出现了2次，文章2中出现了一次，它的出现位置为“2,5,2”这表示什么呢？我们需要结合文章号和出现频率来分析，文章1中出现了2次，那么“2,5”就表示live在文章1中出现的两个位置，文章2中出现了一次，剩下的“2”就表示live是文章2中第2个关键字。

以上此索引结构中最核心的部分。我们注意到关键字是按字符顺序排列的，因此可以用二元搜索算法快速定位关键词。

实现时将上面三列分别作为词典文件（TermDictionary）、频率文件(frequencies)、位置文件(positions)保存。其中词典文件不仅保存有每个关键词，还保留了指向频率文件和位置文件的指针，通过指针可以找到该关键字的频率信息和位置信息。

下面我们可以通过对该索引的查询来解释一下为什么要建立索引。

假设要查询单词“live”2.2查找算法分析2.2.1顺序查找

在表的组织方式中，线性表是最简单的一种。顺序查找(SequentialSearch)是一种最简单的查找方法。

1、顺序查找的基本思想

基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。

2、顺序查找的存储结构要求

顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作存储结构时，扫描必须从第一个结点开始）。

3、基于顺序结构的顺序查找算法

（1）类型说明

typedefstruct{

KeyTypekey；

InfoTypeotherinfo；//此类型依赖于应用

}NodeType；

typedefNodeTypeSeqList[n+1]；//0号单元用作哨兵

（2）具体算法

intSeqSearch(SeqlistR，KeyTypeK)

{//在顺序表R[1..n]中顺序查找关键字为K的结点，

//成功时返回找到的结点位置，失败时返回0

inti；

R[0].key=K；//设置哨兵

for(i=n；R[i].key!=K;i--)；//从表后往前找

returni；//若i为0，表示查找失败，否则R[i]是要找的结点

}//SeqSearch（3）算法分析

①算法中监视哨R[0]的作用

为了在for循环中省去判定防止下标越界的条件i≥1，从而节省比较的时间。

②成功时的顺序查找的平均查找长度：

在等概率情况下，pi=1/n(1≤i≤n)，故成功的平均查找长度为

(n+…+2+1)/n=(n+1)/2

即查找成功时的平均比较次数约为表长的一半。

若K值不在表中，则须进行n+1次比较之后才能确定查找失败。

③表中各结点的查找概率并不相等的ASL

若事先知道表中各结点的查找概率不相等和它们的分布情况，则应将表中结点按查找概率由小到大地存放，以便提高顺序查找的效率。

为了提高查找效率，对算法SeqSearch做如下修改：每当查找成功，就将找到的结点和其后继(若存在)结点交换。这样，使得查找概率大的结点在查找过程中不断往后移，便于在以后的查找中减少比较次数。

④顺序查找的优点

算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。

⑤顺序查找的缺点

查找效率低，因此，当n较大时不宜采用顺序查找。2.2.2二分查找

1、二分查找(BinarySearch)

二分查找又称折半查找，它是一种效率较高的查找方法。

二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。

2、二分查找的基本思想

二分查找的基本思想是：（设R[low..high]是当前的查找区间）（1）首先确定该区间的中点位置：

（2）然后将待查的K值与R[mid].key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：

①若R[mid].key>K，则由表的有序性可知R[mid..n].keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R[1..mid-1]中，故新的查找区间是左子表R[1..mid-1]。

②类似地，若R[mid].key<K，则要查找的K必在mid的右子表R[mid+1..n]中，即新的查找区间是右子表R[mid+1..n]。下一次查找是针对新的查找区间进行的。

因此，从初始的查找区间R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空(即查找失败)时为止。

3、二分查找算法

intBinSearch(SeqListR，KeyTypeK)

{//在有序表R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零

intlow=1，high=n，mid；//置当前查找区间上、下界的初值

while(low<=high){//当前查找区间R[low..high]非空

mid=(low+high)/2；

if(R[mid].key==K)returnmid；//查找成功返回

if(R[mid].kdy>K)

high=mid-1;//继续在R[low..mid-1]中查找

else

low=mid+1；//继续在R[mid+1..high]中查找

}

return0；//当low>high时表示查找区间为空，查找失败

}//BinSeareh

4、二分查找算法的执行过程

先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。如图2.1，2.2。图2.1二分查找算法的执行过程1图2.2二分查找算法的执行过程25、二分查找判定树

二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(DecisionTree)或比较树(ComparisonTree)。

判定树的形态只与表结点个数n相关，而与输入实例中R[1..n].keys的取值无关。

（1）二分查找判定树的组成

①圆结点即树中的内部结点。树中圆结点内的数字表示该结点在有序表中的位置。

②外部结点：圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。

③树中某结点i与其左(右)孩子连接的左(右)分支上的标记"<"、"("、">"、")"表示：当待查关键字K<R[i].key(K>R[i].key)时，应走左(右)分支到达i的左(右)孩子，将该孩子的关键字进一步和K比较。若相等，则查找过程结束返回，否则继续将K与树中更下一层的结点比较。

（2）二分查找判定树的查找

二分查找就是将给定值K与二分查找判定树的根结点的关键字进行比较。若相等，成功。否则若小于根结点的关键字，到左子树中查找。若大于根结点的关键字，则到右子树中查找。

由此可见，成功的二分查找过程恰好是走了一条从判定树的根到被查结点的路径，经历比较的关键字次数恰为该结点在树中的层数。若查找失败，则其比较过程是经历了一条从判定树根到某个外部结点的路径，所需的关键字比较次数是该路径上内部结点的总数。（3）二分查找的平均查找长度设内部结点的总数为n=2h-1，则判定树是深度为h=lg(n+1)的满二叉树(深度h不计外部结点)。树中第k层上的结点个数为2k-1，查找它们所需的比较次数是k。因此在等概率假设下，二分查找成功时的平均查找长度为：

ASLbn≈lg(n+1)-1

二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为：

二分查找的最坏性能和平均性能相当接近。

6、二分查找的优点和缺点

虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。

二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。

对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找。2.2.3分块查找分块查找(BlockingSearch)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。

1、二分查找表存储结构

二分查找表由"分块有序"的线性表和索引表组成。

（1）"分块有序"的线性表

表R[1..n]均分为b块，前b-1块中结点个数为，第b块的结点数小于等于s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是"分块有序"的。

（2）索引表

抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b]，即：

ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。

2、分块查找的基本思想

分块查找的基本思想是：

（1）首先查找索引表

索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。

（2）然后在已确定的块中进行顺序查找

由于块内无序，只能用顺序查找。

3、算法分析

（1）平均查找长度ASL

分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。

①以二分查找来确定块，分块查找成功时的平均查找长度

ASLblk=ASLbn+ASLsq≈lg(b+1)-1+(s+1)/2≈lg(n/s+1)+s/2

②以顺序查找确定块，分块查找成功时的平均查找长度

ASL'blk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)

当s=时ASL'blk取极小值+1，即当采用顺序查找确定块时，应将各块中的结点数选定为。

（2）块的大小

在实际应用中，分块查找不一定要将线性表分成大小相等的若干块，可根据表的特征进行分块。

（3）结点的存储结构

各块可放在不同的向量中，也可将每一块存放在一个单链表中。

（4）分块查找的优点

分块查找的优点是：

①在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。

②因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。

沈阳航空工业学院学士学位论文第三章系统设计 第三章系统设计3.1程序的总体框架图3.1程序的总体框架图3.2索引建立模块分析如果使用基于模式匹配（逐个字符比较）的方式制作，查询效率非常低，因此需要一种高效的查询算法。本题使用的方法为倒排文件索引方法，既对导入的文本文件先按照词库文件建立倒排索引。例如：“thereisnosuchthingasmotionoverandabovethethings”先按照词库文件建立索引，如表3.1所示：词库表aboveasmotionoversuchtherethingthings表3.1词库文件表建立倒排索引后如表3.2所示：词所在文件所在位置出现频率aboveBook01.txt101asBook01.txt61motionBook01.txt71overBook01.txt81suchBook01.txt41thereBook01.txt11thingBook01.txt51thingsBook01.txt121表3.2倒排索引表这样在查找的时候只要找到相应的词，即可获该词所在文件名与该词在文件中的位置以及该词的出现频率。即可直接显示该词前后的一些相关信息。从而达到快速搜索的目的。3.3程序总体模块图图3.2程序总体模块图沈阳航空工业学院学士学位论文第四章详细设计 第四章详细设计4.1深入剖析倒排文件索引算法一个搜索引擎的灵魂就是索引数法，只有好的算法才能完成快速搜索的任务。以下函数为该题目最核心的函数。structfiles_info //该结构为倒排索引结构{ charword[32]; //词文件 char*filename; //所在文件名 longplace; //首次出现的位置 longfrequency; //出现频率}file[10000];voidIndex(char*inname,char*outname){ chara[32]={0}; charb[32]={0}; chard[8]={0}; chare[8]={0}; intn=0; inti; intm; FILE*in,*out,*fp; if((in=fopen(inname,"r"))==NULL) printf("in,can't\n"); if((out=fopen(outname,"w+"))==NULL) printf("out,can't\n"); if((fp=fopen("TermDictionary.txt","r"))==NULL) printf("fp,can't\n"); while(!feof(fp)) //到词库中取词 { d[0]=fgetc(fp); if(d[0]!=10) { strcat(a,d); } if(d[0]==10) { while(!feof(in)&&a[0]!=NULL) //到待查找文件中取词 { e[0]=tolower(fgetc(in)); //大写转小写 if(feof(in)) { m=strlen(a); for(i=0;i<m;i++) { a[i]=0; } rewind(in); }//除去空格与换行的非字母字符转换为空串 if((e[0]<97||e[0]>122)&&(e[0]!='')&&(e[0]!=10)) { e[0]=''; } if((e[0]!=10)&&(e[0]!='')) { strcat(b,e); } if(((e[0]==10)||(e[0]==''))&&(b[0]!=NULL)) { if(strcmp(a,b)!=0) { m=strlen(b); for(inti=0;i<m;i++) { b[i]=0; } } if(strcmp(a,b)==0) { strcpy(file[n].word,a); file[n].filename=inname; file[n].place=ftell(in)-strlen(a); file[n].frequency++; fwrite(&file[n],sizeof(structfiles_info),1,out); n++; rewind(in); m=strlen(a); for(i=0;i<m;i++) { a[i]=0; b[i]=0; } } } } } } fclose(in); fclose(out); fclose(fp);}此函数完成的功能为把inname所指向的文件按照TermDictionary(词库文件)建立倒排索引后，写入outname所指文件。4.2查询的实现由于本系统是对常用词表的查询，所以用顺序查找算法即可。查询的实现主要由两个函数来完成，这两个函数是：::GetWindowText(::GetDlgItem(m_hWnd,IDC_EDITTEXT1),sz,256);::SetWindowText(::GetDlgItem(m_hWnd,IDC_EDITTEXT2),sz);:GetWindowText（）函数是获得查询关健字。:SetWindowText（）是把查询到的结果显示出来。查询流程如图4.1图4.1查询流程图4.3界面设计图形界面的设计在程序的交互设计往往被忽略！一个好的交互设计对产品的成功起着很关键的作用。因为界面用户最先接触到的东西，也是一般性的用户唯一接触到的东西。用户对于界面视觉效果和软件操作方式的易用性的关心，要远远大于他对底层到底用什么样的代码去实现的关心。如果说程序是一个人的肌肉和骨骼，那么界面设计就是人的外貌和品格！所以界面设计是系统中比较重要的部分，这个部分的设计原则是：（1）界面直观、用户接触软件后对界面上对应的功能一目了然、可以方便使用本应用系统。（2）做到用户界面的一致性，在界面设计中应该保持界面的一致性。（3）布局合理化，在一个窗口内部所有控件的布局和信息组织的艺术性,使得用户界面美观。程序主界面如图4.2所示：图4.2程序主界面4.3图显示输入查询关键字：图4.3输入查询关键字4.4图显示点击搜索按钮后给出查询结果：图4.4点击搜索按钮后给出查询结果4.5图是没查找到显示的效果：图4.5没查询到数据沈阳航空工业学院学士学位论文第五章系统性能分析及测试 第五章系统性能分析及测试5.1系统性能分析软件的测试对于保证一个软件的可靠性是至关重要的。面对一个较为庞大而复杂的系统，人们的认识不可能覆盖所有的情况，因此在开发一个软件的各个阶段都不可避免地会发生这样或那样的问题。软件测试的目标是尽可能地发现软件中所潜在的错误。5.1.1系统稳定性分析系统稳定性是指：要求系统不出错或少出错，出错后有解决办法。上面已经论述了本工具的错误处理机制是通过设置捕捉陷阱并将错误通过错误提示消息框告知使用者的，这也是提高系统稳定性的重要方面；另外统一的界面可以很好的控制使用者的操作，使其更加规范，合理；事件驱动机制，也很好的明确了各个控件的任务，避免了处理不明确，任务混淆，提高系统的稳定性。5.1.2系统安全性分析系统的安全性是：系统的易瘫痪因素和对整个绘图工具的安全性隐患。从以上分析看出我们设计的每个模块都是作为一个独立的应用程序提供给系统的，因此它和系统的联系并不是太大，就它本身来说它出错的可能性很小，因为它采用的都是最基本的组件组成的。所以说系统有较好的安全性。5.