课程开始前 为您准备了另一份有用材料的翻译。
霍夫曼编码是一种数据压缩算法，制定了文件压缩的基本思想。 在本文中，我们将讨论固定和可变长度编码、唯一可解码代码、前缀规则以及构建霍夫曼树。
我们知道每个字符都存储为 0 和 1 的序列，占用 8 位。 这称为固定长度编码，因为每个字符使用相同的固定位数来存储。
假设我们收到了文本。 我们如何减少存储单个字符所需的空间量？
主要思想是可变长度编码。 我们可以利用这样一个事实，即文本中的某些字符比其他字符出现得更频繁（) 来开发一种算法，该算法将以更少的位数表示相同的字符序列。 在可变长度编码中，我们为字符分配可变位数，具体取决于它们在给定文本中出现的频率。 最终，一些字符可能只占用 1 位，而其他字符可能占用 2 位、3 位或更多位。 可变长度编码的问题只是序列的后续解码。
如何在知道位序列的情况下明确地对其进行解码？
考虑这条线 “阿巴达”. 它有8个字符，编码固定长度时，需要64位来存储。 请注意，符号频率 "a", "b", "c" и “丁” 分别等于 4、2、1、1。 让我们试着想象一下 “阿巴达” 更少的位，使用这样的事实 “至” 发生频率高于 “乙”和 “乙” 发生频率高于 “C” и “丁”. 让我们从编码开始 “至” 一位等于 0， “乙” 我们将分配一个两位代码 11，并使用三个位 100 和 011 我们将编码 “C” и “丁”.
结果，我们将得到：
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" и “丁” 满足前缀规则的代码。
a
0
b
10
c
110
d
111
使用这种编码，字符串 “阿巴达” 将被编码为 00100100011010 (0|0|10|0|100|011|0|10)。 但 00100100011010 我们已经能够明确解码并返回到我们的原始字符串 “阿巴达”.
霍夫曼编码
现在我们已经处理了可变长度编码和前缀规则，让我们来谈谈霍夫曼编码。
该方法基于二叉树的创建。 其中，节点可以是最终的或内部的。 最初，所有节点都被视为叶子（终端），它代表符号本身及其权重（即出现频率）。 内部节点包含字符的权重并指代两个后代节点。 普遍认为，位 «0 表示跟随左分支，并且 «1 - 在右侧。 在满树 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 - 人物。
来源：
来源： habr.com