Kursuse alguse eelõhtul oleme koostanud teile tõlke veel ühest kasulikust materjalist.
Huffmani kodeerimine on andmete tihendamise algoritm, mille põhiteema on failide tihendamine. Selles artiklis arutleme fikseeritud ja muutuva pikkusega kodeerimise, unikaalselt dekodeeritavate koodide, prefiksireeglite ja Huffmani puu ülesehituse üle.
Teame, et iga sümbol salvestatakse 0 ja 1 järjekordadena ning selleks kulub 8 bitti. Seda nimetatakse fikseeritud pikkusega kodeerimiseks, kuna iga sümbol kasutab salvestamiseks sama fikseeritud arvu bitte.
Oletame, et meil on tekst. Kuidas me saame vähendada ühe sümboli salvestamiseks vajaliku ruumi hulka?
Põhijõud peitub muutuva pikkusega kodeerimises. Saame kasutada fakti, et mõned sümbolid esinevad tekstis sagedamini kui teised (), et lõppkokkuvõttes arendada algoritmi, mis võiks esitada sama sümbolite järjestuse väiksema arvu bittidega. Muutuva pikkusega kodeerimisel määrame sümbolitele erineva arvu bitte sõltuvalt nende esinemissagedusest antud tekstis. Lõppkokkuvõttes võivad mõned sümbolid võtta vaid 1 biti, teised 2 bitti, 3 või rohkem. Muutuva pikkusega kodeerimise probleem seisneb vaid sellele järgnevates dekodeerimisprotsessides.
Kuidas, teades bitijärjestust, seda üheselt dekodeerida?
Vaatleme järgnevat stringi «aabacdab». Selles on 8 sümbolit ja fikseeritud pikkusega kodeerimise korral on selle salvestamiseks vajalik 64 bitti. Tõdeme, et sümbolite esinemissagedus on «a», «b», «c» ja «d» vastavalt 4, 2, 1, 1. Proovime esitada «aabacdab» väiksema arvu bittidega, kasutades fakti, et «a» esindab sagedamini kui «b»., ja «b». esindab sagedamini kui «c» ja «d»Alustame sellest, et kodeerime «a» ühe bitiga, mis on 0, «b». me määrame kahebitise koodi 11, ning kolme bittiga kodeerime 100 ja 011. «c» ja «d».
Lõppkokkuvõttes saame:
a
0
b
11
c
100
d
011
Nii saame stringi «aabacdab» kodeeritud järgmiseks 00110100011011 (0|0|11|0|100|011|0|11), kasutades eespool esitatud koode. Kuid peamine probleem jääb dekodeerimisega seoses. Kui proovime dekodeerida stringi 00110100011011, saame ebaselge tulemuse, sest seda saab esitada järgmiselt:
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
…
Kui kaua aega kulub väljastamiseks?
Selle ebaselguse vältimiseks peame tagama, et meie kodeerimine vastab sellisele mõistele nagu eesmärgireegel, mis omakorda eeldab, et koode saab dekodeerida ainult ühe ainulaadse viisi järgi. Eesmärgireegel tagab, et ükski kood ei ole teise eelmäng. Koodina mõtleme bitid, mida kasutatakse konkreetse sümboli esindamiseks. Ülaltoodud näites 0 – on eelmäng 011, mis rikub eesmärgireeglit. Nii et kui meie koodid vastavad eesmärgireeglile, on dekodeerimine üheselt mõistetav (ja vastupidi).
Vaatame ülaltoodud näidet uuesti. Seekord määrame sümbolitele «a», «b», «c» ja «d» koodid, mis vastavad eesmärgireeglile.
a
0
b
10
c
110
d
111
Kasutades sellist kodeerimist, string «aabacdab» kodeeritakse kui 00100100011010 (0|0|10|0|100|011|0|10). Ja siin 00100100011010 me saame nüüd üheselt dekodeerida ja naasta meie algse stringi juurde «aabacdab».
Huffman'i kodeerimine
Nüüd, kui oleme aru saanud muutuva pikkuse kodeerimisest ja prefiksi reeglist, räägime Huffmani kodeerimisest.
Meetod põhineb binaarstite loomisel. Selles võib sõlm olla kas leht või sisemine. Alguses peetakse kõiki sõlmi lehtedeks (lõplikud), mis esindavad ise sümbolit ja selle kaalu (st esinemissagedust). Sise-sõlmed sisaldavad sümboli kaalu ja viitavad kahele alamsõlmele. Üldiselt tähistab bit „0“ seda, et liigeldakse vasakule harule, ja „1“ paremale. Täielikus puus on N lehti ja N-1 sisemist sõlme. Soovitatav on Huffmani puu ehitamisel kõrvaldada kasutamata sümbolid, et saada optimaalse pikkusega koode.
Me kasutame prioriteetide järjekorda Huffmani puu ehitamiseks, kus madalama sagedusega sõlmele antakse kõrgeim prioriteet. Allpool on toodud ehitamise sammud:
- Looge iga sümboli jaoks leht-sõlm ja lisage need prioriteetide järjekorda.
- Kuni järjekorras on rohkem kui üks leht, teeme järgmist:
- Eemaldage järjekorrast kaks kõrgeima prioriteediga sõlme (madalaima sagedusega).
- Looge uus sisemine sõlm, kus need kaks sõlme on lasteks ja esinemise sagedus on nende kahe sõlme sageduste summa.
- Lisage järjekorda uus prioriteedi sõlm.
- Ainus jäänud sõlm saab olema juursõlm, sellega lõppeb puu ehitamine.
Kujutage ette, et meil on tekst, mis koosneb ainult sümbolitest „a“, „b“, „c“, „d“ ja „e“, ja nende esinemissagedused on vastavalt 15, 7, 6, 6 ja 5. Allpool on illustratsioonid, mis kajastavad algoritmi samme.
Teel juurest igasse lehtsõlme salvestatakse optimaalse prefiksikood (tuntud ka kui Huffmani kood), mis vastab selle lehtsõlmega seotud sümbolile.
Huffmani puu
Allpool leiate Huffmani tihendamisalgoritmi rakenduse keeltes C++ ja 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;
// Puu sõlm
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
{
// Rändab Huffmani puu ja salvestab Huffmani koodid
// kaardile.
public static void encode(Node root, String str,
Map<Character, String> huffmanCode)
{
if (root == null)
return;
// lehtsõlm leitud
if (root.left == null && root.right == null) {
huffmanCode.put(root.ch, str);
}
encode(root.left, str + "0", huffmanCode);
encode(root.right, str + "1", huffmanCode);
}
// Rändab Huffmani puu ja dekodeerib kodeeritud stringi
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// lehtsõlm leitud
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;
}
// Koostab Huffmani puu ja huffmanCode ning dekodeerib antud sisendi teksti
public static void buildHuffmanTree(String text)
{
// arvestab iga tähe esinemissagedust
// ja salvestab selle kaardile
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);
}
// Loob prioriteedi järjekorra elavate sõlmede jaoks Huffmani puus
// Pane tähele, et kõrgeima prioriteedi objektil on madalaim sagedus
PriorityQueue<Node> pq = new PriorityQueue<>(
(l, r) -> l.freq - r.freq);
// Loob iga tähe jaoks lehtsõlme ja lisab selle
// prioriteedi järjekorda.
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
// tee, kuni järjekorras on rohkem kui üks sõlm
while (pq.size() != 1)
{
// Eemaldab kaks kõrgeima prioriteediga sõlme
// (madalaim sagedus) järjekorrast
Node left = pq.poll();
Node right = pq.poll();
// Loob uue sisemise sõlme nende kahe sõlme lapsena
// ja sagedusega, mis on võrreldav kahe sõlme
// sageduste summaga. Lisa uus sõlm prioriteedi järjekorda.
int sum = left.freq + right.freq;
pq.add(new Node(' ', sum, left, right));
}
// juur salvestab viidet Huffmani puu juurele
Node root = pq.peek();
// Rändab Huffmani puu ja salvestab Huffmani koodid kaardile
Map<Character, String> huffmanCode = new HashMap<>();
encode(root, "", huffmanCode);
// prindib Huffmani koodid
System.out.println("Huffmani koodid on: n");
for (Map.Entry<Character, String> entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("nAlgne string oli: n" + text);
// prindib kodeeritud stringi
StringBuilder sb = new StringBuilder();
for (int i = 0 ; i < text.length(); i++) {
sb.append(huffmanCode.get(text.charAt(i)));
}
System.out.println("nKodeeritud string on: n" + sb);
// Rändab taas Huffmani puu ja seekord
// dekodeerib kodeeritud stringi
int index = -1;
System.out.println("nDekodeeritud string on: n");
while (index < sb.length() - 2) {
index = decode(root, index, sb);
}
}
public static void main(String[] args)
{
String text = "Huffmani koodimine on andmete tihendamise algoritm.";
buildHuffmanTree(text);
}
}Märkus: Sisendstringi kasutatav mälu on 47 * 8 = 376 bitti, kuid kodeeritud string võtab vaid 194 bitti, st andmed kokkusurutakse ligikaudu 48%. Ülaltoodud C++ programmis kasutame kodeeritud stringi hoidmiseks string klassi, et programm oleks loetav.
Kuna tõhusate andmestruktuuride prioriteetsed järjekorrad nõuavad sisestamiseks O(log(N)) aega, ja täis binaarses puus on N lehti 2N-1 nõuandeid, ning Huffmani puu on täis binaarne puu, siis algoritm töötab O(Nlog(N)) ajaga, kus N on märkide arv.
Allikad:
Allikas: habr.com
