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

1.技術DNA

2. 智慧場景

3.開篇簡介

本文著重對傳統(tǒng)經(jīng)典壓縮算法的分析與理解，從認識到實現(xiàn)的角度展開描述，主要涉及了 Shannon-Fano、Huffman、算術編碼等編碼方案。除此之外，還附帶了對于數(shù)據(jù)壓縮初識的部分。

3.1 統(tǒng)計編碼是什么

統(tǒng)計編碼（statistical compression），也可稱為熵編碼，其出現(xiàn)是為了彌補傳統(tǒng)VLC可變長編碼在編碼時須進行特定方法匹配的痛點，原因是VLC有時并非能找到最佳選擇，相較來說，統(tǒng)計編碼是一類只需依據(jù)每個字符出現(xiàn)的次數(shù) / 概率，便可自生成一套高效編碼的方案，正因如此，它們具備顯著的通用性。

統(tǒng)計編碼的首要目的是，在信息和碼之間找到明確的一一對應關系，從而保證在解碼時準確無誤地再現(xiàn)回來，或極接近地找到相當?shù)膶P系，同時將失真率控制在一定范圍內(nèi)。但無論借助什么途徑，核心總是要把平均碼長 / 碼率壓低到最低限度。

3.2統(tǒng)計編碼分類

四種常用的統(tǒng)計編碼有：香農(nóng)·范諾編碼、Huffman 編碼、算術編碼以及 ANS，其中，香農(nóng)·范諾編碼稱得上是現(xiàn)代第一個壓縮編碼，具有相當?shù)臍v史意義。

4.香農(nóng)·范諾編碼

4.1誕生背景

早在香農(nóng)（Claude Elwood Shannon） 撰寫《通信的數(shù)學理論》一文，并試圖提出且證明一種可以按符號出現(xiàn)概率實現(xiàn)高效編碼，以最大程度減少通信傳輸所需信道容量的方法之前，時任 MIT 教授的羅伯特·范諾（ Robert Mario Fano ）也已對這一編碼方法展開了相關研究。范諾不久后將其以技術報告的形式獨立進行了發(fā)表，因而，這種編碼被并稱為香農(nóng)·范諾編碼（ Shannon–Fano coding ），它是現(xiàn)代熵編碼與數(shù)據(jù)壓縮技術的雛形。即便它不是最佳的編碼方案，但在有些時候仍會使用。

4.2簡單認識

香農(nóng)·范諾編碼準確的說是一種前綴碼技術，所謂前綴碼，是指編碼后的每個碼字都不會再作為其他碼字的前綴出現(xiàn)，這為后續(xù)解碼操作時字符的唯一確定提供了條件。

以EBACBDBEBCDEAABEEBDDBABEBABCDBBADBCBECA這樣一串字符串為例，我們首先需要統(tǒng)計并計算其中每個字符的出現(xiàn)概率。

經(jīng)以上操作分組完畢后，五個字符已位于整棵樹的最外層葉子處，在每個分支處的左半部分樹干標上 0，右半部分樹干標上 1。最后，從樹根起始，沿樹干依次遍歷至最外層的葉子節(jié)點，便得到了每個字符的香農(nóng)·范諾碼。由于每個樹干的 “0”、“1” 二進制碼獨一無二，所以最終的編碼彼此不會重復。

出現(xiàn)概率較高的字符被編碼成兩位，概率較低的則被編碼成三位。由此，我們便可計算出每個字符平均所需的編碼位數(shù)：

結(jié)果表明，每個字符平均只需約 2.28 個位即可保證在信息不丟失的情況下完美表示。當然，實際在計算機中，是無法把位分割成小數(shù)的，2.28 需二次近似于 3。

然而迄今為止，仍沒有任何一種編碼方案能夠保證在通用情況下達到香農(nóng)熵值。香農(nóng)與范諾兩位杰出科學家為后世壓縮技術的發(fā)展開了一個好頭。

5.哈夫曼編碼

香農(nóng)·范諾編碼固然強大，但它并非總是能產(chǎn)生最優(yōu)前綴碼，所以只能取得一定的壓縮效果，離真正實用的壓縮算法還相去甚遠。

