Voor aanvang van de cursus heeft voor u een vertaling gemaakt van ander nuttig materiaal.
Huffman-codering is een algoritme voor gegevenscompressie dat het basisidee van bestandscompressie formuleert. In dit artikel zullen we het hebben over codering met vaste en variabele lengte, uniek decodeerbare codes, prefixregels en het bouwen van een Huffman-boom.
We weten dat elk teken wordt opgeslagen als een reeks van nullen en enen en 0 bits in beslag neemt. Dit wordt codering met vaste lengte genoemd omdat elk teken hetzelfde vaste aantal bits gebruikt om op te slaan.
Laten we zeggen dat we tekst krijgen. Hoe kunnen we de hoeveelheid ruimte verminderen die nodig is om een enkel teken op te slaan?
Het belangrijkste idee is codering met variabele lengte. We kunnen gebruik maken van het feit dat sommige karakters in de tekst vaker voorkomen dan andere () om een algoritme te ontwikkelen dat dezelfde tekenreeks in minder bits weergeeft. Bij codering met variabele lengte kennen we karakters een variabel aantal bits toe, afhankelijk van hoe vaak ze voorkomen in een bepaalde tekst. Uiteindelijk kunnen sommige tekens slechts 1 bit nodig hebben, terwijl andere 2 bits, 3 of meer nodig hebben. Het probleem met codering met variabele lengte is alleen de daaropvolgende decodering van de reeks.
Hoe, wetende de volgorde van bits, deze ondubbelzinnig decoderen?
Overweeg de lijn "abacdab". Het heeft 8 tekens en bij het coderen van een vaste lengte heeft het 64 bits nodig om het op te slaan. Merk op dat de symboolfrequentie "a", "b", "c" и "NS" is gelijk aan respectievelijk 4, 2, 1, 1. Laten we proberen ons voor te stellen "abacdab" minder bits, gebruikmakend van het feit dat "naar" komt vaker voor dan "B"En "B" komt vaker voor dan "tegen" и "NS". Laten we beginnen met coderen "naar" met één bit gelijk aan 0, "B" we zullen een twee-bits code 11 toewijzen, en met drie bits 100 en 011 zullen we coderen "tegen" и "NS".
Als resultaat krijgen we:
a
0
b
11
c
100
d
011
De lijn dus "abacdab" we zullen coderen als 00110100011011 (0|0|11|0|100|011|0|11)met behulp van bovenstaande codes. Het grootste probleem zal echter het decoderen zijn. Wanneer we proberen de string te decoderen 00110100011011, krijgen we een dubbelzinnig resultaat, omdat het kan worden weergegeven 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
...
etc.
Om deze dubbelzinnigheid te voorkomen, moeten we ervoor zorgen dat onze codering voldoet aan een concept als voorvoegsel regel, wat weer inhoudt dat de codes maar op één unieke manier kunnen worden gedecodeerd. De prefix-regel zorgt ervoor dat geen enkele code een prefix is van een andere. Met code bedoelen we de bits die worden gebruikt om een bepaald teken weer te geven. In het bovenstaande voorbeeld 0 is een voorvoegsel 011, wat in strijd is met de prefix-regel. Dus als onze codes voldoen aan de prefix-regel, kunnen we uniek decoderen (en vice versa).
Laten we het bovenstaande voorbeeld nog eens bekijken. Deze keer zullen we symbolen toewijzen "a", "b", "c" и "NS" codes die voldoen aan de prefix-regel.
a
0
b
10
c
110
d
111
Met deze codering wordt de string "abacdab" zal worden gecodeerd als 00100100011010 (0|0|10|0|100|011|0|10). Maar de 00100100011010 we zullen al in staat zijn om ondubbelzinnig te decoderen en terug te keren naar onze originele string "abacdab".
Huffman-codering
Nu we het hebben gehad over codering met variabele lengte en de prefixregel, laten we het hebben over Huffman-codering.
De methode is gebaseerd op het maken van binaire bomen. Daarin kan het knooppunt definitief of intern zijn. Aanvankelijk worden alle knooppunten beschouwd als bladeren (terminals), die het symbool zelf en zijn gewicht (dat wil zeggen de frequentie van voorkomen) vertegenwoordigen. De interne knooppunten bevatten het gewicht van het teken en verwijzen naar twee onderliggende knooppunten. In algemene overeenstemming, beetje «0» vertegenwoordigt het volgen van de linker tak, en «1» - aan de rechterkant. in volle boom N bladeren en N-1 interne knooppunten. Het wordt aanbevolen dat bij het construeren van een Huffman-boom ongebruikte symbolen worden weggegooid om optimale lengtecodes te verkrijgen.
We zullen een prioriteitswachtrij gebruiken om een Huffman-boom te bouwen, waarbij het knooppunt met de laagste frequentie de hoogste prioriteit krijgt. De bouwstappen worden hieronder beschreven:
- Maak een bladknooppunt voor elk personage en voeg ze toe aan de prioriteitswachtrij.
- Als er meer dan één blad in de wachtrij staat, doet u het volgende:
- Verwijder de twee nodes met de hoogste prioriteit (laagste frequentie) uit de wachtrij;
- Maak een nieuw intern knooppunt, waar deze twee knooppunten kinderen zullen zijn, en de frequentie van voorkomen zal gelijk zijn aan de som van de frequenties van deze twee knooppunten.
- Voeg een nieuw knooppunt toe aan de prioriteitswachtrij.
- Het enige overgebleven knooppunt zal de wortel zijn, en dit zal de constructie van de boom voltooien.
Stel je voor dat we tekst hebben die alleen uit tekens bestaat "a", "b", "c", "d" и "en", en hun frequenties zijn respectievelijk 15, 7, 6, 6 en 5. Hieronder staan illustraties die de stappen van het algoritme weergeven.
Een pad van de root naar een willekeurig eindknooppunt slaat de optimale prefixcode op (ook bekend als de Huffman-code) die overeenkomt met het teken dat aan dat eindknooppunt is gekoppeld.
Huffman-boom
Hieronder vindt u de implementatie van het Huffman-compressie-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);
}
}Opmerking: het geheugen dat wordt gebruikt door de invoerreeks is 47 * 8 = 376 bits en de gecodeerde reeks is slechts 194 bits, d.w.z. gegevens worden met ongeveer 48% gecomprimeerd. In het bovenstaande C++-programma gebruiken we de stringklasse om de gecodeerde string op te slaan om het programma leesbaar te maken.
Omdat per invoeging efficiënte wachtrijgegevensstructuren nodig zijn O(logboek(N)) tijd, maar in een complete binaire boom met N bladeren aanwezig 2N-1 knooppunten, en de Huffman-boom is een complete binaire boom, dan wordt het algoritme uitgevoerd O(Nlog(N)) tijd, waar N - Karakters.
Bronnen:
Bron: www.habr.com