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
前綴＝輸入流［輸入序號］；
輸入流序號++；