Huffman編碼數據壓縮算法實現（附MFC界面）

前言

最近老板接了一個國網電力壓縮的項目交給我們來做，因為要寫一個演示的界面，電腦上又沒有裝QT，想著自己以后可能也不會寫界面這一類的用的不多也就沒下，就直接用了Windows的MFC寫了一個簡單的小壓縮程序，這是本人上研究生以來老板給的第一個橫向項目，自己也是個小菜雞到現在什么語言都用的不太熟悉，就這個機會將自己這次寫的程序寫成一篇文章記錄下來，以備后續參考。應用程序中集成了兩種無損壓縮算法，Huffman編碼和LZ77編碼，還有兩種壓縮算法疊加的組合壓縮。ps：本人不搞數據壓縮，還花了點兒時間研究了下這兩種算法，只懂基本的原理 = =！！

Huffman算法的實現

Huffman算法也是一個比較老的算法了，基本流程是先構建Huffman樹，再進行Huffman編碼，最后將編碼結果用二進制的比特流寫入二進制文件，不多廢話，直接上代碼：

這是huffman算法的頭文件Huffman.h#pragma once#include <iostream> #include <fstream> #include <string> #include <vector> #include <map>using namespace std; //定義樹節點的最大容量 const int MAX_N = 100; //定義為無窮大 const int INF = 0x7fffffff;//哈夫曼樹節點定義 class HNode { public:char data; //節點值double weight; //權重int parent; //雙親節點int lchild; //左孩子節點int rchild; //右孩子節點 };//哈夫曼編碼節點 class HuffCode { public:CString code;//數據的編碼char huffinfo;//被編碼數據 };class HuffMan { public:HuffMan() {}~HuffMan() {}/*********************************************************///函數名：CreateForest//返回值類型：void//參數：string filename//功能：// 1.讀取文件中數據信息// 2.構建單節點二叉樹組成的森林/*******************************************************/bool CreateForest(CString filename, bool replace);/*********************************************************///函數名：CreateHuffManTree//返回值類型：void//參數：NULL//功能：利用森林構建哈夫曼樹/********************************************************/void CreateHuffManTree();/*********************************************************///函數名：CreateHuffCode//返回值類型：bool -> 判斷是否編碼成功，成功返回true,否則false//功能：生成哈夫曼編碼/********************************************************/bool CreateHuffCode();/*********************************************************///函數名：compress//返回值類型：double//參數：需要壓縮文件的路徑//功能：壓縮文件并輸出壓縮比例/********************************************************/double compress(CString filepath, CString outpath, CProgressCtrl &pro, CStatic &m_proview);/*********************************************************///函數名：DeCompress//返回值類型：void//參數：需要解壓縮文件的路徑//功能：解壓縮文件并輸出/********************************************************/void DeCompress(CString outpath, string codestream, CProgressCtrl &pro, CStatic &m_proview, bool replace);/*********************************************************///函數名：GetInfo//返回值類型：string//參數：需要獲取信息的文件的路徑//功能：輸出目標文件的大小，單位為字節//返回值：從編碼的二進制文件中得到源文件的字符統計信息和二進制流，并將二進制流轉換為字符串返回/********************************************************/string GetInfo(CString inpath);/*********************************************************///函數名：AcquireLength//返回值類型：long//參數：需要獲取長度的文件的路徑//功能：輸出目標文件的大小，單位為字節/********************************************************/unsigned long long AcquireLength(CString filepath);/*********************************************************///這個函數其實對于huffman編碼來說沒啥用，可以忽略，是我用來代替文本中重復字符串用的//函數名：Replace//返回值類型：string//參數：需要替換的目標字符串，要替換為的字符串，//功能：輸出目標文件的大小，單位為字節//返回值：返回替換后的字符串/********************************************************/string Replace(string str, string rep, string c);public:HNode ht[MAX_N];//哈夫曼樹HuffCode hcode[MAX_N];//編碼long snum;//總字符數int count = 0;//需要編碼的字符總數map<char, double> statistic;//用于存儲源文件字符統計信息的字典 };

上述程序中，compress和DeCompress函數中CProgressCtrl &pro, CStatic &m_proview，這兩個參數是為了跟MFC進行信息交換的（本來想寫個進度條的），事實上也沒用到= =，不需要的可以省略。

