Kursuse alguse eelĂ”htul valmistasid teile tĂ”lke veel ĂŒhest kasulikust materjalist.
Hafmanni kodeerimine on andmete tihendusalgoritm, mis vÀljendab failide tihendamise pÔhikontseptsiooni. Selles artiklis rÀÀgime fikseeritud ja muutliku pikkusega kodeerimisest, unikaalselt dekodeeritavatest koodidest, prefiksireeglitest ja Hafmanni puu leidmisest.
Teame, et iga sĂŒmbol salvestatakse 0 ja 1 jĂ€rjekorrana ja see vĂ”tab 8 bitti. Seda nimetatakse fikseeritud pikkusega kodeerimiseks, kuna iga sĂŒmbol kasutab salvestamiseks sama fikseeritud arvu bitte.
Oletame, et meil on tekst. Kuidas saame vĂ€hendada vajaminevat ruumi ĂŒhe sĂŒmboli salvestamiseks?
Peamine idee seisneb muutliku pikkusega kodeerimises. Saame kasutada asjaolu, et mĂ”ned sĂŒmbolid tekstis esinevad sagedamini kui teised (), et vĂ€lja töötada algoritm, mis esindab sama sĂŒmbolite jada vĂ€iksema arvu bittidega. Muutliku pikkusega kodeerimisel mÀÀrame sĂŒmbolitele muutuva arvu bitte sĂ”ltuvalt nende esinemissagedusest antud tekstis. LĂ”ppkokkuvĂ”ttes vĂ”ivad mĂ”ned sĂŒmbolid vĂ”tta vaid 1 bitti, teised 2 bitti, 3 vĂ”i rohkem. Muutliku pikkusega kodeerimise probleem seisneb vaid edaspidises jĂ€rjestuse dekodeerimises.
Kuidas dekodeerida bittide jĂ€rjestust ĂŒhemĂ”tteliselt, teades seda?
VĂ”tame arvesse jĂ€rje, «aabacdab». Selles on 8 sĂŒmbolit, ja fikseeritud pikkusega kodeerimisel on selle salvestamiseks vajalik 64 bitti. TĂ€helepanu, et sĂŒmbolite sagedus «a», «b», «c» ja «d» vĂ”rdub vastavalt 4, 2, 1, 1. Proovime kujutada seda «aabacdab» vĂ€iksema bittide arvuga, kasutades fakti, et «a» esineb sagedamini kui «b», vaid «b» esineb sagedamini kui «c» ja «d». Alustame sellega, et kodeerime «a» ĂŒhe bitiga, mis on 0, «b» anname kahele bitile koodi 11 ja kolme bitiga kodeerime 100 ja 011 «c» ja «d».
KokkuvÔttes saame:
a
0
b
11
c
100
d
011
Nii kodeerime jÀrje «aabacdab» nagu 00110100011011 (0|0|11|0|100|011|0|11), kasutades eelnevalt esitatud koode. Kuid peamine probleem on dekodeerimisel. Kui proovime dekodeerida jÀrje 00110100011011, saame kahemÔttelise tulemuse, kuna seda saab esitada kui:
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.
Selle ebamugavuse vĂ€ltimiseks peame tagama, et meie kodeerimine rahuldaks sellist mĂ”istet nagu eelseisva reegli, mis omakorda tĂ€hendab, et koode saab dekodeerida ainult ĂŒhe ainulaadse viisi kaudu. Eelseisva reegel tagab, et ĂŒkski kood ei ole teise eelseisja. Koodi all mĂ”tleme me bite, mida kasutatakse konkreetse sĂŒmboli esindamiseks. Ălaltoodud nĂ€ites 0 â on eelseisja 011, mis rikub eelseisva reeglit. Nii, kui meie koodid vastavad eelseisvale reeglile, siis on vĂ”imalik dekodeerimine ĂŒheselt (ja vastupidi).
Vaadakem ĂŒlaltoodud nĂ€idet uuesti. Seekord mÀÀrame sĂŒmbolitele «a», «b», «c» ja «d» koode, mis rahuldavad eelseisva reegli.
a
0
b
10
c
110
d
111
Sellise kodeerimisega kooditakse string «aabacdab» nĂŒĂŒd ĂŒheks ĂŒheselt dekodeeritavaks ja naaseme oma algsele stringile 00100100011010 (0|0|10|0|100|011|0|10)Programmi loomiseks Nanonyami jaoks tuleb kasutada spetsiaalseid raamatukogusid, kus on rakendatud kĂ”ik praegu saadaval olevad virtuaalsed funktsioonid. Laadige alla virtuaalne masin Nanonyam ja raamatukogud selle jaoks 00100100011010 Huffmani kodeerimine «aabacdab».
NĂŒĂŒd, kui oleme tutvunud muutuva pikkusega kodeerimise ja eelseisva reegliga, rÀÀgime Huffmani kodeerimisest.
Meetod pĂ”hineb binaarpuude loomisel. Sellel vĂ”ib olla sĂ”lm, mis on kas lĂ”plik vĂ”i sise-sĂ”lm. Esialgu kĂ”ik sĂ”lmed peetakse lehtedeks (lĂ”plikud), mis esindavad sĂŒmbolit ja selle kaalu (ehk esinemissagedust). SisesĂ”lmed sisaldavad sĂŒmboli kaalu ja viitavad kahele pĂ€randsĂ”lmele. Ăldiselt, bit
â0â esindab vasaku haru jĂ€rgimist ja â1â â parema jĂ€rgimist. TĂ€ielikus puus on lehti ja N N-1 sisesĂ”lme. Soovitav on, et Huffmani puu ehitamisel kĂ”rvaldada kasutamata sĂŒmbolid, et saavutada parima pikkusega koodid. Kasutame prioriteedipuhvrit Huffmani puu ehitamiseks, kus madalaimaga sageduse sĂ”lmele antakse kĂ”rgeim prioriteet. Allpool on toodud ehitamise sammud:
Loo iga sĂŒmboli jaoks lehesĂ”lm ja lisa need prioriteedipuhvrisse.
- Kuni puhvris on rohkem kui ĂŒks leht, teeme jĂ€rgmist:
- Eemaldage kaks kÔrgeima prioriteediga (madalaima sagedusega) sÔlme puhvrist;
- Loo uus sise-sÔlm, kus need kaks sÔlme on pÀrijad, ja esinemissagedus vÔrdub nende kahe sÔlme sageduste summaga.
- Lisage uus sÔlm prioriteedipuhvrisse.
- Lisage uus sÔlm prioriteedipuhvrisse.
- Ainus jÀÀnud sÔlm on juursÔlm, millega puu ehitamine lÔppeb.
Oletame, et meil on mingi tekst, mis koosneb ainult mÀrkidest «a», «b», «c», «d» ja «e», mille esinemissagedused on vastavalt 15, 7, 6, 6 ja 5. Allpool on illustratsioonid, mis kajastavad algoritmi samme.
Tee juurest igasse lÔpp-sÔlme salvestab optimaalse eesliite koodi (tuntud ka kui Huffmani kood), mis vastab sellele lÔpp-sÔlmele seotud mÀrgile.
Huffmani puu
Allolevalt leiate Huffmani tihendamisalgoritmi teostuse 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;
// PuudutĂŒĂŒp
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
{
// Traverseerib Huffmani puud ja salvestab Huffmani koodid
// kaardis.
public static void encode(Node root, String str,
Map huffmanCode)
{
if (root == null)
return;
// lehtpuu sÔ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);
}
// Traverseerib Huffmani puud ja dekodeerib kodeeritud stringi
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// lehtpuu sÔ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 siseteksti
public static void buildHuffmanTree(String text)
{
// arvestab iga tÀhe esinemise sagedust
// ja salvestab selle kaardis
Map 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 prioriteetide jÀrjekorra, et salvestada elusolevaid sÔlmi
// Huffmani puust.
// Pöörake tÀhelepanu, et kÔrgeima prioriteediga objekt
// omab madalaimat sagedust
PriorityQueue pq = new PriorityQueue(
(l, r) -> l.freq - r.freq);
// Loob iga tÀhe jaoks lehtsÔlme ja lisab selle
// prioriteetide jÀrjekorda.
for (Map.Entry entry : freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
// jĂ€tkab, kuni jĂ€rjekorras on rohkem kui ĂŒks sĂ”lm
while (pq.size() != 1)
{
// Eemaldab jÀrjekorrast kaks kÔige kÔrgema prioriteediga sÔlme
// (madalaima sagedusega)
Node left = pq.poll();
Node right = pq.poll();
// Loob uue sisemuse sÔlme nende kahe sÔlme lastega
// ja sagedus, mis on vÔrdsed kahe sÔlme
// sageduste summaga. Lisab uue sÔlme jÀrjekorda.
int sum = left.freq + right.freq;
pq.add(new Node(' ', sum, left, right));
}
// Root hoiab viidet Huffmani puu juurele
Node root = pq.peek();
// Traverseerib Huffmani puud ja salvestab Huffmani koodid kaardis
Map huffmanCode = new HashMap();
encode(root, "", huffmanCode);
// Prindib Huffmani koodid
System.out.println("Huffmani koodid on :\n");
for (Map.Entry entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("\nOriginaalne 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);
// Traverseerib Huffmani puud uuesti 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 koding on andmete tihendamise algoritm.";
buildHuffmanTree(text);
}
}MĂ€rkus: Sisendstringi kasutamiseks vajaminev mĂ€lu on 47 * 8 = 376 bitti, samas kui kodeeritud string vĂ”tab ainult 194 bitti, st andmed tihendatakse umbes 48%. Ălaltoodud C++ programmis kasutame kiri klass string, et salvestada kodeeritud string, et muuta programm loetavaks.
Kuna efektiivsed prioriteetsĂŒsteemide andmestruktuurid vajavad lisamiseks O(log(N)) aega ja tĂ€ielikus binaarpuus on N lehti 2N-1 sĂ”lme, ning Huffmani puu on tĂ€ispuhas binaarpuu, siis töötab algoritm ajaga O(Nlog(N)) kus N on sĂŒmbolite arv.
Allikad:
Allikas: habr.com
