Pred začiatkom kurzu pripravil pre vás preklad ďalšieho užitočného materiálu.
Huffmanovo kódovanie je algoritmus kompresie údajov, ktorý formuluje základnú myšlienku kompresie súborov. V tomto článku budeme hovoriť o kódovaní s pevnou a premenlivou dĺžkou, jedinečne dekódovateľných kódoch, pravidlách pre predpony a budovaní Huffmanovho stromu.
Vieme, že každý znak je uložený ako postupnosť 0 a 1 a zaberá 8 bitov. Toto sa nazýva kódovanie s pevnou dĺžkou, pretože každý znak používa na uloženie rovnaký pevný počet bitov.
Povedzme, že sme dostali text. Ako môžeme znížiť množstvo miesta potrebného na uloženie jedného znaku?
Hlavnou myšlienkou je kódovanie s premenlivou dĺžkou. Môžeme využiť fakt, že niektoré znaky sa v texte vyskytujú častejšie ako iné () na vývoj algoritmu, ktorý bude reprezentovať rovnakú sekvenciu znakov v menšom počte bitov. Pri kódovaní s premennou dĺžkou priraďujeme znakom premenlivý počet bitov podľa toho, ako často sa v danom texte vyskytujú. Nakoniec, niektoré znaky môžu trvať len 1 bit, zatiaľ čo iné môžu trvať 2 bity, 3 alebo viac. Problémom kódovania s premennou dĺžkou je len následné dekódovanie sekvencie.
Ako to pri poznaní postupnosti bitov jednoznačne dekódovať?
Zvážte čiaru "abacdab". Má 8 znakov a pri kódovaní pevnej dĺžky bude na uloženie potrebovať 64 bitov. Všimnite si, že frekvencia symbolov "a", "b", "c" и "D" rovná sa 4, 2, 1, 1 v tomto poradí. Skúsme si predstaviť "abacdab" menej bitov, využívajúc skutočnosť, že „do“ vyskytuje častejšie ako "B"A "B" vyskytuje častejšie ako "c" и "D". Začnime kódovaním „do“ s jedným bitom rovným 0, "B" priradíme dvojbitový kód 11 a pomocou troch bitov 100 a 011 zakódujeme "c" и "D".
V dôsledku toho dostaneme:
a
0
b
11
c
100
d
011
Takže čiara "abacdab" budeme kódovať ako 00110100011011 (0|0|11|0|100|011|0|11)pomocou vyššie uvedených kódov. Hlavný problém však bude v dekódovaní. Keď sa pokúsime dekódovať reťazec 00110100011011, dostaneme nejednoznačný výsledok, pretože ho možno reprezentovať ako:
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
...
atď
Aby sme sa vyhli tejto nejednoznačnosti, musíme zabezpečiť, aby naše kódovanie spĺňalo taký koncept ako pravidlo predpony, čo zase znamená, že kódy možno dekódovať iba jedným jedinečným spôsobom. Pravidlo prefixu zabezpečuje, že žiadny kód nie je prefixom iného kódu. Kódom rozumieme bity používané na reprezentáciu konkrétneho znaku. V príklade vyššie 0 je predpona 011, čo porušuje pravidlo predpony. Ak teda naše kódy vyhovujú pravidlu prefixu, môžeme ho jednoznačne dekódovať (a naopak).
Vráťme sa k vyššie uvedenému príkladu. Tentoraz budeme priraďovať pre symboly "a", "b", "c" и "D" kódy, ktoré spĺňajú pravidlo prefixu.
a
0
b
10
c
110
d
111
S týmto kódovaním reťazec "abacdab" bude zakódované ako 00100100011010 (0|0|10|0|100|011|0|10). Avšak 00100100011010 už budeme môcť jednoznačne dekódovať a vrátiť sa k nášmu pôvodnému reťazcu "abacdab".
Huffmanovo kódovanie
Teraz, keď sme sa zaoberali kódovaním s premennou dĺžkou a pravidlom pre predponu, povedzme si niečo o Huffmanovom kódovaní.
Metóda je založená na vytváraní binárnych stromov. V ňom môže byť uzol konečný alebo vnútorný. Spočiatku sú všetky uzly považované za listy (terminály), ktoré predstavujú samotný symbol a jeho váhu (teda frekvenciu výskytu). Vnútorné uzly obsahujú váhu znaku a odkazujú na dva podradené uzly. Podľa všeobecnej dohody bit "0" predstavuje nasledujúcu ľavú vetvu a "1" - napravo. v plnom strome N listy a N-1 vnútorné uzly. Pri konštrukcii Huffmanovho stromu sa odporúča vyradiť nepoužívané symboly, aby sa získali kódy optimálnej dĺžky.
Na zostavenie Huffmanovho stromu použijeme prioritný front, kde uzol s najnižšou frekvenciou dostane najvyššiu prioritu. Kroky výstavby sú opísané nižšie:
- Vytvorte listový uzol pre každý znak a pridajte ho do prioritného frontu.
- Keď je vo fronte viac ako jeden hárok, postupujte takto:
- Odstráňte dva uzly s najvyššou prioritou (najnižšou frekvenciou) z frontu;
- Vytvorte nový vnútorný uzol, kde tieto dva uzly budú potomkami a frekvencia výskytu sa bude rovnať súčtu frekvencií týchto dvoch uzlov.
- Pridajte nový uzol do prioritného frontu.
- Jediným zostávajúcim uzlom bude koreň a tým sa dokončí konštrukcia stromu.
Predstavte si, že máme nejaký text, ktorý pozostáva len zo znakov "a B C d" и „a“a ich frekvencie výskytu sú 15, 7, 6, 6 a 5, v tomto poradí. Nižšie sú uvedené ilustrácie, ktoré odrážajú kroky algoritmu.
Cesta od koreňa k akémukoľvek koncovému uzlu uloží optimálny prefixový kód (známy aj ako Huffmanov kód) zodpovedajúci znaku spojenému s týmto koncovým uzlom.
Huffmanov strom
Nižšie nájdete implementáciu Huffmanovho kompresného algoritmu v C++ a 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);
}
}Poznámka: pamäť využívaná vstupným reťazcom je 47 * 8 = 376 bitov a kódovaný reťazec má len 194 bitov t.j. údaje sú komprimované o približne 48 %. Vo vyššie uvedenom programe C++ používame triedu string na uloženie zakódovaného reťazca, aby bol program čitateľný.
Pretože efektívne prioritné dátové štruktúry vyžadujú jedno vloženie O(log(N)) čas, ale v úplnom binárnom strome s N prítomné listy 2N-1 uzly a Huffmanov strom je úplný binárny strom, potom sa spustí algoritmus O(Nlog(N)) čas, kde N - Postavy.
Zdroje:
Zdroj: hab.com