Pred začetkom tečaja za vas pripravili prevod drugega uporabnega gradiva.
Huffmanovo kodiranje je algoritem za stiskanje podatkov, ki oblikuje osnovno idejo stiskanja datotek. V tem članku bomo govorili o kodiranju s fiksno in spremenljivo dolžino, kodah, ki jih je mogoče edinstveno dekodirati, pravilih predpon in gradnji Huffmanovega drevesa.
Vemo, da je vsak znak shranjen kot zaporedje 0 in 1 in zavzema 8 bitov. To se imenuje kodiranje s fiksno dolžino, ker vsak znak za shranjevanje uporablja isto fiksno število bitov.
Recimo, da nam je dano besedilo. Kako lahko zmanjšamo količino prostora, ki je potreben za shranjevanje enega znaka?
Glavna ideja je kodiranje s spremenljivo dolžino. Uporabimo lahko dejstvo, da se nekateri znaki v besedilu pojavljajo pogosteje kot drugi (), da bi razvili algoritem, ki bo predstavil isto zaporedje znakov v manj bitih. Pri kodiranju s spremenljivo dolžino znakom dodelimo različno število bitov, odvisno od tega, kako pogosto se pojavljajo v danem besedilu. Sčasoma lahko nekateri znaki zavzamejo le 1 bit, drugi pa 2 bita, 3 ali več. Težava pri kodiranju s spremenljivo dolžino je samo naknadno dekodiranje zaporedja.
Kako ga, če poznamo zaporedje bitov, nedvoumno dekodirati?
Razmislite o liniji "abacdab". Ima 8 znakov in pri kodiranju fiksne dolžine bo za shranjevanje potreboval 64 bitov. Upoštevajte, da frekvenca simbola "a", "b", "c" и "D" je enako 4, 2, 1, 1. Poskusimo si predstavljati "abacdab" manj bitov z uporabo dejstva, da "do" pojavlja pogosteje kot "B"In "B" pojavlja pogosteje kot "c" и "D". Začnimo s kodiranjem "do" z enim bitom enakim 0, "B" dodelili bomo dvobitno kodo 11, z uporabo treh bitov 100 in 011 pa bomo kodirali "c" и "D".
Kot rezultat bomo dobili:
a
0
b
11
c
100
d
011
Torej linija "abacdab" bomo kodirali kot 00110100011011 (0|0|11|0|100|011|0|11)z uporabo zgornjih kod. Vendar bo glavna težava v dekodiranju. Ko poskušamo dekodirati niz 00110100011011, dobimo dvoumen rezultat, saj ga lahko predstavimo kot:
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
Da bi se izognili tej dvoumnosti, moramo zagotoviti, da naše kodiranje ustreza konceptu, kot je pravilo predpone, kar pomeni, da je kode mogoče dekodirati samo na en edinstven način. Pravilo predpone zagotavlja, da nobena koda ni predpona druge kode. S kodo mislimo na bite, ki se uporabljajo za predstavitev določenega znaka. V zgornjem primeru 0 je predpona 011, ki krši pravilo predpone. Torej, če naše kode izpolnjujejo pravilo predpone, potem lahko enolično dekodiramo (in obratno).
Ponovno poglejmo zgornji primer. Tokrat bomo dodelili simbole "a", "b", "c" и "D" kode, ki ustrezajo pravilu predpone.
a
0
b
10
c
110
d
111
S tem kodiranjem je niz "abacdab" bo kodiran kot 00100100011010 (0|0|10|0|100|011|0|10). Vendar 00100100011010 bomo že lahko nedvoumno dekodirali in se vrnili k našemu izvirnemu nizu "abacdab".
Huffmanovo kodiranje
Zdaj, ko smo obravnavali kodiranje s spremenljivo dolžino in pravilo predpone, se pogovorimo o Huffmanovem kodiranju.
Metoda temelji na ustvarjanju binarnih dreves. V njem je vozlišče lahko končno ali notranje. Sprva se vsa vozlišča štejejo za liste (terminale), ki predstavljajo sam simbol in njegovo težo (to je pogostost pojavljanja). Notranja vozlišča vsebujejo težo znaka in se nanašajo na dve podrejeni vozlišči. Po splošnem dogovoru bit «0» predstavlja sledenje levi veji in «1» - na desni. v polnem drevesu N listi in N-1 notranja vozlišča. Priporočljivo je, da pri konstruiranju Huffmanovega drevesa neuporabljene simbole zavržete, da dobite kode optimalne dolžine.
Za gradnjo Huffmanovega drevesa bomo uporabili prednostno čakalno vrsto, kjer bo vozlišče z najnižjo frekvenco dobilo najvišjo prednost. Koraki gradnje so opisani spodaj:
- Ustvarite listno vozlišče za vsak znak in ga dodajte v prednostno čakalno vrsto.
- Če je v čakalni vrsti več kot en list, naredite naslednje:
- Odstranite dve vozlišči z najvišjo prioriteto (najnižjo frekvenco) iz čakalne vrste;
- Ustvarite novo notranje vozlišče, kjer bosta ti dve vozlišči podrejeni, pogostost pojavljanja pa bo enaka vsoti frekvenc teh dveh vozlišč.
- Dodajte novo vozlišče v prednostno čakalno vrsto.
- Edino preostalo vozlišče bo korenina in s tem bo dokončana konstrukcija drevesa.
Predstavljajte si, da imamo neko besedilo, ki je sestavljeno samo iz znakov "a", "b", "c", "d" и "in", njihove frekvence pojavljanja pa so 15, 7, 6, 6 oziroma 5. Spodaj so ilustracije, ki prikazujejo korake algoritma.
Pot od korena do katerega koli končnega vozlišča bo shranila optimalno kodo predpone (znano tudi kot Huffmanova koda), ki ustreza znaku, povezanemu s tem končnim vozliščem.
Huffmanovo drevo
Spodaj boste našli implementacijo Huffmanovega algoritma stiskanja v C++ in 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);
}
}Opomba: pomnilnik, ki ga uporablja vhodni niz, je 47 * 8 = 376 bitov, kodirani niz pa le 194 bitov, tj. podatki so stisnjeni za približno 48 %. V zgornjem programu C++ uporabljamo razred nizov za shranjevanje kodiranega niza, da je program berljiv.
Ker učinkovite podatkovne strukture prednostne čakalne vrste zahtevajo posamezen vstavek O(log(N)) času, vendar v popolnem binarnem drevesu z N prisotni listi 2N-1 vozlišč in je Huffmanovo drevo popolno binarno drevo, potem se algoritem zažene O(Nlog(N)) čas, kje N - Znaki.
Vir:
Vir: www.habr.com