文章轉(zhuǎn)發(fā)自51CTO【ELT.ZIP】OpenHarmony啃論文俱樂(lè)部——《統(tǒng)計(jì)壓縮編碼機(jī)理分析》

上篇回顧：《統(tǒng)計(jì)壓縮編碼機(jī)理分析（上篇）》

6.算術(shù)編碼

《上篇》中第五章的“哈夫曼編碼”方法建立在符號(hào)和碼字相對(duì)應(yīng)的基礎(chǔ)上。若對(duì)信源單符號(hào)進(jìn)行編碼，則符號(hào)間的相關(guān)性就無(wú)法考慮：若將 m 個(gè)符號(hào)合起來(lái)編碼，第一是會(huì)增加設(shè)備復(fù)雜度，第二是 m＋1 個(gè)符號(hào)間以及組間符號(hào)的相關(guān)性還是無(wú)法考慮。這就使信源編碼的匹配原則不能充分滿足，編碼效率就有所折損。為了克服這種局限性，研究了非分組碼的編碼方法。

算術(shù)編碼是一種非分組碼，其基本原理是將編碼的消息表示成實(shí)數(shù)0和1之間的一個(gè)間隔，消息越長(zhǎng)，編碼表示它的間隔就越小，表示這一間隔所需的二進(jìn)制位就越多。

算數(shù)編碼是一種在有損壓縮與無(wú)損壓縮算法中都經(jīng)常使用的一種算法，主要應(yīng)用于圖像壓縮。算數(shù)編碼與其它統(tǒng)計(jì)編碼不同，其它的統(tǒng)計(jì)編碼通常是把輸入的消息分割成符號(hào)后對(duì)其進(jìn)行編碼，而算數(shù)編碼則將輸入的字符劃分成若干個(gè)子區(qū)間來(lái)代表一個(gè)字符，計(jì)算其概率，進(jìn)行編碼。

6.1基本機(jī)理

算術(shù)編碼的背后是深刻的數(shù)學(xué)思想，簡(jiǎn)單來(lái)說(shuō)，它做了這樣一件事情：

1. 假設(shè)有一段數(shù)據(jù)需要編碼，統(tǒng)計(jì)里面所有的字符和出現(xiàn)的次數(shù)

2. 將區(qū)間 [0,1) 連續(xù)劃分成多個(gè)子區(qū)間，每個(gè)子區(qū)間代表一個(gè)上述字符， 區(qū)間的大小正比于這個(gè)字符在文中出現(xiàn)的概率 p。概率越大，則區(qū)間越大。所有的子區(qū)間加起來(lái)正好是 [0,1)

3. 編碼從一個(gè)初始區(qū)間 [0,1) 開(kāi)始，設(shè)置：

4. 不斷讀入原始數(shù)據(jù)的字符，找到這個(gè)字符所在的區(qū)間，例如 [ L, H )，更新：

5. 最后將得到的區(qū)間 [low, high)中任意一個(gè)小數(shù)以二進(jìn)制形式輸出即得到編碼的數(shù)據(jù)：

6.2編碼過(guò)程

給出下面一段十分簡(jiǎn)單的原始數(shù)據(jù)：

ARBER

像所有統(tǒng)計(jì)編碼一樣，統(tǒng)計(jì)各字符出現(xiàn)的次數(shù)與概率：

字符	次數(shù)	概率
A	1	0.2
B	1	0.2
E	1	0.2
R	2	0.4

將這幾個(gè)字符的區(qū)間在 [0，1) 上按照概率大小連續(xù)一字排開(kāi)，我們得到一個(gè)劃分好的 [0，1)區(qū)間：

開(kāi)始編碼，初始區(qū)間是 [0，1)。注意這里又用了區(qū)間這個(gè)詞，不過(guò)這個(gè)區(qū)間不同于上面代表各個(gè)字符的概率區(qū)間 [0，1)。這里我們可以稱之為編碼區(qū)間，這個(gè)區(qū)間是會(huì)變化的，確切來(lái)說(shuō)是不斷變小。我們將編碼過(guò)程用下圖完整地表示出來(lái)：

我們對(duì)其進(jìn)行步驟拆解：

1. 剛開(kāi)始編碼區(qū)間是 [0，1)，即：

2. 第一個(gè)字符A的概率區(qū)間是 [0，0.2)，則 L = 0，H = 0.2，更新：

3. 第二個(gè)字符R的概率區(qū)間是 [0.6，1)，則 L = 0.6，H = 1，更新：

4. 第三個(gè)字符B的概率區(qū)間是 [0.2，0.4)，則 L = 0.2，H = 0.4，更新：

我們可以看到一個(gè)不斷變化的小數(shù)編碼區(qū)間。每次編碼一個(gè)字符，就在現(xiàn)有的編碼區(qū)間上，按照概率比例取出這個(gè)字符對(duì)應(yīng)的子區(qū)間。例如一開(kāi)始A落在0到0.2上，因此編碼區(qū)間縮小為 [0，0.2)，第二個(gè)字符是R，則在 [0，0.2)上按比例取出R對(duì)應(yīng)的子區(qū)間 [0.12，0.2)，以此類推。每次得到的新的區(qū)間都能精確無(wú)誤地確定當(dāng)前字符，并且保留了之前所有字符的信息，因?yàn)樾碌木幋a區(qū)間永遠(yuǎn)是在之前的子區(qū)間。最后我們會(huì)得到一個(gè)長(zhǎng)長(zhǎng)的小數(shù)，這個(gè)小數(shù)即神奇地包含了所有的原始數(shù)據(jù)，不得不說(shuō)這真是一種非常巧妙的思想。

