前言

哈夫曼編碼是一種貪心算法和二叉樹結(jié)合的字符編碼方式，具有廣泛的應(yīng)用背景，最直觀的是文件壓縮。本文主要講述如何用哈夫曼編解碼實現(xiàn)文件的壓縮和解壓，并給出代碼實現(xiàn)。

哈夫曼編碼的概念

哈夫曼樹又稱作最優(yōu)樹，是一種帶權(quán)路徑長度最短的樹，而通過哈夫曼樹構(gòu)造出的編碼方式稱作哈夫曼編碼。

也就是說哈夫曼編碼是一個通過哈夫曼樹進(jìn)行的一種編碼，一般情況下，以字符 “0” 與 “1” 表示。編碼的實現(xiàn)過程很簡單，只要實現(xiàn)哈夫曼樹，通過遍歷哈夫曼樹，這里我們從根節(jié)點開始向下遍歷，如果

下個節(jié)點是左孩子，則在字符串后面追加 “0”，如果為其右孩子，則在字符串后追加 “1”。結(jié)束條件為當(dāng)前節(jié)點為葉子節(jié)點，得到的字符串就是葉子節(jié)點對應(yīng)的字符的編碼。

哈夫曼樹實現(xiàn)

根據(jù)貪心算法的思想實現(xiàn)，把字符出現(xiàn)頻率較多的字符用稍微短一點的編碼，而出現(xiàn)頻率較少的字符用稍微長一點的編碼。哈夫曼樹就是按照這種思想實現(xiàn)，下面將舉例分析創(chuàng)建哈夫曼樹的具體過程。

下面表格的每一行分別對應(yīng)字符及出現(xiàn)頻率，根據(jù)這些信息就能創(chuàng)建一棵哈夫曼樹。

字符

出現(xiàn)頻率

編碼

總二進(jìn)制位數(shù)

a

500

1

500

b

250

01

500

c

120

001

360

d

60

0001

240

e

30

00001

150

f

20

00000

100

如下圖，將每個字符看作一個節(jié)點，將帶有頻率的字符全部放到優(yōu)先隊列中，每次從隊列中取頻率最小的兩個節(jié)點 a 和 b(這里頻率最小的 a 作為左子樹)，然后新建一個節(jié)點R，把節(jié)點設(shè)置為兩個節(jié)點

的頻率之和，然后把這個新節(jié)點R作為節(jié)點A和B的父親節(jié)點。最后再把R放到優(yōu)先隊列中。重復(fù)這個過程，直到隊列中只有一個元素，即為哈夫曼樹的根節(jié)點。

由上分析可得，哈夫曼編碼的需要的總二進(jìn)制位數(shù)為 500 + 500 + 360 + 240 + 150 + 100 = 1850。上面的例子如果用等長的編碼對字符進(jìn)行壓縮，實現(xiàn)起來更簡單，6 個字符必須要 3 位二進(jìn)制位表示，

解壓縮的時候每次從文本中讀取 3 位二進(jìn)制碼就能翻譯成對應(yīng)的字符，如 000，001，010，011，100，101 分別表示 a，b，c，d，e，f。則需要總的二進(jìn)制位數(shù)為 (500 + 250 + 120 + 60 + 30 + 20)*

3 = 2940。對比非常明顯哈夫曼編碼需要的總二進(jìn)制位數(shù)比等長編碼需要的要少很很多，這里的壓縮率為 1850 / 2940 = 62%。哈夫曼編碼的壓縮率通常在 20% ~90% 之間。

下面代碼是借助標(biāo)準(zhǔn)庫的優(yōu)先隊列 std::priority_queque 實現(xiàn)哈夫曼樹的代碼簡單實現(xiàn)，構(gòu)造函數(shù)需要接受 afMap?入?yún)?#xff0c;huffmanCode 函數(shù)是對象的唯一對外方法，哈夫曼編碼的結(jié)果會寫在 codeMap 里

面。這部分是創(chuàng)建哈夫曼樹的核心代碼，為方便調(diào)試，我還實現(xiàn)了打印二叉樹樹形結(jié)構(gòu)的功能，這里就補(bǔ)貼代碼，有興趣的同學(xué)可以到文末給出的 github 倉庫中下載。

1 using uchar = unsigned char;2

