|
|
最近寫了一個文件壓縮程序，采用的是字典壓縮算法中的一種。
首先介紹一下我的字典壓縮算法：
字典壓縮算法就是用盡可以短(占用的二進制bit 位)的標(biāo)記數(shù)據(jù)，代替盡可能長的 原始文件數(shù)據(jù),從而達到壓縮的效果。
總的來說,字典壓縮算法 可以理解為 一個壓縮機。 一頭輸入(從源文件中讀取數(shù)據(jù)）要壓縮的數(shù)據(jù)，另一頭輸出(輸入到壓縮文件)或不輸出。
與赫夫曼算法比較可知采用服 這種算法 內(nèi)存中不須要滯留 太多原始數(shù)據(jù)，這里說的不須要滯留原始數(shù)據(jù)指的是不須要 先將要壓縮的全部數(shù)據(jù)讀入內(nèi)存。因為這種算法不須要對整個文件數(shù)據(jù)進行統(tǒng)計。
當(dāng)然完全不要滯留是不可能的。這里要滯留的僅僅是字典。
首先我們明白 字典里裝的是什么 prefix (前綴) 和 suffix (后綴) . 例如: index :1 content: preffix : a suffix : b ;
前綴可以是原始數(shù)據(jù)也可以是原始數(shù)據(jù)的標(biāo)記,我們知道對于任可數(shù)據(jù)都是由二進制0或1組成的。所有我們在一次讀一個byte后得到的原始數(shù)據(jù)的范圍在0到255之間。 之所以能夠達到壓縮的效果是因為
我們可以用0到255范圍外的數(shù)來代替很多個原始byte 原始數(shù)據(jù)重復(fù)數(shù)據(jù)越多壓縮效果就越好。這很好理解，然而關(guān)鍵就是怎么才能做到用0到255范圍外的數(shù)據(jù)代替原來的數(shù)據(jù)呢。所以這里我們就要擴展
數(shù)據(jù)位了。也就是說原來8個bit表示的數(shù)據(jù)現(xiàn)在我們要用9個bit來表示.最高位我們讓他為0，因為9位能表示的范圍達到了0到511。當(dāng)然我們也可能要擴展到十二位來表示一個數(shù)據(jù)單元.這就取決于我們
的字典造多大。按理來說字典構(gòu)造得越大達到的壓縮效果是越好。但是這樣程序的復(fù)雜度也將增加。我采用的字典最大index 為4095,達到最大index后重新構(gòu)造字典 也就是十二個bit所能表示的范圍。
然而還有一個關(guān)鍵的問題就是我們解壓的時候怎么知道我們現(xiàn)在一次要讀多少個bit位，字典index 達到最大值后，怎么知道要重構(gòu)字典呢。所以我們還得加上6個數(shù)據(jù)擴展標(biāo)記位(bit位有變時標(biāo)記)，和一個字典重構(gòu)標(biāo)記。
達到擴展數(shù)據(jù)位的方法就是位運算。所以字典壓縮和 解壓程序整個就是位運算.
下面就說壓縮算法:
先來一個例子，便于理解算法
input index prefix suffix string outPut
A A
B 263 A B AB A
A 264 B A BA B
B
A 265 263 A ABA 263
B
A
B 266 265 B ABAB 265
B 267 B B BB B
B
A 268 267 A BBA 267
B
A
B
A 269 266 A ABABA 266
A 270 A A AA A
C 271 A C AC A
D 272 C D CD C
A 273 D A DA D
C
D 274 271 D ACD 271
A
D 275 273 D DAD 273
C 276 D C DC D
A 277 C A CA C
B
A
A 278 265 A ABAA 265
A
B 279 270 B AAB 270
A
B 280 264 B BAB 264
B
原始數(shù)據(jù)占用bit位數(shù):
32*8=256
壓縮后數(shù)據(jù)占用bit位數(shù):
18*9=162
顯然 162<256 原始數(shù)據(jù)被壓縮了。
以C語言為例 字典數(shù)據(jù)結(jié)構(gòu)為：
struct 標(biāo)號｛
word 前綴；
word 后綴；
｝;
結(jié)構(gòu)數(shù)組為：
標(biāo)號標(biāo)號組[4095]；
壓縮算法如下：
int 當(dāng)前最大標(biāo)號＝263；
word 前綴，后綴；
char輸入流［x］；
int 輸入序號＝0
然后，我們讀入第一個字符 A和第二個字符B 。
前綴＝輸入流［輸入序號］；
輸入序號＋＋；
從這里開始，我們開始壓縮過程，直到把數(shù)據(jù)處理玩：
int I=263;
for(輸入序號 ; 輸入序號<X ; 輸入序號++){
后綴＝輸入流［輸入序號］；
//查找當(dāng)前串在表中的位置
bool found=false;
while ( I<當(dāng)前最大標(biāo)號 ) {
if ( 前綴 != 標(biāo)號組［I］。前綴) ｛I＋＋；continue;｝
if( 后綴 != 標(biāo)號組［I］。后綴 ) ｛I＋＋；continue;｝
//找到了，就是這個串
found=true;
前綴＝I； //把當(dāng)前串規(guī)約到標(biāo)號
I＋＋；
break;
｝
if ( ! found ) { //沒找到，把這個串加到標(biāo)號組中
標(biāo)號組［當(dāng)前最大標(biāo)號］。前綴＝前綴；
標(biāo)號組［當(dāng)前最大標(biāo)號］。后綴＝后綴；
當(dāng)前最大標(biāo)號＋＋；
輸出 前綴
前綴＝后綴；
if （當(dāng)前最大標(biāo)號> 4095）{ //已經(jīng)超過了最大的長度
當(dāng)前最大標(biāo)號＝263；
輸出字典重構(gòu) 標(biāo)志；
｝
I=263;
｝
｝
解壓是壓縮的逆過程:
如圖
input index prefix suffix stack outPut
A A
B 263 A B A
263 264 B A B
265 265 263 A AB AB
B 266 265 B ABA ABA
267 267 B B B
266 268 267 A BB BB
A 269 266 A ABAB ABAB
A 270 A A A
C 271 A C A
D 272 C D C
271 273 D A D
273 274 271 D AC AC
D 275 273 D DA DA
C 276 D C D
265 277 C A C
270 278 265 A ABA ABA
264 279 270 B AA AA
B 280 264 B BA BA
B
解壓算法如下：
int 當(dāng)前標(biāo)號＝263；
棧 stack;
int 前綴，后綴；
int 輸入流［x］；
int 輸入序號＝0
前綴＝輸入流［輸入序號］；
輸入流序號++；
for(輸入序號 ; 輸入序號<X ; 輸入序號++){
標(biāo)號組[當(dāng)前標(biāo)號]。前綴=前綴；
后綴=輸入流[輸入流序號]；
//確定當(dāng)前后綴
if(當(dāng)前后綴<256){
標(biāo)號組[當(dāng)前標(biāo)號]。后綴=后綴；
當(dāng)前標(biāo)號++；
}else {
后綴=標(biāo)號組[后綴]。前綴；
while(后綴>255){
后綴=標(biāo)號組[后綴]。前綴；
}
//在字典中找到了原始數(shù)據(jù)前綴
標(biāo)號組[當(dāng)前標(biāo)號]。后綴=后綴；
當(dāng)前標(biāo)號++；
}
//確定前綴并輸出
if(前綴<256){
輸出 (char)前綴；
} else{ /*前綴不是原始數(shù)據(jù)*/
push(標(biāo)號組[前綴].后綴);//字典中序號為當(dāng)前前綴的，結(jié)構(gòu)體后綴入棧
if((標(biāo)號組[前綴].前綴)<256){ //字典中序號為當(dāng)前前綴的，結(jié)構(gòu)體前綴為原始數(shù)據(jù),則入棧
push(標(biāo)號[前綴].前綴); // 入棧
}else{
前綴=標(biāo)號組[前綴].前綴;
while(前綴>256){/*字典中序號為當(dāng)前前綴的，結(jié)構(gòu)體前綴為原始數(shù)據(jù)的標(biāo)記*/
push(標(biāo)號組[前綴].后綴）;//后綴入棧
前綴=標(biāo)號組[前綴].前綴;改變當(dāng)前前綴
}
//字典中找到了序號為當(dāng)前前綴的，結(jié)構(gòu)體前綴為原始數(shù)據(jù)
push(前綴)//前綴入棧
while(stack不空){
輸出(pop());
}
}
前綴=輸入流[輸入流序號]；
}
|
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
