Ngaphambi kokuqala kwesifundo ngikulungiselele inguqulo yolunye ukwaziswa okuwusizo.
I-Huffman coding iyi-algorithm yokucindezela idatha eyakha umqondo oyisisekelo wokucindezelwa kwefayela. Kulesi sihloko, sizokhuluma ngokufaka ikhodi yobude obungaguquki nobuguquguqukayo, amakhodi ahlukanisekayo ahlukile, imithetho yesiqalo, nokwakha isihlahla se-Huffman.
Siyazi ukuthi uhlamvu ngalunye lugcinwa njengokulandelana kuka-0 no-1 futhi luthatha amabhithi angu-8. Lokhu kubizwa nge-fixed length encoding ngoba uhlamvu ngalunye lusebenzisa inombolo efanayo engaguquki yamabhithi ukugcina.
Ake sithi sinombhalo. Singanciphisa kanjani isikhala esidingekayo ukuze kugcinwe umlingisi oyedwa?
Umqondo oyinhloko uwumbhalo wekhodi wobude obuguquguqukayo. Singasebenzisa iqiniso lokuthi ezinye izinhlamvu embhalweni zivela kaningi kunezinye () ukuthuthukisa i-algorithm ezomela ukulandelana kwezinhlamvu kumabhithi ambalwa. Ekubhaleni ngekhodi ubude obuguquguqukayo, sinikeza izinhlamvu inombolo eguquguqukayo yamabhithi, kuye ngokuthi avela kaningi kangakanani embhalweni othile. Ekugcineni, ezinye izinhlamvu zingathatha kancane njengebhithi elingu-1, kanti ezinye zingathatha amabhithi angu-2, 3 noma ngaphezulu. Inkinga ngombhalo wekhodi wobude obuguquguqukayo ukuqoshwa okulandelayo kuphela kokulandelana.
Kanjani, ngokwazi ukulandelana kwezingcezu, ukunquma ngokusobala?
Cabangela umugqa "baba". Inezinhlamvu ezingu-8, futhi uma ibhala ngekhodi ubude obunqunyiwe, izodinga amabhithi angu-64 ukuyigcina. Qaphela ukuthi imvamisa yophawu "a", "b", "c" ΠΈ "D" ilingana no-4, 2, 1, 1 ngokulandelana. Ake sizame ukucabanga "baba" izingcezu ezimbalwa, usebenzisa iqiniso lokuthi "kuya" kwenzeka kaningi kunalokho "B", futhi "B" kwenzeka kaningi kunalokho "c" ΠΈ "D". Ake siqale ngokubhala ikhodi "kuya" nebhithi elilodwa elilingana no-0, "B" sizokwabela ikhodi enamabhithi amabili 11, futhi sisebenzisa izingcezu ezintathu 100 kanye no-011 sizofaka ikhodi. "c" ΠΈ "D".
Ngenxa yalokho, sizothola:
a
0
b
11
c
100
d
011
Ngakho umugqa "baba" sizobhala njenge 00110100011011 (0|0|11|0|100|011|0|11)usebenzisa amakhodi angenhla. Nokho, inkinga enkulu izoba ekuqopheni amakhodi. Lapho sizama ukunquma umucu 00110100011011, sithola umphumela ongaqondakali, njengoba ungamelwa ngokuthi:
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
...
nokunye.
Ukuze sigweme lokhu kungaqondakali, kufanele siqinisekise ukuthi umbhalo wethu wekhodi wenelisa umqondo onjengokuthi umthetho wesiqalo, okusho ukuthi amakhodi angaqoshwa kuphela ngendlela eyodwa eyingqayizivele. Umthetho wesiqalo uqinisekisa ukuthi ayikho ikhodi eyisiqalo yenye. Ngekhodi, sisho izingcezu ezisetshenziselwa ukumela uhlamvu oluthile. Esibonelweni esingenhla 0 isiqalo 011, ephula umthetho wesiqalo. Ngakho-ke, uma amakhodi ethu enelisa umthetho wesiqalo, khona-ke singakwazi ukuqopha ngokuhlukile (futhi ngokuphambene nalokho).
Ake siphinde sivakashele isibonelo esingenhla. Kulokhu sizokwabela izimpawu "a", "b", "c" ΠΈ "D" amakhodi anelisa umthetho wesiqalo.
a
0
b
10
c
110
d
111
Ngalokhu mbhalo wekhodi, iyunithi yezinhlamvu "baba" izofakwa ngekhodi njenge 00100100011010 (0|0|10|0|100|011|0|10). Futhi lapha 00100100011010 sesizokwazi kakade ukucacisa ngokucacile futhi sibuyele kuyunithi yezinhlamvu yethu yasekuqaleni "baba".
Ukufaka ikhodi ye-Huffman
Manje njengoba sesibhekane nombhalo wekhodi wobude obuguquguqukayo kanye nomthetho wesiqalo, ake sikhulume ngombhalo wekhodi we-Huffman.
Indlela isekelwe ekudalweni kwezihlahla kanambambili. Kuyo, i-node ingaba yokugcina noma yangaphakathi. Ekuqaleni, wonke ama-node abhekwa njengamahlamvu (ama-terminals), amelela uphawu ngokwalo nesisindo salo (okungukuthi, imvamisa yokwenzeka). Amanodi angaphakathi aqukethe isisindo somlingisi futhi abhekisela kumanodi enzalo amabili. Ngokuvumelana jikelele, bit Β«0Β» imele ukulandela igatsha kwesokunxele, futhi Β«1Β» - kwesokudla. esihlahleni esigcwele N amahlamvu kanye N-1 amanodi angaphakathi. Kunconywa ukuthi uma wakha isihlahla se-Huffman, izimpawu ezingasetshenzisiwe zilahlwe ukuze kutholwe amakhodi obude obufanele.
Sizosebenzisa ulayini obalulekile ukuze sakhe isihlahla se-Huffman, lapho i-node ene-frequency ephansi izonikezwa kuqala kakhulu. Izinyathelo zokwakha zichazwe ngezansi:
- Dala inodi yeqabunga yohlamvu ngalunye futhi ubangeze kulayini obalulekile.
- Nakuba kunamakhasi angaphezu kwelilodwa kulayini, yenza lokhu okulandelayo:
- Susa amanodi amabili ngokubaluleke kakhulu (imvamisa ephansi) emgqeni;
- Dala i-node entsha yangaphakathi, lapho lawa ma-node amabili azoba izingane, futhi imvamisa yokwenzeka izolingana nesamba samafrikhwensi alawa ma-node amabili.
- Engeza inodi entsha kulayini obalulekile.
- Okuwukuphela kwe-node esele kuyoba impande, futhi lokhu kuzoqedela ukwakhiwa kwesihlahla.
Ake sithi sinombhalo othile oqukethe izinhlamvu kuphela "a B C D" ΠΈ "futhi", futhi amaza okwenzeka kwawo angu-15, 7, 6, 6, no-5, ngokulandelana. Ngezansi kunemifanekiso ebonisa izinyathelo ze-algorithm.
Indlela esuka empandeni iye kunoma iyiphi inodi yesiphetho izogcina ikhodi yesiqalo efanelekile (eyaziwa nangokuthi ikhodi ye-Huffman) ehambisana nohlamvu oluhlobene naleyo nodi yesiphetho.
Isihlahla se-Huffman
Ngezansi uzothola ukuqaliswa kwe-algorithm yokucindezela kwe-Huffman ku-C++ ne-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;
// 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);
}
}Qaphela: inkumbulo esetshenziswa iyunithi yezinhlamvu engu-47 * 8 = 376 bits futhi intambo ekhodiwe ingamabhithi angu-194 kuphela i.e. idatha icindezelwe cishe ngama-48%. Kuhlelo lwe-C++ olungenhla, sisebenzisa isigaba seyunithi yezinhlamvu ukugcina iyunithi yezinhlamvu efakwe ikhodi ukuze senze uhlelo lufundeke.
Ngoba izakhiwo zedatha zomugqa ezibalulekile ezisebenza kahle zidinga ukufakwa ngakunye O(log(N)) isikhathi, kodwa esihlahleni esiphelele kanambambili nge N eshiya ekhona I-2N-1 ama-node, futhi isihlahla se-Huffman siyisihlahla esiphelele kanambambili, bese i-algorithm ingena O(Nlog(N)) isikhathi, kuphi N - Izinhlamvu.
Imithombo:
Source: www.habr.com