Inden kursusstart udarbejdet en oversættelse af et andet nyttigt materiale til dig.
Huffman-kodning er en datakomprimeringsalgoritme, der formulerer den grundlæggende idé om filkomprimering. I denne artikel vil vi tale om kodning med fast og variabel længde, unikt afkodbare koder, præfiksregler og opbygning af et Huffman-træ.
Vi ved, at hvert tegn er gemt som en sekvens af 0'er og 1'er og fylder 8 bit. Dette kaldes kodning med fast længde, fordi hvert tegn bruger det samme faste antal bits til at gemme.
Lad os sige, at vi får tekst. Hvordan kan vi reducere mængden af plads, der kræves for at gemme et enkelt tegn?
Hovedideen er kodning med variabel længde. Vi kan bruge det faktum, at nogle tegn i teksten forekommer oftere end andre () for at udvikle en algoritme, der vil repræsentere den samme sekvens af tegn i færre bits. Ved kodning med variabel længde tildeler vi tegn et variabelt antal bits, afhængigt af hvor ofte de optræder i en given tekst. Til sidst kan nogle tegn tage så lidt som 1 bit, mens andre kan tage 2 bits, 3 eller mere. Problemet med kodning med variabel længde er kun den efterfølgende afkodning af sekvensen.
Hvordan, ved at kende sekvensen af bit, afkode det utvetydigt?
Overvej linjen "abacdab". Den har 8 tegn, og når den koder en fast længde, skal den bruge 64 bit for at gemme den. Bemærk, at symbolfrekvensen "a", "b", "c" и "D" er lig med henholdsvis 4, 2, 1, 1. Lad os prøve at forestille os "abacdab" færre bits, ved at bruge det faktum, at "til" forekommer hyppigere end "B"Og "B" forekommer hyppigere end "c" и "D". Lad os starte med at kode "til" med en bit lig med 0, "B" vi vil tildele en to-bit kode 11, og ved at bruge tre bit 100 og 011 vil vi kode "c" и "D".
Som et resultat vil vi få:
a
0
b
11
c
100
d
011
Så linjen "abacdab" vi vil kode som 00110100011011 (0|0|11|0|100|011|0|11)ved hjælp af koderne ovenfor. Hovedproblemet vil dog være i afkodningen. Når vi forsøger at afkode strengen 00110100011011, vil vi få et tvetydigt resultat, da det kan repræsenteres 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
...
etc.
For at undgå denne tvetydighed skal vi sikre, at vores kodning opfylder et sådant koncept som præfiksregel, hvilket igen indebærer, at koderne kun kan afkodes på én unik måde. Præfiksreglen sikrer, at ingen kode er præfiks for en anden. Med kode mener vi de bits, der bruges til at repræsentere et bestemt tegn. I eksemplet ovenfor 0 er et præfiks 011, som overtræder præfiksreglen. Så hvis vores koder opfylder præfiksreglen, så kan vi entydigt afkode (og omvendt).
Lad os gense eksemplet ovenfor. Denne gang vil vi tildele symboler "a", "b", "c" и "D" koder, der opfylder præfiksreglen.
a
0
b
10
c
110
d
111
Med denne kodning, strengen "abacdab" vil blive kodet som 00100100011010 (0|0|10|0|100|011|0|10). Men 00100100011010 vi vil allerede være i stand til entydigt at afkode og vende tilbage til vores oprindelige streng "abacdab".
Huffman kodning
Nu hvor vi har behandlet kodning med variabel længde og præfiksreglen, lad os tale om Huffman-kodning.
Metoden er baseret på skabelsen af binære træer. I den kan noden enten være endelig eller intern. I starten betragtes alle noder som blade (terminaler), som repræsenterer selve symbolet og dets vægt (det vil sige hyppigheden af forekomst). De interne noder indeholder karakterens vægt og henviser til to efterkommerknuder. Efter almindelig aftale, lidt "0" repræsenterer efter den venstre gren, og "1" - til højre. i fuldt træ N blade og N-1 interne knudepunkter. Det anbefales, at når man konstruerer et Huffman-træ, kasseres ubrugte symboler for at opnå optimale længdekoder.
Vi vil bruge en prioritetskø til at bygge et Huffman-træ, hvor noden med den laveste frekvens vil få den højeste prioritet. Konstruktionstrinnene er beskrevet nedenfor:
- Opret en bladnode for hver karakter og føj dem til prioritetskøen.
- Mens der er mere end ét ark i køen, skal du gøre følgende:
- Fjern de to noder med den højeste prioritet (laveste frekvens) fra køen;
- Opret en ny intern node, hvor disse to noder vil være børn, og hyppigheden af forekomst vil være lig med summen af frekvenserne af disse to noder.
- Tilføj en ny node til prioritetskøen.
- Den eneste tilbageværende knude vil være roden, og dette vil fuldende konstruktionen af træet.
Forestil dig, at vi har noget tekst, der kun består af tegn "a", "b", "c", "d" и "og", og deres forekomstfrekvenser er henholdsvis 15, 7, 6, 6 og 5. Nedenfor er illustrationer, der afspejler algoritmens trin.
En sti fra roden til en hvilken som helst endeknude vil gemme den optimale præfikskode (også kendt som Huffman-koden), der svarer til det tegn, der er knyttet til den endeknude.
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;
// 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);
}
}Note: hukommelsen brugt af inputstrengen er 47 * 8 = 376 bit og den kodede streng er kun 194 bit dvs. data er komprimeret med omkring 48 %. I C++ programmet ovenfor bruger vi strengklassen til at gemme den kodede streng for at gøre programmet læsbart.
Fordi effektive prioritetskødatastrukturer kræver pr. indsættelse O(log(N)) tid, men i et komplet binært træ med N blade til stede 2N-1 noder, og Huffman-træet er et komplet binært træ, så kører algoritmen ind O(Nlog(N)) tid, hvor N - Karakterer.
Kilder:
Kilde: www.habr.com