Innan kursstart förberett för dig en översättning av ett annat användbart material.
Huffman-kodning är en datakomprimeringsalgoritm som formulerar grundidén för filkomprimering. I den här artikeln kommer vi att prata om kodning med fast och variabel längd, unikt avkodningsbara koder, prefixregler och att bygga ett Huffman-träd.
Vi vet att varje tecken lagras som en sekvens av 0:or och 1:or och tar upp 8 bitar. Detta kallas kodning med fast längd eftersom varje tecken använder samma fasta antal bitar att lagra.
Låt oss säga att vi får text. Hur kan vi minska mängden utrymme som krävs för att lagra ett enda tecken?
Huvudidén är kodning med variabel längd. 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 teckensekvens i färre bitar. Vid kodning med variabel längd tilldelar vi tecken ett variabelt antal bitar, beroende på hur ofta de förekommer i en given text. Så småningom kan vissa tecken ta så lite som 1 bit, medan andra kan ta 2 bitar, 3 eller mer. Problemet med kodning med variabel längd är endast den efterföljande avkodningen av sekvensen.
Hur, genom att känna till sekvensen av bitar, avkoda den entydigt?
Tänk på linjen "abacdab". Den har 8 tecken, och när du kodar en fast längd behöver den 64 bitar för att lagra den. Observera att symbolfrekvensen "a", "b", "c" и "D" är lika med 4, 2, 1, 1 respektive. Låt oss försöka föreställa oss "abacdab" färre bitar, med det faktum att "till" förekommer oftare än "B"Och "B" förekommer oftare än "c" и "D". Låt oss börja med att koda "till" med en bit lika med 0, "B" vi kommer att tilldela en två-bitars kod 11, och med tre bitar 100 och 011 kommer vi att koda "c" и "D".
Som ett resultat kommer vi att få:
a
0
b
11
c
100
d
011
Linjen alltså "abacdab" vi kommer att koda som 00110100011011 (0|0|11|0|100|011|0|11)med koderna ovan. Det största problemet kommer dock att vara i avkodningen. När vi försöker avkoda strängen 00110100011011, får vi ett tvetydigt resultat, eftersom det 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
.
etc.
För att undvika denna tvetydighet måste vi se till att vår kodning uppfyller ett sådant koncept som prefixregel, vilket i sin tur innebär att koderna endast kan avkodas på ett unikt sätt. Prefixregeln säkerställer att ingen kod är ett prefix till en annan. Med kod menar vi de bitar som används för att representera ett visst tecken. I exemplet ovan 0 är ett prefix 011, vilket bryter mot prefixregeln. Så, om våra koder uppfyller prefixregeln, kan vi unikt avkoda (och vice versa).
Låt oss återgå till exemplet ovan. Den här gången kommer vi att tilldela symboler "a", "b", "c" и "D" koder som uppfyller prefixregeln.
a
0
b
10
c
110
d
111
Med denna kodning, strängen "abacdab" kommer att kodas som 00100100011010 (0|0|10|0|100|011|0|10). Men 00100100011010 vi kommer redan att kunna entydigt avkoda och återgå till vår ursprungliga sträng "abacdab".
Huffman kodning
Nu när vi har behandlat kodning med variabel längd och prefixregeln, låt oss prata om Huffman-kodning.
Metoden bygger på skapandet av binära träd. I den kan noden vara antingen slutlig eller intern. Inledningsvis betraktas alla noder som löv (terminaler), som representerar själva symbolen och dess vikt (det vill säga förekomstens frekvens). De interna noderna innehåller karaktärens vikt och hänvisar till två efterkommande noder. Enligt allmän överenskommelse, lite "0" representerar efter den vänstra grenen, och "1" - till höger. i fullt träd N blad och N-1 interna noder. Vid konstruktion av ett Huffman-träd rekommenderas att oanvända symboler kasseras för att få optimala längdkoder.
Vi kommer att använda en prioritetskö för att bygga ett Huffman-träd, där noden med lägst frekvens kommer att ges högst prioritet. Konstruktionsstegen beskrivs nedan:
- Skapa en lövnod för varje karaktär och lägg till dem i prioritetskön.
- Medan det finns mer än ett ark i kön gör du följande:
- Ta bort de två noderna med högsta prioritet (lägsta frekvens) från kön;
- Skapa en ny intern nod, där dessa två noder kommer att vara barn, och förekomstfrekvensen kommer att vara lika med summan av frekvenserna för dessa två noder.
- Lägg till en ny nod i prioritetskön.
- Den enda återstående noden kommer att vara roten, och detta kommer att slutföra konstruktionen av trädet.
Föreställ dig att vi har någon text som bara består av tecken "a", "b", "c", "d" и "och", och deras förekomstfrekvenser är 15, 7, 6, 6 respektive 5. Nedan finns illustrationer som återspeglar stegen i algoritmen.
En sökväg från roten till valfri ändnod kommer att lagra den optimala prefixkoden (även känd som Huffman-koden) som motsvarar tecknet som är associerat med den ändnoden.
Huffman träd
Nedan hittar du implementeringen av Huffmans komprimeringsalgoritm i 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;
// 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);
}
}Notera: minnet som används av ingångssträngen är 47 * 8 = 376 bitar och den kodade strängen är endast 194 bitar, dvs. data komprimeras med cirka 48 %. I C++-programmet ovan använder vi strängklassen för att lagra den kodade strängen för att göra programmet läsbart.
Eftersom effektiva prioriterade ködatastrukturer kräver per infogning O(log(N)) tid, men i ett komplett binärt träd med N blad närvarande 2N-1 noder, och Huffman-trädet är ett komplett binärt träd, då körs algoritmen in O(Nlog(N)) tid, var N - Tecken.
Källor:
Källa: will.com