C語言中壓縮字符串的算法

本文格式為Word版，下載可任意編輯——C語言中壓縮字符串的算法C語言中壓縮字符串的算法

在C應(yīng)用中，經(jīng)常需要將字符串壓縮成一個整數(shù)，即字符串散列。下面是我為大家整理的C語言中壓縮字符串的算法，接待參考~

譬如下面這些問題：

1探尋引擎會通過日志文件把用戶每次檢索使用的全體檢索串都記錄下來，每個查詢串的長度為1-255字節(jié)。請找出最熱門的10個檢索串。

2有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個詞。

3有10個文件，每個文件1G，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復(fù)。要求你按照query的頻度排序。

4給定a、b兩個文件，各存放50億個url，每個url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的`url。

5一個文本文件，大約有一萬行，每行一個詞，要求統(tǒng)計出其中最頻繁展現(xiàn)的前10個詞。

這些問題都需要將字符串壓縮成一個整數(shù)，或者說是散列到某個整數(shù)M。然后再舉行取余操作，譬如M%16，就可以將該字符串放到編號為M%16的文件中，一致的字符串?dāng)喽ㄊ窃谕粋€文件中。通過這種處理，就可以將一個大文件等價劃分成若干小文件，而對于小文件，就可以用常規(guī)的方法處理，內(nèi)排序、hash_map等等。結(jié)果將這些小文件的處理結(jié)果綜合起來，就可以求得原問題的解。

下面介紹一些字符串壓縮的算法。

方法1：最簡樸就是將全體字符加起來，代碼如下：

unsignedlongHashStringconstchar*pString,unsignedlongtableSize

unsignedlonghashValue=0;

while*pString

hashValue+=*pString++;

returnhashValue%tableSize;

分析：假設(shè)字符串的長度有限，而散列表對比大的話，濫用對比大。例如，假設(shè)字符串最長為16字節(jié)，那么用到的僅僅是散列表的前16*127=2032。假使散列表含2729項，那么2032以后的項都用不到。

方法2：將上次計算出來的hash值左移5位（乘以32），再和當(dāng)前關(guān)鍵字相加，能得到較好的平勻分布的效果。

unsignedlongHashStringconstchar*pString,unsignedlongtableSize

unsignedlonghashValue=0;

while*pString

hashValue=hashValue5+*pString++;

returnhashValue%tableSize;

分析：這種方法需要遍歷整個字符串，假設(shè)字符串對比大，效率對比低。

方法3：利用哈夫曼算法，假設(shè)只有0-9這十個字符組成的字符串，我們借助哈夫曼算法，直接來看實例：

#defineSize10

intfreq[Size];

stringcode[Size];

stringword;

structNode

intid;

intfreq;

Node*left;

Node*right;

Nodeintfreq_in:id-1,freqfreq_in

left=right=NULL;

;

structNodeLess

booloperatorconstNode*a,constNode*bconst

returna-freqb-freq;

;

voidinit

forinti=0;iSize;++i

freq[i]=0;

forinti=0;iword.size;++i

++freq[word[i]];

voiddfsNode*root,stringres

ifroot-id=0

code[root-id]=res;

else

ifNULL!=root-left

dfsroot-left,res+0;

ifNULL!=root-right

dfsroot-right,res+1;

voidNodesNode*root

ifNULL==root

return;

ifNULL==root-leftNULL==root-right

root;

else

Nodesroot-left;

Nodesroot-right;

root;

voidBuildTree

priority_queueNode*,vector,NodeLessnodes;

forinti=0;iSize;++i

//0==freq[i]的處境未處理

Node*newNode=newNodefreq[i];

newNode-id=i;

nodes.pushnewNode;

whilenodes.size1

Node*left=nodes.top;

nodes.pop;

Node*right=nodes.top;

nodes.pop;

Node*newNode=newNodeleft-freq+right-freq;

newNod