Voor die aanvang van die kursus het vir jou 'n vertaling van 'n ander nuttige materiaal voorberei.
Huffman-kodering is 'n data-kompressie-algoritme wat die basiese idee van lêerkompressie formuleer. In hierdie artikel sal ons praat oor enkodering met vaste en veranderlike lengte, uniek dekodeerbare kodes, voorvoegselreëls en die bou van 'n Huffman-boom.
Ons weet dat elke karakter gestoor word as 'n reeks van 0'e en 1'e en neem 8 bisse op. Dit word vaste lengte enkodering genoem omdat elke karakter dieselfde vaste aantal bisse gebruik om te stoor.
Kom ons sê ons het 'n teks. Hoe kan ons die hoeveelheid spasie wat benodig word om 'n enkele karakter te stoor verminder?
Die hoofgedagte is enkodering met veranderlike lengte. Ons kan die feit gebruik dat sommige karakters in die teks meer dikwels voorkom as ander () om 'n algoritme te ontwikkel wat dieselfde volgorde karakters in minder stukkies sal verteenwoordig. In veranderlike lengte enkodering ken ons karakters 'n veranderlike aantal bisse toe, afhangend van hoe gereeld hulle in 'n gegewe teks voorkom. Uiteindelik kan sommige karakters net 1 bis neem, terwyl ander 2 bisse, 3 of meer kan neem. Die probleem met veranderlike lengte enkodering is slegs die daaropvolgende dekodering van die volgorde.
Hoe, met kennis van die volgorde van stukkies, dit ondubbelsinnig dekodeer?
Oorweeg die lyn "abacdab". Dit het 8 karakters, en wanneer 'n vaste lengte gekodeer word, sal dit 64 bisse benodig om dit te stoor. Let daarop dat die simbool frekwensie "a", "b", "c" и "D" is gelyk aan 4, 2, 1, 1 onderskeidelik. Kom ons probeer ons voorstel "abacdab" minder stukkies, met behulp van die feit dat "tot" kom meer gereeld voor as "B"En "B" kom meer gereeld voor as "c" и "D". Kom ons begin deur kodering "tot" met een bietjie gelyk aan 0, "B" ons sal 'n twee-bis-kode 11 toeken, en deur drie bisse 100 en 011 te enkodeer "c" и "D".
As gevolg hiervan sal ons kry:
a
0
b
11
c
100
d
011
Dus die lyn "abacdab" ons sal enkodeer as 00110100011011 (0|0|11|0|100|011|0|11)deur die kodes hierbo te gebruik. Die grootste probleem sal egter in dekodering wees. Wanneer ons probeer om die string te dekodeer 00110100011011, kry ons 'n dubbelsinnige resultaat, aangesien dit voorgestel kan word as:
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
...
ens.
Om hierdie dubbelsinnigheid te vermy, moet ons verseker dat ons enkodering voldoen aan so 'n konsep soos voorvoegselreël, wat weer impliseer dat die kodes slegs op een unieke manier gedekodeer kan word. Die voorvoegselreël verseker dat geen kode 'n voorvoegsel van 'n ander is nie. Met kode bedoel ons die bisse wat gebruik word om 'n spesifieke karakter voor te stel. In die voorbeeld hierbo 0 is 'n voorvoegsel 011, wat die voorvoegselreël oortree. Dus, as ons kodes aan die voorvoegselreël voldoen, kan ons uniek dekodeer (en omgekeerd).
Kom ons kyk weer na die voorbeeld hierbo. Hierdie keer sal ons vir simbole toewys "a", "b", "c" и "D" kodes wat aan die voorvoegselreël voldoen.
a
0
b
10
c
110
d
111
Met hierdie enkodering, die string "abacdab" sal geënkodeer word as 00100100011010 (0|0|10|0|100|011|0|10). Maar die 00100100011010 ons sal reeds ondubbelsinnig kan dekodeer en terugkeer na ons oorspronklike string "abacdab".
Huffman-kodering
Noudat ons gehandel het oor veranderlike lengte-enkodering en die voorvoegselreël, kom ons praat oor Huffman-kodering.
Die metode is gebaseer op die skepping van binêre bome. Daarin kan die nodus óf finaal óf intern wees. Aanvanklik word alle nodusse beskou as blare (terminale), wat die simbool self en sy gewig (dit is die frekwensie van voorkoms) verteenwoordig. Die interne nodusse bevat die gewig van die karakter en verwys na twee afstammelinge nodusse. By algemene ooreenkoms, bietjie «0» verteenwoordig na aanleiding van die linker tak, en «1» - aan die regterkant. in volle boom N blare en N-1 interne nodusse. Dit word aanbeveel dat wanneer 'n Huffman-boom gebou word, ongebruikte simbole weggegooi word om optimale lengtekodes te verkry.
Ons sal 'n prioriteitsry gebruik om 'n Huffman-boom te bou, waar die nodus met die laagste frekwensie die hoogste prioriteit sal kry. Die konstruksiestappe word hieronder beskryf:
- Skep 'n blaarknoop vir elke karakter en voeg dit by die prioriteitswaglys.
- Terwyl daar meer as een vel in die tou is, doen die volgende:
- Verwyder die twee nodusse met die hoogste prioriteit (laagste frekwensie) uit die tou;
- Skep 'n nuwe interne nodus, waar hierdie twee nodusse kinders sal wees, en die frekwensie van voorkoms sal gelyk wees aan die som van die frekwensies van hierdie twee nodusse.
- Voeg 'n nuwe nodus by die prioriteitswaglys.
- Die enigste oorblywende nodus sal die wortel wees, en dit sal die bou van die boom voltooi.
Stel jou voor dat ons een of ander teks het wat net uit karakters bestaan "a", "b", "c", "d" и "en", en hul voorkomsfrekwensies is onderskeidelik 15, 7, 6, 6 en 5. Hieronder is illustrasies wat die stappe van die algoritme weerspieël.
'n Pad vanaf die wortel na enige eindknoop sal die optimale voorvoegselkode stoor (ook bekend as die Huffman-kode) wat ooreenstem met die karakter wat met daardie eindknoop geassosieer word.
Huffman boom
Hieronder vind u die implementering van die Huffman-kompressie-algoritme in C++ en 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);
}
}Let wel: die geheue wat deur die invoerstring gebruik word is 47 * 8 = 376 bisse en die geënkodeerde string is slegs 194 bisse m.a.w. data word met ongeveer 48% saamgepers. In die C++-program hierbo gebruik ons die stringklas om die geënkodeerde string te stoor om die program leesbaar te maak.
Omdat doeltreffende prioriteitswagdatastrukture per invoeging vereis word O(log(N)) tyd, maar in 'n volledige binêre boom met N blare teenwoordig 2N-1 nodes, en die Huffman-boom is 'n volledige binêre boom, dan loop die algoritme in O(Nlog(N)) tyd, waar N - Karakters.
Bronne:
Bron: will.com