Напярэдадні старту курса падрыхтавалі для вас перавод яшчэ аднаго карыснага матэрыялу.
Кадаваньне Хафмана - гэта алгарытм сціску дадзеных, які фармулюе асноўную ідэю сціску файлаў. У гэтым артыкуле мы будзем казаць аб кадаванні фіксаванай і зменнай даўжыні, унікальна дэкадуемых кодах, прэфіксных правілах і пабудове дрэва Хаффмана.
Мы ведаем, што кожны сімвал захоўваецца ў выглядзе паслядоўнасці з 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