6.3解碼過(guò)程

如果理解了編碼的原理，那么解碼的方法顯而易見(jiàn)，就是編碼過(guò)程的逆推。從編碼得到的小數(shù)開(kāi)始，不斷地尋找小數(shù)落在了哪個(gè)概率區(qū)間，就能將原來(lái)的字符一個(gè)個(gè)地找出來(lái)。例如得到的小數(shù)是0.14432，則第一個(gè)字符顯然是A，因?yàn)樗湓诹?[0，0.2)上，接下來(lái)再看0.14432落在了 [0，0.2)區(qū)間的哪一個(gè)相對(duì)子區(qū)間，發(fā)現(xiàn)是 [0.6，1)， 就能找到第二個(gè)字符是R，依此類推。在此不再贅述具體步驟。

6.4算法實(shí)現(xiàn)

#include 
#include 
#include 
#include 


char inStr[100], chSet[20]; //輸入字符串和字符集
float P[20];                    //每個(gè)字符的概率
float pZone[20];              //概率區(qū)間
int strLen;         //輸入字符串長(zhǎng)度
int chNum;          //字符集中字符個(gè)數(shù)
int binary[100];
float infoLen;          //信息量大小


void compress();        //編碼函數(shù)
void uncompress();      //解碼函數(shù)