3 structNode {4 uchar c;5 intfreq;6 Node *left;7 Node *right;8 Node(uchar _c, int f, Node *l = nullptr, Node *r =nullptr)9 : c(_c), freq(f), left(l), right(r) {}10 bool operator

11 return freq >node.freq;12 }13 };14

15 classhuffTree {16 public:17 huffTree(const std::map&afMap) {18 for(auto i : afMap) {19 Node n(i.first, i.second);20 q.push(n);21 }22 _makehuffTree();23 }24 ~huffTree() {25 Node node =q.top();26 _deleteTree(node.left);27 _deleteTree(node.right);28 }29 void huffmanCode(std::map&codeMap) {30 Node node =q.top();31 std::stringprefix;32 _huffmanCode(&node, prefix, codeMap);33 }34 private:35 static bool _isLeaf(Node*n) {36 return n->left == nullptr && n->right ==nullptr;37 }38 void _deleteTree(Node*n) {39 if (!n) return;40 _deleteTree(n->left);41 _deleteTree(n->right);42 deleten;43 }44 void_makehuffTree() {45 while (q.size() != 1) {46 Node *left = newNode(q.top()); q.pop();47 Node *right = newNode(q.top()); q.pop();48 Node node('R', left->freq + right->freq, left, right);49 q.push(node);50 }51 }52 void _huffmanCode(Node *root, std::string&prefix,53 std::map&codeMap) {54 std::string tmp =prefix;55 if (root->left !=nullptr) {56 prefix += '0';57 if (_isLeaf(root->left)) {58 codeMap[root->left->c] =prefix;59 } else{60 _huffmanCode(root->left, prefix, codeMap);61 }62 }63 if (root->right !=nullptr) {64 prefix =tmp;65 prefix += '1';66 if (_isLeaf(root->right)) {67 codeMap[root->right->c] =prefix;68 } else{69 _huffmanCode(root->right, prefix, codeMap);70 }71 }72 }73 private:74 std::priority_queueq;75 };

文件壓縮實現(xiàn)

首先需要給出文件壓縮和下面將要提到的文件解壓縮的公共頭文件，如下：

1 //得到index位的值，若index位為0，則GET_BYTE值為假，否則為真

2 #define GET_BYTE(vbyte, index) (((vbyte) & (1 << ((index) ^ 7))) != 0)

3 //index位置1

4 #define SET_BYTE(vbyte, index) ((vbyte) |= (1 << ((index) ^ 7)))

5 //index位置0

6 #define CLR_BYTE(vbyte, index) ((vbyte) &= (~(1 << ((index) ^ 7))))

7

8 using uchar = unsigned char;9

10 structfileHead {11 char flag[4]; //壓縮二進(jìn)制文件頭部標(biāo)志 ycy

12 uchar alphaVariety; //字符種類

13 uchar lastValidBit; //最后一個字節(jié)的有效位數(shù)

14 char unused[10]; //待用空間

15 }; //這個結(jié)構(gòu)體總共占用16個字節(jié)的空間

16

17 structalphaFreq {18 uchar alpha; //字符,考慮到文件中有漢字，所以定義成uchar

19 int freq; //字符出現(xiàn)的頻度

20 alphaFreq() {}21 alphaFreq(const std::pair&x)22 : alpha(x.first), freq(x.second) {}23 };

下面是文件壓縮的代碼具體實現(xiàn)。過程其實相對簡單，理解起來不難。首先需要讀取文件信息，統(tǒng)計每一個字符出現(xiàn)的次數(shù)，這里實現(xiàn)是從 std::map 容器以字符為 key 累加統(tǒng)計字符出現(xiàn)的次數(shù)。然后，

用統(tǒng)計的結(jié)果 _afMap 創(chuàng)建哈夫曼樹，得到相應(yīng)的每個字符的哈夫曼編碼 _codeMap。最后，就是將數(shù)據(jù)寫入壓縮文件，該過程需要先寫入文件頭部信息， 即結(jié)構(gòu)體 fileHead 的內(nèi)容，這部分解壓縮的時

候進(jìn)行格式校驗等需要用到。接著將 _afMap 的字符及頻率數(shù)據(jù)依次寫入文件中，這部分是解壓縮時重新創(chuàng)建哈夫曼樹用來譯碼。到這一步就依次讀取源文件的每一個字符，將其對應(yīng)的哈夫曼編碼寫進(jìn)

