readme.txt

问题重述：有一个内含有大约40万条常用词汇的词库。现给定一篇文章

问题重述：有一个内含有大约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
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃源码网 - 下载文件说明：                              CodePub.com┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
┃          做最好的源码下载网站：源码网，www.codepub.com         ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
┃【使用前请您先阅读以下条款，否则请勿使用本站提供的文件！】      ┃
┃ 1) 推荐使用：WinRAR V3.4以上版本解压本站软件                   ┃
┃ 2) 本站不保证所提供软件或程序的完整性和安全性。                ┃
┃ 3) 请在使用前查毒 (这也是您使用其它网络资源所必须注意的) 。    ┃
┃ 4) 由本站提供的程序对您网站或计算机造成严重后果的本站概不负责。┃
┃ 5) 本站提供的程序均为网上搜集，如果该程序涉及或侵害到您的版权请┃
┃ 立即写信通知我们。                                             ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
┃ 如果遇到MD5加密文件(一般都是这个)，而又不知道密码的，          ┃
┃ 请用这组加密的数据1739fddf100746ca替换,那么密码就是:codepub.com┃
┃ (这个是16位的,32位的是:7773164f11739fddf100746ca6b337834)      ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
┃ 欢迎广大程序作者到本站发布您的作品！                           ┃
┃ 源码网 - 下载源码就到源码网                                    ┃
┃ 联系邮箱：wuse#codepub.com( #替换成@ )                         ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