為此，在其基礎上演化出的第一個稱得上實用的壓縮編碼哈夫曼編碼（ Huffman Code ），由大衛(wèi)·哈夫曼（ David Albert Huffman ）于 1952 年的博士論文《最小冗余度代碼的構(gòu)造方法（ A Method for the Construction of Minimum Redundancy Codes ）》中提出。哈夫曼編碼同樣依據(jù)字符使用的頻率來分配表示字符的碼字，不同的是，頻繁出現(xiàn)的字符被分配較短的編碼，出現(xiàn)不是那么頻繁的字符則會被分配較長的編碼。

哈夫曼編碼效率高、運算速度快、實現(xiàn)方式靈活。自 Windows10 起所支持的 CompactOS 特性，便是利用哈夫曼壓縮來減小操作系統(tǒng)體積的一項技術。直至今天，許多《數(shù)據(jù)結(jié)構(gòu)》教材在討論二叉樹時仍繞不開哈夫曼這樣一個話題，不過，比起算法本身，最為人們津津樂道的還是發(fā)明算法的過程。

5.1青出于藍而勝于藍

1951 年，哈夫曼作為一名 MIT 的學生，正在上一門由導師范諾教授的《信息學》課程。不過，既然正式上了一門課，那期末考核是在所難免的。范諾出了道選擇題，給學生們兩種通過考核的方式：第一選項是夜以繼日地照常復習，最后參與期末考試；第二選項是完成期末論文，也被叫做大作業(yè)。同學們普遍認為，在 MIT 這樣一個地方，考試的難度可不是個小兒科，盡管如此，比起要求邏輯嚴謹、證明充分的學科論文來說，大多數(shù)同學還是更傾向于去考試。哈夫曼選擇了不隨波逐流，他認為后者相對于他而言更簡單，又能逃脫考試的浩劫，何樂而不為？

不出所料，最終只有哈夫曼一人選擇了獨自開辟新路徑 —— 范諾限定了這樣一個課題：“給定一組字母、數(shù)字或其他各種符號，設法找到其最有效的二進制編碼”。實際上，這即是范諾與香農(nóng)等大科學家所正在研究的內(nèi)容，是信息論與數(shù)據(jù)壓縮領域尚未解決的難題，但他并未告訴學生們這一點。

結(jié)合所學知識，哈夫曼知道“最有效”一詞的意思是“編碼長度足夠短”。起初，哈夫曼認為這個問題應該不是什么難事，漸漸地，他發(fā)現(xiàn)事情其實遠并非他想得那樣。經(jīng)過幾個月的苦思冥想與文獻查找，哈夫曼確實設計出了許多算法，但令人沮喪的是，沒有一種算法可以被證明達到了“最有效”的條件…… 到了學期結(jié)束的前一周，仍舊沒有取得任何實質(zhì)性突破，哈夫曼開始為之感到疲倦。迫于即將結(jié)課的壓力，他不得不撂掉手頭上這已不可能完成的任務，回頭轉(zhuǎn)向為常規(guī)考試的準備。一天早餐后，就在哈夫曼隨手抓起桌上的研究筆記將其扔進廢紙簍之時，一切突然明朗了起來，他說那是他生命中最奇特的時刻。這樣一個困擾領域?qū)＜以S久的難題，被一個年僅 25 歲的小伙子當作課程作業(yè)給解決了。

哈夫曼后來回憶道，如果他知道他的老師和信息學之父彼時也都在努力解決這個問題，他可能永遠也不會想到去嘗試。他很慶幸自己在正確的時間做了正確的事，慶幸他的老師在那時沒有告訴他還有其他更優(yōu)秀的人也曾在這個問題上苦苦掙扎。

5.2編碼方法

