網(wǎng)站首頁 行業(yè)快訊 > 正文
霍夫曼樹（圖解霍夫曼編碼）
簡明易懂的霍夫曼編碼來啦，用圖片的形式解答霍夫曼是不是很簡單呢，瀏覽完本文就去動手試一試吧！
責(zé)編 | 張紅月
出處 | 沉默王二
今天來給大家普及一下霍夫曼編碼（Huffman Coding），一種用于無損數(shù)據(jù)壓縮的熵編碼算法，由美國計(jì)算機(jī)科學(xué)家大衛(wèi)·霍夫曼在 1952 年提出——這么專業(yè)的解釋，不用問，來自維基百科了。
說實(shí)話，很早之前我就聽說過霍夫曼編碼，除了知道它通常用于 GZIP、BZIPPKZIP 這些常規(guī)的壓縮格式中，我還知道它通常用于壓縮重復(fù)率比較高的字符數(shù)據(jù)。
大家想啊，英文就 26 個字母進(jìn)行的無限組合，重復(fù)率高得一逼??！常用的漢字也不多，2500 個左右，別問我怎么知道的，我有問過搜索引擎的。
字符重復(fù)的頻率越高，霍夫曼編碼的工作效率就越高！
是時候，和大家一起來了解一下霍夫曼編碼的工作原理啦，畢竟一名優(yōu)秀的程序員要能做到知其然知其所以然——請?jiān)试S我又用了一次這句快用臭了話。
假設(shè)下面的字符串要通過網(wǎng)絡(luò)發(fā)送。
大家應(yīng)該知道，每個字符占 8 個比特，上面這串字符總共有 15 個字符，所以一共要占用 15*8=120 個比特。沒有疑問吧？有疑問的同學(xué)請不好意思下。
如果我們使用霍夫曼編碼的話，就可以將這串字符壓縮到一個更小的尺寸。怎么做到的呢？
霍夫曼編碼首先會使用字符的頻率創(chuàng)建一棵樹，然后通過這個樹的結(jié)構(gòu)為每個字符生成一個特定的編碼，出現(xiàn)頻率高的字符使用較短的編碼，出現(xiàn)頻率低的則使用較長的編碼，這樣就會使編碼之后的字符串平均長度降低，從而達(dá)到數(shù)據(jù)無損壓縮的目的。
拿上面這串初始字符來一步步的說明下霍夫曼編碼的工作步驟。
計(jì)算字符串中每個字符的頻率
B 出現(xiàn) 1 次，C 出現(xiàn) 6 次，A 出現(xiàn) 5 次，D 出現(xiàn) 3 次。
按照字符出現(xiàn)的頻率進(jìn)行排序，組成一個隊(duì)列 Q
出現(xiàn)頻率最低的在前面，出現(xiàn)頻率高的在后面。
把這些字符作為葉子節(jié)點(diǎn)開始構(gòu)建一顆樹
首先創(chuàng)建一個空節(jié)點(diǎn) z，將最小頻率的字符分配給 z 的左側(cè)，并將頻率排在第二位的分配給 z 的右側(cè)，然后將 z 賦值為兩個字符頻率的和。
B 的頻率最小，所以在左側(cè)，然后是頻率為 3 的 D，在右側(cè)；然后把它們的父節(jié)點(diǎn)的值設(shè)為 4，子節(jié)點(diǎn)的頻率之和。
然后從隊(duì)列 Q 中刪除 B 和 D，并將它們的和添加到隊(duì)列中，上圖中 * 表示的位置。緊接著，重新創(chuàng)建一個空的節(jié)點(diǎn) z，并將 4 作為左側(cè)的節(jié)點(diǎn)，頻率為 5 的 A 作為右側(cè)的節(jié)點(diǎn)，4 與 5 的和作為父節(jié)點(diǎn)。
繼續(xù)按照之前的思路構(gòu)建樹，直到所有的字符都出現(xiàn)在樹的節(jié)點(diǎn)中。
版權(quán)說明： 本文由用戶上傳，如有侵權(quán)請聯(lián)系刪除！
猜你喜歡：
- 2022-09-20 男人惡心是什么病的前兆（惡心是什么病的前兆）
- 2022-09-20 山東財(cái)經(jīng)大學(xué)東方學(xué)院考研率怎么樣（山東財(cái)經(jīng)大學(xué)考研率是多少）
- 2022-09-20 廣西最早的大學(xué)叫什么大學(xué)（在桂林設(shè)立的廣西最早的大學(xué)是哪所大學(xué)）
- 2022-09-20 小兒肺炎有5個常見癥狀嗎（小兒肺炎有5個常見癥狀）
- 2022-09-20 m是哪個服裝品牌的標(biāo)志（標(biāo)志為M的衣服是什么牌子的）
- 2022-09-20 什么叫正比例什么叫反比例舉例說明（什么叫反比例,舉個例子說明,）
- 2022-09-20 一包煙要多少根煙絲（一包煙要多少根）
- 2022-09-20 男人吃櫻桃對身體有什么好處（男人吃櫻桃有什么好處）
最新文章：
- 2023-07-02 怎樣挑選新鮮的豬肝?（怎么挑選新鮮豬肝 挑選新鮮豬肝的小技巧）
- 2023-07-02 木地板都有哪些種類（木地板的種類有哪些）
- 2023-07-02 白蠟?zāi)炯揖叩膬?yōu)缺點(diǎn)（松木家具的優(yōu)缺點(diǎn)）
- 2023-07-02 怎么清洗窗簾布上的污垢（怎么清洗窗簾）
- 2023-07-02 世界上最可愛的小倉鼠的樣子（可愛小倉鼠的種類）
- 2023-07-02 小貓拉不出來屎怎么辦（小貓拉不出屎怎么辦）
- 2023-07-02 新飛小冰箱耗電量一天多少度（小冰箱耗電量一天多少度）
- 2023-07-02 公司注銷工業(yè)房產(chǎn)怎么辦手續(xù)（公司注銷工業(yè)房產(chǎn)怎么辦）
- 2023-07-02 鳳凰層到底好還是不好（鳳凰層是哪一層）
- 2023-07-02 馬桶寬度空間留多少（馬桶兩邊的空間大小是多少）
- 2023-07-02 如何訓(xùn)練貓咪小便（如何訓(xùn)練貓大小便）
- 2023-07-02 衛(wèi)生間吊頂防潮層做法圖集（衛(wèi)生間吊頂方法是什么）
- 2023-07-02 狗狗為什么總是流口水怎么辦（狗狗為什么愛流口水）
- 2023-07-02 臥室窗戶漏水由誰負(fù)責(zé)維修（臥室窗戶漏風(fēng)怎么辦）
- 2023-07-02 世界名貓大全（世界名貓你知道幾種）
- 2023-07-02 applewatchseries7和6對比（apple watch series 7和6的區(qū)別）