哈夫曼樹

1、定義和基本概念

哈夫曼樹：最優二叉樹，帶權路徑長度最短的樹

基本概念：

• 路徑：從樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑
• 路徑長度：路徑上的分支數目
• 樹的路徑長度：根結點到每一個結點的路徑長度之和
• 權：樹中結點賦予一個含有某種意義的數值
• 帶權路徑長度：從根結點到該結點之間的路徑長度與該結點的權的乘積

• 樹的帶權路徑長度(WPL)：樹中所有葉子結點的帶權路徑長度之和

  故哈夫曼樹是WPL最短的樹，也稱最優樹

注：

• 滿二叉樹不一定為最優二叉樹
• 哈夫曼樹中權越大的葉子離根越近
• 具有相同帶權結點的哈夫曼樹不唯一

2、哈夫曼樹的構造

貪心算法：構造哈夫曼樹時首先選擇權小的葉子結點

構造過程：

1. 根據n個給定的權值{w1, w2, w3, ... , wn}構成n棵二叉樹的森林F={T1, T2, ..., Tn}，其中Ti隻有一個帶權為wi的根結點（即構造一個全是根的森林）
2. 在F中選取兩顆最小的權的樹作為左右子樹，進而構造出一顆新的二叉樹，且設定新的二叉樹的根結點的權值為其左右子樹上根結點的權值的和（即選用兩個權小的樹造一個新的二叉樹）
3. 在F上删除原來的兩顆樹，并将新的二叉樹加入至F中（即删除原樹添新樹）
4. 重複2、3步驟，直至森林中僅剩餘一顆樹，此樹即為哈夫曼樹

算法實作：

1. 存儲結構

由于哈夫曼樹為二叉樹，故可采取順序存儲結構存儲或鍊式存儲結構存儲二叉樹，本例采用順序存儲

一維結構體數組元素的成員有權值、雙親、左孩子、右孩子

typedef struct HTNode
{
    int weight;
    int parent, lchild, rchild;
}HTNode, * HufmanTree;           

由于建構哈夫曼樹時要生成n-1個新結點，故數組的大小為2n-1，但為了存儲操作友善，不使用0下标，數組大小為2n

1. 算法操作

1. 初始化哈夫曼樹

根據權重的數組構造各個獨立的結點形成森林，其中結點的雙親和孩子均為0

1. 建構哈夫曼樹

找到所有雙親域為空的結點中的最小和次小權重，修改其雙親域，并為新結點添加左孩子和右孩子，其權重等于其孩子的權重之和，依次循環查找建立，直到數組已滿

typedef struct HTNode
{
    int weight;
    int parent, lchild, rchild;
}HTNode, * HuffmanTree;

// 查找雙親域為0的權最小的結點
static void Select(HuffmanTree hf, int i, int* s1, int* s2)
{
    int min1 = 1000;
    int min2 = 1000;
    for (int j = 1; j <= i - 1; j++)
    {
        if (!hf[j].parent && min1 > hf[j].weight)
        {
            min1 = hf[j].weight;
            *s1 = j;
        }
    }
    for (int j = 1; j <= i - 1; j++)
    {
        if (!hf[j].parent && j != *s1 && min2 > hf[j].weight)
        {
            min2 = hf[j].weight;
            *s2 = j;
        }
    }
}

HuffmanTree CreateHuffmanTree(int* weightArr, int len)
{
    // 初始化哈夫曼樹
    if (len <= 1) return NULL;
    HuffmanTree ht = (HuffmanTree)malloc(sizeof(HTNode) * len * 2);
    if (ht)
    {
        for (int i = 1; i < len * 2; i++)
        {
            ht[i].parent = 0;
            ht[i].lchild = 0;
            ht[i].rchild = 0;
        }
        for (int i = 1; i <= len; i++)
        {
            ht[i].weight = weightArr[i - 1];
        }

        // 建立哈夫曼樹
        int s1, s2;
        for (int i = len + 1; i < 2 * len; i++)
        {
            Select(ht, i, &s1, &s2);
            ht[s1].parent = i;
            ht[s2].parent = i;
            ht[i].lchild = s1;
            ht[i].rchild = s2;
            ht[i].weight = ht[s1].weight + ht[s2].weight;
        }
    }

    return ht;
}

static void Print(HuffmanTree t, int m)
{
    for (int i = 1; i <= m; i++)
    {
        printf("%d %d %d %d %d\n", i, t[i].weight, t[i].parent, t[i].lchild, t[i].rchild);
    }
}

int main()
{
    int arr[] = { 7, 19, 2, 6, 8 };
    int len = sizeof(arr) / sizeof(arr[0]);
    HuffmanTree ht = CreateHuffmanTree(arr, len);
    Print(ht, len * 2 - 1);

    return 0;
}           

3、哈夫曼編碼

不定長編碼：出現次數較多的字元編以較短的編碼

字首編碼：如果在一個編碼方案中，任一個編碼都不是任何編碼的字首，則稱編碼是字首編碼

哈夫曼編碼：

1. 統計字元集中每個字元在電文中出現的平均機率（機率越大，編碼越短）
2. 利用哈夫曼樹的特點，将機率值視為權值建構哈夫曼樹，即機率越大路徑越短

3. 在哈夫曼樹的每個分支上标0或1：

   ​ 結點的左分支為0，右分支為1，把從根到葉子的路徑連接配接，作為該葉子代表的字元的編碼

哈夫曼編碼的性質：

1. 哈夫曼編碼是字首編碼

哈夫曼編碼是葉子路徑上的編碼序列，其路徑必定唯一，沒有任何一個葉子路徑為其它路徑的字首

1. 哈夫曼編碼是最優編碼

1. 定義哈夫曼編碼的結構

typedef char** HCode;           

1. 實作哈夫曼編碼

1. 根據權值建構哈夫曼樹（具體建構方法見哈夫曼樹的建構）
2. 建立臨時動态字元數組以存放周遊過程中的字元值
3. 依次周遊每個葉子結點，周遊的結果儲存至臨時數組中，當一個葉子結點周遊結束則将字元串複制到對應的哈夫曼編碼中，直到所有葉子結點周遊完畢

HCode CreateHuffmanCode(HuffmanTree ht, int n)
{
    if (n <= 1) return NULL;
    // 建立哈夫曼編碼數組
    HCode hc = (char**)malloc(sizeof(char*) * (n + 1));
    if (hc)
    {
        // 建立臨時字元數組
        char* cd = (char*)malloc(sizeof(char) * n);
        if (cd)
        {
            // 初始化臨時數組
            int start = 0;  
            int c = 0;
            int f = 0;
            cd[n - 1] = '\0';
            // 依次周遊每個葉子結點
            for (int i = 1; i <= n; i++)
            {
                start = n - 1;
                c = i;
                f = ht[i].parent;
                // 周遊葉子結點到根的路徑
                while (f)
                {
                    start--;
                    cd[start] = ht[f].lchild == c ? '0' : '1';
                    c = f;
                    f = ht[f].parent;
                }
                // 拷貝臨時數組至哈夫曼編碼
                hc[i] = (char*)malloc(sizeof(char) * (n - start));
                if (hc[i])
                {
                    strcpy(hc[i], cd + start);
                }
                else
                {
                    free(cd);
                    free(hc);
                    return NULL;
                }
            }
            // 釋放記憶體，傳回結果
            free(cd);
            return hc;
        }
        else
        {
            return NULL;
        }
    }
    else
    {
        return NULL;
    }
}