資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究霍夫曼編碼演算法
霍夫曼編碼是一種無損資料壓縮演算法。這種演算法將可變長度程式碼分配給輸入的不同字元。程式碼長度與字元的使用頻率相關。使用最頻繁的字元具有最短程式碼，而最不頻繁的字元具有最長程式碼。
主要有兩個部分。第一個部分是建立霍夫曼樹，另一個部分是遍歷樹以查詢程式碼。
例如，考慮一些字串“YYYZXXYYX”，字元 Y 的頻率大於 X，而字元 Z 的頻率最低。因此，Y 的程式碼長度小於 X，而 X 的程式碼長度小於 Z。
根據每個字元的頻率為其分配程式碼的複雜度為 O(n log n)
輸入和輸出
Input: A string with different characters, say “ACCEBFFFFAAXXBLKE” Output: Code for different characters: Data: K, Frequency: 1, Code: 0000 Data: L, Frequency: 1, Code: 0001 Data: E, Frequency: 2, Code: 001 Data: F, Frequency: 4, Code: 01 Data: B, Frequency: 2, Code: 100 Data: C, Frequency: 2, Code: 101 Data: X, Frequency: 2, Code: 110 Data: A, Frequency: 3, Code: 111
演算法
huffmanCoding(string)
輸入：不同字元的字串。
輸出：每個單個字元的程式碼。
Begin define a node with character, frequency, left and right child of the node for Huffman tree. create a list ‘freq’ to store frequency of each character, initially, all are 0 for each character c in the string do increase the frequency for character ch in freq list. done for all type of character ch do if the frequency of ch is non zero then add ch and its frequency as a node of priority queue Q. done while Q is not empty do remove item from Q and assign it to left child of node remove item from Q and assign to the right child of node traverse the node to find the assigned code done End
traverseNode(n: node, code)
輸入：霍夫曼樹的節點 n 及之前呼叫分配的程式碼
輸出：與每個字元分配的程式碼
if a left child of node n ≠φ then traverseNode(leftChild(n), code+’0’) //traverse through the left child traverseNode(rightChild(n), code+’1’) //traverse through the right child else display the character and data of current node.
例子
#include #include#include using namespace std; struct node { int freq; char data; const node *child0, *child1; node(char d, int f = -1) { //assign values in the node data = d; freq = f; child0 = NULL; child1 = NULL; } node(const node *c0, const node *c1) { data = 0; freq = c0->freq + c1->freq; child0=c0; child1=c1; } bool operator<( const node &a ) const { //< operator performs to find priority in queue return freq >a.freq; } void traverse(string code = "")const { if(child0!=NULL) { child0->traverse(code+'0'); //add 0 with the code as left child child1->traverse(code+'1'); //add 1 with the code as right child }else { cout << "Data: " << data<< ", Frequency: "< qu; int frequency[256]; for(int i = 0; i<256; i++) frequency[i] = 0; //clear all frequency for(int i = 0; i1) { node *c0 = new node(qu.top()); //get left child and remove from queue qu.pop(); node *c1 = new node(qu.top()); //get right child and remove from queue qu.pop(); qu.push(node(c0, c1)); //add freq of two child and add again in the queue } cout << "The Huffman Code: "<
輸出
The Huffman Code: Data: K, Frequency: 1, Code: 0000 Data: L, Frequency: 1, Code: 0001 Data: E, Frequency: 2, Code: 001 Data: F, Frequency: 4, Code: 01 Data: B, Frequency: 2, Code: 100 Data: C, Frequency: 2, Code: 101 Data: X, Frequency: 2, Code: 110 Data: A, Frequency: 3, Code: 111
更新時間： 2022年12月23日
32K+ 人氣
廣告