文件中去。至此壓縮文件的過程結(jié)束。下面的代碼不是很難，我就不加注釋了。

1 classhuffEncode {2 public:3 bool encode(const char* srcFilename, const char*destFilename) {4 if (!_getAlphaFreq(srcFilename)) return false;5 huffTree htree(_afMap);6 htree.huffmanCode(_codeMap);7 return_encode(srcFilename, destFilename);8 }9 private:10 int_getLastValidBit() {11 int sum = 0;12 for(auto it : _codeMap) {13 sum += it.second.size() *_afMap.at(it.first);14 sum &= 0xFF;15 }16 sum &= 0x7;17 return sum == 0 ? 8: sum;18 }19 bool _getAlphaFreq(const char*filename) {20 uchar ch;21 std::ifstream is(filename, std::ios::binary);22 if (!is.is_open()) {23 printf("read file failed! filename: %s", filename);24 return false;25 }26 is.read((char*)&ch, sizeof(uchar));27 while (!is.eof()) {28 _afMap[ch]++;29 is.read((char*)&ch, sizeof(uchar));30 }31 is.close();32 return true;33 }34 bool _encode(const char* srcFilename, const char*destFilename) {35 uchar ch;36 uchar value;37 int bitIndex = 0;38 fileHead filehead = {'e', 'v', 'e', 'n'};39 filehead.alphaVariety =(uchar) _afMap.size();40 filehead.lastValidBit =_getLastValidBit();41

42 std::ifstream is(srcFilename, std::ios::binary);43 if (!is.is_open()) {44 printf("read file failed! filename: %s", srcFilename);45 return false;46 }47 std::ofstream io(destFilename, std::ios::binary);48 if (!io.is_open()) {49 printf("read file failed! filename: %s", destFilename);50 return false;51 }52

53 io.write((char*)&filehead, sizeof(fileHead));54 for(auto i : _afMap) {55 alphaFreq af(i);56 io.write((char*)&af, sizeof(alphaFreq));57 }58

59 is.read((char*)&ch, sizeof(uchar));60 while (!is.eof()) {61 std::string code =_codeMap.at(ch);62 for(auto c : code) {63 if ('0' ==c) {64 CLR_BYTE(value, bitIndex);65 } else{66 SET_BYTE(value, bitIndex);67 }68 ++bitIndex;69 if (bitIndex >= 8) {70 bitIndex = 0;71 io.write((char*)&value, sizeof(uchar));72 }73 }74 is.read((char*)&ch, sizeof(uchar));75 }76

77 if(bitIndex) {78 io.write((char*)&value, sizeof(uchar));79 }80 is.close();81 io.close();82 return true;83 }84 private:85 std::map_afMap;86 std::map_codeMap;87 };

文件解壓縮實現(xiàn)

文件解壓縮其實就是哈夫曼編碼的譯碼過程，處理過程相對于壓縮過程來說相對復(fù)雜一點，但其實就是將文件編碼按照哈夫曼編碼的既定規(guī)則翻譯出原來對應(yīng)的字符，并將字符寫到文件中的過程。較為

詳細(xì)的過程是先讀取文件頭部信息，校驗文件格式是否是上面壓縮文件的格式(這里是flag的四個字符為even)，不是則返回錯誤。然后根據(jù)頭部信息字符種類?alphaVariety(即字符的個數(shù))依次讀取字

符及其頻率，并將讀取的內(nèi)容放到? _afMap 中，然后創(chuàng)建哈夫曼樹,得到相應(yīng)的每個字符的哈夫曼編碼 _codeMap，并遍歷 _codeMap 創(chuàng)建以字符編碼為 key 的譯碼器 _decodeMap，主要方便是后面譯碼

的時候根據(jù)編碼獲取其對應(yīng)的字符。然后讀取壓縮文件剩余的內(nèi)容，每次讀取一個字節(jié)即 8 個二進(jìn)制位，獲取哈夫曼樹根節(jié)點，用一個樹節(jié)點指針pNode指向根節(jié)點，然后逐個讀取二進(jìn)制，每次根據(jù)二

