Në prag të fillimit të kursit kanë përgatitur për ju përkthimin e një materiali tjetër të dobishëm.
Kodimi i Huffman-it është një algoritëm kompresimi të dhënash që formulon idenë kryesore të kompresimit të skedarëve. Në këtë artikull do të flasim për kodimin me gjatësi fikse dhe të ndryshme, kode që dekodohen unikisht, rregulla prefiksuese dhe ndërtimin e drurit të Huffman-it.
Ne e dimë se çdo simbol ruhet si një sërë prej 0 dhe 1 dhe zë 8 bite. Kjo quhet kodim me gjatësi fikse, pasi çdo simbol përdor të njëjtin numër fikse bitësh për ruajtje.
Supozoni se kemi një tekst. Si mund ta pakësojmë sasinë e hapësirës që kërkohet për ruajtjen e një simboli?
Ideja kryesore qëndron në kodimin me gjatësi të ndryshme. Ne mund të përdorim faktin se disa simbole në tekst shfaqen më shpesh se të tjerat (), për të krijuar një algoritëm që do të përfaqësonte të njëjtën sekuencë karakteresh me një numër më të vogël bitësh. Kur kodifikojmë me gjatësi të ndryshueshme, ne i caktojmë karaktereve një numër të ndryshueshëm bitësh në varësi të frekuencës së shfaqjes së tyre në këtë tekst. Në fund, disa karaktere mund të zënë vetëm 1 bit, ndërsa të tjerët 2, 3 ose më shumë. Problemi me kodifikimin e gjatësi të ndryshueshme qëndron vetëm te dekodimi i mëvonshëm i sekuencës.
Si, duke ditur sekuencën e bitëve, ta dekodojmë atë në mënyrë të qartë?
Le të shqyrtojmë stringun «aabacdab». Në të, ka 8 karaktere, dhe kur kodifikohet me gjatësi të fiksuar, ne do të kemi nevojë për 64 bitë për ta ruajtur. Vëreni se frekuenca e karaktereve «a», «b», «c» dhe «d» është 4, 2, 1, 1 përkatësisht. Le të provojmë ta përfaqësojmë «aabacdab» me një numër më të vogël bitësh, duke përdorur faktin se «a» shfaqet më shpesh se «b», dhe «b» shfaqet më shpesh se «c» dhe «d». Ne do të fillojmë duke kodifikuar «a» me një bit, të cilin e caktojmë si 0, «b» ne do t’i caktojmë kodin me dy bitë 11, dhe me tre bitë 100 dhe 011 do ta kodifikojmë «c» dhe «d».
Në fund do të kemi:
a
0
b
11
me
100
d
011
Pra, stringun «aabacdab» ne do ta kodifikojmë si 00110100011011 (0|0|11|0|100|011|0|11), duke kodet e paraqitura më lartë. Megjithatë, problemi kryesor do të jetë dekodimi. Kur përpiqemi të dekodojmë vargun 00110100011011, do të kemi një rezultat të paqartë, sepse mund të paraqitet si:
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
…
etj.
Për të shmangur këtë paqartësi, duhet të garantojmë që kodimi ynë plotëson një koncept si regulli i prefiksit, i cili, nga ana tjetër, nënkupton se kodet mund të dekodohen vetëm në një mënyrë unike. Rregulli i prefiksit garanton që asnjë kod nuk do të jetë prefiks i një tjetri. Me kod nënkuptojmë bits që përdoren për të përfaqësuar një simbol të caktuar. Në shembullin e mësipërm 0 – është një prefiks 011, që shkel rregullin e prefiksit. Pra, nëse kodet tona përmbushin rregullin e prefiksit, atëherë dekodimi mund të bëhet njëkuptimshëm (dhe anasjelltas).
Le të rishikojmë shembullin e mësipërm. Këtë herë do t'i caktojmë simboleve «a», «b», «c» dhe «d» kodat që përmbushin rregullin e prefiksit.
a
0
b
10
me
110
d
111
Me këtë lloj kodimi, vargu «aabacdab» do të kodifikohet si 00100100011010 (0|0|10|0|100|011|0|10). Ja se si 00100100011010 ne do të mund të dekodojmë pa dyshim dhe të kthehemi në vargjin tonë origjinal «aabacdab».
Kodimi i Huffmanit
Tani që u nihilizuam me kodimin me gjatësi të ndryshueshme dhe rregullin e prefikseve, le të flasim për kodimin e Huffmanit.
Metoda bazohet në krijimin e pemëve binare. Në të, një nyjë mund të jetë ose përfundimtare ose brendshme. Fillimisht, të gjitha nyjat merren si gjethe (përfundimtare), që paraqesin vetë simbolin dhe peshën e tij (dmth, frekuencën e shfaqjes). Nyjat e brendshme mbajnë peshën e simbolit dhe referohen në dy nyjat trashëguese. Sipas marrëveshjes, biti "0" përfaqëson ndjekjen e degës së majtë, ndërsa "1" — për degën e djathtë. Në një pemë të plotë N gjethe dhe N-1 nyje të brendshme. Rekomandohet që gjatë ndërtimit të pemës së Huffmanit të përjashtohen simbolet e pa përdorura për të marrë kodet e gjatësi optimale.
Ne do të përdorim një radhë me prioritete për të ndërtuar pemën e Huffmanit, ku nyjës me frekuencën më të ulët do t'i caktohet prioriteti më i lartë. Më poshtë janë hapat e ndërtimit:
- Krijoni një nyjë-gjethe për çdo simbol dhe shtoni ato në radhë me prioritete.
- Përderisa në radhë ka më shumë se një gjethe, bëni si më poshtë:
- Hiqni dy nyje me prioritetin më të lartë (me frekuencën më të ulët) nga radhët;
- Krijoni një nyje të re të brendshme, ku këto dy nyje do të jenë trashëgimtarët, dhe frekuenca e shfaqjes do të jetë e barabartë me shumën e frekuencave të këtyre dy nyjeve.
- Shtoni një nyje të re në radhën e prioriteteve.
- Nyja e vetme që mbetet do të jetë rrënjore, dhe ndërtimi i pemës do të përfundojë këtu.
Le të supozojmë se kemi një tekst, i cili përbëhet vetëm nga simbolet «a», «b», «c», «d» dhe «e», dhe frekuencat e shfaqjes së tyre janë të barabarta me 15, 7, 6, 6 dhe 5 përkatësisht. Më poshtë janë ilustruar hapat e algoritmit.
Rruga nga rrënja deri në çdo nyje përfundimtare do të ruajë kodin optimal të prefiksit (i njohur gjithashtu si kodi Huffman), që i përket simbolit të lidhur me këtë nyje përfundimtare.
Pema Huffman
Më poshtë do të gjeni implementimin e algoritmit të kompresimit të Huffman në gjuhët C++ dhe 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;
// Një nod i pemës
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
{
// kalon pemën Huffman dhe ruan kodet Huffman
// në një hartë.
public static void encode(Node root, String str,
Map huffmanCode)
{
if (root == null)
return;
// gjetur një nod gjethe
if (root.left == null && root.right == null) {
huffmanCode.put(root.ch, str);
}
encode(root.left, str + "0", huffmanCode);
encode(root.right, str + "1", huffmanCode);
}
// kalon pemën Huffman dhe dekodifikon stringun e koduar
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// gjetur një nod gjethe
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;
}
// Ndërton pemën Huffman dhe huffmanCode dhe dekodifikon tekstin e dhënë
public static void buildHuffmanTree(String text)
{
// numëron frekuencën e shfaqjes së çdo karakteri
// dhe e ruan atë në një hartë
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);
}
// Krijon një radhë prioritare për të ruajtur nodet e gjalla të pemës Huffman
// Vërejtje që artikulli me prioritet më të lartë ka frekuencën më të ulët
PriorityQueue pq = new PriorityQueue((l, r) -> l.freq - r.freq);
// Krijon një nod gjethe për çdo karakter dhe e shton atë
// në radhën prioritare.
for (Map.Entry entry : freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
// bëj deri sa të ketë më shumë se një nod në radhë
while (pq.size() != 1)
{
// Heq dy nodet me prioritet më të lartë
// (frekuencën më të ulët) nga radhë
Node left = pq.poll();
Node right = pq.poll();
// Krijon një nod të ri të brendshëm me këto dy nodet si fëmijë
// dhe me frekuencë të barabartë me shumën e dy frekuencave të nodit
// Shton nodin e ri në radhën prioritare.
int sum = left.freq + right.freq;
pq.add(new Node(' ', sum, left, right));
}
// rrënja ruan treguesin për rrënjën e pemës Huffman
Node root = pq.peek();
// kalon pemën Huffman dhe ruan kodet Huffman në një hartë
Map huffmanCode = new HashMap();
encode(root, "", huffmanCode);
// printon kodet Huffman
System.out.println("Kodet Huffman janë :\n");
for (Map.Entry entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("\nStringu origjinal ishte :\n" + text);
// printon stringun e koduar
StringBuilder sb = new StringBuilder();
for (int i = 0 ; i < text.length(); i++) {
sb.append(huffmanCode.get(text.charAt(i)));
}
System.out.println("\nStringu i koduar është :\n" + sb);
// kalon përsëri pemën Huffman dhe këtë herë
// dekodifikon stringun e koduar
int index = -1;
System.out.println("\nStringu i dekoduar është: \n");
while (index < sb.length() - 2) {
index = decode(root, index, sb);
}
}
public static void main(String[] args)
{
String text = "Huffman coding është një algoritëm kompresimi të dhënash.";
buildHuffmanTree(text);
}
}Shënim: Memoria e përdorur nga stringu hyrës është 47 * 8 = 376 bit, ndërsa stringu i koduar zë vetëm 194 bit, dmth. të dhënat kompresohen rreth 48%. Në programin në C++ më sipër, ne përdorim klasën string për të ruajtur stringun e koduar, për ta bërë programin më të lexueshëm.
Duke pasur parasysh se strukturat efektive të të dhënave për prioritetin kërkojnë O(log(N)) kohë, dhe në një pemë binar të plotë me N gjethe përmbajnë 2N-1 nodi, dhe pema e Huffman-it është një pemë binar e plotë, algoritmi punon për O(Nlog(N)) kohë, ku N – numri i simboleve.
Burimet:
Burimi: habr.com