int main()
{
    
    int i,j;
            
    printf("input the length of char set:
");
    scanf("%d", &chNum);
    getchar();


    printf("input the char and its p
");
    for (i=0; i < chNum; i++) {
        printf("input char: ");
        scanf("%c", &chSet[i]);
            
        getchar();
        //printf("sssss%c  ", chSet[i]); 
        printf("
input its p: ");
        scanf("%f",&P[i]);
        getchar();
        printf("
");
    }
    /* test
    for (i = 0; i < chNum; ++i)
         printf("%c<-------------->%f
", chSet[i], P[i]);
    */


    // 計(jì)算概率區(qū)間
    pZone[0] = 0;
    for (i=1; i < chNum; ++i)
        pZone[i] = pZone[i-1] + P[i-1];


    printf("input the string 
");
    fgets(inStr, 100, stdin);
    strLen = strlen(inStr);
    /************* test ***************/
    printf("the string is: 
");
    puts(inStr);


    printf("*********** compress **************
");
    compress();
    printf("
*********** uncompress **************
");
    uncompress();
    return 0; 


}


void compress()
{
    float low = 0, high = 1;
    float L, H, zlen = 1;
    float cp;       //輸入字符的概率
    float result;       //結(jié)果
    int i, j;


    for (i=0; i < strLen; i++) {
        for (j=0; j < chNum; j++) {
            if (inStr[i] == chSet[j]) {
                
                //cp = P[j];
                //L = pZone[j];
                low = low + zlen * pZone[j];
                zlen *= P[j]; 
                break;
            }
        }
        //low = low + zlen * L;
        //zlen *= cp; 
        
    }
    result = low;
    
    printf("the result is %f
", result);
    
    infoLen = log(1/zlen) / log(2);     //計(jì)算香農(nóng)信息量


    if(infoLen > (int)infoLen)
        infoLen = (int)infoLen + 1;
    else
        infoLen = (int)infoLen;


    for (i=0; i < infoLen; i++) {
        result *= 2;
        
        if (result > 1) {
            result = result - 1;
            binary[i] = 1;


        } else if (result < 1) {
                binary[i] = 0;


        } else {
            break;
        }


    }


    if (i >= infoLen) {
        for (j=i; j >= 1; j--) {        
            binary[j-1] = (binary[j-1]+1)%2;
            if (binary[j-1] == 1)
                break;  
        }
    }


    printf("****************** the compress result*****************
");
    for (j=0; j < i; j++)
        printf("%d ", binary[j]);
}


void uncompress()
{ 
    int i,j;
    float w = 0.5;
    float deResult=0;
    
    float newLow,newLen;
    float low=0,zlen=1;


    for (i=0; i < infoLen; i++) {
        deResult += w*binary[i];
        w *= 0.5;
    }
    printf("uncompress to ten:%f
", deResult);


    printf("uncompress result:
");
    for (i=0; i < strLen; i++) {
        for (j=chNum; j > 0; j--) {
            newLow = low;
            newLen = zlen;
                newLow += newLen * pZone[j-1];      
            newLen *= P[j-1];   
            if (deResult >= newLow) {
                low=newLow;
                zlen=newLen;
                printf("%c ",chSet[j-1]);
                break;
            }
        }
    }
    
}

6.5與哈夫曼編碼的比較我們首先回顧一下哈夫曼編碼，換一組數(shù)據(jù)并統(tǒng)計(jì)字符的出現(xiàn)次數(shù)，生成哈夫曼樹(shù)，我們可以得到以下字符編碼集：

字符	次數(shù)	編碼
a	3	0
b	3	1
c	2	10
d	1	110
e	2	111

仔細(xì)觀察編碼所表示的小數(shù)，從0.0到0.111，其實(shí)就是構(gòu)成了算數(shù)編碼中的各個(gè)概率區(qū)間，并且概率越大，所用的bit數(shù)越少，區(qū)間則反而越大。如果用哈夫曼編碼一段數(shù)據(jù)abcde，則得到：000110110111

如果點(diǎn)上小數(shù)點(diǎn)，把它也看成一個(gè)小數(shù)，其實(shí)和算數(shù)編碼的形式很類似，不斷地讀入字符，找到它應(yīng)該落在當(dāng)前區(qū)間的哪一個(gè)子區(qū)間，整個(gè)編碼過(guò)程形成一個(gè)不斷收攏變小的區(qū)間。

由此我們可以看到這兩種編碼，或者說(shuō)熵編碼的本質(zhì)。概率越小的字符，用更多的bit去表示，這反映到概率區(qū)間上就是，概率小的字符所對(duì)應(yīng)的區(qū)間也小，因此這個(gè)區(qū)間的上下邊際值的差值越小，為了唯一確定當(dāng)前這個(gè)區(qū)間，則需要更多的數(shù)字去表示它。我們?nèi)砸允M(jìn)制來(lái)說(shuō)明，例如大區(qū)間0.2到0.3，我們需要0.2來(lái)確定，一位足以表示；但如果是小的區(qū)間0.11112到0.11113，則需要0.11112才能確定這個(gè)區(qū)間，編碼時(shí)就需要5位才能將這個(gè)字符確定。其實(shí)編碼一個(gè)字符需要的bit數(shù)就等于 -log ( p )，這里是十進(jìn)制，所以log應(yīng)以10為底，在二進(jìn)制下以2為底，也就是香農(nóng)公式里的形式。

哈夫曼編碼的不同之處就在于，它所劃分出來(lái)的子區(qū)間并不是嚴(yán)格按照概率的大小等比例劃分的。例如上面的d和e，概率其實(shí)是不同的，但卻得到了相同的子區(qū)間大小0.125；再例如c，和d，e構(gòu)成的子樹(shù)，c應(yīng)該比d，e的區(qū)間之和要小，但實(shí)際上它們是一樣的都是0.25。我們可以將哈夫曼編碼和算術(shù)編碼在這個(gè)例子里的概率區(qū)間做個(gè)對(duì)比：

這說(shuō)明哈夫曼編碼可以看作是對(duì)算數(shù)編碼的一種近似，它并不是完美地呈現(xiàn)原始數(shù)據(jù)中字符的概率分布。也正是因?yàn)檫@一點(diǎn)微小的偏差，使得哈夫曼編碼的壓縮率通常比算數(shù)編碼略低一些?；蛘哒f(shuō)，算數(shù)編碼能更逼近香農(nóng)給出的理論熵值。

7.數(shù)據(jù)壓縮的定義、背景與分類

首先我們要知道什么是數(shù)據(jù)壓縮。數(shù)據(jù)壓縮是指在不丟失有用信息的前提下，縮減數(shù)據(jù)量以減少儲(chǔ)存空間，提高其傳輸、儲(chǔ)存和處理效率，或按照一定的算法對(duì)數(shù)據(jù)重新組織，減少數(shù)據(jù)的冗余和存儲(chǔ)空間的一種技術(shù)方法。

那么為什么會(huì)出現(xiàn)數(shù)據(jù)壓縮這門技術(shù)呢？一門技術(shù)的快速發(fā)展必然有其背景，有其誕生的必要性。

數(shù)據(jù)壓縮背景摘要：在信息儲(chǔ)存和數(shù)據(jù)傳輸日益增長(zhǎng)的今天，數(shù)據(jù)壓縮變得越來(lái)越重要，數(shù)據(jù)壓縮是一種用來(lái)減小數(shù)據(jù)大小的技術(shù)。當(dāng)一些巨大的文件必須通過(guò)網(wǎng)絡(luò)傳輸存儲(chǔ)在數(shù)據(jù)存儲(chǔ)設(shè)備上，且其大小超過(guò)數(shù)據(jù)存儲(chǔ)的容量或?qū)⑾拇罅康木W(wǎng)絡(luò)傳輸帶寬時(shí)，這是非常有用的。隨互聯(lián)網(wǎng)和資源有限的移動(dòng)設(shè)備的出現(xiàn)，數(shù)據(jù)壓縮變得更加重要。它可以有效地用于節(jié)省儲(chǔ)存空間和帶寬，從而減少了下載時(shí)間.

數(shù)據(jù)壓縮算法發(fā)展至今，已經(jīng)有了相當(dāng)多的算法，按數(shù)據(jù)質(zhì)量可分為有損壓縮和無(wú)損壓縮兩大類。無(wú)損算法可以從壓縮的信息中精確地重構(gòu)原始消息，有損算法只能近似地重構(gòu)原始消息。

8.游程編碼（RLE）

設(shè)想一下，一旦一個(gè)像素呈現(xiàn)出一種特定的顏色(黑色或白色)，下面的像素極有可能也是相同的顏色。因此，與其單獨(dú)編碼每個(gè)像素的顏色，我們可以簡(jiǎn)單地編碼每個(gè)顏色的運(yùn)行長(zhǎng)度。RLE是一種非常簡(jiǎn)單的數(shù)據(jù)壓縮形式，其中數(shù)據(jù)序列（稱為游程，重復(fù)的字符串）存儲(chǔ)在兩個(gè)部分：?jiǎn)蝹€(gè)數(shù)值和計(jì)數(shù)。這對(duì)于包含許多這樣的運(yùn)行的數(shù)據(jù)是最有用的，例如，簡(jiǎn)單的圖形圖像，如圖標(biāo)、線條圖和動(dòng)畫。但它對(duì)于運(yùn)行次數(shù)不多的文件是沒(méi)有用的，因?yàn)樗赡軙?huì)大大增加文件的大小。

例如：純白色背景上的純黑色文本，b 代表一個(gè)黑色像素，w 代表一個(gè)白色像素：wwwwwbwwwwwbbbwwwwwbwwwww 用RLE表示為：5w1b5w3b5w1b5w

由于游程編碼執(zhí)行無(wú)損數(shù)據(jù)壓縮，它非常適合基于調(diào)色板的圖像，如紋理。但通常不應(yīng)用于現(xiàn)實(shí)的圖像，如照片。另外，游程編碼用于傳真機(jī)非常高效，因?yàn)榇蠖鄶?shù)傳真文件都有很多空白，偶爾會(huì)有黑色的干擾。

9.Lempel-Ziv算法

lempel-Ziv 算法是一種基于字典的編碼算法，而以往的算法往往基于概率編碼，它是文件無(wú)損壓縮的首選方法。這主要是由于它對(duì)不同文件格式的適應(yīng)性但是對(duì)于小文件，字典的長(zhǎng)度可能會(huì)超過(guò)原始文件的長(zhǎng)度，但是對(duì)于大文件，這種方法是非常有效的。

Ziv 和 Lempel 在1977年和1978年的兩篇獨(dú)立論文中描述了該算法的兩個(gè)主要變體，通常被稱為 LZ77和 LZ78。

LZ77 算法基于滑動(dòng)窗口的思想，該算法只在距離當(dāng)前位置固定距離內(nèi)的窗口查找匹配項(xiàng)。而 LZ78 算法基于一種更保守的方法向字典中添加字符串。

lempel-ziv-welch(LZW) 是目前使用最多的 Lempel-Ziv 算法。它是在 LZ77 和 LZ78 壓縮算法的基礎(chǔ)上改進(jìn)的。編碼器建立一個(gè)自適應(yīng)字典來(lái)表示變長(zhǎng)字符串，不需要任何先驗(yàn)概率信息。解碼器根據(jù)接收到的代碼動(dòng)態(tài)地在編碼器中構(gòu)建相同的字典。

現(xiàn)在 LZW 應(yīng)用于 GIF 圖像，UNIX 壓縮等。

基本步驟：

1. 初始化字典。

2. 將輸入數(shù)據(jù)的符號(hào)按順序組合到緩沖區(qū)中，直到在字典中找到最長(zhǎng)的字符串

3. 在緩沖區(qū)中發(fā)送表示的代碼。

4. 將緩沖區(qū)中的字符串與下一個(gè)空代碼中的下一個(gè)符號(hào)結(jié)合保存到字典中。

5. 清空緩沖區(qū)，然后重復(fù)步驟 2～5，直到全部數(shù)據(jù)結(jié)束。

表3是一個(gè)LZW的例子，輸入字符串為ABABBABCABABBA，初始碼為1、2、3，分別表示A、B、C。

編碼后的字符串為“124523461”。14個(gè)字符壓縮為9個(gè)字符。因此壓縮比為14/9=1.56。

9.1LZ編碼的應(yīng)用

在LZ的變體中，最流行的是LZW算法然而，LZW最初是實(shí)用最多的算法，專利問(wèn)題導(dǎo)致越來(lái)越多的使用LZ算法。LZ算法最受歡迎的實(shí)現(xiàn)是Phil Katz最初設(shè)計(jì)的deflate算法。Deflate是一種無(wú)損數(shù)據(jù)壓縮算法，使用了LZ算法和哈夫曼算法的組合，下面列舉LZ算法的主要應(yīng)用：

9.1.1文件壓縮 UNIX 壓縮

UNIX compress 命令是LZW最早的應(yīng)用之一。字典的大小是自適應(yīng)的。當(dāng)字典被填滿時(shí)，大小逐漸增加一倍。代碼字的最大大小bmax可以由用戶設(shè)置為9到16之間，16位是默認(rèn)值。而一旦字典包含2bmax條目，壓縮就會(huì)成為一種靜態(tài)字典編碼技術(shù)，此時(shí)算法監(jiān)視壓縮比。如果壓縮比低于閾值，則將刷新字典，并重新啟動(dòng)字典構(gòu)建過(guò)程。這樣一來(lái)，字典總是能反映源的地方特征。

9.1.2圖像壓縮 gif 格式

圖形交換格式(GIF)是 Compuserve 信息服務(wù)公司開(kāi)發(fā)的圖形圖像編碼格式。它是 LZW 算法的另一種實(shí)現(xiàn)，與 Unix 中的 compress 命令非常相似，正如我們?cè)谇懊娴膽?yīng)用程序中提到的那樣。

9.1.3圖像壓縮 png 格式

PNG 標(biāo)準(zhǔn)是互聯(lián)網(wǎng)上最早開(kāi)發(fā)的標(biāo)準(zhǔn)之一。1994 年12 月，Unisys 公司(該公司從 Sperry 那里獲得了 LZW的專利)和 CompuServe 公司宣布，他們將開(kāi)始向支持GIF 的軟件的作者收取版稅。該公告導(dǎo)致了數(shù)據(jù)壓縮領(lǐng)域的一場(chǎng)革命，行成了Usenet組comp.compression的核心。社區(qū)決定開(kāi)發(fā)一種無(wú)專利的 GIF 替代品，三個(gè)月內(nèi) PNG 誕生了。Modem sV.42 上的壓縮ITU-T 建議 V.42 之二是為通過(guò)電話網(wǎng)絡(luò)使用而制定的壓縮標(biāo)準(zhǔn)，并附有 C CITT 建議 V.42 中所述的糾錯(cuò)程序。該算法用于連接計(jì)算機(jī)和遠(yuǎn)程用戶的調(diào)制解調(diào)器。該算法有兩種運(yùn)行模式和壓縮模式。在透明模式下，數(shù)據(jù)以不壓縮的形式傳輸，在壓縮模式下，數(shù)據(jù)使用LZW算法進(jìn)行壓縮。

10.多媒體壓縮JPEG和MPEG

10.1背景

媒體圖像已經(jīng)成為日常生活中一個(gè)至關(guān)重要且無(wú)處不在的組成部分。圖像中編碼的信息量是相當(dāng)大的。即使有了帶寬和儲(chǔ)存能力的進(jìn)步，如果圖像不被壓縮，許多應(yīng)用程序的成本將會(huì)太高。

10.2圖像壓縮：JPEG壓縮算法

JPEG用于靜態(tài)圖像，圖像壓縮是減少表示數(shù)字圖像所需的數(shù)據(jù)量的過(guò)程，這是通過(guò)刪除所有冗余或不必要的信息來(lái)實(shí)現(xiàn)的。一個(gè)未壓縮的圖像需要大量的數(shù)據(jù)來(lái)表示。

編碼算法：

1、顏色空間轉(zhuǎn)換

如果顏色分量是獨(dú)立的（不相關(guān)的），則可以獲得最好的 壓縮結(jié)果，例如在YCbCr中，大部分信息集中在亮度上，而色度上的信息較少。RGB顏色分量可以通過(guò)線性變換轉(zhuǎn)換為YCbCr分量，如下式：

2、色度下降采樣

使用YCbCr顏色空間，我們還可以通過(guò)壓縮Cb和Cr分量的分辨率來(lái)節(jié)省空間。它們是色度分量，我們可以減少它們以使用圖像壓縮。由于亮度對(duì)眼睛的重要性，我們不需要色度像亮度一樣頻繁，所以我們可以對(duì)其進(jìn)行下降采樣。因此可以除去部分Cb和Cr的元素。因此，例如將RGB44格式轉(zhuǎn)換為YCbCr42的格式，這樣就可以獲得一個(gè)1:5的數(shù)據(jù)壓縮比，不過(guò)此步驟是一個(gè)可選的過(guò)程。

3、離散余弦變換（DCT）

在這一步，每88塊的分量（Y,Cb,Cr）被轉(zhuǎn)換成頻域表示。DCT方程是一個(gè)相當(dāng)復(fù)雜的方程，有兩個(gè)余弦系數(shù)。細(xì)節(jié)參考JPEG標(biāo)準(zhǔn)。

4、量化

對(duì)人眼來(lái)說(shuō)，亮度比色度更重要。對(duì)眼睛來(lái)說(shuō)，在大范圍內(nèi)看到亮度的微小差異比高頻亮度變化的確切強(qiáng)度更容易分辨。利用這一特性，我們可以大大減少高頻成分中的信息。JPEG編碼通過(guò)簡(jiǎn)單地將頻率域中的每個(gè)分量除以該分量中的一個(gè)常數(shù)，然后四舍五入到最近的整數(shù)來(lái)實(shí)現(xiàn)這一點(diǎn)。因此，許多高頻分量被四舍五入到零，其余大部分分量變成了小的正數(shù)或負(fù)數(shù)，占用更少的比特來(lái)儲(chǔ)存。

5、熵編碼

熵編碼是一種無(wú)損數(shù)據(jù)壓縮的方法。在這里，我們將圖像組件排序?yàn)殇忼X形，然后使用游程編碼（RLE）算法，將相似的頻率連接在一起，以壓縮序列。

6、哈夫曼算法

應(yīng)用前面的步驟，我們得到的數(shù)據(jù)就是DCT系數(shù)序列。這一步即是最后一步，我們用哈夫曼編碼或者算數(shù)壓縮算法來(lái)壓縮這些系數(shù)。該方案主要采用Huffman壓縮，將其視為第二次無(wú)損壓縮。

10.3視頻壓縮：MPEG壓縮算法

MPEG壓縮算法的基本思想是將離散樣本流轉(zhuǎn)換為符號(hào)的比特流。以減少占用空間，理論上，視頻流是一組離散圖像。MPEG使用這種連續(xù)幀之間的特殊或時(shí)間關(guān)系來(lái)壓縮視頻流。在一段數(shù)據(jù)中，利用這些關(guān)系的技術(shù)越有效，對(duì)數(shù)據(jù)的壓縮就越有效。

在MPEG編碼算法中，我們只對(duì)視頻序列中的新部分和視頻中運(yùn)動(dòng)部分的信息進(jìn)行編碼。例如，考慮圖9，上面的三張圖。對(duì)于壓縮我們只需考慮新的部分，如圖9，我們只需要考慮底部的三個(gè)序列。視頻壓縮的基本原理是圖像對(duì)圖像的預(yù)測(cè)。一組圖像中的第一個(gè)圖像是i幀。這些幀顯示開(kāi)始一個(gè)心得場(chǎng)景，因此不需要被壓縮，因?yàn)樗麄儧](méi)有依賴于該圖像之外。但其他幀可以使用第一張圖片的一部分作為參考。從一個(gè)參考圖像預(yù)測(cè)的圖像稱為p幀，從兩個(gè)其他參考圖像雙向預(yù)測(cè)的圖像稱為B幀。因此，總的來(lái)說(shuō)，我們將有以下幀MPEG編碼：

