霍夫曼編碼 · Programiz 中文系列教程

# 霍夫曼編碼 > 原文： [https://www.programiz.com/dsa/huffman-coding](https://www.programiz.com/dsa/huffman-coding) #### 在本教程中，您將學習霍夫曼編碼的工作原理。此外，您還將找到使用 C，C++ ，Java 和 Python 進行霍夫曼編碼的工作示例。霍夫曼編碼是一種壓縮數據以減小其大小而又不丟失任何細節的技術。它最早由 David Huffman 開發。霍夫曼編碼通常可用于壓縮其中經常出現字符的數據。 * * * ## 霍夫曼編碼的工作原理？假設下面的字符串要通過網絡發送。 ![string](https://img.kancloud.cn/6b/44/6b443cd8ae004d0e6a9d58ac3d057cc7_936x186.png "initial string") 初始字符串每個字符占用 8 位。上面的字符串中總共有 15 個字符。因此，總共需要`8 * 15 = 120`位來發送此字符串。使用霍夫曼編碼技術，我們可以將字符串壓縮為較小的大小。霍夫曼編碼首先使用字符的頻率創建一棵樹，然后為每個字符生成代碼。一旦數據被編碼，就必須被解碼。解碼是使用同一棵樹完成的。霍夫曼編碼使用**前綴代碼**的概念，可以防止解碼過程中出現歧義。與字符關聯的代碼不應出現在任何其他代碼的前綴中。上面創建的樹有助于維護屬性。霍夫曼編碼是通過以下步驟完成的。 1. 計算字符串中每個字符的頻率。 ![frequency of string](https://img.kancloud.cn/9d/3b/9d3b97baef6a355a0e760165b8128845_622x244.png "frequency of string") 字符串的頻率 2. 按頻率升序對字符進行排序。這些存儲在優先隊列`Q`中。 ![huffman coding](https://img.kancloud.cn/85/7a/857a4ffd8ecdf3e4d40d9bcc92a9cfae_622x244.png "characters sorted in according to the frequency") 根據頻率排序的字符 3. 使每個唯一字符作為葉節點。 4. 創建一個空節點`z`。將最小頻率分配給`z`的左子代，并將第二個最小頻率分配給`z`的右代。將`z`的值設置為上述兩個最小頻率的總和。 ![huffman coding](https://img.kancloud.cn/d0/34/d0348e2c81e7e37bd0b8fa5869b91754_492x548.png "getting the sum of the least numbers") 取得最小數的總和 5. 從`Q`中刪除這兩個最小頻率，并將總和添加到頻率列表中（*表示上圖中的內部節點）。 6. 將節點`z`插入樹中。 7. 對所有字符重復步驟 3 到 5。 ![huffman coding](https://img.kancloud.cn/69/4b/694ba16e6568c9ffc96f152b1241bfd1_560x676.png "getting the sum of the least numbers") 對所有字符重復步驟 3 至 5。 ? ![huffman coding](https://img.kancloud.cn/26/50/26503aa75cbfeac8c3ebd6a249a24671_560x804.png "getting the sum of the least numbers") 對所有字符重復步驟 3 至 5。 8. 對于每個非葉節點，將 0 分配給左邊，將 1 分配給右邊。 ![huffman coding](https://img.kancloud.cn/5a/6b/5a6b4792503baec5b63b430163518ca1_560x608.png "getting the sum of the least numbers") 將 0 分配給左邊，將 1 分配給右邊為了通過網絡發送上面的字符串，我們必須發送樹以及上面的壓縮代碼。總大小如下表所示。 | 字符 | 頻率 | 編碼 | 大小 | | --- | --- | --- | --- | | `a` | 5 | 11 | `5 * 2 = 10` | | `b` | 1 | 100 | `1 * 3 = 3` | | `c` | 6 | 0 | `6 * 1 = 6` | | `d` | 3 | 101 | `3 * 3 = 9` | | `4 * 8 = 32`位 | 15 位 | ? | 28 位 | 如果不進行編碼，則字符串的總大小為 120 位。編碼后，大小減小為`32 + 15 + 28 = 75`。 * * * ## 解碼代碼為了解碼代碼，我們可以獲取代碼并遍歷樹以找到字符。假設要解碼 101，我們可以如下圖所示從根開始遍歷。 ![huffman coding](https://img.kancloud.cn/35/e0/35e081a072c7a78c1cae75382f47d3c9_560x608.png "decoding") 解碼 * * * ## 霍夫曼編碼算法 ``` create a priority queue Q consisting of each unique character. sort then in ascending order of their frequencies. for all the unique characters: create a newNode extract minimum value from Q and assign it to leftChild of newNode extract minimum value from Q and assign it to rightChild of newNode calculate the sum of these two minimum values and assign it to the value of newNode insert this newNode into the tree return rootNode ``` * * * ## Python，Java 和 C/C++ 示例 ```py # Huffman Coding in python string = 'BCAADDDCCACACAC' # Creating tree nodes class NodeTree(object): def __init__(self, left=None, right=None): self.left = left self.right = right def children(self): return (self.left, self.right) def nodes(self): return (self.left, self.right) def __str__(self): return '%s_%s' % (self.left, self.right) # Main function implementing huffman coding def huffman_code_tree(node, left=True, binString=''): if type(node) is str: return {node: binString} (l, r) = node.children() d = dict() d.update(huffman_code_tree(l, True, binString + '0')) d.update(huffman_code_tree(r, False, binString + '1')) return d # Calculating frequency freq = {} for c in string: if c in freq: freq[c] += 1 else: freq[c] = 1 freq = sorted(freq.items(), key=lambda x: x[1], reverse=True) nodes = freq while len(nodes) > 1: (key1, c1) = nodes[-1] (key2, c2) = nodes[-2] nodes = nodes[:-2] node = NodeTree(key1, key2) nodes.append((node, c1 + c2)) nodes = sorted(nodes, key=lambda x: x[1], reverse=True) huffmanCode = huffman_code_tree(nodes[0][0]) print(' Char | Huffman code ') print('----------------------') for (char, frequency) in freq: print(' %-4r |%12s' % (char, huffmanCode[char])) ``` ```java // Huffman Coding in Java import java.util.PriorityQueue; import java.util.Comparator; class HuffmanNode { int item; char c; HuffmanNode left; HuffmanNode right; } // For comparing the nodes class ImplementComparator implements Comparator<HuffmanNode> { public int compare(HuffmanNode x, HuffmanNode y) { return x.item - y.item; } } // IMplementing the huffman algorithm public class Huffman { public static void printCode(HuffmanNode root, String s) { if (root.left == null && root.right == null && Character.isLetter(root.c)) { System.out.println(root.c + " | " + s); return; } printCode(root.left, s + "0"); printCode(root.right, s + "1"); } public static void main(String[] args) { int n = 4; char[] charArray = { 'A', 'B', 'C', 'D' }; int[] charfreq = { 5, 1, 6, 3 }; PriorityQueue<HuffmanNode> q = new PriorityQueue<HuffmanNode>(n, new ImplementComparator()); for (int i = 0; i < n; i++) { HuffmanNode hn = new HuffmanNode(); hn.c = charArray[i]; hn.item = charfreq[i]; hn.left = null; hn.right = null; q.add(hn); } HuffmanNode root = null; while (q.size() > 1) { HuffmanNode x = q.peek(); q.poll(); HuffmanNode y = q.peek(); q.poll(); HuffmanNode f = new HuffmanNode(); f.item = x.item + y.item; f.c = '-'; f.left = x; f.right = y; root = f; q.add(f); } System.out.println(" Char | Huffman code "); System.out.println("--------------------"); printCode(root, ""); } } ``` ```c // Huffman Coding in C #include <stdio.h> #include <stdlib.h> #define MAX_TREE_HT 50 struct MinHNode { char item; unsigned freq; struct MinHNode *left, *right; }; struct MinHeap { unsigned size; unsigned capacity; struct MinHNode **array; }; // Create nodes struct MinHNode *newNode(char item, unsigned freq) { struct MinHNode *temp = (struct MinHNode *)malloc(sizeof(struct MinHNode)); temp->left = temp->right = NULL; temp->item = item; temp->freq = freq; return temp; } // Create min heap struct MinHeap *createMinH(unsigned capacity) { struct MinHeap *minHeap = (struct MinHeap *)malloc(sizeof(struct MinHeap)); minHeap->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHNode **)malloc(minHeap->capacity * sizeof(struct MinHNode *)); return minHeap; } // Function to swap void swapMinHNode(struct MinHNode **a, struct MinHNode **b) { struct MinHNode *t = *a; *a = *b; *b = t; } // Heapify void minHeapify(struct MinHeap *minHeap, int idx) { int smallest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2; if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq) smallest = left; if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq) smallest = right; if (smallest != idx) { swapMinHNode(&minHeap->array[smallest], &minHeap->array[idx]); minHeapify(minHeap, smallest); } } // Check if size if 1 int checkSizeOne(struct MinHeap *minHeap) { return (minHeap->size == 1); } // Extract min struct MinHNode *extractMin(struct MinHeap *minHeap) { struct MinHNode *temp = minHeap->array[0]; minHeap->array[0] = minHeap->array[minHeap->size - 1]; --minHeap->size; minHeapify(minHeap, 0); return temp; } // Insertion function void insertMinHeap(struct MinHeap *minHeap, struct MinHNode *minHeapNode) { ++minHeap->size; int i = minHeap->size - 1; while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) { minHeap->array[i] = minHeap->array[(i - 1) / 2]; i = (i - 1) / 2; } minHeap->array[i] = minHeapNode; } void buildMinHeap(struct MinHeap *minHeap) { int n = minHeap->size - 1; int i; for (i = (n - 1) / 2; i >= 0; --i) minHeapify(minHeap, i); } int isLeaf(struct MinHNode *root) { return !(root->left) && !(root->right); } struct MinHeap *createAndBuildMinHeap(char item[], int freq[], int size) { struct MinHeap *minHeap = createMinH(size); for (int i = 0; i < size; ++i) minHeap->array[i] = newNode(item[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } struct MinHNode *buildHuffmanTree(char item[], int freq[], int size) { struct MinHNode *left, *right, *top; struct MinHeap *minHeap = createAndBuildMinHeap(item, freq, size); while (!checkSizeOne(minHeap)) { left = extractMin(minHeap); right = extractMin(minHeap); top = newNode('$', left->freq + right->freq); top->left = left; top->right = right; insertMinHeap(minHeap, top); } return extractMin(minHeap); } void printHCodes(struct MinHNode *root, int arr[], int top) { if (root->left) { arr[top] = 0; printHCodes(root->left, arr, top + 1); } if (root->right) { arr[top] = 1; printHCodes(root->right, arr, top + 1); } if (isLeaf(root)) { printf(" %c | ", root->item); printArray(arr, top); } } // Wrapper function void HuffmanCodes(char item[], int freq[], int size) { struct MinHNode *root = buildHuffmanTree(item, freq, size); int arr[MAX_TREE_HT], top = 0; printHCodes(root, arr, top); } // Print the array void printArray(int arr[], int n) { int i; for (i = 0; i < n; ++i) printf("%d", arr[i]); printf("\n"); } int main() { char arr[] = {'A', 'B', 'C', 'D'}; int freq[] = {5, 1, 6, 3}; int size = sizeof(arr) / sizeof(arr[0]); printf(" Char | Huffman code "); printf("\n--------------------\n"); HuffmanCodes(arr, freq, size); } ``` ```cpp // Huffman Coding in C++ #include <iostream> using namespace std; #define MAX_TREE_HT 50 struct MinHNode { unsigned freq; char item; struct MinHNode *left, *right; }; struct MinH { unsigned size; unsigned capacity; struct MinHNode **array; }; // Creating Huffman tree node struct MinHNode *newNode(char item, unsigned freq) { struct MinHNode *temp = (struct MinHNode *)malloc(sizeof(struct MinHNode)); temp->left = temp->right = NULL; temp->item = item; temp->freq = freq; return temp; } // Create min heap using given capacity struct MinH *createMinH(unsigned capacity) { struct MinH *minHeap = (struct MinH *)malloc(sizeof(struct MinH)); minHeap->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHNode **)malloc(minHeap->capacity * sizeof(struct MinHNode *)); return minHeap; } // Swap function void swapMinHNode(struct MinHNode **a, struct MinHNode **b) { struct MinHNode *t = *a; *a = *b; *b = t; } // Heapify void minHeapify(struct MinH *minHeap, int idx) { int smallest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2; if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq) smallest = left; if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq) smallest = right; if (smallest != idx) { swapMinHNode(&minHeap->array[smallest], &minHeap->array[idx]); minHeapify(minHeap, smallest); } } // Check if size if 1 int checkSizeOne(struct MinH *minHeap) { return (minHeap->size == 1); } // Extract the min struct MinHNode *extractMin(struct MinH *minHeap) { struct MinHNode *temp = minHeap->array[0]; minHeap->array[0] = minHeap->array[minHeap->size - 1]; --minHeap->size; minHeapify(minHeap, 0); return temp; } // Insertion void insertMinHeap(struct MinH *minHeap, struct MinHNode *minHeapNode) { ++minHeap->size; int i = minHeap->size - 1; while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) { minHeap->array[i] = minHeap->array[(i - 1) / 2]; i = (i - 1) / 2; } minHeap->array[i] = minHeapNode; } // BUild min heap void buildMinHeap(struct MinH *minHeap) { int n = minHeap->size - 1; int i; for (i = (n - 1) / 2; i >= 0; --i) minHeapify(minHeap, i); } int isLeaf(struct MinHNode *root) { return !(root->left) && !(root->right); } struct MinH *createAndBuildMinHeap(char item[], int freq[], int size) { struct MinH *minHeap = createMinH(size); for (int i = 0; i < size; ++i) minHeap->array[i] = newNode(item[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } struct MinHNode *buildHfTree(char item[], int freq[], int size) { struct MinHNode *left, *right, *top; struct MinH *minHeap = createAndBuildMinHeap(item, freq, size); while (!checkSizeOne(minHeap)) { left = extractMin(minHeap); right = extractMin(minHeap); top = newNode('$', left->freq + right->freq); top->left = left; top->right = right; insertMinHeap(minHeap, top); } return extractMin(minHeap); } void printHCodes(struct MinHNode *root, int arr[], int top) { if (root->left) { arr[top] = 0; printHCodes(root->left, arr, top + 1); } if (root->right) { arr[top] = 1; printHCodes(root->right, arr, top + 1); } if (isLeaf(root)) { cout << root->item << " | "; printArray(arr, top); } } // Wrapper function void HuffmanCodes(char item[], int freq[], int size) { struct MinHNode *root = buildHfTree(item, freq, size); int arr[MAX_TREE_HT], top = 0; printHCodes(root, arr, top); } // Print the array void printArray(int arr[], int n) { int i; for (i = 0; i < n; ++i) cout << arr[i]; cout << "\n"; } int main() { char arr[] = {'A', 'B', 'C', 'D'}; int freq[] = {5, 1, 6, 3}; int size = sizeof(arr) / sizeof(arr[0]); cout << "Char | Huffman code "; cout << "\n----------------------\n"; HuffmanCodes(arr, freq, size); } ``` * * * ## 霍夫曼編碼復雜度基于每個唯一字符的頻率進行編碼的時間復雜度為`O(nlog n)`。從優先隊列中提取最小頻率發生`2*(n-1)`次，其復雜度為`O(log n)`。因此，總體復雜度為`O(nlog n)`。 * * * ## 霍夫曼編碼應用 * 霍夫曼編碼用于常規壓縮格式，例如 GZIP，BZIP2，PKZIP 等。 * 用于文本和傳真傳輸。