這是Huffman算法的主程序文件#include "stdafx.h" //沒寫界面這個可以不要 #include "ApplicationDlg.h" //沒寫界面這個可以不要 #include "Huffman.h" #include <bitset>/*********************************************************///函數名：AcquireLength//返回值類型：long//參數：需要獲取長度的文件的路徑//功能：輸出目標文件的大小，單位為字節/********************************************************/ unsigned long long HuffMan::AcquireLength(CString filepath) {CStdioFile inputFile;unsigned long long inSize;if (inputFile.Open(filepath, CStdioFile::modeRead)){inSize = inputFile.GetLength();}inputFile.Close();return inSize; }/*********************************************************///這個函數其實對于huffman編碼來說沒啥用，可以忽略，是我用來代替文本中重復字符串用的//函數名：Replace//返回值類型：string//參數：需要替換的目標字符串，要替換為的字符串，//功能：輸出目標文件的大小，單位為字節//返回值：返回替換后的字符串/********************************************************/ string HuffMan::Replace(string str, string rep, string c) {int pos;pos = str.find(rep);查找指定的串while (pos != -1){str.replace(pos, rep.length(), c);用新的串替換掉指定的串pos = str.find(rep);//繼續查找指定的串，直到所有的都找到為止}return str; } /*********************************************************/ //函數名：CreateForest //返回值類型：void //參數：string filename //返回：創建成功返回True，失敗返回False //功能： // 1.讀取文件中數據信息 // 2.構建單節點二叉樹組成的森林 /*******************************************************/ bool HuffMan::CreateForest(CString filename, bool replace = FALSE) {int i = 0;fstream readfile;ULONGLONG inSize = AcquireLength(filename);string strALL; //存儲從文件中讀到的字符char c, b;long pcount = 0;readfile.open(filename, ios::in);if (!readfile.is_open()) {cout << "Could not find the file\n";cout << "Program terminating\n";exit(EXIT_FAILURE);}//下面這個if語句是為了替換源文件中的一些字符串并將新內容從新輸入到一個文件中， 文件名為replace.txtif (replace){while (!readfile.eof()){if (readfile.good()){c = readfile.get();if (c == '6'){b = readfile.get();if (b == '8'){strALL += '#';}else{readfile.seekg(-1, ios::cur);strALL += c;}}else{strALL += c;}}}CString root = filename.Left(filename.ReverseFind('\\') + 1);CString file_replace = root + TEXT("replace.txt");ofstream repfile;repfile.open(file_replace, ios::out);repfile << strALL;repfile.close();}else{while (!readfile.eof()){if (readfile.good()){c = readfile.get(); //每個字符都讀，包括回車鍵‘\n’strALL += c;}}}readfile.close();pcount = strALL.length();snum = pcount - 1;//讀取文件中各個字符出現的頻次，單個字符的ASCII碼值不會超過127，所以使用一個大小為127的數組進行統計double *numbers = new double[127]();for (long i = 0; i < snum; i++){numbers[strALL[i]]++;}//構造霍夫曼樹的節點，并將字符出現的頻次信息寫入一個字典中待后續使用for (int j = 0; j < 127; j++){if (numbers[j] != 0){ht[count].data = (char) j;ht[count].weight = numbers[j];statistic[ht[count].data] = ht[count].weight;count++;}}delete[] numbers;return true; }/*********************************************************/ //函數名：CreateHuffManTree //返回值類型：void //參數：NULL //功能：利用森林構建哈夫曼樹 /********************************************************/ void HuffMan::CreateHuffManTree() {//左右孩子int lnode, rnode;//最小的兩個頻率值double min1, min2;//先將各個待編碼字符的左右孩子節點的值初始化為-1，作為后續判斷葉子節點的標志for (int i = 0; i < count; i++){ht[i].parent = ht[i].lchild = ht[i].rchild = -1;}//end for -> init result//根據單獨的節點構造出一顆完整的霍夫曼樹，整棵樹的節點數量為2 * count - 1for (int j = count; j < 2 * count - 1; j++){//每次重新搜尋最小權值的時候都將最小值和次小值初始化min1 = min2 = INF;lnode = rnode = -1;//遍歷尋找最小的兩個頻率值min1和min2for (int k = 0; k < j; k++){//逐一排查不存在雙親的節點if (ht[k].parent == -1){//每次尋找最小值節點時先除去含有雙親的節點if (ht[k].weight < min1)//小于最小{min2 = min1;//最小賦值給次小rnode = lnode;//同理下標min1 = ht[k].weight;//新的最小頻率值lnode = k;//其下標}//end if -> less//不小于最小，小于次小else if (ht[k].weight < min2){min2 = ht[k].weight;rnode = k;}//end else if -> only bigger than min1//no else }//end if -> search}ht[j].weight = ht[lnode].weight + ht[rnode].weight;//雙親結點權重ht[j].lchild = lnode;//雙親節點左孩子ht[j].rchild = rnode;ht[lnode].parent = j;//原最小頻率值所在節點的雙親節點賦值為當前節點jht[rnode].parent = j;ht[j].parent = -1;//雙親節點參與比較，賦值為-1} }/*********************************************************/ //函數名：CreateHuffCode //返回值類型：bool -> 判斷是否編碼成功，成功返回true,否則false //功能：根據構造好的霍夫曼樹生成哈夫曼編碼 /********************************************************/ bool HuffMan::CreateHuffCode() {int f, c;HuffCode hc;for (int i = 0; i < count; i++)//作為hcode下標{//自下往上搜尋，直至找到parent為-1的節點即是根節點hc.huffinfo = ht[i].data;c = i;//下標->左節點f = ht[i].parent;while (f != -1)//未到根節點{if (ht[f].lchild == c)//找到左節點{hc.code = _T("0") + hc.code;//左邊較小賦值為0}//end if -> left nodeelse{hc.code = _T("1") + hc.code;//右邊賦值為1}//end else -> right nodec = f;//替換為上一層節點f = ht[f].parent;//上一層的雙親節點}//end whilehcode[i] = hc;//賦值當前編碼hc.code = "";//清空code內容，進行下一次訪問}//end forreturn true; }/*********************************************************/ //函數名：compress //返回值類型：double //參數：需要壓縮文件的路徑，壓縮文件的輸出路徑 //返回值：壓縮比例 //功能：對源文件進行壓縮并輸出 /********************************************************/ double HuffMan::compress(CString filepath, CString outpath, CProgressCtrl &pro, CStatic &m_proview) {ifstream inFile;inFile.open(filepath);if (!inFile.is_open()) {cout << "Could not find the file\n";cout << "Program terminating\n";exit(EXIT_FAILURE);}ofstream outFile;outFile.open(outpath, ios::out | ios::binary);if (!outFile.is_open()) {cout << "Could not find the file\n";cout << "Program terminating\n";exit(EXIT_FAILURE);}//將字符的統計信息寫入壓縮文件，字符總數+各個字符出現的頻次，以供后續解壓使用outFile << snum;outFile << ":";for (auto iter : statistic){outFile << iter.first << "~" << iter.second << " ";}//統計信息結束標志outFile << "*@#";//開始寫入壓縮內容，每8位一個字節寫入文件，末尾不夠8位的話補0char c;int pos = 0;long number = 0;char value = 0;double progress = 0;CString code, str;double step = 100 / snum;inFile >> noskipws; //讀字符的時候不跳過換行符inFile >> c;number++;while (!inFile.eof()){if (inFile.good()){ for (int j = 0; j < count; j++){if (c == hcode[j].huffinfo){code = hcode[j].code; //找到字符對應的編碼break;}}for (int i = 0; i < code.GetLength(); i++){value = value << 1;if (code[i] == '1'){value |= 1; //這個應該好理解， 00000000 | 00000001 = 00000001，相當于最低位賦值1}if (++pos == 8){outFile << value; // 滿8位就將其寫入文件value = 0;pos = 0;}}inFile >> c;}}//末尾不夠8位補0if (pos){value = value << (8 - pos);outFile << value;}inFile.close();outFile.close();ULONGLONG originLen = AcquireLength(filepath);ULONGLONG compressLen = AcquireLength(outpath);double ratio = double(compressLen) * 100 / double(originLen);return ratio; }/*********************************************************///函數名：GetInfo//返回值類型：string//參數：需要獲取信息的文件的路徑//功能：輸出目標文件的大小，單位為字節//返回值：從編碼的二進制文件中得到源文件的字符統計信息和二進制流，并將二進制流轉換為字符串返回/********************************************************/ string HuffMan::GetInfo(CString inpath) {//先將待解壓文件中的字符統計信息和編碼內容讀取出來，分別用strline和codestream來表示char c, o, p, q;bitset<8> a;string strline, codestream; //strline存儲二進制文件中的字符及對應權值，codestream存儲01串fstream infile_b(inpath, ios::in | ios::binary);while (true) //從二進制文件中獲取字符及對應權值{if (infile_b.peek() == EOF)break;infile_b.read(&o, 1);if (o == '*'){infile_b.read(&p, 1);infile_b.read(&q, 1);if (p == '@'&&q == '#')break;else infile_b.seekg(-2, ios::cur);}strline += o;}while (true) //讀取字符轉化為01串{if (infile_b.peek() == EOF)break;infile_b.read(&c, 1);a = c; //字符賦值給bitset<8>可直接轉化為二進制codestream += a.to_string();}//根據字符統計信息構造霍夫曼樹，然后逐字符讀取編碼內容根據霍夫曼樹進行解碼char key;double b;long t;double snumcopy;string tmp, num;map<char, double> data_b;while (!strline.empty()) //讀取其中存儲的字符以及出現的頻次，由此生成哈弗曼樹{if (snum == 0){//提取文件中字符的總數t = strline.find(':');num = strline.substr(0, t);strline.erase(0, t + 1);snum = long(stoi(num, nullptr, 10));snumcopy = double(snum);}//提取各個字符的數量并將其存入字典key = strline.at(0);strline.erase(0, 2);t = strline.find(' ');tmp = strline.substr(0, t);strline.erase(0, t + 1);b = double(stoi(tmp, nullptr, 10));pair<char, double> item(key, b);data_b.insert(item);}map<char, double>::iterator it;count = 0;for (it = data_b.begin(); it != data_b.end(); it++){ht[count].data = (*it).first;ht[count].weight = (*it).second;count++;}CreateHuffManTree();//此處生成霍夫曼樹infile_b.close();return codestream; } /*********************************************************/ //函數名：DeCompress //返回值類型：void //參數：需要解壓縮文件的路徑 //功能：解壓縮文件并輸出，輸出文件為.txt文件 /********************************************************/ void HuffMan::DeCompress(CString outpath, string codestream, CProgressCtrl &pro, CStatic &m_proview, bool replace = FALSE) {fstream outfile_t(outpath, ios::out);CString str;long number = 0;double snumcopy;double progress = 0;snumcopy = double(snum);double step = 100 / snumcopy;//從根節點開始，根據壓縮內容，遇到0向左，遇到1向右，直至讀取到葉子節點，將葉子節點代表的字符寫入txt文件HNode root = ht[2 * count - 2];for (auto i : codestream) //用01串遍歷哈弗曼樹{if (i == '0') //遇0，走左root = ht[root.lchild];else //遇1，走右root = ht[root.rchild];if (root.lchild == -1 && root.rchild == -1) //遇葉子節點，提取字符并存儲{if (replace){number++;if (root.data == '#'){outfile_t << "68";}else{outfile_t << root.data;}root = ht[2 * count - 2];snum -= 1;}else{number++;outfile_t << root.data;/*pro.SetPos(number);progress += step;str.Format(L"%.2f", progress);str = str + TEXT("%");m_proview.SetWindowTextW(str);*/root = ht[2 * count - 2];snum -= 1;} }if (snum == 0){break;}}outfile_t.close(); }