• I-frames：獨(dú)立的；不需要參考幀預(yù)測(cè)

• P幀：從最后一個(gè)I或P參考幀預(yù)測(cè)

• B-frames：雙向：從兩個(gè)參考幀預(yù)測(cè)，一個(gè)在過(guò)去，一個(gè)在未來(lái)，將考慮最佳匹配。

MPEG應(yīng)用程序：MPEG在現(xiàn)實(shí)世界中有很多的應(yīng)用。我們?cè)诖肆信e其中一些：

1、有限電視。一些電視系統(tǒng)通過(guò)有線電視線路發(fā)送MPEG-II節(jié)目

2、直接廣播衛(wèi)星。MPEG視頻流被跌形/解碼器接收，它提取的數(shù)據(jù)為標(biāo)準(zhǔn)NTSC電視信號(hào)。

3、媒體的金庫(kù)。Silicon Graphics、Storage Tech和其他供應(yīng)商正在生產(chǎn)按需視頻系統(tǒng)，在一個(gè)安裝上有兩萬(wàn)個(gè)文件MPEG編碼的電影。

4、實(shí)時(shí)編碼，這仍是專業(yè)人士的專屬領(lǐng)域。結(jié)合特殊用途的并行硬件，實(shí)時(shí)編碼器的成本可達(dá)2萬(wàn)至5萬(wàn)美元。

