統(tǒng)計壓縮編碼機(jī)理分析（上篇）

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

接下來，采用優(yōu)先級隊列 priority_queue 數(shù)據(jù)結(jié)構(gòu)來構(gòu)建二叉樹是不二選擇，既滿足存儲節(jié)點(diǎn)序列，又可自動排序，如此，事先也就不用再給頻數(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é)點(diǎn)，返回地址到tree并排序
        if (frequencies[i] != 0)
            tree.push(new LeafNode(frequencies[i], static_cast(i)));


    while (tree.size() > 1)    // 不斷向上構(gòu)造內(nèi)部節(jié)點(diǎn)，直至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 的實(shí)例 tree 之后，便可開始遍歷頻數(shù)表，將權(quán)值不為 0 的字符連同權(quán)值一起以葉子節(jié)點(diǎn)類型對象存進(jìn) tree，并會按權(quán)值遞增的順序排列。完畢后，循環(huán)依次取出隊頭前兩個最小的葉子節(jié)點(diǎn)記錄地址，生成上層內(nèi)部節(jié)點(diǎn)再入隊重新排序，最終返回樹根地址。

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

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


void GenerateCodes(const INode * node, const HuffCode& prefix, HuffCodeMap& outCodes)
{
    if (const InternalNode * in = dynamic_cast(node))    // 驗(yàn)證是否為內(nèi)部節(jié)點(diǎn)
    {
        // 劃分左路
        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))    // 驗(yàn)證是否為葉子節(jié)點(diǎn)
        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);    // 得到對應(yīng)哈夫曼樹并返回根節(jié)點(diǎn)地址
        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));    // 強(qiáng)轉(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)哈夫曼碼的設(shè)計

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

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

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

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

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

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

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

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

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

• 可用來增強(qiáng)其他壓縮方案

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

ELT.ZIP是誰？

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

成員：

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

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

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

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

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

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

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

寫在最后

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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