I anledning af starten på kurset har udarbejdet en oversættelse af endnu et nyttigt materiale.
Huffman-kodning er en datakomprimeringsalgoritme, der formulerer den grundlæggende idé bag filkomprimering. I denne artikel vil vi tale om faste og variable længdekodninger, entydigt dekodérbare koder, præfiksregler og opbygning af et Huffman-træ.
Vi ved, at hvert tegn gemmes som en sekvens af 0 og 1 og optager 8 bit. Dette kaldes kodning af fast længde, da hvert tegn bruger et ensartet og fast antal bits til opbevaring.
Lad os antage, at der findes en tekst. Hvordan kan vi reducere det plads, der kræves for at gemme et enkelt tegn?
Den grundlæggende idé ligger i kodning af variabel længde. Vi kan udnytte det faktum, at nogle tegn i teksten optræder oftere end andre (), for at udvikle en algoritme, der repræsenterer den samme sekvens af tegn med færre bits. Ved kodning af variabel længde tildeler vi tegn variable antal bits afhængigt af, hvor ofte de forekommer i den given tekst. I sidste ende kan nogle tegn kun optage 1 bit, mens andre optager 2, 3 eller flere bits. Problemet med kodning af variabel længde ligger kun i efterfølgende dekodning af sekvensen.
Hvordan kan vi, når vi kender sekvensen af bits, dekode den entydigt?
Overvej strengen «aabacdab». Den indeholder 8 tegn, og ved kodning af fast længde ville det kræve 64 bits til opbevaring. Bemærk, at frekvenserne for tegnene «a», «b», «c» og «d» er henholdsvis 4, 2, 1, 1. Lad os prøve at repræsentere «aabacdab» med færre bits ved at bruge det faktum, at «a» optræder oftere end «b». Lad os begynde med at kode, og «b». Lad os begynde med at kode optræder oftere end ‘c’ og «d»med en bit, der er 0, «a» vi tildeler en to-bits kode 11, og med tre bits koder vi 100 og 011 «b». Lad os begynde med at kode I sidste ende får vi: ‘c’ og «d».
Således vil vi kode strengen
en
0
b
11
c
100
d
011
som «aabacdab» , ved at bruge de koder, der er nævnt ovenfor. Men det grundlæggende problem ligger i dekodningen. Når vi forsøger at dekode strengen 00110100011011 (0|0|11|0|100|011|0|11), vil vi få et tvetydigt resultat, da den kan repræsenteres som: 001101000110110|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
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
…
osv.
For at undgå denne tvetydighed skal vi sikre os, at vores kodning opfylder et begreb som præfikregel, som igen indebærer, at koderne kun kan dekodes på én unik måde. Præfikreglen sikrer, at ingen kode vil være et præfiks for en anden. Med kode mener vi de bits, der bruges til at repræsentere et bestemt tegn. I det ovenstående eksempel 0 – er et præfiks 011, hvilket overtræder præfikreglen. Så hvis vores koder opfylder præfikreglen, kan dekodningen udføres entydigt (og omvendt).
Lad os gennemgå det ovenstående eksempel igen. Denne gang vil vi tildele tegnene «a», «b», «c» og «d» koder, der opfylder præfikreglen.
en
0
b
10
c
110
d
111
Med denne kodning vil strengen «aabacdab» blive kodet som 00100100011010 (0|0|10|0|100|011|0|10)Men en 00100100011010 vi vil allerede kunne dekode entydigt og vende tilbage til vores oprindelige streng «aabacdab».
Huffman-kodning
Nu hvor vi har forstået kodning af variabel længde og præfikreglen, lad os tale om Huffman-kodning.
Metoden bygger på at skabe binære træer. I den kan en node være enten en blad- eller en indre node. Oprindeligt betragtes alle noder som blade (endelige), der repræsenterer selve tegnet og dets vægt (dvs. frekvensen af forekomst). Indre noder indeholder vægten af tegnet og henviser til to underordnede noder. Efter almindelig aftale repræsenterer bit „0“ at følge den venstre gren, mens „1“ er for den højre. I et komplet træ N blade og N-1 indre noder. Det anbefales at udelade ubrugte tegn ved opbygning af Huffman-træet for at opnå koder af optimal længde.
Vi vil bruge en prioriteret kø til at bygge Huffman-træet, hvor noden med den laveste frekvens tildeles højeste prioritet. Nedenfor beskrives trinene til opbygning:
- Opret en bladnode for hvert tegn, og tilføj dem til den prioriterede kø.
- Så længe der er mere end én blad i køen, gør følgende:
- Fjern to noder med højeste prioritet (den laveste frekvens) fra køen;
- Opret en ny indre node, hvor disse to noder vil være underordnede, og frekvensen vil være summen af frekvenserne for disse to noder.
- Tilføj den nye node til den prioriterede kø.
- Den eneste tilbageblevne node vil være rodnoden, og dette vil afslutte opbygningen af træet.
Lad os forestille os, at vi har en tekst, der kun består af tegn «a», «b», «c», «d» og ‘e’, og hyppigheden af deres forekomst er henholdsvis 15, 7, 6, 6 og 5. Nedenfor er illustrationer, der viser trinene i algoritmen.
Vejen fra roden til enhver endenode vil opbevare den optimale præfiks-kode (også kendt som Huffman-koden), der svarer til det tegn, der er knyttet til denne endenode.
Huffman-træ
Nedenfor finder du implementeringen af Huffman-komprimeringsalgoritmen i C++ og 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;
// En træ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
{
// Traversere Huffman-træet og gemme Huffman-koder
// i et kort.
public static void encode(Node root, String str,
Map<Character, String> huffmanCode)
{
if (root == null)
return;
// Fundet et bladnode
if (root.left == null && root.right == null) {
huffmanCode.put(root.ch, str);
}
encode(root.left, str + "0", huffmanCode);
encode(root.right, str + "1", huffmanCode);
}
// Traversere Huffman-træet og dekode den kodede streng
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// Fundet et bladnode
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;
}
// Bygger Huffman-træ og huffmanCode og dekoder givet inputtekst
public static void buildHuffmanTree(String text)
{
// Tæl frekvensen af hvert tegns optræden
// og gem det i et kort
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);
}
// Opret en prioriteret kø til at gemme levende noder i Huffman-træet
// Bemærk at det højeste prioriterede element har den laveste frekvens
PriorityQueue<Node> pq = new PriorityQueue<>(
(l, r) -> l.freq - r.freq);
// Opret en bladnode for hvert tegn og tilføj det
// til den prioriterede kø.
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
// Gør indtil der er mere end én node i køen
while (pq.size() != 1)
{
// Fjern de to noder med højeste prioritet
// (laveste frekvens) fra køen
Node left = pq.poll();
Node right = pq.poll();
// Opret en ny intern node med disse to noder som børn
// og med en frekvens svarende til summen af de to noders
// frekvenser. Tilføj den nye node til den prioriterede kø.
int sum = left.freq + right.freq;
pq.add(new Node(' ', sum, left, right));
}
// root gemmer pointeren til roden af Huffman-træet
Node root = pq.peek();
// Traversere Huffman-træet og gemme Huffman-koderne i et kort
Map<Character, String> huffmanCode = new HashMap<>();
encode(root, "", huffmanCode);
// Udskriv Huffman-koderne
System.out.println("Huffman-koderne er :n");
for (Map.Entry<Character, String> entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("nDen originale streng var :n" + text);
// Udskriv den kodede streng
StringBuilder sb = new StringBuilder();
for (int i = 0 ; i < text.length(); i++) {
sb.append(huffmanCode.get(text.charAt(i)));
}
System.out.println("nDen kodede streng er :n" + sb);
// Traversere Huffman-træet igen og denne gang
// dekode den kodede streng
int index = -1;
System.out.println("nDen dekodede streng er: n");
while (index < sb.length() - 2) {
index = decode(root, index, sb);
}
}
public static void main(String[] args)
{
String text = "Huffman-kodning er en data komprimerings-algoritme.";
buildHuffmanTree(text);
}
}Bemærk: Hukommelsen, som bruges af inputstrengen, er 47 * 8 = 376 bit, mens den kodede streng kun optager 194 bit, dvs. data komprimeres med cirka 48%. I det ovenstående C++ program bruger vi klassen string til at gemme den kodede streng for at gøre programmet læsbart.
Da effektive datastrukturer for prioritetskøer kræver O(log(N)) tid til indsættelse, og i et fuldt binært træ med N blade er der 2N-1 noder, og Huffman-træet er et fuldt binært træ, så algoritmen arbejder på O(Nlog(N)) tid, hvor N er antallet af tegn.
Kilder:
Kilde: habr.com
