顺序表字典二分法逐级检索 源码

问题重述：有一个内含有大约40万条常用词汇的词库。现给定一篇文章，使用这个词库分析出常用词汇的出现次数，并按出现次数由高到低排序这些词语。 改进算法的思路： 1. 通常一篇文章所包含的词语远少于词库中40万的数量； 2. 数据库建立索引之后，可采用“二分法”对词语进行快速定位； 3. 逐字缩小查询范围，如果查询到某个字符时范围已经为0，那么可以预测其后的词一定也不存在，（例如查询到forest时已经没有匹配的词了，就可以到此结束）。 以下是算法的实现： 一、首先，利用文本文件制作词典（二进制文件）。包括导入字符串数据、排序、剔除重复项、创建索引表。 字典文件格式描述如下： 1. 文件头（16字节）： -------------------------------------------------------------------------- | "MAODICT"字符串(8字节) | 索引区开始位置(4字节) | 索引区结束位置(4字节) | -------------------------------------------------------------------------- 2. 字符串存储区： 每条字符串均以'\0'结尾，连续存放。 3. 索引区： 每个索引表项格式（5字节）： --------------------------------------------- | 字符串偏移量（4字节） | 词条长度（1字节） | --------------------------------------------- 字符串紧跟文件头存放，索引区在字符串存储区之后。 文件头和索引表项结构体： // Dictionary file header typedef struct _DictHeader { char maodict[8]; // string "MAODICT" long so; // index start offset long eo; // index end offset } DictHeader; // Index item structure(5 bytes) typedef struct _IndexItem { union { long offset; // string offset char * str; // string pointer(unused) }; char length; // string length } IndexItem; // Dictionary file header typedef struct _DictHeader { char maodict[8]; // string "MAODICT" long so; // index start offset long eo; // index end offset } DictHeader; // Index item structure(5 bytes) typedef struct _IndexItem { union { long offset; // string offset char * str; // string pointer(unused) }; char length; // string length } IndexItem; 数据导入代码咱略，详见附件msearch.cpp中的textToBinaryFile()函数。 二、利用创建的字典文件，编写检索程序。SearchTextFile()函数利用传入的文件名打开并进行“内存文件映射”，利用传入的数据流读取文本数据。从某个位置起始，向后组成“词语”进行查询，到一定长度“失配”后，起始位置移到下一个字符。由于数据流不能回退，故需缓存已读取的字符，每次“失配”后将缓冲区向前整体移动一个字符位置（memmove()）。算法利用了两个变量：j 用于记录当前字符相对于起始位置的偏移，k 用于记录缓冲区中已读取的字符的数量。 三、二分法逐字检索 是查询程序的核心算法。 四、使用方法： Usage: msearch -c <source file> .... 利用文本文件创建字典. msearch <dict file> .... 以 dict file 作为字典，读取标准输入内容进行检索，以[Ctrl+Z]结尾. msearch -h .... 显示帮助信息. Examples: msearch -c English.txt .... Create English.dat. msearch English.dat <gpl3.txt >result.txt .... 检索gpl3.txt，将结果写入result.txt，使用字典English.dat 详细说明请见： http://blog.csdn.net/rssn_net/archive/2009/01/30/3854760.aspx