哈夫曼編碼譯碼功能的簡單實現

許子明

摘 要：哈夫曼樹是一種典型的數據結構，由哈夫曼樹生成的哈夫曼編碼具有不等長的特點，常被用于數據通信的二進制編碼中，可以提高存儲和處理文本的效率。本文提出一種建立簡單的哈夫曼編碼、譯碼系統的方法。在建立完成的哈夫曼樹的基礎上，生成哈夫曼編碼，并對字符串進行編碼，對已有的數字編碼進行譯碼。

關鍵詞：哈夫曼樹；哈夫曼編碼；編碼；譯碼

1 哈夫曼樹和哈夫曼編碼簡介

給定n個權值作為n個葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹（Huffman Tree）。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。二叉樹的路徑長度是指由根結點到所有葉子結點的路徑長度之和。如果二叉樹中的葉子結點都有一定的權值，則從根結點到每一個葉子結點的路徑長度與該葉子結點權值的乘積之和稱為二叉樹的帶權路徑長度。

對于字符串序列，如果對每個字符在計算機內采用固定長度的二進制位來表示，例如標準ASCII碼用7位二進制碼表示一個字符，這種編碼形式稱為固定長度編碼。若對于不同的字符采用不同長度的二進制位來表示，那么這種方式稱為可變長度編碼。可變長度編碼的特點是對出現頻率不同的字符采用不同長度的編碼。對頻率高的字符采用短編碼，對頻率低的字符采用長編碼的方式。這樣我們就可以減少數據的存儲空間，提高存儲和傳輸的效率。而通過哈夫曼樹形成的哈夫曼編碼是一種有用的可變長度編碼。

例：對字符集S={A，B，E，C，D，F}，權值W={3，5，9，11，12，13}建立哈夫曼樹。

對應的哈夫曼編碼為：A：1100，B：1101，C：00，D：01，E：111，F：10。

2 生成哈夫曼編碼原理

首先建立結構體BTNode用來表示哈夫曼樹中每一個結點。在結構體BTNode內，建立數組code用于存儲該結點的哈夫曼編碼；建立變量level記錄該結點所在樹的層次，初始化為0；建立字符變量cha記錄該結點所表示的字符；并實例化建立結構體BTNode *lchild，*rchild表示該節點的左右孩子結點。在生成哈夫曼編碼的函數中，利于隊列作為輔助。首先建立類型為結構體BTNode的隊列，然后使得樹的根root結點進入隊列。當隊列不為空時，將隊頭元素賦給同類型變量p。然后先判斷p的左孩子是否為空，若不為空，則使得p的level變量加1賦給其左孩子結點中的level變量。然后利用for循環和level變量的值進行遍歷，將p中的code數組記錄的數據依次賦給p的左孩子結點的code數組，繼承父節點的編碼，最后在編碼后加上數字0，生成該孩子結點的哈夫曼編碼。然后再將p的左孩子節點加入到隊尾。然后類似地，再對p的右孩子結點進行判斷與編碼，并加入到隊尾。最后再刪除隊頭元素，然后再把新的隊頭元素賦給p，再進行循環操作直到隊列為空。

3 編碼原理

在哈夫曼編碼成功后，當輸入由字符集中字符組成的任意字符串時，可以利用已生成的哈夫曼編碼進行編碼。在編碼的函數Find中有字符類參數ch傳入進行比較的字符，還有結構體參數BTNode t用來指向樹中的某個結點。開始時，將第一個字符與根結點作為參數傳入Find函數中，然后在Find函數中將結點中存儲的與字符串的字符進行比較，若相同則記錄下該結點，并將返回，得到該字符的編碼。若不相同，則使用Find函數遞歸遍歷根節點的左右孩子節點，不斷遞歸直到找到需要的字符為止。將所有字符的編碼依次存儲在隊列中，則可以得到該字符串的編碼。

4 譯碼原理

當輸入數字編碼時，可以利用已經建成的哈夫曼樹進行譯碼。將數字編碼存入隊列中，作為參數傳入譯碼函數中。建立結構體BTNode的指針p，初始化指向根節點root。當p指向的結點不為空，且該結點的左右孩子均不為空時，取出數字編碼隊列中隊頭的元素進行比較，若為0，則p指向p的左孩子結點；若為1，則p指向p的右孩子結點。然后刪除隊頭元素，再進行新的隊頭元素的比較，直到p指向哈夫曼樹的葉子節點為止，然后返回該葉子節點中存儲的字符。或者當數字編碼遍歷完之后，結束譯碼函數。最后將譯碼得到的字符串輸出即可。