項目概覽

利用 最小堆 構建 霍夫曼樹，結合文件流操作與位元級讀寫，實現通用文件的無損壓縮與解壓。核心模塊包括：存儲結構設計、壓縮流程、解壓流程、編碼生成、霍夫曼樹構建、最小堆實現、文件讀寫操作。

核心原理

壓縮流程

1. 讀取文件，統計每個字節（0-255）出現頻率
2. 以頻率為權值構建最小堆，進而構建霍夫曼樹
3. 遍歷樹生成字符編碼（左 0 右 1），存入存儲結構
4. 二次掃描文件，按編碼將位流打包寫入 .compress 文件
5. 將字符與頻率表寫入 .config 配置文件，供解壓重建樹使用

解壓流程

1. 讀取 .config 重建字符頻率表
2. 構建霍夫曼樹
3. 讀取 .compress 位流，從根節點按位遍歷樹，到達葉子節點輸出原始字符
4. 根據根節點權值（總字符數）判斷解壓結束

關鍵數據結構

using LongType = long long;

struct FileInfo {
    unsigned char ch;      // 字符
    LongType count;        // 頻率
    std::string code;      // 霍夫曼編碼

    FileInfo(LongType c = 0) : ch(0), count(c), code() {}
    FileInfo operator+(const FileInfo& rhs) const {
        return FileInfo(count + rhs.count);
    }
    bool operator!=(const FileInfo& rhs) const { return count != rhs.count; }
    bool operator<(const FileInfo& rhs) const { return count < rhs.count; }
};

最小堆實現

模板類 Heap<T, Compare> 支持自定義比較器，提供 Push、Pop、Top、Empty 等操作，構建採用 _AdjustDown 自下而上堆化，時間複雜度 O(n)。

template <class T, class Compare = Less<T>>
class Heap {
    std::vector<T> _array;
    void _AdjustDown(int root);
    void _AdjustUp(int child);
public:
    Heap() = default;
    Heap(const T* arr, size_t n);
    Heap(std::vector<T>& vec);
    void Push(const T& x);
    void Pop();
    const T& Top() const;
    bool Empty() const;
    size_t Size() const { return _array.size(); }
};

霍夫曼樹構建

HuffManTree<T> 內部節點結構 HuffManNode 含左右孩子、父節點指針與權值。構建算法：

1. 將非無效權值節點入最小堆
2. 反覆取出兩個最小節點，創建父節點（權值為和），重新入堆
3. 直到堆剩一個節點，即為根節點

template <class T>
class HuffManTree {
    using Node = HuffManNode<T>;
    struct Compare {
        bool operator()(Node* l, Node* r) const { return l->_weight < r->_weight; }
    };
    Node* _root = nullptr;

    void _CreatHuffmanTree(const T* arr, size_t n, const T& invalid);
    bool _Destroy(Node*& root);
public:
    HuffManTree() = default;
    ~HuffManTree() { _Destroy(_root); }
    void CreatHuffmanTree(const T* arr, size_t n, const T& invalid);
    Node* GetRoot() const { return _root; }
};

文件壓縮核心類

class FileCompress {
    FileInfo _info[256];  // 字符統計表

    // 遞歸生成編碼
    void huffmancode(HuffManNode<FileInfo>* root, std::string& code);

    // 讀取配置文件行
    static bool readline(FILE* fp, std::string& line);

public:
    FileCompress();
    void filecompress(const char* filename);   // 壓縮入口
    void uncompressfile(const char* filename); // 解壓入口
};

壓縮關鍵邏輯

void FileCompress::filecompress(const char* filename) {
    // 1. 統計頻率
    FILE* in = fopen(filename, "rb");
    int ch = fgetc(in);
    while (ch != EOF) {
        _info[(unsigned char)ch].count++;
        ch = fgetc(in);
    }

    // 2. 構建樹 & 生成編碼
    HuffManTree<FileInfo> tree;
    FileInfo invalid(0);
    tree.CreatHuffmanTree(_info, 256, invalid);
    std::string code;
    huffmancode(tree.GetRoot(), code);

    // 3. 寫入壓縮文件（位打包）
    std::string out_name = std::string(filename) + ".compress";
    FILE* out = fopen(out_name.c_str(), "wb");
    rewind(in);
    ch = fgetc(in);
    unsigned char byte = 0;
    int bit_cnt = 0;
    while (ch != EOF) {
        const std::string& c = _info[(unsigned char)ch].code;
        for (char b : c) {
            byte = (byte << 1) | (b == '1');
            if (++bit_cnt == 8) {
                fputc(byte, out);
                byte = 0; bit_cnt = 0;
            }
        }
        ch = fgetc(in);
    }
    if (bit_cnt) {
        byte <<= (8 - bit_cnt);
        fputc(byte, out);
    }

    // 4. 寫入配置文件
    std::string cfg_name = std::string(filename) + ".config";
    FILE* cfg = fopen(cfg_name.c_str(), "w");
    char buf[32];
    for (int i = 0; i < 256; ++i) {
        if (_info[i] != invalid) {
            fprintf(cfg, "%c,%lld\n", _info[i].ch, _info[i].count);
        }
    }
    fclose(in); fclose(out); fclose(cfg);
}

解壓關鍵邏輯

void FileCompress::uncompressfile(const char* filename) {
    // 1. 讀取配置重建頻率表
    std::string cfg_name = std::string(filename) + ".config";
    FILE* cfg = fopen(cfg_name.c_str(), "r");
    std::string line;
    while (readline(cfg, line)) {
        if (!line.empty()) {
            unsigned char ch = line[0];
            _info[ch].count = atoll(line.substr(2).c_str());
        }
    }
    fclose(cfg);

    // 2. 重建霍夫曼樹
    HuffManTree<FileInfo> tree;
    FileInfo invalid(0);
    tree.CreatHuffmanTree(_info, 256, invalid);
    auto* root = tree.GetRoot();

    // 3. 解壓位流
    std::string cmp_name = std::string(filename) + ".compress";
    std::string out_name = std::string(filename) + ".uncompress";
    FILE* in = fopen(cmp_name.c_str(), "rb");
    FILE* out = fopen(out_name.c_str(), "wb");

    auto* cur = root;
    int bit_pos = 8;
    int ch = fgetc(in);
    LongType total = root->_weight.count;

    while (total--) {
        if (bit_pos == 0) { bit_pos = 8; ch = fgetc(in); }
        --bit_pos;
        cur = (ch & (1 << bit_pos)) ? cur->_right : cur->_left;
        if (!cur->_left && !cur->_right) {
            fputc(cur->_weight.ch, out);
            cur = root;
        }
    }
    fclose(in); fclose(out);
}