哈夫曼編碼是分組編碼、可變長編碼，是依據(jù)各字符出現(xiàn)的概率構(gòu)造碼字的。制作碼表的基本原理是基于二叉樹的編碼思想：所有可能的輸入字符在哈夫曼樹上對應為一個葉子節(jié)點，節(jié)點的位置就是該字符的哈夫曼編碼。其次，基于字符串中每個字符的累計出現(xiàn)次數(shù)進行編碼，出現(xiàn)頻率越高得到的編碼越短。特別的，為了構(gòu)造出唯一可譯碼，這些葉子節(jié)點都是哈夫曼樹上的終極節(jié)點，不再延伸，不再出現(xiàn)前綴碼。可以感受到，哈夫曼編碼與香農(nóng)·范諾編碼的實現(xiàn)過程極其類似，但還是有些許不同，哈夫曼編碼的大體步驟如下：

• 將信源消息符號按其出現(xiàn)的概率大小依次排列

• 取兩個概率最小的字符分別配以 0 和 1 兩個碼元，并將這兩個概率相加作為一個新字符的概率，與未分配二進制碼的字符一起重新排隊

• 對重排后的兩個概率最小的字符重復步驟 2 的過程

• 不斷重復上述過程，直到最后兩個字符被配以 0 和 1 為止

• 從最后一級開始，向前返回得到各個信源符號所對應的碼元序列，即相應碼字

5.3舉個例子

讓我們淺試一下，現(xiàn)在有一串由 5 個不同字符 ( A, B, C, D, E ) 組成的字符串序列：

BACAB BACDA ABBBE

步驟一：根據(jù)上述字符串，統(tǒng)計各個字符出現(xiàn)的次數(shù)并排序：

步驟二：把次數(shù)最少的兩者放在一起并相加，同時將結(jié)果按順序重新放入隊列。顯然，是 D: 1, E: 1, 1 + 1 = 2。

步驟三：繼續(xù)抽出兩個值最小的卡片，重復上一步并以此類推……

步驟四：現(xiàn)在，我們完成了步驟二的迭代，一棵二叉樹的模型自然形成了，下面要做的就是分別在每個分支的左樹干上標 0、右樹干上標 1。

步驟五：從樹根到每片葉子依次遍歷，將經(jīng)過的 0、1 記錄下來，即可得到哈夫曼碼表。

所以，原本的字符串BACABBACDAABBBE用哈夫曼碼表示為：100010001100010011000001110111，符合字符出現(xiàn)次數(shù)越多編碼長度越短的標準。

5.4一些性質(zhì)

與香農(nóng)·范諾編碼相比，哈夫曼編碼的平均碼長更小，編碼效率高，信息傳輸速率大。所以在壓縮信源信息率的實用設備中，哈夫曼編碼還是比較常用的。哈夫曼方法得到的碼并非唯一，不唯一的原因有兩點：

1. 每次對信源進行壓縮時，最后分配給兩個概率最小的字符以 0 和 1 可以是任意的，由此可以得到不同的哈夫曼碼，但不會影響碼字的長度。

2. 對信源進行縮減時，兩個概率最小的字符合并后的概率與其他信源字符的概率相等時，它們在壓縮信源中放置的前后相對次序可以是任意的，由此也會得到不同的哈夫曼碼。此時將影響碼字的長度，一般將合并的概率放在上面，這樣可獲得較小的碼長方差。

哈夫曼碼是用概率匹配方法進行信源編碼。它有兩個明顯特點：一是哈夫曼碼的編碼方法保證了概率大的符號對應于短碼，概率小的符號對應于長碼，充分利用了短碼；二是壓縮信源的最后二個碼字總是最后一位不同，從而保證了哈夫曼碼是即時碼。

編碼平均長度等式：

對于哈夫曼編碼的基本理論，我們差不多都清楚了，下面嘗試如何用代碼去實現(xiàn)它。

5.5算法實現(xiàn)

哈夫曼算法的模型基于二叉樹，樹的節(jié)點分為終端節(jié)點（葉子節(jié)點）與非終端節(jié)點（內(nèi)部節(jié)點）。為了達成一個在二叉樹下更通用、標準的定義，我們將字符出現(xiàn)的頻率抽象為權重。初始第一輪迭代時，每個最底層的節(jié)點都是葉子節(jié)點，包含兩個字段：字符與權重；在第二輪及以后的迭代中，產(chǎn)生的每個節(jié)點都是內(nèi)部節(jié)點，包含三個字段：權重、指向左子節(jié)點的鏈接與指向右子節(jié)點的鏈接。

