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