色哟哟视频在线观看-色哟哟视频在线-色哟哟欧美15最新在线-色哟哟免费在线观看-国产l精品国产亚洲区在线观看-国产l精品国产亚洲区久久

0
  • 聊天消息
  • 系統消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術視頻
  • 寫文章/發帖/加入社區
會員中心
創作中心

完善資料讓更多小伙伴認識你,還能領取20積分哦,立即完善>

3天內不再提示

統計壓縮編碼機理分析(上篇)

共熵服務中心 ? 來源:未知 ? 2022-12-21 21:25 ? 次閱讀

9d8b1912-8131-11ed-8abf-dac502259ad0.png

文章轉發自51CTO【ELT.ZIP】OpenHarmony啃論文俱樂部——《統計壓縮編碼機理分析》

1.技術DNA

9dbb62c0-8131-11ed-8abf-dac502259ad0.png

2. 智慧場景

場景 技術 開源項目
自動駕駛 / AR 點云壓縮 Draco/ 基于深度學習算法/PCL/OctNet
語音信號 稀疏快速傅里葉變換 SFFT
視頻 有損視頻壓縮 AV1/H.266編碼/H.266解碼/VP9
GPU 渲染 網格壓縮 MeshOpt/Draco
科學、云計算 動態選擇壓縮算法框架 Ares
內存縮減 無損壓縮 LZ4
科學應用 分層數據壓縮 HCompress
醫學圖像 醫學圖像壓縮 DICOM
數據庫服務器 無損通用壓縮 Brotli
人工智能圖像 人工智能圖像壓縮 RAISR
文本傳輸 短字符串壓縮 AIMCS
GAN媒體壓縮 GAN 壓縮的在線多粒度蒸餾 OMGD
圖像壓縮 圖像壓縮 OpenJPEG
文件同步 文件傳輸壓縮 rsync
數據庫系統 快速隨機訪問字符串壓縮 FSST
通用數據 高通量并行無損壓縮 ndzip
系統數據讀寫 增強只讀文件系統 EROFS

3.開篇簡介

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

3.1 統計編碼是什么

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

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

3.2統計編碼分類

四種常用的統計編碼有:香農·范諾編碼、Huffman 編碼、算術編碼以及 ANS,其中,香農·范諾編碼稱得上是現代第一個壓縮編碼,具有相當的歷史意義。

4.香農·范諾編碼

4.1誕生背景

9e0d00ee-8131-11ed-8abf-dac502259ad0.png

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

4.2簡單認識

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

以EBACBDBEBCDEAABEEBDDBABEBABCDBBADBCBECA這樣一串字符串為例,我們首先需要統計并計算其中每個字符的出現概率。

字符 A B C D E
計數 7 14 5 6 7
概率 0.179 0.359 0.128 0.154 0.179
下一步,將它們按照概率大小降序排列:
字符 B A E D C
計數 14 7 7 6 5
概率 0.359 0.179 0.179 0.154 0.128
然后,找到這樣一個兩字符之間的最佳分割點,它使兩側概率和盡可能接近,也就是差值最小,反復進行下去:

9e4429ac-8131-11ed-8abf-dac502259ad0.jpg

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

9e707354-8131-11ed-8abf-dac502259ad0.jpg

符號 A B C D E
計數 7 14 5 6 7
編碼 1 0 111 110 10

出現概率較高的字符被編碼成兩位,概率較低的則被編碼成三位。由此,我們便可計算出每個字符平均所需的編碼位數:

9e91a89e-8131-11ed-8abf-dac502259ad0.png

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

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

5.哈夫曼編碼

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

9eaea0a2-8131-11ed-8abf-dac502259ad0.jpg

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

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

5.1青出于藍而勝于藍

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

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

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

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

5.2編碼方法

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

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

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

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

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

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

5.3舉個例子

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

BACAB BACDA ABBBE

步驟一:根據上述字符串,統計各個字符出現的次數并排序:

字符 B A C D E
次數 6 5 2 1 1
9eca4924-8131-11ed-8abf-dac502259ad0.jpg

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

9eeb1fb4-8131-11ed-8abf-dac502259ad0.jpg

步驟三:繼續抽出兩個值最小的卡片,重復上一步并以此類推……

9f110940-8131-11ed-8abf-dac502259ad0.jpg

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

9f3e9f7c-8131-11ed-8abf-dac502259ad0.jpg

步驟五:從樹根到每片葉子依次遍歷,將經過的 0、1 記錄下來,即可得到哈夫曼碼表

字符 B A C D E
次數 6 5 2 1 1
編碼 1 0 10 110 111

