Virum Ufank vum Cours Mir hunn eng Iwwersetzung vun engem anere nëtzlecht Material fir Iech virbereet.
Huffman Kodéierung ass en Datekompressiounsalgorithmus deen d'Basis Iddi vun der Dateikompressioun formuléiert. An dësem Artikel schwätze mir iwwer fix a variabel Längt Kodéierung, eenzegaarteg dekodéierbar Coden, Präfixregelen, an Huffman Bamkonstruktioun.
Mir wëssen datt all Charakter als Sequenz vun 0s an 1s gespäichert ass an 8 Bits besetzt. Dëst gëtt Kodéierung vun enger fixer Längt genannt well all Charakter déi selwecht fix Zuel vu Späicherbits benotzt.
Loosst eis soen datt den Text gëtt. Wéi kënne mir d'Quantitéit u Plaz reduzéieren déi néideg ass fir ee Charakter ze späicheren?
D'Basis Iddi ass variabel Längt Kodéierung. Mir kënnen d'Tatsaach benotzen datt verschidde Charaktere méi dacks am Text optrieden wéi anerer () fir en Algorithmus z'entwéckelen, deen déiselwecht Sequenz vun Zeechen a manner Bits representéiert. A variabelen Längt Kodéierung zouzeweise mir eng variabel Zuel vu Bits un Zeechen ofhängeg vun der Frequenz vun hirem Optriede an engem bestëmmten Text. Schlussendlech kënnen e puer Charaktere just 1 Bit ophuelen, anerer kënnen 2 Bits, 3 oder méi huelen. De Problem mat variabelen Längt Kodéierung ass nëmmen déi spéider Decodéierung vun der Sequenz.
Wéi, wann Dir eng Sequenz vu Bits kennt, kënnt Dir et eendeiteg dekodéieren?
Betruecht der Linn "aabacdab". Et huet 8 Zeechen, a mat fixer Längt Kodéierung brauch et 64 Bits fir et ze späicheren. Bedenkt datt d'Symbol Frequenz "a", "b", "c" и "D" entsprécht 4, 2, 1, 1 respektiv. Loosst eis probéieren Iech virzestellen "aabacdab" a manner Stécker, profitéiert vun der Tatsaach, datt "zu" geschitt méi dacks wéi "B"an "B" geschitt méi dacks wéi "c" и "D". Mir fänke mam Kodéierung un "zu" mat engem Bit gläich wéi 0, "B" mir wäerten en zwee-Bit Code un 11 zouginn, a mat dräi Bits 100 an 011 codéiere mir "c" и "D".
Als Resultat wäerte mir kréien:
a
0
b
11
c
100
d
011
Also d'Linn "aabacdab" mir Code et als 00110100011011 (0|0|11|0|100|011|0|11)benotzt d'Coden hei uewen. Wéi och ëmmer, den Haaptproblem wäert an der Dekodéierung sinn. Wa mir probéieren de String ze decodéieren 00110100011011, wäerte mir en zweedeiteg Resultat kréien, well et ka representéiert ginn als:
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
...
an esou weider.
Fir dës Ambiguititéit ze vermeiden, musse mir sécherstellen datt eis Kodéierung e Konzept wéi z Präfix Regel, wat am Tour implizéiert datt d'Coden op nëmmen eng eenzegaarteg Manéier dekodéiert kënne ginn. D'Präfixregel garantéiert datt kee Code e Präfix vun engem aneren ass. Mam Code menge mir d'Bits déi benotzt gi fir e bestëmmte Charakter ze representéieren. Am uewe genannte Beispill 0 ass e Präfix 011, wat d'Präfixregel verletzt. Also, wann eis Coden d'Präfixregel erfëllen, da kënne mir eendeiteg decodéieren (a vice-versa).
Loosst eis d'Beispill hei uewen iwwerpréiwen. Dës Kéier wäerte mir fir Symboler zougewisen "a", "b", "c" и "D" Coden déi de Präfixregel erfëllen.
a
0
b
10
c
110
d
111
Mat dëser Kodéierung gëtt de String "aabacdab" gëtt kodéiert als 00100100011010 (0|0|10|0|100|011|0|10). Awer 00100100011010 mir kënnen elo eendeiteg decodéieren an zréck op eis ursprénglech String "aabacdab".
Huffman coding
Elo datt mir d'Verännerlech Längt Kodéierung an d'Präfixregel verstinn, loosst eis iwwer Huffman Kodéierung schwätzen.
D'Method baséiert op der Schafung vun binäre Beem. An et kann en Node entweder final oder intern sinn. Am Ufank ginn all Node als Blieder (Enn) ugesinn, déi d'Symbol selwer a säi Gewiicht representéieren (dat ass d'Frequenz vum Optriede). Déi intern Wirbelen enthalen d'Gewiicht vum Charakter a bezéien sech op zwee Nofolgernoden. Duerch allgemeng Accord, bëssen "0" duerstellt folgende déi lénks Branche, an "1" - Riets. Am vollen Bam N Blieder an N-1 intern Wirbelen. Et ass recommandéiert datt wann Dir en Huffman Bam konstruéiert, onbenotzt Symboler verworf ginn fir Coden vun enger optimaler Längt ze kréien.
Mir wäerten eng Prioritéit Schlaang benotzen engem Huffman Bam ze bauen, wou den Node mat der niddregsten Frequenz déi héchste Prioritéit gëtt. D'Konstruktiounsschrëtt ginn hei ënnen beschriwwen:
- Schafen eng Blat Node fir all Symbol a füügt se an d'Prioritéitschlaang.
- Wärend et méi wéi ee Blat an der Schlaang ass, maacht déi folgend:
- Ewechzehuelen déi zwee héchste Prioritéit (niddregsten Frequenz) Node aus der Schlaang;
- Erstellt en neien internen Node, wou dës zwee Wirbelen d'Nofolger sinn, an d'Frequenz vum Optriede gëtt gläich wéi d'Zomm vun den Frequenzen vun dësen zwee Wirbelen.
- Füügt en neien Node an d'Prioritéitschlaang.
- Déi eenzeg verbleiwen Node wäert de Root Node sinn, an dëst wäert de Bau vum Bam fäerdeg maachen.
Loosst eis virstellen datt mir en Text hunn deen nëmmen aus Charaktere besteet "a", "b", "c", "d" и "an", an hir Frequenzen vum Optriede sinn 15, 7, 6, 6 a 5, respektiv. Drënner sinn Illustratiounen déi d'Schrëtt vum Algorithmus reflektéieren.
De Wee vun der Wuerzel op all Blatknuet späichert den optimale Präfixcode (och bekannt als Huffman Code) entsprécht dem Charakter verbonne mat deem Blatknuet.
Huffman Baum
Hei ënnen fannt Dir eng Implementatioun vum Huffman Kompressiounsalgorithmus an C++ an 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);
}
}Opgepasst: d'Erënnerung déi vum Input String benotzt gëtt ass 47 * 8 = 376 Bits an déi kodéiert String hëlt nëmmen 194 Bits op, d.h. Daten ginn ëm ongeféier 48% kompriméiert. Am C ++ Programm hei uewen benotze mir d'Stringklass fir eng kodéiert String ze späicheren fir de Programm liesbar ze maachen.
Well efficace Prioritéit Schlaang Daten Strukturen verlaangen pro Insertion O(log(N)) Zäit, an an engem komplett binäre Bam mat N Blieder presentéieren 2N-1 Noden, an den Huffman Bam ass e komplette binäre Bam, da funktionnéiert den Algorithmus an O(Nlog(N)) Zäit, wou N - Charaktere.
Quell:
Source: will.com