11.今天的數(shù)據(jù)壓縮：應(yīng)用程序和問(wèn)題

11.1網(wǎng)絡(luò)

今天隨著用戶數(shù)量的增加和遠(yuǎn)程辦公，以及使用云計(jì)算的應(yīng)用程序部署模型的出現(xiàn)，更多正在傳輸?shù)臄?shù)據(jù)對(duì)網(wǎng)絡(luò)連接的壓力導(dǎo)致了額外的問(wèn)題。

數(shù)據(jù)壓縮重要的作用之一是將其應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)。然而，在帶寬有限的網(wǎng)絡(luò)環(huán)境下，實(shí)現(xiàn)高的壓縮比是提高應(yīng)用程序性能的必要條件，如果壓縮比過(guò)低，網(wǎng)絡(luò)將保持飽和，性能增益將非常小。同樣，如果壓縮速度過(guò)低，壓縮機(jī)也會(huì)成為瓶頸。許多網(wǎng)絡(luò)數(shù)據(jù)的傳輸優(yōu)化解決方案都只關(guān)注網(wǎng)絡(luò)層的優(yōu)化。這些解決方案不僅缺乏靈活性，而且沒(méi)有包含能夠進(jìn)一步增強(qiáng)通過(guò)網(wǎng)絡(luò)鏈接傳輸數(shù)據(jù)的應(yīng)用程序性能的優(yōu)化。

