C++ 哈夫曼編碼

1.哈夫曼編碼的結點類：

struct HuffmanNode {
    int weight; // 權重，出現的次數或者頻率
    char ch; // 存儲符号
    string code; // 存儲該符号對應的編碼
    int leftChild, rightChild, parent; // 左、右孩子，父結點
};

2.思路：

（1）統計輸入的字元串中不同字元的出現的次數，作為權值，然後存到哈夫曼編碼數組中：

// 2.統計輸入的字元串的各個字元出現的個數
    memset(arr, 0, sizeof(arr)); // 清零
    for(i = 0; i < len; i++) // 統計次數
        arr[str[i]]++; // str[i] -> 轉成對應的ASCII碼，如'0'->48
    leafSize = 0; // 出現不同字元的個數
    for(i = 0; i < 256; i++) {
        if(arr[i] != 0) { // 有出現的字元
            // cout << "字元:" << (char)i << "次數為：" << arr[i] << endl;
            HuffmanTree[leafSize].ch = (char)i; // 将數字轉成對應的字元
            HuffmanTree[leafSize].weight = arr[i]; // 權重
            leafSize++;
        }
    }

（2）然後，根據Huffman樹的原理：權值越大的離根越近，權值越小的離根越遠，建立Huffman樹；

// 3.選取兩個較小值合并
    int first, second; // 兩個較小的結點
    for(i = leafSize; i < (2*leafSize-1); i++) { // 做leafSize-1趟
        getMin(first, second, i); // 選取兩個較小的元素
        Merge(first,second,i); // 合并
    }

（3）編碼：接着，從葉子結點出發，如果該結點為父結點的左孩子，則在編碼追加“0”；

如果為其右孩子，則編碼追加“1”，

注意：上面得到的編碼要倒過來存放。因為字元對應的編碼是從根到葉子結點所得到的編碼，而上面剛好相反。

// 編碼:利用哈夫曼編碼原理對資料進行加密
void HuffmanCode::Encode() {
    string code; // 存儲符号的不定長二進制編碼
    int i, j, k, parent;
    
    for(i = 0; i < leafSize; i++) { // 從葉子結點出發
        j = i;
        code = ""; // 初始化為空
        while(HuffmanTree[j].parent != -1) { // 往上找到根結點
            parent = HuffmanTree[j].parent; // 父結點
            if(j == HuffmanTree[parent].leftChild) // 如果是左孩子，則記為0
                code += "0";
            else // 右孩子，記為1
                code += "1";
            j = parent; // 上移到父結點
        }
        // 編碼要倒過來：因為是從葉子往上走到根，而編碼是要從根走到葉子結點
        for(k = (int)code.size()-1; k >= 0 ; k--)
            HuffmanTree[i].code += code[k]; // 儲存編碼
        cout << "字元：" << HuffmanTree[i].ch << "的編碼為：" << HuffmanTree[i].code << " ";
    }
}

（4）解碼：每一次加一個編碼數字，然後從哈夫曼編碼數組中查找。如果查找到，就轉成對應的字元，接着解碼剩下的編碼；

如果沒查找到，就再添加一個編碼數字，然後從哈夫曼編碼數組中查找…

如果最後周遊完所有編碼，但是還是沒有把所有編碼解碼成功，說明編碼中有誤，輸出“解碼出錯！”。

// 解碼
void HuffmanCode::Decode(string str) {
    string decode, temp; // decode儲存整個解碼, temp儲存每一個解碼
    int len = (int)str.size(); // 編碼的長度
    int i, j;
    
    decode = temp = ""; // 初始化為空
    for(i = 0; i < len; i++) {
        temp += str[i]; // 加一個編碼
        for(j = 0; j < leafSize; j++) {
            if(HuffmanTree[j].code == temp) { // 在葉子結點中找到對應的編碼
                decode += HuffmanTree[j].ch; // 轉成對應的字元
                temp = "";
                break;
            }
        }
        if(i == len-1 && j == leafSize) { // 周遊完都沒找到對應的編碼
            cout << "解碼出錯！" << endl;
            return;
        }
    }
    cout << decode << endl;
}

3.實作程式：

(1)HuffmanCode.h

#ifndef HuffmanCode_h
#define HuffmanCode_h
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

struct HuffmanNode {
    int weight; // 權重，出現的次數或者頻率
    char ch; // 存儲符号
    string code; // 存儲該符号對應的編碼
    int leftChild, rightChild, parent; // 左、右孩子，父結點
};

class HuffmanCode {
public:
    HuffmanCode(string str); // 構造函數
    ~HuffmanCode(); // 析構函數
    void getMin(int &first, int &second, int parent); // 選取兩個較小的元素
    void Merge(int first, int second, int parent); // 合并
    void Encode(); // 編碼:利用哈夫曼編碼原理對資料進行加密
    void Decode(string str); // 解碼
private:
    HuffmanNode *HuffmanTree; // 數組
    int leafSize; // 統計不同字元的個數
};

