Berî destpêkirina qursê ji bo we wergera materyalek din a kêrhatî amade kir.
Kodkirina Huffman algorîtmayek berhevkirina daneyê ye ku ramana bingehîn a berhevkirina pelê formule dike. Di vê gotarê de, em ê li ser şîfrekirina dirêjahiya sabît û guhêrbar, kodên bêhempa yên dekodkirî, qaîdeyên pêşgir, û avakirina darek Huffman biaxivin.
Em dizanin ku her karakter wekî rêzek ji 0 û 1yan tê hilanîn û 8 bit digire. Ji vê re kodkirina dirêjahiya sabît tê gotin ji ber ku her karakter heman hejmara sabît a bit bikar tîne da ku hilîne.
Em bêjin nivîseke me heye. Em çawa dikarin mîqdara cîhê ku ji bo hilanîna karakterek yekane hewce dike kêm bikin?
Fikra sereke şîfrekirina dirêjahiya guhêrbar e. Em dikarin vê rastiyê bikar bînin ku hin tîpên di nivîsê de ji yên din pirtir pêk tên () ji bo pêşxistina algorîtmayek ku dê heman rêza karakteran di hindik bit de temsîl bike. Di şîfrekirina dirêjahiya guhêrbar de, em li gorî ka çend caran di metnek diyar de xuya dibin, hejmareke guhêrbar bit diyar dikin. Di dawiyê de, dibe ku hin karakter bi qasî 1 bit bigirin, lê yên din dikarin 2 bit, 3 an jî zêdetir bigirin. Pirsgirêka bi şîfrekirina dirêjahiya guhêrbar tenê deşîfrekirina paşerojê ya rêzikê ye.
Meriv çawa rêza bitkan nas dike, wê bi rengekî nezelal deşîfre bike?
Rêzê bifikirin "abacdab". Ew 8 tîpan heye, û dema ku dirêjiyek sabît kod dike, ji bo hilanîna wê 64 bit hewce dike. Bala xwe bidin frekansa sembolê "a", "b", "c" и "D" 4, 2, 1, 1 wekhev e. Werin em hewl bidin ku xeyal bikin "abacdab" bits kêmtir, bi kar tînin ku rastiya ku "ber" ji wê zêdetir pêk tê "B"û "B" ji wê zêdetir pêk tê "c" и "D". Ka em bi kodkirinê dest pê bikin "ber" bi bitek 0 re wekhev e, "B" em ê kodek du-bit 11 destnîşan bikin, û sê bit 100 û 011 bikar bînin em ê şîfre bikin "c" и "D".
Di encamê de, em ê bistînin:
a
0
b
11
c
100
d
011
Ji ber vê yekê rêz "abacdab" em ê wekî kod bikin 00110100011011 (0|0|11|0|100|011|0|11)bikaranîna kodên li jor. Lêbelê, pirsgirêka sereke dê di deşîfrekirinê de be. Dema ku em hewl didin ku string deşîfre bikin 00110100011011, em encamek nezelal distînin, ji ber ku ew dikare wekî:
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î awayî.
Ji bo ku em ji vê nezelaliyê dûr nekevin, divê em piştrast bikin ku kodkirina me têgehek weha têr dike qaîdeya pêşgir, ku di encamê de tê vê wateyê ku kod tenê bi rengek yekta têne deşîfre kirin. Rêbaza pêşgir piştrast dike ku tu kod ne pêşgira yekî din e. Bi kodê, mebesta me ew bit e ku ji bo temsîlkirina karakterek taybetî têne bikar anîn. Di mînaka jorîn de 0 pêşgirek e 011, ku qaîdeya pêşgiran binpê dike. Ji ber vê yekê, heke kodên me qaîdeya pêşgir têr dikin, wê hingê em dikarin yekta deşîfre bikin (û berûvajî).
Werin em ji nû ve li mînaka li jor binêrin. Vê carê em ê ji bo sembolan destnîşan bikin "a", "b", "c" и "D" kodên ku qaîdeya pêşgir têr dikin.
a
0
b
10
c
110
d
111
Bi vê şîfrekirinê, string "abacdab" dê wek kodkirin 00100100011010 (0|0|10|0|100|011|0|10). Û vir 00100100011010 em ê jixwe karibin bi awayekî zelal deşîfre bikin û vegerin rêza xweya eslî "abacdab".
Kodkirina Huffman
Naha ku me bi şîfrekirina dirêjahiya guhêrbar û qaîdeya pêşgiran re mijûl kir, bila em li ser kodkirina Huffman biaxivin.
Rêbaz li ser afirandina darên binaryî ye. Di wê de, girêk dikare an dawî an hundurîn be. Di destpêkê de, hemî girêk wekî pel (termînalan) têne hesibandin, ku sembola xwe û giraniya wê (ango, pirbûna rûdanê) temsîl dikin. Girêkên hundurîn giraniya karakterê vedihewîne û du girêkên dûndanê vedibêje. Bi peymana giştî, bit «0» li pey şaxê çepê temsîl dike, û «1» - li aliyê rastê. bi darê tije N pel û N-1 girêkên navxweyî. Tête pêşniyar kirin ku dema ku darek Huffman tê çêkirin, sembolên neyên bikar anîn werin avêtin da ku kodên dirêjahiya çêtirîn bistînin.
Em ê rêzek pêşîn bikar bînin da ku darek Huffman ava bikin, ku li wir girêka bi frekansa herî kêm dê pêşîniya herî bilind jê re were dayîn. Pêngavên avakirinê li jêr têne diyar kirin:
- Ji bo her karakterek girêk pelek biafirînin û wan li rêza pêşîn lê zêde bikin.
- Dema ku di rêzê de ji yek pelek bêtir heye, jêrîn bikin:
- Du girêkên bi pêşîniya herî bilind (frekansa herî kêm) ji rêzê derxînin;
- Girêkek navxweyî ya nû biafirînin, ku ev her du girêk dê zarok bin, û frekansa rûdanê dê bi berhevoka frekansên van her du girêkan re wekhev be.
- Nodek nû li rêza pêşîn zêde bikin.
- Tenê girêka mayî dê kok be, û ev ê avakirina darê temam bike.
Bifikirin ku me nivîsek heye ku tenê ji tîpan pêk tê "a", "b", "c", "d" и "û", û frekansên rûdana wan bi rêzê 15, 7, 6, 6 û 5 in. Li jêr nîgarên ku gavên algorîtmê nîşan didin hene.
Rêyek ji kokê berbi her girêka dawîyê dê koda pêşgira çêtirîn (ku wekî koda Huffman jî tê zanîn) ku bi karaktera ku bi wê girêka dawîyê ve girêdayî ye hilîne.
Dara Huffman
Li jêr hûn ê pêkanîna algorîtmaya kompresyona Huffman di C++ û Java de bibînin:
#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);
}
}Têbînî: bîranîna ku ji hêla rêzika têketinê ve tê bikar anîn 47 * 8 = 376 bit e û rêzika kodkirî tenê 194 bit e, yanî. Daneyên ji hêla 48% ve têne teng kirin. Di bernameya C++ ya li jor de, em çîna rêzê bikar tînin da ku rêzika kodkirî hilînin da ku bername were xwendin.
Ji ber ku strukturên daneya rêza pêşîn a bikêr ji her têxê hewce dike O(log(N)) dem, lê di dara binary temam bi N pelên heyî 2N-1 girêkan, û dara Huffman darek binaryek bêkêmasî ye, wê hingê algorîtma tê de dimeşe O(Nlog(N)) dem, li ku N - Karakterên.
Çavkaniyên
Source: www.habr.com