11.2基于報(bào)文或會(huì)話的壓縮

許多網(wǎng)絡(luò)壓縮系統(tǒng)是基于數(shù)據(jù)包的?；跀?shù)據(jù)包的壓縮系統(tǒng)使用解壓器緩沖發(fā)送到遠(yuǎn)程網(wǎng)絡(luò)的數(shù)據(jù)包。然后，這些數(shù)據(jù)包在單個(gè)時(shí)間內(nèi)或作為一個(gè)組被壓縮，然后發(fā)送到解壓器，在那里這個(gè)過(guò)程被逆轉(zhuǎn)。

當(dāng)壓縮數(shù)據(jù)包時(shí)，這些系統(tǒng)必須在將小數(shù)據(jù)包寫入網(wǎng)絡(luò)和執(zhí)行額外的工作來(lái)聚合和封裝多個(gè)數(shù)據(jù)包寫入網(wǎng)絡(luò)和執(zhí)行額外的工作來(lái)聚合和封裝多個(gè)數(shù)據(jù)包之間做出選擇，這兩種選擇都不會(huì)產(chǎn)生最佳效果。向網(wǎng)絡(luò)寫入小數(shù)據(jù)包會(huì)增加TCP/IP報(bào)頭的開(kāi)銷，而聚合和封裝數(shù)據(jù)包會(huì)增加流的封裝報(bào)頭。

