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)號(hào)｛
word 前綴；
word 后綴；
｝;
結(jié)構(gòu)數(shù)組為：
標(biāo)號(hào)標(biāo)號(hào)組[4095]；
壓縮算法如下：
int 當(dāng)前最大標(biāo)號(hào)＝263；
word 前綴，后綴；
char輸入流［x］；
int 輸入序號(hào)＝0
然后，我們讀入第一個(gè)字符 A和第二個(gè)字符B 。
前綴＝輸入流［輸入序號(hào)］；
輸入序號(hào)＋＋；
從這里開始，我們開始?jí)嚎s過程，直到把數(shù)據(jù)處理玩：
int I=263;
for(輸入序號(hào) ; 輸入序號(hào)<X ; 輸入序號(hào)++){
后綴＝輸入流［輸入序號(hào)］；
//查找當(dāng)前串在表中的位置
bool found=false;
while ( I<當(dāng)前最大標(biāo)號(hào) ) {
if ( 前綴 != 標(biāo)號(hào)組［I］。前綴) ｛I＋＋；continue;｝
if( 后綴 != 標(biāo)號(hào)組［I］。后綴 ) ｛I＋＋；continue;｝
//找到了，就是這個(gè)串
found=true;
前綴＝I； //把當(dāng)前串規(guī)約到標(biāo)號(hào)
I＋＋；
break;
｝
if ( ! found ) { //沒找到，把這個(gè)串加到標(biāo)號(hào)組中
標(biāo)號(hào)組［當(dāng)前最大標(biāo)號(hào)］。前綴＝前綴；
標(biāo)號(hào)組［當(dāng)前最大標(biāo)號(hào)］。后綴＝后綴；
當(dāng)前最大標(biāo)號(hào)＋＋；
輸出 前綴
前綴＝后綴；
if （當(dāng)前最大標(biāo)號(hào)> 4095）{ //已經(jīng)超過了最大的長(zhǎng)度
當(dāng)前最大標(biāo)號(hà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)號(hào)＝263；
棧 stack;
int 前綴，后綴；
int 輸入流［x］；
int 輸入序號(hào)＝0
前綴＝輸入流［輸入序號(hào)］；
輸入流序號(hào)++；