Prije početka tečaja pripremio za vas prijevod drugog korisnog materijala.
Huffmanovo kodiranje je algoritam za kompresiju podataka koji formulira osnovnu ideju kompresije datoteke. U ovom ćemo članku govoriti o kodiranju fiksne i promjenjive duljine, kodovima koji se mogu jedinstveno dekodirati, pravilima prefiksa i izgradnji Huffmanovog stabla.
Znamo da je svaki znak pohranjen kao niz 0 i 1 i zauzima 8 bita. To se zove kodiranje fiksne duljine jer svaki znak koristi isti fiksni broj bitova za pohranu.
Recimo da smo dobili tekst. Kako možemo smanjiti količinu prostora potrebnog za pohranu jednog znaka?
Glavna ideja je kodiranje promjenjive duljine. Možemo se poslužiti činjenicom da se neki znakovi u tekstu pojavljuju češće od drugih () za razvoj algoritma koji će prikazati isti niz znakova u manje bitova. Kod kodiranja promjenjive duljine, znakovima dodjeljujemo promjenjivi broj bitova, ovisno o tome koliko se često pojavljuju u određenom tekstu. Na kraju, neki znakovi mogu uzeti samo 1 bit, dok drugi mogu uzeti 2 bita, 3 ili više. Problem s kodiranjem promjenjive duljine je samo naknadno dekodiranje niza.
Kako ga, znajući slijed bitova, nedvosmisleno dekodirati?
Razmotrite liniju "abacdab". Ima 8 znakova, a kod kodiranja fiksne duljine trebat će mu 64 bita za pohranu. Imajte na umu da frekvencija simbola "a", "b", "c" и "D" jednako je 4, 2, 1, 1 redom. Pokušajmo zamisliti "abacdab" manje bitova, koristeći činjenicu da "do" javlja se češće od "B"I "B" javlja se češće od "c" и "D". Počnimo s kodiranjem "do" s jednim bitom jednakim 0, "B" dodijelit ćemo dvobitni kod 11, a pomoću tri bita 100 i 011 kodirati ćemo "c" и "D".
Kao rezultat, dobit ćemo:
a
0
b
11
c
100
d
011
Dakle linija "abacdab" kodirat ćemo kao 00110100011011 (0|0|11|0|100|011|0|11)koristeći gore navedene kodove. Međutim, glavni problem bit će u dekodiranju. Kada pokušamo dekodirati niz 00110100011011, dobit ćemo dvosmislen rezultat, budući da se može predstaviti kao:
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
...
itd.
Kako bismo izbjegli ovu dvosmislenost, moramo osigurati da naše kodiranje zadovoljava koncept kao što je pravilo prefiksa, što zauzvrat implicira da se kodovi mogu dekodirati samo na jedan jedinstven način. Pravilo prefiksa osigurava da nijedan kod nije prefiks drugog. Pod kodom mislimo na bitove koji se koriste za predstavljanje određenog znaka. U gornjem primjeru 0 je prefiks 011, što krši pravilo prefiksa. Dakle, ako naši kodovi zadovoljavaju pravilo prefiksa, tada možemo jedinstveno dekodirati (i obrnuto).
Pogledajmo ponovno gornji primjer. Ovaj put ćemo dodijeliti simbole "a", "b", "c" и "D" kodovi koji zadovoljavaju pravilo prefiksa.
a
0
b
10
c
110
d
111
S ovim kodiranjem, niz "abacdab" bit će kodiran kao 00100100011010 (0|0|10|0|100|011|0|10). Ali 00100100011010 već ćemo moći nedvosmisleno dekodirati i vratiti se na naš izvorni niz "abacdab".
Huffmanovo kodiranje
Sada kada smo se pozabavili kodiranjem promjenjive duljine i pravilom prefiksa, razgovarajmo o Huffmanovu kodiranju.
Metoda se temelji na stvaranju binarnih stabala. U njemu čvor može biti konačni ili unutarnji. U početku se svi čvorovi smatraju listovima (terminalima), koji predstavljaju sam simbol i njegovu težinu (odnosno učestalost pojavljivanja). Unutarnji čvorovi sadrže težinu znaka i odnose se na dva čvora potomka. Po općem dogovoru, bit "0" predstavlja praćenje lijeve grane, i "1" - na desno. u punom stablu N lišće i N-1 unutarnji čvorovi. Preporuča se da se kod konstruiranja Huffmanovog stabla neiskorišteni simboli odbace kako bi se dobili kodovi optimalne duljine.
Koristit ćemo red prioriteta za izgradnju Huffmanovog stabla, gdje će čvor s najnižom frekvencijom dobiti najveći prioritet. Koraci izgradnje opisani su u nastavku:
- Stvorite lisni čvor za svaki znak i dodajte ih u red prioriteta.
- Dok postoji više od jednog lista u redu čekanja, učinite sljedeće:
- Uklonite dva čvora s najvišim prioritetom (najnižom frekvencijom) iz reda čekanja;
- Napravite novi interni čvor, gdje će ova dva čvora biti djeca, a učestalost pojavljivanja će biti jednaka zbroju frekvencija ova dva čvora.
- Dodajte novi čvor u red prioriteta.
- Jedini preostali čvor bit će korijen, a to će dovršiti konstrukciju stabla.
Zamislimo da imamo neki tekst koji se sastoji samo od znakova "a", "b", "c", "d" и "i", a njihove učestalosti pojavljivanja su 15, 7, 6, 6, odnosno 5. Ispod su ilustracije koje odražavaju korake algoritma.
Put od korijena do bilo kojeg krajnjeg čvora pohranit će optimalni prefiks kod (također poznat kao Huffmanov kod) koji odgovara znaku pridruženom tom krajnjem čvoru.
Huffmanovo drvo
Ispod ćete pronaći implementaciju Huffmanovog algoritma kompresije u C++ i Javi:
#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);
}
}Napomena: memorija koju koristi ulazni niz je 47 * 8 = 376 bita, a kodirani niz ima samo 194 bita, tj. podaci su komprimirani za oko 48%. U gornjem C++ programu koristimo klasu string za pohranjivanje kodiranog niza kako bi program bio čitljiv.
Budući da učinkovite strukture podataka reda prioriteta zahtijevaju po umetanju O(log(N)) vrijeme, ali u potpunom binarnom stablu sa N lišće prisutno 2N-1 čvorova, a Huffmanovo stablo je potpuno binarno stablo, tada se pokreće algoritam O(Nlog(N)) vrijeme, gdje N - Likovi.
Izvori:
Izvor: www.habr.com