Før kursstart forberedt for deg en oversettelse av et annet nyttig materiale.
Huffman-koding er en datakomprimeringsalgoritme som formulerer den grunnleggende ideen om filkomprimering. I denne artikkelen vil vi snakke om koding med fast og variabel lengde, unikt dekodbare koder, prefiksregler og å bygge et Huffman-tre.
Vi vet at hvert tegn er lagret som en sekvens av 0-er og 1-er og tar opp 8 biter. Dette kalles koding med fast lengde fordi hvert tegn bruker det samme faste antallet biter å lagre.
La oss si at vi har en tekst. Hvordan kan vi redusere mengden plass som kreves for å lagre et enkelt tegn?
Hovedideen er koding med variabel lengde. Vi kan bruke det faktum at noen tegn i teksten forekommer oftere enn andre () for å utvikle en algoritme som vil representere den samme sekvensen av tegn i færre biter. Ved koding med variabel lengde tildeler vi tegn et variabelt antall biter, avhengig av hvor ofte de vises i en gitt tekst. Til slutt kan noen tegn ta så lite som 1 bit, mens andre kan ta 2 biter, 3 eller mer. Problemet med koding med variabel lengde er bare den påfølgende dekodingen av sekvensen.
Hvordan, ved å kjenne sekvensen av biter, dekode den utvetydig?
Vurder linjen "abacdab". Den har 8 tegn, og når du koder en fast lengde, trenger den 64 biter for å lagre den. Merk at symbolfrekvensen "a", "b", "c" и "D" tilsvarer henholdsvis 4, 2, 1, 1. La oss prøve å forestille oss "abacdab" færre biter, ved å bruke det faktum at "til" forekommer oftere enn "B"Og "B" forekommer oftere enn "c" и "D". La oss starte med å kode "til" med en bit lik 0, "B" vi vil tilordne en to-bits kode 11, og ved å bruke tre bits 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 å bruke kodene ovenfor. Hovedproblemet vil imidlertid være i dekoding. Når vi prøver å dekode strengen 00110100011011, vil vi få et tvetydig resultat, siden det kan representeres 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 å unngå denne tvetydigheten må vi sørge for at vår koding tilfredsstiller et slikt konsept som prefiksregel, som igjen innebærer at kodene kun kan dekodes på én unik måte. Prefiksregelen sikrer at ingen kode er et prefiks til en annen. Med kode mener vi bitene som brukes til å representere et bestemt tegn. I eksemplet ovenfor 0 er et prefiks 011, som bryter med prefiksregelen. Så hvis kodene våre tilfredsstiller prefiksregelen, kan vi unikt dekode (og omvendt).
La oss se på eksemplet ovenfor. Denne gangen vil vi tildele for symboler "a", "b", "c" и "D" koder som tilfredsstiller prefiksregelen.
a
0
b
10
c
110
d
111
Med denne kodingen, strengen "abacdab" vil bli kodet som 00100100011010 (0|0|10|0|100|011|0|10). Men 00100100011010 vi vil allerede være i stand til entydig å dekode og gå tilbake til vår opprinnelige streng "abacdab".
Huffman-koding
Nå som vi har behandlet variabel lengdekoding og prefiksregelen, la oss snakke om Huffman-koding.
Metoden er basert på opprettelsen av binære trær. I den kan noden enten være endelig eller intern. Til å begynne med regnes alle noder som blader (terminaler), som representerer selve symbolet og dets vekt (det vil si hyppigheten av forekomst). De interne nodene inneholder vekten av karakteren og refererer til to etterkommernoder. Etter generell avtale, litt "0" representerer følgende venstre gren, og "1" - til høyre. i fullt tre N blader og N-1 interne noder. Det anbefales at når du konstruerer et Huffman-tre, kasseres ubrukte symboler for å oppnå optimale lengdekoder.
Vi vil bruke en prioritetskø for å bygge et Huffman-tre, hvor noden med lavest frekvens vil bli gitt høyest prioritet. Byggetrinnene er beskrevet nedenfor:
- Lag en bladnode for hver karakter og legg dem til i prioritetskøen.
- Mens det er mer enn ett ark i køen, gjør du følgende:
- Fjern de to nodene med høyest prioritet (laveste frekvens) fra køen;
- Lag en ny intern node, hvor disse to nodene vil være barn, og frekvensen av forekomst vil være lik summen av frekvensene til disse to nodene.
- Legg til en ny node i prioritetskøen.
- Den eneste gjenværende noden vil være roten, og dette vil fullføre konstruksjonen av treet.
Tenk deg at vi har en tekst som kun består av tegn "a", "b", "c", "d" и "og", og deres forekomstfrekvenser er henholdsvis 15, 7, 6, 6 og 5. Nedenfor er illustrasjoner som gjenspeiler trinnene til algoritmen.
En bane fra roten til en hvilken som helst endenode vil lagre den optimale prefikskoden (også kjent som Huffman-koden) som tilsvarer tegnet knyttet til den endenoden.
Huffman-tre
Nedenfor finner du implementeringen av 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);
}
}Merk: minnet som brukes av inngangsstrengen er 47 * 8 = 376 biter og den kodede strengen er bare 194 biter, dvs. data er komprimert med omtrent 48 %. I C++-programmet ovenfor bruker vi strengklassen for å lagre den kodede strengen for å gjøre programmet lesbart.
Fordi effektive prioriterte kødatastrukturer krever per innsetting O(log(N)) tid, men i et komplett binært tre med N blader tilstede 2N-1 noder, og Huffman-treet er et komplett binært tre, så kjører algoritmen inn O(Nlog(N)) tid, hvor N - Tegn.
Kilder:
Kilde: www.habr.com