課程開始前 為您準備了另一份有用材料的翻譯。
霍夫曼編碼是一種數據壓縮算法，制定了文件壓縮的基本思想。 在本文中，我們將討論固定和可變長度編碼、唯一可解碼代碼、前綴規則以及構建霍夫曼樹。
我們知道每個字符都存儲為 0 和 1 的序列，佔用 8 位。 這稱為固定長度編碼，因為每個字符使用相同的固定位數來存儲。
假設我們收到了文本。 我們如何減少存儲單個字符所需的空間量？
主要思想是可變長度編碼。 我們可以利用這樣一個事實，即文本中的某些字符比其他字符出現得更頻繁（) 來開發一種算法，該算法將以更少的位數表示相同的字符序列。 在可變長度編碼中，我們為字符分配可變位數，具體取決於它們在給定文本中出現的頻率。 最終，一些字符可能只佔用 1 位，而其他字符可能佔用 2 位、3 位或更多位。 可變長度編碼的問題只是序列的後續解碼。
如何在知道位序列的情況下明確地對其進行解碼？
考慮這條線 “阿巴達”. 它有8個字符，編碼固定長度時，需要64位來存儲。 請注意，符號頻率 "a", "b", "c" и “D” 分別等於 4、2、1、1。 讓我們試著想像一下 “阿巴達” 更少的位，使用這樣的事實 “至” 發生頻率高於 “乙”和 “乙” 發生頻率高於 “C” и “D”. 讓我們從編碼開始 “至” 一位等於 0， “乙” 我們將分配一個兩位代碼 11，並使用三個位 100 和 011 我們將編碼 “C” и “D”.
結果，我們將得到：
a
0
b
11
c
100
d
011
所以這條線 “阿巴達” 我們將編碼為 00110100011011 (0|0|11|0|100|011|0|11)使用上面的代碼。 然而，主要問題在於解碼。 當我們嘗試解碼字符串時 00110100011011，我們得到一個模棱兩可的結果，因為它可以表示為：
0|011|0|100|011|0|11 adacdab
0|0|11|0|100|0|11|011 aabacabd
0|011|0|100|0|11|0|11 adacabab
...
等等
為了避免這種歧義，我們必須確保我們的編碼滿足這樣的概念 前綴規則，這反過來意味著代碼只能以一種獨特的方式解碼。 前綴規則確保沒有代碼是另一個代碼的前綴。 通過代碼，我們指的是用於表示特定字符的位。 在上面的例子中 0 是前綴 011，這違反了前綴規則。 所以，如果我們的代碼滿足前綴規則，那麼我們就可以唯一解碼（反之亦然）。
讓我們回顧一下上面的例子。 這次我們將為符號賦值 "a", "b", "c" и “D” 滿足前綴規則的代碼。
a
0
b
10
c
110
d
111
使用這種編碼，字符串 “阿巴達” 將被編碼為 00100100011010 (0|0|10|0|100|011|0|10)。 但 00100100011010 我們已經能夠明確解碼並返回到我們的原始字符串 “阿巴達”.
霍夫曼編碼
現在我們已經處理了可變長度編碼和前綴規則，讓我們來談談霍夫曼編碼。
該方法基於二叉樹的創建。 其中，節點可以是最終的或內部的。 最初，所有節點都被視為葉子（終端），它代表符號本身及其權重（即出現頻率）。 內部節點包含字符的權重並指代兩個後代節點。 普遍認為，位 «0» 表示跟隨左分支，並且 «1» - 在右側。 在滿樹 N 葉子和 N-1 內部節點。 建議在構造哈夫曼樹時，丟棄不用的符號，以獲得最優的長度碼。
我們將使用優先級隊列來構建霍夫曼樹，其中頻率最低的節點將獲得最高優先級。 施工步驟說明如下：
- 為每個字符創建一個葉節點，並將它們添加到優先級隊列中。
- 當隊列中有多張工作表時，請執行以下操作：
- 從隊列中移除優先級最高（頻率最低）的兩個節點；
- 創建一個新的內部節點，這兩個節點將成為子節點，出現頻率將等於這兩個節點的頻率之和。
- 將新節點添加到優先級隊列。
- 唯一剩下的節點將是根，這將完成樹的構建。
想像一下，我們有一些僅由字符組成的文本 “A B C D” и “和”, 它們的出現頻率分別為 15、7、6、6 和 5。 下面是反映算法步驟的插圖。
從根到任何端節點的路徑將存儲與該端節點關聯的字符對應的最佳前綴代碼（也稱為霍夫曼代碼）。
霍夫曼樹
您將在下面找到 Huffman 壓縮算法在 C++ 和 Java 中的實現：
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;
// A Tree node
struct Node
{
char ch;
int freq;
Node *left, *right;
};
// Function to allocate a new tree node
Node* getNode(char ch, int freq, Node* left, Node* right)
{
Node* node = new Node();
node->ch = ch;
node->freq = freq;
node->left = left;
node->right = right;
return node;
}
// Comparison object to be used to order the heap
struct comp
{
bool operator()(Node* l, Node* r)
{
// highest priority item has lowest frequency
return l->freq > r->freq;
}
};
// traverse the Huffman Tree and store Huffman Codes
// in a map.
void encode(Node* root, string str,
unordered_map<char, string> &huffmanCode)
{
if (root == nullptr)
return;
// found a leaf node
if (!root->left && !root->right) {
huffmanCode[root->ch] = str;
}
encode(root->left, str + "0", huffmanCode);
encode(root->right, str + "1", huffmanCode);
}
// traverse the Huffman Tree and decode the encoded string
void decode(Node* root, int &index, string str)
{
if (root == nullptr) {
return;
}
// found a leaf node
if (!root->left && !root->right)
{
cout << root->ch;
return;
}
index++;
if (str[index] =='0')
decode(root->left, index, str);
else
decode(root->right, index, str);
}
// Builds Huffman Tree and decode given input text
void buildHuffmanTree(string text)
{
// count frequency of appearance of each character
// and store it in a map
unordered_map<char, int> freq;
for (char ch: text) {
freq[ch]++;
}
// Create a priority queue to store live nodes of
// Huffman tree;
priority_queue<Node*, vector<Node*>, comp> pq;
// Create a leaf node for each character and add it
// to the priority queue.
for (auto pair: freq) {
pq.push(getNode(pair.first, pair.second, nullptr, nullptr));
}
// do till there is more than one node in the queue
while (pq.size() != 1)
{
// Remove the two nodes of highest priority
// (lowest frequency) from the queue
Node *left = pq.top(); pq.pop();
Node *right = pq.top(); pq.pop();
// Create a new internal node with these two nodes
// as children and with frequency equal to the sum
// of the two nodes' frequencies. Add the new node
// to the priority queue.
int sum = left->freq + right->freq;
pq.push(getNode('', sum, left, right));
}
// root stores pointer to root of Huffman Tree
Node* root = pq.top();
// traverse the Huffman Tree and store Huffman Codes
// in a map. Also prints them
unordered_map<char, string> huffmanCode;
encode(root, "", huffmanCode);
cout << "Huffman Codes are :n" << 'n';
for (auto pair: huffmanCode) {
cout << pair.first << " " << pair.second << 'n';
}
cout << "nOriginal string was :n" << text << 'n';
// print encoded string
string str = "";
for (char ch: text) {
str += huffmanCode[ch];
}
cout << "nEncoded string is :n" << str << 'n';
// traverse the Huffman Tree again and this time
// decode the encoded string
int index = -1;
cout << "nDecoded string is: n";
while (index < (int)str.size() - 2) {
decode(root, index, str);
}
}
// Huffman coding algorithm
int main()
{
string text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
return 0;
}import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
// A Tree node
class Node
{
char ch;
int freq;
Node left = null, right = null;
Node(char ch, int freq)
{
this.ch = ch;
this.freq = freq;
}
public Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
};
class Huffman
{
// traverse the Huffman Tree and store Huffman Codes
// in a map.
public static void encode(Node root, String str,
Map<Character, String> huffmanCode)
{
if (root == null)
return;
// found a leaf node
if (root.left == null && root.right == null) {
huffmanCode.put(root.ch, str);
}
encode(root.left, str + "0", huffmanCode);
encode(root.right, str + "1", huffmanCode);
}
// traverse the Huffman Tree and decode the encoded string
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// found a leaf node
if (root.left == null && root.right == null)
{
System.out.print(root.ch);
return index;
}
index++;
if (sb.charAt(index) == '0')
index = decode(root.left, index, sb);
else
index = decode(root.right, index, sb);
return index;
}
// Builds Huffman Tree and huffmanCode and decode given input text
public static void buildHuffmanTree(String text)
{
// count frequency of appearance of each character
// and store it in a map
Map<Character, Integer> freq = new HashMap<>();
for (int i = 0 ; i < text.length(); i++) {
if (!freq.containsKey(text.charAt(i))) {
freq.put(text.charAt(i), 0);
}
freq.put(text.charAt(i), freq.get(text.charAt(i)) + 1);
}
// Create a priority queue to store live nodes of Huffman tree
// Notice that highest priority item has lowest frequency
PriorityQueue<Node> pq = new PriorityQueue<>(
(l, r) -> l.freq - r.freq);
// Create a leaf node for each character and add it
// to the priority queue.
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
// do till there is more than one node in the queue
while (pq.size() != 1)
{
// Remove the two nodes of highest priority
// (lowest frequency) from the queue
Node left = pq.poll();
Node right = pq.poll();
// Create a new internal node with these two nodes as children
// and with frequency equal to the sum of the two nodes
// frequencies. Add the new node to the priority queue.
int sum = left.freq + right.freq;
pq.add(new Node('', sum, left, right));
}
// root stores pointer to root of Huffman Tree
Node root = pq.peek();
// traverse the Huffman tree and store the Huffman codes in a map
Map<Character, String> huffmanCode = new HashMap<>();
encode(root, "", huffmanCode);
// print the Huffman codes
System.out.println("Huffman Codes are :n");
for (Map.Entry<Character, String> entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("nOriginal string was :n" + text);
// print encoded string
StringBuilder sb = new StringBuilder();
for (int i = 0 ; i < text.length(); i++) {
sb.append(huffmanCode.get(text.charAt(i)));
}
System.out.println("nEncoded string is :n" + sb);
// traverse the Huffman Tree again and this time
// decode the encoded string
int index = -1;
System.out.println("nDecoded string is: n");
while (index < sb.length() - 2) {
index = decode(root, index, sb);
}
}
public static void main(String[] args)
{
String text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
}
}注： 輸入字符串使用的內存是 47 * 8 = 376 位，編碼後的字符串只有 194 位，即數據壓縮了大約 48%。 在上面的 C++ 程序中，我們使用 string 類來存儲編碼後的字符串，以提高程序的可讀性。
因為高效的優先級隊列數據結構需要每次插入 O（日誌（N）） 時間，但在一個完整的二叉樹中 N 留下禮物 2N-1 節點，哈夫曼樹是完全二叉樹，則算法運行在 O(Nlog(N)) 時間，地點 N - 人物。
來源：
來源： www.habr.com