因此，首先需要具備的兩個必要元素便是內(nèi)部節(jié)點與葉子節(jié)點，同時，它們又都包含權重這一相同字段，所以我們先定義基類 INode：

// C++實現(xiàn)
class INode
{
public:
    const unsigned weight;    // 權重
    virtual ~INode() {}


protected:
    INode(unsigned weight) : weight(weight) {}
};

為了避免不必要的干擾，將 INode 的構(gòu)造函數(shù)聲明為 protected。

葉子節(jié)點與內(nèi)部節(jié)點的定義即是繼承 INode 后，把剩下的另外字段補充上去，通過調(diào)用父類 INode 的構(gòu)造函數(shù)生成權值。

// 葉子節(jié)點
class LeafNode : public INode
{
public:
    const char c;    // 字符


    LeafNode(unsigned weight, char c) : INode(weight), c(c) {}
};

// 內(nèi)部節(jié)點
class InternalNode : public INode
{
public:
    INode * const left;    // 左指針
    INode * const right;    // 右指針


    InternalNode(INode * leftChild, INode * rightChild) : INode(leftChild->weight + rightChild->weight), left(leftChild), right(rightChild) {}
    ~InternalNode()
    {
        delete left;
        delete right;
    }
};

基本元素現(xiàn)已齊全，繼續(xù)進行下一步操作。上一小節(jié)我們說到，靜態(tài) Huffman 算法需要對數(shù)據(jù)進行兩次遍歷，第一次是得到概率表并構(gòu)建樹，第二次才進行字符編碼。先來看第一次，在構(gòu)建樹之前必須提供一套排好序的概率表，假設現(xiàn)在有這樣一串字符DATACOMPRESSION，我們?nèi)绾卧谟嬎銠C中用復雜度較低的算法統(tǒng)計并排序？肯定不能用眼睛盯著來數(shù)了。

因為總字符數(shù)是一定的，所以用字符出現(xiàn)的次數(shù)，即頻數(shù)，來代替概率是等效的。統(tǒng)計頻數(shù)很簡單 —— 聲明一個容量足夠保存任意字符的數(shù)組，將遍歷到的每個字符作為參數(shù)傳遞給這個數(shù)組，由于字符在現(xiàn)代計算機中均以 ASCII、Unicode 等編碼集存儲，所以每當遇到一個字符時就在數(shù)組中對應字符編碼數(shù)值的位置遞增 1 即可，省去了記錄下標的麻煩。

// 生成頻數(shù)表
#define CAPACITY 1<char * ptr = "DATACOMPRESSION";    // 聲明字符串DATACOMPRESSION
unsigned frequencies[CAPACITY] = {0};    // 聲明并初始化數(shù)組
while (*ptr != '')            // 依次在每個字符對應于數(shù)組的位置中遞增1
    ++frequencies[*ptr++];

盡管浪費了很多未被填充的空間，但這點數(shù)量級的浪費實際上微不足道，況且填充的數(shù)據(jù)越多利用率也越高。

接下來，采用優(yōu)先級隊列 priority_queue 數(shù)據(jù)結(jié)構(gòu)來構(gòu)建二叉樹是不二選擇，既滿足存儲節(jié)點序列，又可自動排序，如此，事先也就不用再給頻數(shù)表排序了?，F(xiàn)在，封裝函數(shù) BuildTree，只需唯一形參 frequencies[CAPACITY]：

// 構(gòu)建二叉樹
INode* BuildTree(const unsigned (&frequencies)[CAPACITY])
{
    struct NodeCmp    // 聲明仿函數(shù)用于priority_queue排序
    {
        bool operator()(const INode * lhs, const INode * rhs) const { return lhs->weight > rhs->weight; }
    };
    priority_queue, NodeCmp> tree;    // 得到對象tree*,>


    for (unsigned i = 0; i < CAPACITY; ++i)    // 構(gòu)造葉子節(jié)點，返回地址到tree并排序
        if (frequencies[i] != 0)
            tree.push(new LeafNode(frequencies[i], static_cast(i)));


    while (tree.size() > 1)    // 不斷向上構(gòu)造內(nèi)部節(jié)點，直至tree中只剩樹根
    {
        INode * leftChild = tree.top();
        tree.pop();


        INode * rightChild = tree.top();
        tree.pop();


        INode * parent = new InternalNode(leftChild, rightChild);
        tree.push(parent);
    }
    return tree.top();
}