關于使用C++遍歷某個文件夾下所有文件的方法

這里僅記錄關鍵代碼，下述代碼可以封裝進函數里，前提是文件夾中只含有文件而不含有子文件夾，包含子文件夾遍歷的代碼多加一層判斷寫個遞歸就好了

bool cmp(std::string const &arg_a, std::string const &arg_b) {return arg_a.size() < arg_b.size() || (arg_a.size() == arg_b.size() && arg_a < arg_b); }long hFile = 0; string path = "E:\\胡浩星\\工作項目\\電力數據壓縮\\霍夫曼編碼實驗\\[450, 500)"; vector<string> files; vector<string>::iterator it; struct _finddata_t fileinfo; string p; if ((hFile = _findfirst(p.assign(path).append("\\*").c_str(), &fileinfo)) != -1) {do {files.push_back(p.assign(path).append("\\").append(fileinfo.name));} while (_findnext(hFile, &fileinfo) == 0); //尋找下一個，成功返回0，否則-1_findclose(hFile); }files.erase(files.begin(), files.begin() + 2); //這里一般來講返回的vector中前兩個元素是文件夾當前目錄，與文件夾所在目錄，程序中用不到就剔除了 sort(files.begin(), files.end(), cmp); //很多需要根據文件名的數字順序進行排序，所以需要這一句，比如圖片如果是按照1， 2， 3， 4， 5.....這樣命名的話就需要這步操作

最終的效果圖：

第一次寫博客，如果中間有什么東西寫錯了誤導了大家請見諒，歡迎大家批評指正。

總結

以上是生活随笔為你收集整理的记录一个小型的数据压缩项目的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。