rle

一種壓縮過的點陣圖文件格式，RLE壓縮方案是一種極其成熟的壓縮方案，特點是無損失壓縮，既節省了磁碟空間又不損失任何圖像數據。

在打開這種壓縮文件時，要花費更多時間，此外，一些兼容性不太好的應用程序可能會打不開。

ABBBBBBBBA - 1A8B1A

不過RLE還有一個缺點，那要是內容像ABCABCABC的話使用這種演演算法文件會增大，就是1A1B1C1A1B1C1A1B1C了，更長，就達不到壓縮的效果了。簡單的說RLE壓縮就是將一串連續的相同數據轉化為特定的格式達到壓縮的目的。

下面都對byte流壓縮。

如輸入數據

LPBTEpByte={1,1,1,1,1,1};

壓縮的數據為6,1

壓縮了4個字元。

但是在數據流裡面不能直接這麼替換，而應該使用特殊的控制字元，否則無法解壓。

比如pByte={6,1,0,1,1,1,1,1,1};

這樣有兩個6,1無法判斷是原有的6,1還是{1,1,1,1,1,1}壓縮后的代碼。

所以應該有控制字元。

(1)

為了達到最大壓縮率，可以先掃描源數據流，使用最少出現的字元做控制字元。

如pByte={6,1,0,1,1,1,1,1,1,...};

掃描后發現0為最少出現的字元。

我們使用0作為壓縮的控制，其他字元代表他本身。源數據裡面的0,用0,0來表示。

那麼pByte壓縮後為

6,1,0,0,0,6,1......

解壓時BYTEa,b,c;

a=依次掃描壓縮數據，如果輸入字元為非控制字元，則直接輸出到解壓流。

如果為控制字元，b=其下一字元是否也為控制字元，如果是，在輸出流輸出控制字元的代碼。

如果不是c=讀壓縮流，然後輸出b個c到輸出流。

注意：該處對於>Ctrlcode的編碼需要自己計算偏移.

如ctrl=2.那麼n=3時應該修正為2.

剛才介紹的方法是最大壓縮率的，但是因為對每個輸入字元需要檢查，速度不算快。

(2)

為了增加解壓速度，可以採用其他的編碼方式。

主要方法是不對每個輸入字元進行檢查，只檢查較少次就達到幾乎相同的壓縮率。

來看看這個改進的方法。

仔細觀察，其實對不重複的字元也可以用控制n+數據的方式表示。這裡的n帶表n個未壓縮數據。

還是剛才的數據。

pByte={6,1,0,1,1,1,1,1,1}

不用掃描選擇0為控制

壓縮為3,{6,1,0,}0,6,1

nctrlnm

解壓就非常方便了

掃描數據讀一個字元，

{

n=read;

if(n)

{

字元拷貝n個

}

else

{

n=read();

m=read;

write(n個m);

}

}

(3)優化

對(1)的優化。

觀察得知，1,1,1這樣的數據壓縮率為0