得到 priority_queue 的實例 tree 之后，便可開始遍歷頻數(shù)表，將權值不為 0 的字符連同權值一起以葉子節(jié)點類型對象存進 tree，并會按權值遞增的順序排列。完畢后，循環(huán)依次取出隊頭前兩個最小的葉子節(jié)點記錄地址，生成上層內(nèi)部節(jié)點再入隊重新排序，最終返回樹根地址。

一切就緒，終于可以給字符編碼了！字符編碼兩要素 —— 字符與碼，一一對應，符合映射關系，用 vector 序列容器存儲碼、map 關聯(lián)容器存儲鍵值當是再好不過了。仍用一個函數(shù)實現(xiàn)此功能，需要三個參數(shù)：根節(jié)點地址、目的編碼、map 容器。在函數(shù)體中，借助 dynamic_cast 類型識別符判斷節(jié)點類型從而執(zhí)行不同語句。若為內(nèi)部節(jié)點，則在每層通過之前構(gòu)建的二叉樹指針劃分為兩路，左路添 0 ，右路添 1，再分別遞歸調(diào)用本身而進到下一層迭代；若為葉子節(jié)點，則說明已經(jīng)到達我們要編碼的字符處，于是插入<字符, 編碼>鍵值對到 map 中。

// 搜索二叉樹并編碼
using HuffCode = vector;
using HuffCodeMap = map;,>


void GenerateCodes(const INode * node, const HuffCode& prefix, HuffCodeMap& outCodes)
{
    if (const InternalNode * in = dynamic_cast(node))    // 驗證是否為內(nèi)部節(jié)點
    {
        // 劃分左路
        HuffCode leftPrefix = prefix;
        leftPrefix.push_back(false);
        GenerateCodes(in->left, leftPrefix, outCodes);
        // 劃分右路
        HuffCode rightPrefix = prefix;
        rightPrefix.push_back(true);
        GenerateCodes(in->right, rightPrefix, outCodes);
    }
    else if (const LeafNode * lf = dynamic_cast(node))    // 驗證是否為葉子節(jié)點
        outCodes[lf->c] = prefix;    // 插入鍵值對
}

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 


#define CAPACITY 1<using namespace std;
using HuffCode = vector;
using HuffCodeMap = map;,>


class INode
{
public:
    const unsigned weight;
    virtual ~INode() {}


protected:
    INode(unsigned weight) : weight(weight) {}
};


class InternalNode : public INode
{
public:
    INode * const left;
    INode * const right;


    InternalNode(INode * leftChild, INode * rightChild) : INode(leftChild->weight + rightChild->weight), left(leftChild), right(rightChild) {}
    ~InternalNode()
    {
        delete left;
        delete right;
    }
};


class LeafNode : public INode
{
public:
    const char c;


    LeafNode(unsigned weight, char c) : INode(weight), c(c) {}
};


// 構(gòu)建樹
INode* BuildTree(const unsigned (&frequencies)[CAPACITY])
{
    struct NodeCmp
    {
        bool operator()(const INode * lhs, const INode * rhs) const { return lhs->weight > rhs->weight; }
    };
    priority_queue, NodeCmp> tree;*,>


    for (unsigned i = 0; i < CAPACITY; ++i)
        if (frequencies[i] != 0)
            tree.push(new LeafNode(frequencies[i], static_cast(i)));


    while (tree.size() > 1)
    {
        INode * leftChild = tree.top();
        tree.pop();


        INode * rightChild = tree.top();
        tree.pop();


        INode * parent = new InternalNode(leftChild, rightChild);
        tree.push(parent);
    }
    return tree.top();
}


