C 語言資料壓縮實作：簡單字串壓縮與哈夫曼編碼

一、簡單字串壓縮（RLE 變體）

壓縮規則

1. 僅壓縮連續重複字符，如 "abcbc" 無連續重複則保持原樣。
2. 壓縮格式為 「次數+字符」，次數為 1 時省略。例："xxxyyyyyyz" → "3x6yz"。

核心演算法邏輯

• 雙指標 i（掃描）、j（當前字符起始）配合計數器 count。
• 連續相同則 count++，遇不同字符時寫入結果：count>1 先轉數字字串再加字符，count<=1 直接寫字符。
• 使用 itoa 將整數轉字串，strcpy 拼接至結果緩衝區。

關鍵代碼片段

do {
    if (i < length && str[i++] == str[j]) count++;
    if (str[i] != str[j]) {
        if (count <= 1) res[k++] = str[j];
        else {
            char temp[10] = {0};
            itoa(count, temp, 10);
            strcpy(res + k, temp);
            k += strlen(temp);
            res[k++] = str[j];
        }
        j = i;
        count = 0;
    }
} while (i < length);

二、哈夫曼編碼（Huffman Coding）

核心原理

哈夫曼樹為帶權路徑長度最小的二叉樹。編碼策略：高頻字符用短編碼，低頻字符用長編碼，達到無損壓縮。例如英文中 e 可能 1 bit，z 需 25 bits，遠優於固定 8 bits/字節。

實作流程

1. 量化：將輸入資料（如 DCT 係數）量化為整數陣列。
2. 統計權重：掃描量化值，建立 Node[]、Weight[] 陣列，記錄唯一值及其出現次數。
3. 建樹：create_HuffmanTree 反覆選取兩最小權重節點合併，構建哈夫曼樹。
4. 生成編碼：HuffmanCoding 從葉節點向根回溯，生成各字符編碼串。
5. 計算壓縮比：累加 頻率 × 編碼長度 得總位元數，與原始位元數比較。

關鍵資料結構

typedef struct HfTreeNode {
    int weight;      // 權重
    int parent;      // 父節點索引
    int lchild, rchild; // 左右子節點
} HfTreeNode;

typedef struct {
    char code[10];   // 編碼串
    int start;       // 編碼起始位置
} HCodeType;

總結

簡單 RLE 適合長連續重複場景；哈夫曼編碼為通用無損壓縮基石，廣泛應用於 JPEG、ZIP、MP3 等格式。理解其樹構建與編碼回溯過程，有助於深入掌握資訊論與壓縮技術核心。