所以,原本的字符串BACABBACDAABBBE用哈夫曼碼表示為:100010001100010011000001110111,符合字符出現次數越多編碼長度越短的標準。

5.4一些性質

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

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

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

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

編碼平均長度等式:

9f5fe4a2-8131-11ed-8abf-dac502259ad0.png

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

5.5算法實現

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

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

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


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

為了避免不必要的干擾,將 INode 的構造函數聲明為 protected。

葉子節點與內部節點的定義即是繼承 INode 后,把剩下的另外字段補充上去,通過調用父類 INode 的構造函數生成權值。

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


    LeafNode(unsigned weight, char c) : INode(weight), c(c) {}
};
內部節點中指向左右子節點的鏈接毫無疑問使用指針來實現,且指向 INode 類型。自身權值則通過將左右子節點的權值相加得到。此外,還需顯式聲明一個析構函數,以便在后續操作中自動釋放空間、防止野指針與內存泄漏。
// 內部節點
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;
    }
};

基本元素現已齊全,繼續進行下一步操作。上一小節我們說到,靜態 Huffman 算法需要對數據進行兩次遍歷,第一次是得到概率表并構建樹,第二次才進行字符編碼。先來看第一次,在構建樹之前必須提供一套排好序的概率表,假設現在有這樣一串字符DATACOMPRESSION,我們如何在計算機中用復雜度較低的算法統計并排序?肯定不能用眼睛盯著來數了。

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

// 生成頻數表
#define CAPACITY 1<char * ptr = "DATACOMPRESSION";    // 聲明字符串DATACOMPRESSION
unsigned frequencies[CAPACITY] = {0};    // 聲明并初始化數組
while (*ptr != '')            // 依次在每個字符對應于數組的位置中遞增1
    ++frequencies[*ptr++];
經過一番操作后,得到的數組狀態如下,下標反映指針所指位置:

9f7925b6-8131-11ed-8abf-dac502259ad0.jpg

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

接下來,采用優先級隊列 priority_queue 數據結構來構建二叉樹是不二選擇,既滿足存儲節點序列,又可自動排序,如此,事先也就不用再給頻數表排序了?,F在,封裝函數 BuildTree,只需唯一形參 frequencies[CAPACITY]:

// 構建二叉樹
INode* BuildTree(const unsigned (&frequencies)[CAPACITY])
{
    struct NodeCmp    // 聲明仿函數用于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)    // 構造葉子節點,返回地址到tree并排序
        if (frequencies[i] != 0)
            tree.push(new LeafNode(frequencies[i], static_cast(i)));


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

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

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


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;    // 插入鍵值對
}
至此,編碼的整體流程我們已經基本實現了,接下來應對其進行測試、驗證結果,用例如下:
#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) {}
};