// 構造函數
HuffmanCode::HuffmanCode(string str) {
    int len = (int)str.size(); // 字元串的長度
    int arr[256], i; // 存儲字元串各個字元的個數
    HuffmanTree = new HuffmanNode[256]; // 動态配置設定空間
    
    // 1.初始化HuffmanTree數組
    for(i = 0; i < (2 * len - 1); i++) { // 葉子結點為len,則樹最多有2*len-1個結點
        HuffmanTree[i].leftChild = HuffmanTree[i].rightChild = HuffmanTree[i].parent = -1;
        HuffmanTree[i].code = "";
    }
    // 2.統計輸入的字元串的各個字元出現的個數
    memset(arr, 0, sizeof(arr)); // 清零
    for(i = 0; i < len; i++) // 統計次數
        arr[str[i]]++; // str[i] -> 轉成對應的ASCII碼，如'0'->48
    leafSize = 0; // 出現不同字元的個數
    for(i = 0; i < 256; i++) {
        if(arr[i] != 0) { // 有出現的字元
            // cout << "字元:" << (char)i << "次數為：" << arr[i] << endl;
            HuffmanTree[leafSize].ch = (char)i; // 将數字轉成對應的字元
            HuffmanTree[leafSize].weight = arr[i]; // 權重
            leafSize++;
        }
    }
    
    // 3.選取兩個較小值合并
    int first, second; // 兩個較小的結點
    for(i = leafSize; i < (2*leafSize-1); i++) { // 做leafSize-1趟
        getMin(first, second, i); // 選取兩個較小的元素
        Merge(first,second,i); // 合并
    }
}

// 析構函數
HuffmanCode::~HuffmanCode() {
    delete []HuffmanTree;
}

// 選取權值兩個較小的元素
void HuffmanCode::getMin(int &first, int &second, int parent) {
    double weight = 0;
    int i;
    
    // 找權重最小元素
    for(i = 0; i < parent; i++) {
        if(HuffmanTree[i].parent != -1) // 已選過，直接跳過
            continue;
        if(weight == 0) { // 第一次找到沒選過的結點
            weight = HuffmanTree[i].weight;
            first = i;
        }
        else if(HuffmanTree[i].weight < weight) { // 權值更小
            weight = HuffmanTree[i].weight;
            first = i;
        }
    }
    // 找權重次小元素
    weight = 0;
    for(i = 0; i < parent; i++) {
        if(HuffmanTree[i].parent != -1 || i == first) // 已選過，直接跳過
            continue;
        if(weight == 0) { // 第一次找到沒選過的結點
            weight = HuffmanTree[i].weight;
            second = i;
        }
        else if(HuffmanTree[i].weight < weight) { // 權值更小
            weight = HuffmanTree[i].weight;
            second = i;
        }
    }
}

// 合并
void HuffmanCode::Merge(int first, int second, int parent) {
    HuffmanTree[first].parent = HuffmanTree[second].parent = parent; // 父結點
    HuffmanTree[parent].leftChild = first; // 左孩子
    HuffmanTree[parent].rightChild = second; // 右孩子
    HuffmanTree[parent].weight = HuffmanTree[first].weight + HuffmanTree[second].weight; // 權值
}

// 編碼:利用哈夫曼編碼原理對資料進行加密
void HuffmanCode::Encode() {
    string code; // 存儲符号的不定長二進制編碼
    int i, j, k, parent;
    
    for(i = 0; i < leafSize; i++) { // 從葉子結點出發
        j = i;
        code = ""; // 初始化為空
        while(HuffmanTree[j].parent != -1) { // 往上找到根結點
            parent = HuffmanTree[j].parent; // 父結點
            if(j == HuffmanTree[parent].leftChild) // 如果是左孩子，則記為0
                code += "0";
            else // 右孩子，記為1
                code += "1";
            j = parent; // 上移到父結點
        }
        // 編碼要倒過來：因為是從葉子往上走到根，而編碼是要從根走到葉子結點
        for(k = (int)code.size()-1; k >= 0 ; k--)
            HuffmanTree[i].code += code[k]; // 儲存編碼
        cout << "字元：" << HuffmanTree[i].ch << "的編碼為：" << HuffmanTree[i].code << " ";
    }
}

// 解碼
void HuffmanCode::Decode(string str) {
    string decode, temp; // decode儲存整個解碼, temp儲存每一個解碼
    int len = (int)str.size(); // 編碼的長度
    int i, j;
    
    decode = temp = ""; // 初始化為空
    for(i = 0; i < len; i++) {
        temp += str[i]; // 加一個編碼
        for(j = 0; j < leafSize; j++) {
            if(HuffmanTree[j].code == temp) { // 在葉子結點中找到對應的編碼
                decode += HuffmanTree[j].ch; // 轉成對應的字元
                temp = "";
                break;
            }
        }
        if(i == len-1 && j == leafSize) { // 周遊完都沒找到對應的編碼
            cout << "解碼出錯！" << endl;
            return;
        }
    }
    cout << decode << endl;
}
#endif /* HuffmanCode_h */

(2)main.cpp

#include "HuffmanCode.h"

int main(int argc, const char * argv[]) {
    string str;
    
    cout << "請輸入字元串進行編碼：" << endl;
    cin >> str; // 輸入要加密的字元串
    HuffmanCode st(str); // 對象
    cout << "對字元串編碼情況如下：" << endl;
    st.Encode(); // 編碼
    cout << endl;
    cout << "請輸入要解碼的二進制編碼:" << endl;
    cin >> str;
    cout << "解碼如下：" << endl;
    st.Decode(str); // 解碼
    return 0;
}

測試資料：Myfatherwasaself-taughtmandolinplayer.Hewasoneofthebeststringinstrumentplayersinourtown.

10000010111100011110010101000011001-> Myfather

測試結果：

C++ 哈夫曼編碼

C++ 哈夫曼編碼

繼續閱讀

2021-08-13c++——類之操作符重載

[轉]ISUP信令的IAM消息詳細内容

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

Linux裝置模型（中）之上層容器