Inför kursstarten har förberett en översÀttning av Ànnu ett anvÀndbart material för dig.
Huffman-kodning Àr en algoritm för datakomprimering som formulerar den grundlÀggande idén om filkomprimering. I den hÀr artikeln kommer vi att diskutera fast och variabel lÀngdkodning, unikt avkodningsbara koder, prefixregler och byggandet av Huffman-trÀd.
Vi vet att varje tecken lagras som en sekvens av 0 och 1 och tar upp 8 bitar. Detta kallas fast lÀngdkodning eftersom varje tecken anvÀnder ett lika fast antal bitar för lagring.
LÄt oss sÀga att vi har en text. Hur kan vi minska det utrymme som krÀvs för att lagra ett tecken?
Den grundlÀggande idén Àr variabel lÀngdkodning. Vi kan anvÀnda det faktum att vissa tecken i texten förekommer oftare Àn andra (), för att utveckla en algoritm som kommer att representera samma teckenföljd med fÀrre bitar. Vid variabel lÀngdkodning tilldelar vi tecken ett variabelt antal bitar beroende pÄ hur ofta de förekommer i denna text. Som ett resultat kan vissa tecken ta upp endast 1 bit, medan andra tar 2 bitar, 3 eller mer. Problemet med variabel lÀngdkodning Àr endast att dÀrefter avkoda sekvensen.
Hur kan vi, med sekvensen av bitar, avkoda den entydigt?
LÄt oss titta pÄ strÀngen «aabacdab». Den innehÄller 8 tecken, och vid fast lÀngdkodning kommer den att behöva 64 bitar för att lagras. Vi noterar att frekvensen av tecknen «a», «b», «c» och «d» Àr 4, 2, 1, 1 respektive. LÄt oss försöka representera «aabacdab» med fÀrre bitar, med tanke pÄ att «a» förekommer oftare Àn «b», och «b» förekommer oftare Àn «c» och «d». Vi börjar med att koda «a» med en bit, lika med 0, «b» vi tilldelar en tvÄbitarskod 11, och med tre bitar kodar vi 100 och 011 «c» och «d».
SÄ vi fÄr:
a
0
b
11
c
100
d
011
DÀrför kommer vi att koda strÀngen «aabacdab» som 00110100011011 (0|0|11|0|100|011|0|11), med hjÀlp av koderna som presenterats ovan. Men det grundlÀggande problemet kommer att vara avkodningen. NÀr vi försöker avkoda strÀngen 00110100011011, fÄr vi ett tvetydigt resultat eftersom den kan representeras som:
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
âŠ
och sÄ vidare.
För att undvika denna tvetydighet mĂ„ste vi sĂ€kerstĂ€lla att vĂ„r kodning uppfyller ett begrepp som prefixregel, vilket i sin tur innebĂ€r att koderna kan avkodas pĂ„ ett unikt sĂ€tt. Prefixregeln garanterar att ingen kod Ă€r en prefix av en annan. Med kod avser vi bitarna som anvĂ€nds för att representera en specifik symbol. I det ovanstĂ„ende exemplet 0 â Ă€r ett prefix 011, vilket bryter mot prefixregeln. SĂ„ om vĂ„ra koder uppfyller prefixregeln kan avkodningen ske entydigt (och vice versa).
LÄt oss granska exemplet ovan. Den hÀr gÄngen kommer vi att tilldela symbolerna «a», «b», «c» och «d» koder som uppfyller prefixregeln.
a
0
b
10
c
110
d
111
Med en sÄdan kodning kommer strÀngen «aabacdab» att kodas som 00100100011010 (0|0|10|0|100|011|0|10). Och hÀr Àr 00100100011010 vi kommer redan att kunna avkoda den entydigt och ÄtergÄ till vÄr ursprungliga strÀng «aabacdab».
Huffman-kodning
Nu nÀr vi har förstÄtt kodning av variabel lÀngd och prefixregeln, lÄt oss prata om Huffman-kodning.
Metoden bygger pÄ att skapa binÀra trÀd. I det kan en nod vara antingen en terminal eller en intern. FrÄn början betraktas alla noder som löv (terminaler) som representerar sjÀlva symbolen och dess vikt (dvs. frekvens). Interna noder innehÄller symbolvikten och hÀnvisar till tvÄ arvnodar. Enligt vanlig praxis representerar biten «0» att följa den vÀnstra grenen, medan «1» representerar den högra. I ett fullt trÀd finns det N blad och N-1 interna noder. Det rekommenderas att man vid byggandet av Huffman-trÀdet lÀmnar bort oanvÀnda symboler för att fÄ koder av optimal lÀngd.
Vi kommer att anvÀnda en prioriteringskö för att bygga Huffman-trÀdet, dÀr noden med lÀgst frekvens tilldelas högsta prioritet. Stegen för konstruktion beskrivs nedan:
- Skapa ett lövnod för varje symbol och lÀgg till dem i prioriteringskön.
- SÄ lÀnge som det finns mer Àn en löv i kön gör vi följande:
- Ta bort tvÄ noder med högsta prioritet (med lÀgst frekvens) frÄn kön;
- Skapa en ny intern nod dÀr dessa tvÄ noder Àr arvtagare, och frekvensen Àr summan av frekvenserna för dessa tvÄ noder.
- LÀgg till den nya noden i prioriteringskön.
- Den enda kvarvarande noden kommer att vara roten, och dÀrmed avslutas byggandet av trÀdet.
LÄt oss förestÀlla oss att vi har en viss text som endast bestÄr av tecken «a», «b», «c», «d» och «e», och frekvenserna för deras förekomst Àr 15, 7, 6, 6 och 5 respektive. Nedan följer illustrationer som visar stegen i algoritmen.
VÀgen frÄn roten till varje slutnod kommer att lagra den optimala prefixkoden (Àven kÀnd som Huffman-kod) som motsvarar tecknet kopplat till denna slutnod.
Huffman-trÀd
Nedan finner du en implementation av Huffman-komprimeringsalgoritmen pÄ C++ och 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 nod i trÀdet
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
{
// Traversera Huffman-trÀdet och lagra Huffman-koder
// i en karta.
public static void encode(Node root, String str,
Map huffmanCode)
{
if (root == null)
return;
// hittade en bladnod
if (root.left == null && root.right == null) {
huffmanCode.put(root.ch, str);
}
encode(root.left, str + "0", huffmanCode);
encode(root.right, str + "1", huffmanCode);
}
// Traversera Huffman-trÀdet och avkoda den kodade strÀngen
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// hittade en bladnod
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Àd och huffmanCode och avkodar given indata
public static void buildHuffmanTree(String text)
{
// rÀkna frekvensen av varje teckens utseende
// och lagra det i en karta
Map 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);
}
// Skapa en prioritetskö för att lagra aktiva noder i Huffman-trÀdet
// Observera att det högsta prioriterade objektet har lÀgst frekvens
PriorityQueue pq = new PriorityQueue(
(l, r) -> l.freq - r.freq);
// Skapa en bladnod för varje tecken och lÀgg till den
// i prioritetskön.
for (Map.Entry entry : freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
// gör tills det finns mer Àn en nod i kön
while (pq.size() != 1)
{
// Ta bort de tvÄ noderna med högsta prioritet
// (lÀgsta frekvens) frÄn kön
Node left = pq.poll();
Node right = pq.poll();
// Skapa en ny intern nod med dessa tvÄ noder som barn
// och med frekvensen lika med summan av de tvÄ nodernas
// frekvenser. LÀgg till den nya noden i prioritetskön.
int sum = left.freq + right.freq;
pq.add(new Node(' ', sum, left, right));
}
// root lagrar pekare till rot av Huffman-trÀdet
Node root = pq.peek();
// Traversera Huffman-trÀdet och lagra Huffman-koderna i en karta
Map huffmanCode = new HashMap();
encode(root, "", huffmanCode);
// skriv ut Huffman-koderna
System.out.println("Huffman-koderna Àr :\n");
for (Map.Entry entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("\nDen ursprungliga strÀngen var :\n" + text);
// skriv ut den kodade strÀngen
StringBuilder sb = new StringBuilder();
for (int i = 0 ; i < text.length(); i++) {
sb.append(huffmanCode.get(text.charAt(i)));
}
System.out.println("\nDen kodade strÀngen Àr :\n" + sb);
// Traversera Huffman-trÀdet igen och den hÀr gÄngen
// avkoda den kodade strÀngen
int index = -1;
System.out.println("\nDen avkodade strÀngen Àr: \n");
while (index < sb.length() - 2) {
index = decode(root, index, sb);
}
}
public static void main(String[] args)
{
String text = "Huffman kodning Àr en algoritm för datakompression.";
buildHuffmanTree(text);
}
}AnmÀrkning: Minnet som anvÀnds av indat strÀngen Àr 47 * 8 = 376 bitar, och den kodade strÀngen tar endast 194 bitar, vilket innebÀr att data komprimeras med ungefÀr 48 %. I C++-programmet ovan anvÀnder vi klassen string för att lagra den kodade strÀngen för att göra programmet lÀsbart.
Eftersom effektiva datatyper för prioritetsköer krÀver O(log(N)) tid för insÀttning, och i ett fullstÀndigt binÀrt trÀd med N blad finns 2N-1 noder, och Huffman-trÀdet Àr ett fullstÀndigt binÀrt trÀd, sÄ fungerar algoritmen pÄ O(Nlog(N)) tid, dÀr N Àr antalet tecken.
KĂ€llor:
KĂ€lla: habr.com