進(jìn)制位的值，當(dāng)值為 0 指針走左子樹，當(dāng)值為 1 指針走右子樹，并將值添加到 std::string 類型的字符串 code 后面，直到走到葉子結(jié)點位置為止。用 code 作為 key 可在譯碼器 _decodeMap 中取得對應(yīng)

的字符，將字符寫到新文件中去。然后清空 code，pNode重新指向根節(jié)點，繼續(xù)走上面的流程，直到讀完文件內(nèi)容。文件最后一個字節(jié)的處理和描述有點不一樣，需根據(jù)文件頭信息的最后一位有效

位?lastValidBit 進(jìn)行特殊處理，這里特別提醒一下。

1 classhuffDecode {2 public:3 huffDecode() : _fileHead(nullptr), _htree(nullptr) {4 _fileHead = newfileHead();5 }6 ~huffDecode() {7 if (!_fileHead) delete_fileHead;8 if (!_htree) delete_htree;9 }10 private:11 static bool _isLeaf(Node*n) {12 return n->left == nullptr && n->right ==nullptr;13 }14 long _getFileSize(const char*strFileName) {15 std::ifstream in(strFileName);16 if (!in.is_open()) return 0;17

18 in.seekg(0, std::ios_base::end);19 std::streampos sp = in.tellg();20 in.close();21 returnsp;22 }23 bool _getAlphaFreq(const char*filename) {24 std::ifstream is(filename, std::ios::binary);25 if (!is) {26 printf("read file failed! filename: %s", filename);27 return false;28 }29

30 is.read((char*)_fileHead, sizeof(fileHead));31 if (!(_fileHead->flag[0] == 'e' &&

32 _fileHead->flag[1] == 'v' &&

33 _fileHead->flag[2] == 'e' &&

34 _fileHead->flag[3] == 'n')) {35 printf("not support this file format! filename: %s\n", filename);36 return false;37 }38 for (int i = 0; i < static_cast(_fileHead->alphaVariety); ++i) {39 alphaFreq af;40 is.read((char*)&af, sizeof(af));41 _afMap.insert(std::pair(af.alpha, af.freq));42 }43 is.close();44 return true;45 }46 bool _decode(const char*srcFilename,47 const char*destFilename) {48 long fileSize =_getFileSize(srcFilename);49

50 std::ifstream is(srcFilename, std::ios::binary);51 if (!is) {52 printf("read file failed! filename: %s", srcFilename);53 return false;54 }55 is.seekg(sizeof(fileHead) + sizeof(alphaFreq) * _fileHead->alphaVariety);56

57 Node node = _htree->getHuffTree();58 Node* pNode = &node;59

60 std::ofstream io(destFilename, std::ios::binary);61 if (!io) {62 printf("create file failed! filename: %s", destFilename);63 return false;64 }65

66 uchar value;67 std::stringcode;68 int index = 0;69 long curLocation = is.tellg();70 is.read((char*)&value, sizeof(uchar));71 while (1) {72 if(_isLeaf(pNode)) {73 uchar alpha =_decodeMap[code];74 io.write((char*)&alpha, sizeof(uchar));75 if (curLocation >= fileSize && index >= _fileHead->lastValidBit) {76 break;77 }78 code.clear();79 pNode = &node;80 }81

82 if(GET_BYTE(value, index)) {83 code += '1';84 pNode = pNode->right;85 } else{86 pNode = pNode->left;87 code += '0';88 }89 if (++index >= 8) {90 index = 0;91 is.read((char*)&value, sizeof(uchar));92 curLocation = is.tellg();93 }94 }95

96 is.close();97 io.close();98 return true;99 }100 public:101 bool decode(const char* srcFilename, const char*destFilename) {102 if (!_getAlphaFreq(srcFilename)) return false;103 long fileSize =_getFileSize(srcFilename);104 _htree = newhuffTree(_afMap);105 _htree->watch();106 _htree->huffmanCode(_codeMap);107

108 for(auto it : _codeMap) {109 _decodeMap.insert(std::pair<:string uchar>(it.second, it.first));110 }111

112 return_decode(srcFilename, destFilename);113 }114 private:115 fileHead *_fileHead;116 huffTree *_htree;117 std::map_afMap;118 std::map_codeMap;119 std::map<:string uchar>_decodeMap;120 };

總結(jié)

以上是生活随笔為你收集整理的labview霍夫曼编码_哈夫曼编解码压缩解压文件—C++实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。