11.3字典壓縮大小

幾乎所有壓縮實(shí)用程序的一個(gè)共同限制是有限的儲(chǔ)存空間。

與對(duì)網(wǎng)絡(luò)的請(qǐng)求相似，并不是所有在網(wǎng)絡(luò)上傳輸?shù)淖止?jié)都以相同的頻率重復(fù)。一些字節(jié)模式出現(xiàn)的頻率很高，因?yàn)樗麄兪橇餍形臋n或公共網(wǎng)絡(luò)協(xié)議的一部分。其他字節(jié)模式只出現(xiàn)一次，并且永遠(yuǎn)不重復(fù)。經(jīng)常重復(fù)的字節(jié)序列和不經(jīng)常重復(fù)的字節(jié)序列之間的關(guān)系可以在Zipfs定律中看到。

11.4基于塊或基于字節(jié)的壓縮

基于塊的壓縮系統(tǒng)儲(chǔ)存先前在網(wǎng)絡(luò)上傳輸?shù)臄?shù)據(jù)片段。當(dāng)?shù)诙斡龅竭@些塊時(shí)，對(duì)這些網(wǎng)塊的引用被傳輸?shù)竭h(yuǎn)程設(shè)備，然后遠(yuǎn)程設(shè)備重新構(gòu)建原始數(shù)據(jù)。

基于塊的系統(tǒng)的一個(gè)關(guān)鍵缺點(diǎn)是，重復(fù)的數(shù)據(jù)幾乎從不與塊的長(zhǎng)度完全相同。因此，匹配通常只是部分匹配，不壓縮一些重復(fù)的數(shù)據(jù)。如圖12說(shuō)明了使用256字節(jié)塊的系統(tǒng)試圖壓縮512自治街的數(shù)據(jù)時(shí)會(huì)發(fā)生什么。

11.5能源效率

能源效率領(lǐng)域，尤其是無(wú)線傳感器網(wǎng)絡(luò)是當(dāng)今世界最熱門的網(wǎng)絡(luò)研究領(lǐng)域之一。無(wú)線傳感器網(wǎng)絡(luò)由分布在空間上的傳感器組成，用于檢測(cè)物理或環(huán)境條件，如溫度、聲音、振動(dòng)、壓力、運(yùn)動(dòng)或污染物，并協(xié)同將他們的數(shù)據(jù)通過(guò)網(wǎng)絡(luò)傳遞到主要位置。而傳感器的大小和成本限制導(dǎo)致了資源的限制，如能源、內(nèi)存、計(jì)算速度和通信帶寬。巨大共享傳感器之間的數(shù)據(jù)需要能量高效、低延遲和高精度。

目前，如果傳感器系統(tǒng)設(shè)計(jì)者想要壓縮獲得的數(shù)據(jù)，他們必須卡法特定于應(yīng)用程序的壓縮算法，或者使用非為資源所限的傳感器節(jié)點(diǎn)設(shè)計(jì)的現(xiàn)成算法。