// 構建樹
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;    // 聲明指向字符數組的指針
    cout << "Input original string: ";


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


        INode * root = BuildTree(frequencies);    // 得到對應哈夫曼樹并返回根節點地址
        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);
        // 判定是否繼續
        if (toupper(choice) == 'Y')
        {
            char each;    // 定義單字符
            bool flag = true;
            HuffCode total;    // 定義bool向量
            HuffCodeMap::const_iterator it = codes.begin();    // 創建初始迭代器


            while (getchar() != '
')
                continue;
            cout << "Input encoded string: ";
            // 獲取輸入行單個字符
            while ((each = cin.get()) && each != '
')
            {
                each -= 48;    // 轉換為數字表示
                total.push_back(static_cast(each));    // 強轉為bool型壓入容器
                // 依據編碼表反向匹配
                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;
}<>
初始時,聲明一個指向字符數組的指針用于保存字符串,然后從堆中創建一塊 CAPACITY 大小的空間并獲取用戶輸入。編碼時,需要注意的點是聲明頻率表時應同時初始化為 0,避免最終頻次統計錯誤。輸出單個字符編碼時,通過相應迭代器從頭至尾遍歷輸出每對鍵、值。若輸出完整編碼,將每個字符進行一次比較匹配即可。解碼時,用戶輸入的字符串為 01 長序列,因而定義單字符以方便逐位比較。每讀取一位字符在 HuffCode 中嘗試一輪全匹配,成功即輸出,否則即進入下一輪迭代。

5.6動態哈夫曼碼的設計

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

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

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

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

9fa97e78-8131-11ed-8abf-dac502259ad0.jpg

算法 A 具備以下優點:

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

  • 在 t 小于 104 時,相比所有“兩遍算法”都表現得更好

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

  • 在文件壓縮、網絡通信和硬件實現方面有巨大應用潛力

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

< 未完待續……>

ELT.ZIP是誰?

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

成員:

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

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

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

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

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

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

9fc8ed9e-8131-11ed-8abf-dac502259ad0.png

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

寫在最后

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

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

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

a28ba9ae-8131-11ed-8abf-dac502259ad0.jpg

a2a3672e-8131-11ed-8abf-dac502259ad0.jpg

a2cc4b1c-8131-11ed-8abf-dac502259ad0.jpg

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

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

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

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

3)企業/學校/老師/學生為什么要參與 & 啃論文俱樂部的運營辦法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

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

a2e41896-8131-11ed-8abf-dac502259ad0.png

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

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


原文標題:統計壓縮編碼機理分析(上篇)

文章出處:【微信公眾號:開源技術服務中心】歡迎添加關注!文章轉載請注明出處。


聲明:本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人,不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用,如有內容侵權或者其他違規問題,請聯系本站處理。 舉報投訴
  • 開源技術
    +關注

    關注

    0

    文章

    389

    瀏覽量

    7928
  • OpenHarmony
    +關注

    關注

    25

    文章

    3713

    瀏覽量

    16256

原文標題:統計壓縮編碼機理分析(上篇)

文章出處:【微信號:開源技術服務中心,微信公眾號:共熵服務中心】歡迎添加關注!文章轉載請注明出處。

收藏 人收藏

    評論

    相關推薦

    Minitab 在統計分析中的應用

    在當今數據驅動的世界中,統計分析成為了一個不可或缺的工具。Minitab作為一款功能強大的統計軟件,它能夠幫助用戶進行數據探索、假設檢驗、回歸分析等多種統計分析。 1. 數據管理 Mi
    的頭像 發表于 12-02 15:23 ?313次閱讀

    Huffman壓縮算法概述和詳細流程

    Huffman壓縮算法是一種基于字符出現頻率的編碼算法,通過構建Huffman樹,將出現頻率高的字符用短編碼表示,出現頻率低的字符用長編碼表示,從而實現對數據的
    的頭像 發表于 10-21 13:48 ?240次閱讀

    音頻信號的無損壓縮編碼是什么

    音頻信號的無損壓縮編碼是一種在不損失音頻質量的前提下,減少音頻文件大小的技術。這種技術對于存儲和傳輸音頻數據非常有用,尤其是在帶寬有限或存儲空間有限的情況下。無損壓縮編碼技術可以應用于各種音頻格式
    的頭像 發表于 09-25 14:10 ?405次閱讀

    示波器統計曲線和故障分析pass/fail測試

    虛擬示波器可以應用在工業自動化檢測中,除了常規的檢測波形和測量值參數以外,由多個行業客戶定制和驗證的統計曲線和故障分析(pass/fail)功能也為工業自動化檢測帶來極大的便利。(一)故障分析
    發表于 08-30 10:19

    LOTO示波器統計曲線和故障分析pass/fail測試

    虛擬示波器可以應用在工業自動化檢測中,除了常規的檢測波形和測量值參數以外,由多個行業客戶定制和驗證的統計曲線和故障分析(pass/fail)功能也為工業自動化檢測帶來極大的便利。(一)故障分析
    的頭像 發表于 08-30 10:07 ?306次閱讀
    LOTO示波器<b class='flag-5'>統計</b>曲線和故障<b class='flag-5'>分析</b>pass/fail測試

    眾鑫創展----1080P十倍光學變焦攝像頭方案

    OZ003是一款1080P支持十倍光學變焦的高清攝像頭模組。由索尼200萬像素高性能感光芯片,以及集成了高性能的ISP圖像處理模塊和視頻壓縮編碼器的SoC芯片組成。具備優異的圖像處理能力、極高
    的頭像 發表于 05-11 16:34 ?458次閱讀
    眾鑫創展----1080P十倍光學變焦攝像頭方案

    鴻蒙OpenHarmony南向:【Hi3516開發板介紹】

    Hi3516DV300作為新一代行業專用Smart HD IP攝像機SOC,集成新一代ISP(Image Signal Processor)、H.265視頻壓縮編碼器以及高性能NNIE引擎,具備低碼率、高畫質、低功耗等特點,并具備強勁的智能處理和分析能力。
    的頭像 發表于 05-06 16:13 ?605次閱讀
    鴻蒙OpenHarmony南向:【Hi3516開發板介紹】

    【RTC程序設計:實時音視頻權威指南】音視頻的編解碼壓縮技術

    音視頻所載有的信息在通過傳輸的時候就需要壓縮編碼。 其中,文本壓縮是指通過使用各種算法和技術,將文本數據表示為更緊湊的形式,以減少存儲空間。 霍夫曼編碼是一種無損壓縮算法,它可以根
    發表于 04-28 21:04

    FPGA壓縮算法有哪些

    在圖像壓縮算法中可以采用哈夫曼編碼的方式對編碼冗余的信息進行壓縮,可以采用預測的方式來減少像素間冗余,可以采用量化的方式完成心理視覺冗余信息的去除
    的頭像 發表于 04-15 11:48 ?637次閱讀
    FPGA<b class='flag-5'>壓縮</b>算法有哪些

    FFmpeg創始人為音頻壓縮工具TSAC,將音頻壓縮至極低比特率

    TSAC 官方網站提供了一系列原始音頻與壓縮音頻的對比試聽資源:https://bellard.org/tsac/TSCA。該壓縮技術基于為立體聲擴展的 Descript 音頻編碼器以及Transformer 模型,旨在提升
    的頭像 發表于 04-12 15:55 ?1022次閱讀

    谷歌推出Jpegli開源編碼庫,優化圖片壓縮,提升圖像品質

    另一大優勢則在于,Jpegli在保持對現有JPEG編碼/解碼器的全面兼容的前提下,同樣支持常用的8位格式,且額外支持10位乃至更高的可選項(有助于減輕壓縮偽影等問題)。
    的頭像 發表于 04-07 11:16 ?563次閱讀

    在CPU芯片領域,中國將迎來新型服務器的發展機遇,

    光致發光和壓縮編碼”(SPACE)的成像技術。通過使用SPACE,開發了一種多功能超寬帶、多波長壓縮成像傳感器。 研究亮點 開創了基于多種鑭系摻雜換能器的隨機光致發光與壓縮編碼方案(SPACE),能夠實現對X射線、紫外、近紅外I
    的頭像 發表于 03-21 17:23 ?530次閱讀
    在CPU芯片領域,中國將迎來新型服務器的發展機遇,

    雷達波形的產生與脈沖壓縮技術

      相位編碼信號的相位調制函數是離散的有限狀態,屬于“離散型“編碼脈沖壓縮信號。   在相位編碼中,二相編碼信號是常用的脈壓信號形式之
    的頭像 發表于 02-20 10:57 ?767次閱讀
    雷達波形的產生與脈沖<b class='flag-5'>壓縮</b>技術

    哈夫曼編碼怎么算 哈夫曼編碼左邊是0還是1

    哈夫曼編碼是一種基于頻率的變長編碼方式,常用于數據壓縮和信息傳輸領域。它是由美國數學家大衛·哈夫曼在1952年發明的,被廣泛應用于無損壓縮領域。 哈夫曼
    的頭像 發表于 01-30 11:27 ?2874次閱讀

    機房精密空調壓縮機排氣量不足原因分析

    機房精密空調壓縮機排氣量不足原因分析
    的頭像 發表于 01-20 11:49 ?838次閱讀
    機房精密空調<b class='flag-5'>壓縮</b>機排氣量不足原因<b class='flag-5'>分析</b>
    主站蜘蛛池模板: 91系列在线观看免费| 国产精品久久久久影院嫩草| 黄色a级免费网站| 区一区二视频免费观看| 一级毛片视频免费| 国产精品久久自在自2021| 欧美精品一区二区三区视频| 一区二区三区国产| 国产黄A片在线观看永久免费麻豆| 免费看b站| 一级毛片两人添下面| 国产麻豆精品久久一二三| 秋霞电影网午夜鲁丝片| 2022国产麻豆剧传媒剧情| 和姐姐做插得很深| 午夜国产在线观看| 成人手机在线| 女教师の诱惑| 最近中文字幕免费高清MV视频6 | 欧美激情一区二区三区视频| 野花韩国高清完整版在线观看5 | 同桌上课把奶露出来给我玩| 亚洲手机在线人成视频| 国产成人精视频在线观看免费| 麻豆狠色伊人亚洲综合网站| 亚洲欧洲日韩视频在钱| 国产精品无码久久久久不卡| 日韩精品一区二区中文| asian4you裸模| 老湿影院色情a| 樱花草动漫www| 娇妻让壮男弄的流白浆| 性夜影院午夜看片| 国产精品亚洲精品爽爽| 忘忧草日本在线社区WWW电影| 动漫成年美女黄漫网站| 日本wwwxx爽69护士| 啊好大好厉害好爽真骚| 欧美日韩午夜群交多人轮换| 97国产精品视频在线观看| 蜜桃视频一区二区|