// 搜索二叉樹并編碼
void GenerateCodes(const INode * node, const HuffCode& prefix, HuffCodeMap& outCodes)
{
    if (const InternalNode * in = dynamic_cast(node))
    {
        HuffCode leftPrefix = prefix;
        leftPrefix.push_back(false);
        GenerateCodes(in->left, leftPrefix, outCodes);


        HuffCode rightPrefix = prefix;
        rightPrefix.push_back(true);
        GenerateCodes(in->right, rightPrefix, outCodes);
    }
    else if (const LeafNode * lf = dynamic_cast(node))
        outCodes[lf->c] = prefix;
}


int main()
{
    char* SampleString = nullptr;    // 聲明指向字符數(shù)組的指針
    cout << "Input original string: ";


    // 判定堆內(nèi)存分配成功與否及讀取輸入行
    while ((SampleString = new char[CAPACITY]) && cin.getline(SampleString, CAPACITY))
    {
        // 編碼過程
        cout << endl;
        char * ptr = SampleString;    // 創(chuàng)建地址副本
        unsigned frequencies[CAPACITY] = {0};    // 初始化頻率表
        while (*ptr != '')    // 統(tǒng)計頻次
            ++frequencies[*ptr++];


        INode * root = BuildTree(frequencies);    // 得到對應哈夫曼樹并返回根節(jié)點地址
        HuffCodeMap codes;
        GenerateCodes(root, HuffCode(), codes);    // 為每個字符賦予哈夫曼碼
        delete root;


        // 遍歷map容器輸出不同字符與編碼
        for (HuffCodeMap::const_iterator it = codes.begin(); it != codes.end(); ++it)
        {
            cout << it->first << ": ";
            copy(it->second.begin(), it->second.end(), ostream_iterator(cout));
            cout << endl;
        }
        cout << SampleString << ": ";
        ptr = SampleString;


        // 輸出字符串完整編碼
        while (*ptr != '')
        {
            for (HuffCodeMap::const_iterator it = codes.begin(); it != codes.end(); ++it)
                if (it->first == *ptr)
                    copy(it->second.begin(), it->second.end(), ostream_iterator(cout));
            ptr++;
        }
        delete SampleString;
        SampleString = nullptr;


        // 解碼過程
        char choice;
        cout << endl << endl << "Decoding? (Y/N): ";
        cin.get(choice);
        // 判定是否繼續(xù)
        if (toupper(choice) == 'Y')
        {
            char each;    // 定義單字符
            bool flag = true;
            HuffCode total;    // 定義bool向量
            HuffCodeMap::const_iterator it = codes.begin();    // 創(chuàng)建初始迭代器


            while (getchar() != '
')
                continue;
            cout << "Input encoded string: ";
            // 獲取輸入行單個字符
            while ((each = cin.get()) && each != '
')
            {
                each -= 48;    // 轉(zhuǎn)換為數(shù)字表示
                total.push_back(static_cast(each));    // 強轉(zhuǎn)為bool型壓入容器
                // 依據(jù)編碼表反向匹配
                while (it != codes.end())
                {
                    if (total == it->second)
                    {
                        if (flag)
                        {
                            cout << "Original string: ";
                            flag = false;
                        }
                        cout << it->first;    // 反向輸出字符
                        total.clear();    // 清空容器
                    }
                    ++it;
                }
                it = codes.begin();
            }
        }
        else
            while (getchar() != '
')
                continue;
        cout << endl << string(60, '-') << endl << "Carry on, input next string: ";
    }
    cout << endl;


    return 0;
}<>

5.6動態(tài)哈夫曼碼的設計

在此之前，我們一直所述的對象均為靜態(tài)哈夫曼編碼，靜態(tài)哈夫曼碼有個不太好的點，你差不多注意到了 —— 傳統(tǒng)靜態(tài) Huffman 編碼需要對數(shù)據(jù)進行兩次遍歷：第一次是構(gòu)造和傳輸 Huffman 樹到接收端，以收集消息中不同字符出現(xiàn)的頻率計數(shù)；第二次再基于第一次構(gòu)造的靜態(tài)樹結(jié)構(gòu)，編碼和傳輸消息本身。那么，這會導致在將其用于網(wǎng)絡通信時產(chǎn)生較大延遲，或者在文件壓縮應用程序中產(chǎn)生額外的磁盤訪問進而減慢算法。

于是，動態(tài)哈夫曼編碼誕生了。動態(tài)哈夫曼編碼（Dynamic Huffman coding），又稱適應性哈夫曼編碼（Adaptive Huffman coding），是基于哈夫曼編碼的自適應編碼技術。它允許在符號正在傳輸時構(gòu)建代碼，允許一次編碼并適應數(shù)據(jù)中變化的條件，即隨著數(shù)據(jù)流的到達，動態(tài)地收集和更新符號的概率（頻率）。一次編碼的好處是使得源程序可以實時編碼，但由于單個丟失會損壞整個代碼，因此它對傳輸錯誤更加敏感。

所以，F(xiàn)aller 和 Gallager 兩人各提出了一種單次遍歷方案，后被 Knuth 大大改進，用于構(gòu)造動態(tài) Huffman 編碼。發(fā)送器用來編碼消息中第 t+1 個字符的二叉樹（同時也是接收器用來重建第 t+1 個字符的二叉樹）是消息前 t 個字符的二叉樹。如此，發(fā)送器和接收器就都會從相同的初始樹開始，發(fā)送器永遠不需要將樹發(fā)送給接收器。很顯然，這與靜態(tài) Huffman 算法的情況不同。

不久，又有研究者設計并證明了一種于所有單遍方案中，在最壞情況下表現(xiàn)仍然是最優(yōu)的算法 A，它可以用于網(wǎng)絡通信的通用編碼方案，也可以作為基于文字的壓縮算法中的一種高效子例程。

算法 A 具備以下優(yōu)點：

• 對于編碼效率差異相對較大的小消息，每個字母占用更少的位

• 在 t 小于 104 時，相比所有“兩遍算法”都表現(xiàn)得更好

• 能對消息進行實時編解碼，每個字符使用不到一個額外的比特位對消息編碼

• 在文件壓縮、網(wǎng)絡通信和硬件實現(xiàn)方面有巨大應用潛力

• 可用來增強其他壓縮方案

< 未完待續(xù)……>

ELT.ZIP是誰？

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

成員：

上海工程技術大學大二在校生閆旭

合肥師范學院大二在校生楚一凡

清華大學大二在校生趙宏博

成都信息工程大學大一在校生高云帆

黑龍江大學大一在校生高鴻萱

山東大學大三在校生張智騰

ELT.ZIP是來自6個地方的同學，在OpenHarmony成長計劃啃論文俱樂部里，與來自華為、軟通動力、潤和軟件、拓維信息、深開鴻等公司的高手一起，學習、研究、切磋操作系統(tǒng)技術...

寫在最后

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

啃論文俱樂部的宗旨是希望同學們在開源活動中得到軟件技術能力提升、得到技術寫作能力提升、得到講解技術能力提升。大學一年級新生〇門檻參與，已有俱樂部來自多所高校的大一同學寫出高居榜首的技術文章。

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

OpenHarmony開源與開發(fā)者成長計劃—“啃論文俱樂部”學習資料合集

1）入門資料：啃論文可以有怎樣的體驗

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

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

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

4）往期啃論文俱樂部同學分享會精彩回顧：

同學分享會No1.成長計劃啃論文分享會紀要（2022/02/18）https://docs.qq.com/doc/DY2RZZmVNU2hTQlFY

同學分享會No.2 成長計劃啃論文分享會紀要（2022/03/11）https://docs.qq.com/doc/DUkJ5c2NRd2FRZkhF

同學們分享會No.3 成長計劃啃論文分享會紀要（2022/03/25）

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

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

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

后續(xù)，我們會在服務中心公眾號陸續(xù)分享一些 OpenHarmony 開源與開發(fā)者成長計劃—“啃論文俱樂部”學習心得體會和總結(jié)資料。記得呼朋引伴來看哦。