Kursun başlamazdan əvvəl sizin üçün başqa bir faydalı materialın tərcüməsini hazırladı.
Huffman kodlaşdırması, fayl sıxılmasının əsas ideyasını formalaşdıran məlumatların sıxılma alqoritmidir. Bu yazıda biz sabit və dəyişən uzunluqlu kodlaşdırma, unikal şəkildə deşifrə olunan kodlar, prefiks qaydaları və Huffman ağacının qurulması haqqında danışacağıq.
Biz bilirik ki, hər bir simvol 0 və 1 ardıcıllığı kimi saxlanılır və 8 bit tutur. Buna sabit uzunluqlu kodlaşdırma deyilir, çünki hər bir simvol saxlamaq üçün eyni sabit sayda bit istifadə edir.
Tutaq ki, bizə mətn verilmişdir. Bir simvolu saxlamaq üçün tələb olunan yerin miqdarını necə azaltmaq olar?
Əsas fikir dəyişən uzunluqlu kodlaşdırmadır. Mətndə bəzi simvolların digərlərindən daha tez-tez baş verməsindən istifadə edə bilərik () eyni simvol ardıcıllığını daha az bitlə təmsil edəcək bir alqoritm hazırlamaq. Dəyişən uzunluqlu kodlaşdırmada biz simvollara verilən mətndə onların tez-tez görünməsindən asılı olaraq dəyişən bit sayı təyin edirik. Nəhayət, bəzi simvollar 1 bit qədər, digərləri isə 2 bit, 3 və ya daha çox ala bilər. Dəyişən uzunluqlu kodlaşdırma ilə bağlı problem yalnız ardıcıllığın sonrakı dekodlanmasıdır.
Bitlərin ardıcıllığını bilməklə, onu birmənalı şəkildə necə deşifrə etmək olar?
Xətti nəzərdən keçirin "abacdab". Onun 8 simvolu var və sabit uzunluğu kodlayan zaman onu saxlamaq üçün 64 bit lazımdır. Qeyd edək ki, simvol tezliyi "a", "b", "c" и "D" müvafiq olaraq 4, 2, 1, 1-ə bərabərdir. Təsəvvür etməyə çalışaq "abacdab" ki, istifadə edərək, daha az bit "to" nisbətən daha tez-tez baş verir "B"Və "B" nisbətən daha tez-tez baş verir "c" и "D". Kodlaşdırma ilə başlayaq "to" bir bit 0-a bərabər, "B" iki bitlik kod 11 təyin edəcəyik və üç bit 100 və 011 istifadə edərək kodlaşdıracağıq "c" и "D".
Nəticədə əldə edəcəyik:
a
0
b
11
c
100
d
011
Beləliklə, xətt "abacdab" olaraq kodlayacağıq 00110100011011 (0|0|11|0|100|011|0|11)yuxarıdakı kodlardan istifadə etməklə. Bununla belə, əsas problem dekodlaşdırmada olacaq. Biz simli deşifrə etməyə çalışdığımız zaman 00110100011011, biz qeyri-müəyyən nəticə əldə edirik, çünki o, aşağıdakı kimi təqdim edilə bilər:
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
...
və s.
Bu qeyri-müəyyənliyin qarşısını almaq üçün kodlaşdırmamızın belə bir anlayışa cavab verməsini təmin etməliyik prefiks qaydası, bu da öz növbəsində kodların yalnız bir unikal şəkildə deşifrə edilməsini nəzərdə tutur. Prefiks qaydası heç bir kodun digərinin prefiksi olmadığını təmin edir. Kod dedikdə, müəyyən bir simvolu təmsil etmək üçün istifadə olunan bitləri nəzərdə tuturuq. Yuxarıdakı nümunədə 0 prefiksdir 011, prefiks qaydasını pozur. Beləliklə, kodlarımız prefiks qaydasına cavab verirsə, biz unikal şəkildə deşifrə edə bilərik (və əksinə).
Yuxarıdakı nümunəyə yenidən baxaq. Bu dəfə simvollar üçün təyin edəcəyik "a", "b", "c" и "D" prefiks qaydasını təmin edən kodlar.
a
0
b
10
c
110
d
111
Bu kodlaşdırma ilə simli "abacdab" kimi kodlanacaq 00100100011010 (0|0|10|0|100|011|0|10). Ancaq 00100100011010 biz artıq birmənalı şəkildə deşifrə edə və orijinal sətirimizə qayıda biləcəyik "abacdab".
Huffman kodlaması
Dəyişən uzunluqlu kodlaşdırma və prefiks qaydası ilə məşğul olduğumuz üçün indi Huffman kodlaşdırması haqqında danışaq.
Metod ikili ağacların yaradılmasına əsaslanır. Onda node son və ya daxili ola bilər. Əvvəlcə bütün qovşaqlar simvolun özünü və çəkisini (yəni baş vermə tezliyini) təmsil edən yarpaqlar (terminallar) hesab olunur. Daxili qovşaqlar xarakterin çəkisini ehtiva edir və iki nəsil qovşağına istinad edir. Ümumi razılaşma ilə, bit «0» sol budaqdan sonra təmsil edir və «1» - sağda. tam ağacda N yarpaqları və N-1 daxili qovşaqlar. Huffman ağacını qurarkən optimal uzunluq kodlarını əldə etmək üçün istifadə olunmamış simvolları atmaq tövsiyə olunur.
Biz Huffman ağacını qurmaq üçün prioritet növbədən istifadə edəcəyik, burada ən aşağı tezlikli node ən yüksək prioritet veriləcəkdir. Tikinti mərhələləri aşağıda təsvir edilmişdir:
- Hər simvol üçün yarpaq qovşağı yaradın və onları prioritet növbəyə əlavə edin.
- Növbədə birdən çox vərəq olduqda aşağıdakıları edin:
- Ən yüksək prioritet (ən aşağı tezlik) olan iki qovşağı növbədən çıxarın;
- Bu iki qovşağın uşaq olacağı və baş vermə tezliyi bu iki qovşağın tezliklərinin cəminə bərabər olacaq yeni bir daxili qovşaq yaradın.
- Prioritet növbəsinə yeni node əlavə edin.
- Yalnız qalan düyün kök olacaq və bu, ağacın tikintisini tamamlayacaqdır.
Təsəvvür edin ki, bizdə yalnız simvollardan ibarət mətn var "a B C D" и "və", və onların baş vermə tezliyi müvafiq olaraq 15, 7, 6, 6 və 5-dir. Aşağıda alqoritmin addımlarını əks etdirən təsvirlər verilmişdir.
Kökdən hər hansı bir son qovluğa qədər olan yol həmin son node ilə əlaqəli simvola uyğun gələn optimal prefiks kodunu (həmçinin Huffman kodu kimi tanınır) saxlayacaq.
Huffman ağacı
Aşağıda Huffman sıxılma alqoritminin C++ və Java dillərində tətbiqini tapa bilərsiniz:
#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);
}
}Qeyd: giriş sətrinin istifadə etdiyi yaddaş 47 * 8 = 376 bit, kodlanmış sətir isə yalnız 194 bit, yəni. məlumatlar təxminən 48% sıxılır. Yuxarıdakı C++ proqramında biz proqramı oxunaqlı etmək üçün kodlanmış sətri saxlamaq üçün string sinfindən istifadə edirik.
Çünki effektiv prioritet növbə məlumat strukturları hər daxiletmə tələb edir O(log(N)) zaman, lakin tam ikili ağac ilə N yarpaqlar mövcuddur 2N-1 qovşaqlar və Huffman ağacı tam ikili ağacdır, sonra alqoritm işə düşür O(Nlog(N)) vaxt, harada N - Personajlar.
Mənbə:
Mənbə: www.habr.com