Prije početka kursa pripremio za vas prijevod još jednog korisnog materijala.
Huffmanovo kodiranje je algoritam kompresije podataka koji formulira osnovnu ideju kompresije datoteka. U ovom članku ćemo govoriti o kodiranju fiksne i promjenjive dužine, jedinstveno dekodirajućim kodovima, pravilima prefiksa i izgradnji Huffmanovog stabla.
Znamo da je svaki znak pohranjen kao niz od 0 i 1 i da zauzima 8 bitova. Ovo se zove kodiranje fiksne dužine jer svaki znak koristi isti fiksni broj bitova za pohranu.
Recimo da nam je dat tekst. Kako možemo smanjiti količinu prostora potrebnog za pohranjivanje jednog znaka?
Glavna ideja je kodiranje promjenjive dužine. Možemo iskoristiti činjenicu da se neki znakovi u tekstu pojavljuju češće od drugih () da se razvije algoritam koji će predstavljati isti niz znakova u manje bitova. U kodiranju promjenjive dužine, karakterima dodjeljujemo promjenjiv broj bitova, ovisno o tome koliko se često pojavljuju u datom tekstu. Na kraju, neki znakovi mogu zauzeti samo 1 bit, dok drugi mogu zauzeti 2 bita, 3 ili više. Problem sa kodiranjem promenljive dužine je samo naknadno dekodiranje sekvence.
Kako, znajući redoslijed bitova, nedvosmisleno ga dekodirati?
Razmotrite liniju "abacdab". Ima 8 znakova, a kada se kodira fiksne dužine, trebat će mu 64 bita da ga pohrani. Imajte na umu da je frekvencija simbola "a", "b", "c" и "D" jednako 4, 2, 1, 1 respektivno. 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" sa jednim bitom jednakim 0, "B" dodijelit ćemo dvobitni kod 11, a pomoću tri bita 100 i 011 ćemo kodirati "c" и "D".
Kao rezultat, dobićemo:
a
0
b
11
c
100
d
011
Dakle, linija "abacdab" kodiraćemo kao 00110100011011 (0|0|11|0|100|011|0|11)koristeći gore navedene kodove. Međutim, glavni problem će biti u dekodiranju. Kada pokušamo dekodirati niz 00110100011011, dobijamo 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
...
i tako dalje.
Da 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 podrazumijevamo bitove koji se koriste za predstavljanje određenog znaka. U primjeru iznad 0 je prefiks 011, što krši pravilo prefiksa. Dakle, ako naši kodovi zadovoljavaju pravilo prefiksa, onda možemo jedinstveno dekodirati (i obrnuto).
Vratimo se na gornji primjer. Ovaj put ćemo dodijeliti za simbole "a", "b", "c" и "D" kodovi koji zadovoljavaju pravilo prefiksa.
a
0
b
10
c
110
d
111
Sa ovim kodiranjem, string "abacdab" će biti kodiran kao 00100100011010 (0|0|10|0|100|011|0|10). I ovde 00100100011010 već ćemo moći nedvosmisleno dekodirati i vratiti se na naš originalni niz "abacdab".
Huffman kodiranje
Sada kada smo se pozabavili kodiranjem promenljive dužine i pravilom prefiksa, hajde da pričamo o Huffman kodiranju.
Metoda se zasniva na kreiranju binarnih stabala. U njemu čvor može biti završni ili interni. U početku se svi čvorovi smatraju listovima (terminalima), koji predstavljaju sam simbol i njegovu težinu (tj. učestalost pojavljivanja). Unutrašnji čvorovi sadrže težinu karaktera i odnose se na dva čvora potomka. Po opštem dogovoru, bit "0" predstavlja praćenje lijeve grane, i "1" - desno. u punom stablu N listovi i N-1 unutrašnji čvorovi. Preporučuje se da se prilikom konstruisanja Huffmanovog stabla neiskorišteni simboli odbace kako bi se dobili optimalni kodovi dužine.
Koristit ćemo prioritetni red za izgradnju Huffmanovog stabla, gdje će čvor sa najnižom frekvencijom dobiti najveći prioritet. Koraci izgradnje su opisani u nastavku:
- Kreirajte lisni čvor za svaki znak i dodajte ih u prioritetni red.
- Dok postoji više od jednog lista u redu čekanja, učinite sljedeće:
- Uklonite dva čvora sa najvišim prioritetom (najnižom frekvencijom) iz reda;
- Kreirajte novi interni čvor, gdje će ova dva čvora biti djeca, a učestalost pojavljivanja će biti jednaka zbiru frekvencija ova dva čvora.
- Dodajte novi čvor u prioritetni red.
- Jedini preostali čvor će biti korijen, a to će dovršiti konstrukciju stabla.
Zamislite da imamo neki tekst koji se sastoji samo od znakova "a b c d" и "i", a frekvencije njihovog pojavljivanja su 15, 7, 6, 6 i 5, respektivno. Ispod su ilustracije koje odražavaju korake algoritma.
Put od korijena do bilo kojeg krajnjeg čvora će pohraniti optimalni prefiks kod (također poznat kao Huffman kod) koji odgovara znaku povezanom s tim krajnjim čvorom.
Huffmanovo drvo
Ispod ćete nać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 je samo 194 bita, tj. podaci su komprimirani za oko 48%. U C++ programu iznad, koristimo string klasu da pohranimo kodirani string kako bismo program učinili čitljivim.
Zato što efikasne strukture podataka reda prioriteta zahtijevaju po umetanju O(log(N)) vrijeme, ali u potpunom binarnom stablu sa N ostavlja prisutni 2N-1 čvorova, a Hafmanovo stablo je kompletno binarno stablo, tada se algoritam uključuje O(Nlog(N)) vrijeme, gdje N - Likovi.
Izvori:
izvor: www.habr.com