問題重述：有一個(gè)內(nèi)含有大約40萬條常用詞匯的詞庫(kù)。現(xiàn)給定一篇文章，使用這個(gè)詞庫(kù)分析出常用詞匯的出現(xiàn)次數(shù)，并按出現(xiàn)次數(shù)由高到低排序這些詞語。

改進(jìn)算法的思路：
  1. 通常一篇文章所包含的詞語遠(yuǎn)少于詞庫(kù)中40萬的數(shù)量；
  2. 數(shù)據(jù)庫(kù)建立索引之后，可采用“二分法”對(duì)詞語進(jìn)行快速定位；

  3. 逐字縮小查詢范圍，如果查詢到某個(gè)字符時(shí)范圍已經(jīng)為0，那么可以預(yù)測(cè)其后的詞一定也不存在，（例如查詢到forest時(shí)已經(jīng)沒有匹配的詞了，就可以到此結(jié)束）。
以下是算法的實(shí)現(xiàn)：

一、首先，利用文本文件制作詞典（二進(jìn)制文件）。包括導(dǎo)入字符串?dāng)?shù)據(jù)、排序、剔除重復(fù)項(xiàng)、創(chuàng)建索引表。

字典文件格式描述如下：

  1. 文件頭（16字節(jié)）：

--------------------------------------------------------------------------
| "MAODICT"字符串(8字節(jié)) | 索引區(qū)開始位置(4字節(jié)) | 索引區(qū)結(jié)束位置(4字節(jié)) |
--------------------------------------------------------------------------

  2. 字符串存儲(chǔ)區(qū)：

     每條字符串均以'\0'結(jié)尾，連續(xù)存放。

  3. 索引區(qū)：

     每個(gè)索引表項(xiàng)格式（5字節(jié)）：

---------------------------------------------
| 字符串偏移量（4字節(jié)） | 詞條長(zhǎng)度（1字節(jié)） |
---------------------------------------------

字符串緊跟文件頭存放，索引區(qū)在字符串存儲(chǔ)區(qū)之后。

文件頭和索引表項(xiàng)結(jié)構(gòu)體：

// 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;
 

數(shù)據(jù)導(dǎo)入代碼咱略，詳見附件msearch.cpp中的textToBinaryFile()函數(shù)。

二、利用創(chuàng)建的字典文件，編寫檢索程序。SearchTextFile()函數(shù)利用傳入的文件名打開并進(jìn)行“內(nèi)存文件映射”，利用傳入的數(shù)據(jù)流讀取文本數(shù)據(jù)。從某個(gè)位置起始，向后組成“詞語”進(jìn)行查詢，到一定長(zhǎng)度“失配”后，起始位置移到下一個(gè)字符。由于數(shù)據(jù)流不能回退，故需緩存已讀取的字符，每次“失配”后將緩沖區(qū)向前整體移動(dòng)一個(gè)字符位置（memmove()）。算法利用了兩個(gè)變量：j 用于記錄當(dāng)前字符相對(duì)于起始位置的偏移，k 用于記錄緩沖區(qū)中已讀取的字符的數(shù)量。

三、二分法逐字檢索 是查詢程序的核心算法。

四、使用方法：

Usage:   
  msearch -c <source file>  .... 利用文本文件創(chuàng)建字典.   
  msearch <dict file>       .... 以 dict file 作為字典，讀取標(biāo)準(zhǔn)輸入內(nèi)容進(jìn)行檢索，以[Ctrl+Z]結(jié)尾.   
  msearch -h                .... 顯示幫助信息.   
Examples:   
  msearch -c English.txt    .... Create English.dat.
  msearch English.dat <gpl3.txt >result.txt
             .... 檢索gpl3.txt，將結(jié)果寫入result.txt，使用字典English.dat

詳細(xì)說明請(qǐng)見： http://blog.csdn.net/rssn_net/archive/2009/01/30/3854760.aspx
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃源碼網(wǎng) - 下載文件說明：                              CodePub.com┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
┃          做最好的源碼下載網(wǎng)站：源碼網(wǎng)，www.codepub.com         ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
┃【使用前請(qǐng)您先閱讀以下條款，否則請(qǐng)勿使用本站提供的文件！】      ┃
┃ 1) 推薦使用：WinRAR V3.4以上版本解壓本站軟件                   ┃
┃ 2) 本站不保證所提供軟件或程序的完整性和安全性。                ┃
┃ 3) 請(qǐng)?jiān)谑褂们安槎?(這也是您使用其它網(wǎng)絡(luò)資源所必須注意的) 。    ┃
┃ 4) 由本站提供的程序?qū)δW(wǎng)站或計(jì)算機(jī)造成嚴(yán)重后果的本站概不負(fù)責(zé)。┃
┃ 5) 本站提供的程序均為網(wǎng)上搜集，如果該程序涉及或侵害到您的版權(quán)請(qǐng)┃
┃ 立即寫信通知我們。                                             ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
┃ 如果遇到MD5加密文件(一般都是這個(gè))，而又不知道密碼的，          ┃
┃ 請(qǐng)用這組加密的數(shù)據(jù)1739fddf100746ca替換,那么密碼就是:codepub.com┃
┃ (這個(gè)是16位的,32位的是:7773164f11739fddf100746ca6b337834)      ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
┃ 歡迎廣大程序作者到本站發(fā)布您的作品！                           ┃
┃ 源碼網(wǎng) - 下載源碼就到源碼網(wǎng)                                    ┃
┃ 聯(lián)系郵箱：wuse#codepub.com( #替換成@ )                         ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