多语种二分查找类库及文件生成工具的实现

开篇：润墨网以专业的文秘视角，为您筛选了一篇多语种二分查找类库及文件生成工具的实现范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：该文，为了满足机器翻译系统、词典、维文字转换等系统中对文件的快速访问，使用C#设计与实现了基于二分查找的检索类和该类可访问的文件生成工具。

关键词：二分查找；关键词；内容；二分查找；C#

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2013）31-6996-03

1 概述

查找即在某种数据结构中找出满足给定特征的结点，若找到则查找成功，否则，查找失败。查找的基本问题是采用什么样的存储结构和算法得以提高查找效率。常用查找算法有顺序查找、二分查找、分块查找等。

顺序查找的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键词和给定值K相比较。若当前扫描到的结点关键词与K相等，则查找成功；若扫描结束后，仍未找到关键词等于K的结点，则查找失败。顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。顺序查找算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键词有序，它都同样适用。顺序查找的缺点查找效率低，因此，当词汇表较大时不宜采用顺序查找。

二分查找要求线形表中的结点按关键词值升序或降序排列，用给定值k先与中间结点的关键词比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键词的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。虽然二分查找的效率高，但是要将表按关键词排序。而排序本身是一种很费时的运算。即使采用高效率的排序方法也要花费O（nlgn）的时间。二分查找只适用顺序存储结构。

分块查找也称为索引查找，把线形分成若干块，在每一块中的数据元素的存储顺序是任意的，但要求块与块之间须按关键词值的大小有序排列，还要建立一个按关键词值递增顺序排列的索引表，索引表中的一项对应线形表中的一块，索引项包括两个内容：① 键域存放相应块的最大关键词；② 链域存放指向本块第一个结点的指针。分块查找分两步进行，先确定待查找的结点属于哪一块，然后在块内查找结点。

分块查找的优点是：

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

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

分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。

2 文件结构设计

2.2 排序规则文件

存储排序文件，如果使用二进制进行排序大小可以为空。排序文件应为文本文件，字符集的排序信息以行为单位存储，即每行存储一个字母。例如，给英文字母的排序规则，则需要把26个英文字母写到26行。

2.3 索引

索引包含了通过排序规则进行排序的数据的索引。该文中的数据是以二进制方式进行排序的。索引的内容是四个Int类型，分别是Key字符串在数据段的地址和长度和Value字符串在数据段的地址和长度。通过地址和长度可以获取数据段中Key和Value的数据。

2.4 数据

数据段中存放着实际需要的数据，它们是通过以二进制形式连续存放的，通过索引进行获取。每一条数据的内容是KeyString + ValueString。

3 二分查找算法的实现

参考文献：

[1] 雷军环，刘震.数据结构（C#语言版）[M].北京：清华大学出版社，2009.

[2] 邝继顺，颜运昌.汉语词典的快速查询算法研究[J].小型微型计算机系统，2001（11）：1396-1398.

[3] 李江波，，陈祖舜.汉语词典的快速查询算法研究[J].中文信息学报，2006（5）：31-39.