主要的嘗試是實(shí)現(xiàn)一種專門為傳感器網(wǎng)絡(luò)設(shè)計(jì)的傳感器Lempel-Ziv(S-LZW）壓縮算法。針對(duì)無(wú)線傳感網(wǎng)絡(luò)中設(shè)計(jì)高效數(shù)據(jù)壓縮算法的趨勢(shì)，Vidhyapriyal和P.Vanathi設(shè)計(jì)并實(shí)現(xiàn)了兩種集成了最短路徑路由技術(shù)的無(wú)損數(shù)據(jù)壓縮算法，以減少原始數(shù)據(jù)的大小，并在傳感器網(wǎng)絡(luò)中實(shí)現(xiàn)速率、能量和精度之間的最佳權(quán)衡。

12.總結(jié)

在數(shù)據(jù)存儲(chǔ)和信息傳輸量不斷增長(zhǎng)的今天，數(shù)據(jù)壓縮技術(shù)發(fā)揮著重要作用。即使在帶寬和存儲(chǔ)能力方面有了進(jìn)步，如果數(shù)據(jù)沒(méi)有被壓縮，許多應(yīng)用程序的成本將太高，用戶無(wú)法使用他們。本文我們嘗試介紹了無(wú)損壓縮和有損壓縮兩種壓縮類型，以及數(shù)據(jù)壓縮中的一些主要概念、算法和方法，并討論了他們的不同應(yīng)用和工作方式，然后我們探討了兩個(gè)主要的日常應(yīng)用；以JPEG為例進(jìn)行圖像壓縮，以MPEG為例進(jìn)行了視頻壓縮。最后我們討論了當(dāng)今數(shù)據(jù)壓縮的主要應(yīng)用和存在的問(wèn)題。

< 本文完>

ELT.ZIP是誰(shuí)？

ELT<=>Elite(精英)，.ZIP為壓縮格式，ELT.ZIP即壓縮精英。

成員：

上海工程技術(shù)大學(xué)大二在校生閆旭

合肥師范學(xué)院大二在校生楚一凡

清華大學(xué)大二在校生趙宏博

成都信息工程大學(xué)大一在校生高云帆

黑龍江大學(xué)大一在校生高鴻萱

山東大學(xué)大三在校生張智騰

ELT.ZIP是來(lái)自6個(gè)地方的同學(xué)，在OpenHarmony成長(zhǎng)計(jì)劃啃論文俱樂(lè)部里，與來(lái)自華為、軟通動(dòng)力、潤(rùn)和軟件、拓維信息、深開(kāi)鴻等公司的高手一起，學(xué)習(xí)、研究、切磋操作系統(tǒng)技術(shù)...

寫在最后

OpenHarmony 成長(zhǎng)計(jì)劃—“啃論文俱樂(lè)部”（以下簡(jiǎn)稱“啃論文俱樂(lè)部”）是在 2022年 1 月 11 日的一次日?；顒?dòng)中誕生的。截至 3 月 31 日，啃論文俱樂(lè)部已有 87 名師生和企業(yè)導(dǎo)師參與，目前共有十二個(gè)技術(shù)方向并行探索，每個(gè)方向都有專業(yè)的技術(shù)老師帶領(lǐng)同學(xué)們通過(guò)啃綜述論文制定技術(shù)地圖，按“降龍十八掌”的學(xué)習(xí)方法編排技術(shù)開(kāi)發(fā)內(nèi)容，并通過(guò)專業(yè)推廣培養(yǎng)高校開(kāi)發(fā)者成為軟件技術(shù)學(xué)術(shù)級(jí)人才。

啃論文俱樂(lè)部的宗旨是希望同學(xué)們?cè)陂_(kāi)源活動(dòng)中得到軟件技術(shù)能力提升、得到技術(shù)寫作能力提升、得到講解技術(shù)能力提升。大學(xué)一年級(jí)新生〇門檻參與，已有俱樂(lè)部來(lái)自多所高校的大一同學(xué)寫出高居榜首的技術(shù)文章。

如今，搜索“啃論文”，人們不禁想到、而且看到的都是我們——OpenHarmony 成長(zhǎng)計(jì)劃—“啃論文俱樂(lè)部”的產(chǎn)出。

OpenHarmony開(kāi)源與開(kāi)發(fā)者成長(zhǎng)計(jì)劃—“啃論文俱樂(lè)部”學(xué)習(xí)資料合集

1）入門資料：啃論文可以有怎樣的體驗(yàn)

https://docs.qq.com/slide/DY0RXWElBTVlHaXhi?u=4e311e072cbf4f93968e09c44294987d

2）操作辦法：怎么從啃論文到開(kāi)源提交以及深度技術(shù)文章輸出https://docs.qq.com/slide/DY05kbGtsYVFmcUhU

3）企業(yè)/學(xué)校/老師/學(xué)生為什么要參與 & 啃論文俱樂(lè)部的運(yùn)營(yíng)辦法https://docs.qq.com/slide/DY2JkS2ZEb2FWckhq

4）往期啃論文俱樂(lè)部同學(xué)分享會(huì)精彩回顧：

同學(xué)分享會(huì)No1.成長(zhǎng)計(jì)劃啃論文分享會(huì)紀(jì)要（2022/02/18）https://docs.qq.com/doc/DY2RZZmVNU2hTQlFY

同學(xué)分享會(huì)No.2 成長(zhǎng)計(jì)劃啃論文分享會(huì)紀(jì)要（2022/03/11）https://docs.qq.com/doc/DUkJ5c2NRd2FRZkhF

同學(xué)們分享會(huì)No.3 成長(zhǎng)計(jì)劃啃論文分享會(huì)紀(jì)要（2022/03/25）

https://docs.qq.com/doc/DUm5pUEF3ck1VcG92?u=4e311e072cbf4f93968e09c44294987d

現(xiàn)在，你是不是也熱血沸騰，摩拳擦掌地準(zhǔn)備加入這個(gè)俱樂(lè)部呢？當(dāng)然歡迎啦！啃論文俱樂(lè)部向任何對(duì)開(kāi)源技術(shù)感興趣的大學(xué)生開(kāi)發(fā)者敞開(kāi)大門。

掃碼添加 OpenHarmony 高校小助手，加入“啃論文俱樂(lè)部”微信群

后續(xù)，我們會(huì)在服務(wù)中心公眾號(hào)陸續(xù)分享一些 OpenHarmony 開(kāi)源與開(kāi)發(fā)者成長(zhǎng)計(jì)劃—“啃論文俱樂(lè)部”學(xué)習(xí)心得體會(huì)和總結(jié)資料。記得呼朋引伴來(lái)看哦。