Ennen kurssin alkua valmisti sinulle käännöksen toisesta hyödyllisestä materiaalista.
Huffman-koodaus on tietojen pakkausalgoritmi, joka muotoilee tiedostojen pakkaamisen perusidean. Tässä artikkelissa puhumme kiinteästä ja muuttuvamittaisesta koodauksesta, yksilöllisesti purettavissa olevista koodeista, etuliitesäännöistä ja Huffman-puun rakentamisesta.
Tiedämme, että jokainen merkki on tallennettu 0:n ja 1:n sekvenssinä ja vie 8 bittiä. Tätä kutsutaan kiinteäpituiseksi koodaukseksi, koska jokainen merkki käyttää samaa kiinteää määrää bittejä tallentamiseen.
Oletetaan, että meille annetaan tekstiä. Kuinka voimme vähentää yhden merkin tallentamiseen tarvittavaa tilaa?
Pääideana on muuttuvapituinen koodaus. Voimme käyttää sitä tosiasiaa, että jotkut tekstin merkit esiintyvät useammin kuin toiset () kehittääksesi algoritmin, joka edustaa samaa merkkijonoa pienemmillä biteillä. Vaihtuvapituisessa koodauksessa määritämme merkit vaihtelevan määrän bittejä riippuen siitä, kuinka usein ne esiintyvät tietyssä tekstissä. Lopulta jotkut merkit voivat kestää vain 1 bitin, kun taas toiset voivat kestää 2 bittiä, 3 tai enemmän. Vaihtuvapituisen koodauksen ongelma on vain sekvenssin myöhempi dekoodaus.
Kuinka purkaa se yksiselitteisesti, kun tiedät bittisekvenssin?
Harkitse linjaa "abacdab". Siinä on 8 merkkiä, ja kiinteän pituuden koodattaessa se tarvitsee 64 bittiä sen tallentamiseen. Huomaa, että symbolitaajuus "a", "b", "c" и "D" on vastaavasti 4, 2, 1, 1. Yritetään kuvitella "abacdab" vähemmän bittejä käyttämällä sitä tosiasiaa "kohteeseen" esiintyy useammin kuin "B"Ja "B" esiintyy useammin kuin "vs" и "D". Aloitetaan koodaamalla "kohteeseen" jossa yksi bitti on yhtä suuri kuin 0, "B" annamme kaksibittisen koodin 11, ja käytämme kolmea bittiä 100 ja 011 koodaamme "vs" и "D".
Tuloksena saamme:
a
0
b
11
c
100
d
011
Joten linja "abacdab" koodaamme nimellä 00110100011011 (0|0|11|0|100|011|0|11)käyttämällä yllä olevia koodeja. Suurin ongelma tulee kuitenkin olemaan dekoodauksessa. Kun yritämme purkaa merkkijonoa 00110100011011, saamme epäselvän tuloksen, koska se voidaan esittää seuraavasti:
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
...
jne.
Tämän epäselvyyden välttämiseksi meidän on varmistettava, että koodauksemme täyttää sellaisen käsitteen kuin etuliitteen sääntö, mikä puolestaan tarkoittaa, että koodit voidaan purkaa vain yhdellä ainutlaatuisella tavalla. Etuliitesääntö varmistaa, että mikään koodi ei ole toisen etuliite. Koodilla tarkoitamme bittejä, joita käytetään edustamaan tiettyä merkkiä. Yllä olevassa esimerkissä 0 on etuliite 011, mikä rikkoo etuliitesääntöä. Joten, jos koodimme täyttävät etuliitesäännön, voimme purkaa yksilöllisesti (ja päinvastoin).
Katsotaanpa uudelleen yllä olevaa esimerkkiä. Tällä kertaa jaamme symboleja "a", "b", "c" и "D" koodit, jotka täyttävät etuliitesäännön.
a
0
b
10
c
110
d
111
Tällä koodauksella merkkijono "abacdab" koodataan muodossa 00100100011010 (0|0|10|0|100|011|0|10). Mutta 00100100011010 voimme jo purkaa yksiselitteisesti ja palata alkuperäiseen merkkijonoamme "abacdab".
Huffman koodaus
Nyt kun olemme käsitelleet muuttuvapituista koodausta ja etuliitesääntöä, puhutaan Huffman-koodauksesta.
Menetelmä perustuu binääripuiden luomiseen. Siinä solmu voi olla joko lopullinen tai sisäinen. Aluksi kaikkia solmuja pidetään lehtinä (päätteinä), jotka edustavat itse symbolia ja sen painoa (eli esiintymistiheyttä). Sisäiset solmut sisältävät merkin painon ja viittaavat kahteen jälkeläiseen solmuun. Yleisellä sopimuksella vähän «0» edustaa vasemman haaran seuraamista, ja «1» - oikealla. täydessä puussa N lehdet ja N-1 sisäiset solmut. On suositeltavaa, että Huffman-puuta rakennettaessa käyttämättömät symbolit hylätään optimaalisen pituuskoodin saamiseksi.
Käytämme prioriteettijonoa Huffman-puun rakentamiseen, jossa alhaisimman taajuuden omaava solmu saa korkeimman prioriteetin. Rakentamisen vaiheet on kuvattu alla:
- Luo lehtisolmu jokaiselle merkille ja lisää ne prioriteettijonoon.
- Kun jonossa on useampi kuin yksi arkki, toimi seuraavasti:
- Poista kaksi solmua, joilla on korkein prioriteetti (matalin taajuus) jonosta;
- Luo uusi sisäinen solmu, jossa nämä kaksi solmua ovat lapsia, ja esiintymistiheys on yhtä suuri kuin näiden kahden solmun taajuuksien summa.
- Lisää uusi solmu prioriteettijonoon.
- Ainoa jäljellä oleva solmu on juuri, ja tämä viimeistelee puun rakentamisen.
Kuvittele, että meillä on tekstiä, joka koostuu vain merkeistä "a", "b", "c", "d" и "ja", ja niiden esiintymistiheydet ovat vastaavasti 15, 7, 6, 6 ja 5. Alla on kuvat, jotka kuvastavat algoritmin vaiheita.
Polku juuresta mihin tahansa päätesolmuun tallentaa optimaalisen etuliitekoodin (tunnetaan myös nimellä Huffman-koodi), joka vastaa kyseiseen päätesolmuun liittyvää merkkiä.
Huffman puu
Alta löydät Huffman-pakkausalgoritmin toteutuksen C++:ssa ja Javassa:
#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);
}
}Huom: syötemerkkijonon käyttämä muisti on 47 * 8 = 376 bittiä ja koodattu merkkijono on vain 194 bittiä eli. tiedot pakataan noin 48 %. Yllä olevassa C++-ohjelmassa käytämme merkkijonoluokkaa tallentamaan koodatun merkkijonon, jotta ohjelma olisi luettavissa.
Koska tehokkaat prioriteettijonotietorakenteet vaativat lisäystä kohti O(log(N)) aikaa, mutta täydellisessä binääripuussa N lehdet läsnä 2N-1 solmuja, ja Huffman-puu on täydellinen binääripuu, niin algoritmi ajaa sisään O(Nlog(N)) aika, missä N - Hahmot.
Lähteet:
Lähde: will.com