Напередодні старту курсу підготували вам переклад ще одного корисного матеріалу.
Кодування Хаффмана – це алгоритм стиснення даних, який формулює основну ідею стиснення файлів. У цій статті ми говоритимемо про кодування фіксованої та змінної довжини, унікально декодовані коди, префіксні правила та побудову дерева Хаффмана.
Ми знаємо, що кожен символ зберігається у вигляді послідовності з 0 та 1 і займає 8 біт. Це називається кодуванням фіксованої довжини, оскільки кожен символ використовує однакову фіксовану кількість бітів для зберігання.
Допустимо, дано текст. Як ми можемо зменшити кількість місця, необхідного для збереження одного символу?
Основна ідея полягає у кодуванні змінної довжини. Ми можемо використовувати той факт, що деякі символи в тексті зустрічаються частіше, ніж інші (), щоб розробити алгоритм, який представлятиме ту ж послідовність символів меншою кількістю бітів. При кодуванні змінної довжини ми присвоюємо символам змінну кількість бітів залежно від частоти їхньої появи у цьому тексті. Зрештою, деякі символи можуть займати всього 1 біт, а інші 2 біти, 3 або більше. Проблема з кодуванням змінної довжини полягає лише в подальшому декодуванні послідовності.
Як, знаючи послідовність бітів, декодувати її однозначно?
Розглянемо рядок «aabacdab». У ній 8 символів і при кодуванні фіксованої довжини для її зберігання знадобиться 64 біти. Зауважимо, що частота символів "a", "b", "c" и «D» дорівнює 4, 2, 1, 1 відповідно. Давайте спробуємо уявити «aabacdab» меншою кількістю бітів, використовуючи той факт, що "до" зустрічається частіше, ніж "В", а "В" зустрічається частіше, ніж "с" и «D». Почнемо ми з того, що закодуємо "до" за допомогою одного біта, що дорівнює 0, "В" ми надамо двобітний код 11, а за допомогою трьох бітів 100 і 011 закодуємо "с" и «D».
У результаті в нас вийде:
a
0
b
11
c
100
d
011
Таким чином рядок «aabacdab» ми закодуємо як 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
З використанням такого кодування, рядок «aabacdab» буде закодована як 00100100011010 (0|0|10|0|100|011|0|10). А ось 00100100011010 ми вже зможемо однозначно декодувати і повернутися до нашого вихідного рядка «aabacdab».
Кодування Хаффмана
Тепер, коли ми розібралися з кодуванням змінної довжини та префіксним правилом, поговоримо про кодування Хаффмана.
Метод ґрунтується на створенні бінарних дерев. У ньому вузол може бути кінцевим, або внутрішнім. Спочатку всі вузли вважаються листям (кінцевим), яке представляє сам символ і його вагу (тобто частоту появи). Внутрішні вузли містять вагу символу і посилаються на два вузли-спадкоємці. За загальною угодою, біт «0» представляє прямування по лівій гілки, а «1» - По правій. У повному дереві N листя та N-1 внутрішніх вузлів. Рекомендується, щоб при побудові дерева Хаффмана відкидалися символи, що не використовуються для отримання кодів оптимальної довжини.
Ми будемо використовувати чергу з пріоритетами для побудови дерева Хаффмана, де вузлу з найменшою частотою буде надано найвищий пріоритет. Нижче описані кроки побудови:
- Створіть вузол-аркуш для кожного символу та додайте їх у чергу з пріоритетами.
- Поки що в черзі більше одного аркуша робимо таке:
- Видаліть два вузли з найвищим пріоритетом (з найнижчою частотою) із черги;
- Створіть новий внутрішній вузол, де ці два вузли будуть спадкоємцями, а частота появи дорівнюватиме сумі частот цих двох вузлів.
- Додайте новий вузол у чергу пріоритетів.
- Єдиний вузол, що залишився, буде кореневим, на цьому побудова дерева закінчиться.
Уявімо, що у нас є певний текст, який складається лише із символів "a", "b", "c", "d" и "і", А частоти їх появи дорівнюють 15, 7, 6, 6 і 5 відповідно. Нижче наведено ілюстрації, що відображають кроки алгоритму.
Шлях від кореня до будь-якого кінцевого вузла зберігатиме оптимальний префіксний код (також відомий як код Хаффмана), що відповідає символу, пов'язаному з цим кінцевим вузлом.
Дерево Хаффмана
Нижче ви знайдете реалізацію алгоритму стиснення Хаффмана мовами 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%. У програмі на С++ вище ми використовуємо клас string для зберігання закодованого рядка, щоб зробити читану програму.
Оскільки ефективні структури даних черги пріоритетів вимагають на вставку O(log(N)) часу, а в повному бінарному дереві з N листям присутній 2N-1 вузлів, і дерево Хаффмана - це повне бінарне дерево, алгоритм працює за O(Nlog(N)) часу, де N - кількість символів.
Джерела:
Джерело: habr.com