rle8壓縮

A. RLE壓縮是怎麼回事啊

RLE壓縮及優化

簡單的說RLE壓縮就是將一串連續的相同數據轉化為特定的格式達到壓縮的目的。

下面都對byte流壓縮。
如輸入數據
LPBTE pByte={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 ......

解壓時 BYTE a,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
n ctrl n m

解壓就非常方便了

掃描數據讀一個字元，
{
n=read;
if(n)
{
字元拷貝n個
}
else
{
n=read();
m=read;
write (n個m);
}

}

(3)優化

對(1)的優化。
觀察得知，1,1,1這樣的數據壓縮率為0,
所以當n<=3時不用壓縮。
而直接寫為1,1,1樣的格式。

另外如果有多個控制字元連續。也可以壓縮。
觀察ctrl=0;
0,0,0,0
如果用控制編碼為8個0
而壓縮編碼為0,4,0 所以控制字元連續兩個即可壓縮。

對(2)：

只對壓縮編碼優化。
例
1,2,3,4,1,1
如果死套公式，為
4,1,2,3,4,0,2,1
反倒增加2個位元組。
如果用
6,1,2,3,4,1,1隻增加一個位元組。