Sa wala pa magsugod ang kurso nag-andam alang kanimo ug hubad sa laing mapuslanong materyal.
Ang Huffman coding usa ka data compression algorithm nga nagporma sa batakang ideya sa file compression. Niini nga artikulo, maghisgot kita bahin sa fixed ug variable length encoding, talagsaon nga decodable code, prefix rules, ug pagtukod ug Huffman tree.
Nahibal-an namon nga ang matag karakter gitipigan ingon usa ka han-ay sa 0 ug 1 ug adunay 8 ka bit. Gitawag kini nga fixed length encoding tungod kay ang matag karakter naggamit sa parehas nga fixed nga gidaghanon sa mga bits aron tipigan.
Ingnon ta nga gihatagan mig text. Sa unsa nga paagi kita makapakunhod sa gidaghanon sa luna nga gikinahanglan sa pagtipig sa usa ka karakter?
Ang panguna nga ideya mao ang variable nga gitas-on nga pag-encode. Mahimo natong gamiton ang kamatuoran nga ang pipila ka mga karakter sa teksto mas kanunay mahitabo kay sa uban () aron makahimo ug algorithm nga magrepresentar sa parehas nga pagkasunod-sunod sa mga karakter sa gamay nga piraso. Sa variable nga gitas-on nga pag-encode, nag-assign kami sa mga karakter sa usa ka variable nga gidaghanon sa mga bit, depende kung unsa ka sagad kini makita sa usa ka teksto. Sa kadugayan, ang ubang mga karakter mahimong mokuha ug 1 ka gamay, samtang ang uban mahimong 2 ka bit, 3 o labaw pa. Ang problema sa variable nga gitas-on nga pag-encode mao lamang ang sunod nga pag-decode sa han-ay.
Giunsa, nahibal-an ang han-ay sa mga tipik, pag-decode niini nga dili klaro?
Tagda ang linya "abacdab". Kini adunay 8 nga mga karakter, ug kung mag-encode sa usa ka pirmi nga gitas-on, magkinahanglan kini og 64 bits aron matipigan kini. Timan-i nga ang simbolo frequency "a", "b", "c" ΠΈ "D" katumbas sa 4, 2, 1, 1 matag usa. Atong sulayan paghanduraw "abacdab" mas gamay nga mga piraso, gamit ang kamatuoran nga "sa" mahitabo nga mas kanunay kay sa "B"ug "B" mahitabo nga mas kanunay kay sa "c" ΠΈ "D". Magsugod ta sa coding "sa" nga adunay usa ka gamay nga katumbas sa 0, "B" mag-assign kami og two-bit code 11, ug gamit ang tulo ka bits 100 ug 011 atong i-encode "c" ΠΈ "D".
Ingon usa ka sangputanan, makuha namon:
a
0
b
11
c
100
d
011
Busa ang linya "abacdab" atong i-encode ingon 00110100011011 (0|0|11|0|100|011|0|11)gamit ang mga code sa ibabaw. Bisan pa, ang panguna nga problema mao ang pag-decode. Sa diha nga kita mosulay sa pag-decode sa hilo 00110100011011, nakakuha kami usa ka dili klaro nga sangputanan, tungod kay mahimo kini irepresentar ingon:
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
...
ug uban pa.
Aron malikayan kini nga pagkadili klaro, kinahanglan natong sigurohon nga ang atong pag-encode makatagbaw sa maong konsepto sama sa lagda sa prefix, nga sa baylo nagpasabot nga ang mga kodigo mahimo lamang ma-decode sa usa ka talagsaon nga paagi. Ang lagda sa prefix nagsiguro nga walay code ang prefix sa lain. Pinaagi sa code, gipasabut namon ang mga piraso nga gigamit sa pagrepresentar sa usa ka partikular nga karakter. Sa pananglitan sa ibabaw 0 usa ka prefix 011, nga naglapas sa lagda sa prefix. Busa, kung ang atong mga code makatagbaw sa prefix nga lagda, nan kita talagsaon nga maka-decode (ug vice versa).
Atong balikon ang pananglitan sa ibabaw. Niining higayona kita mag-assign alang sa mga simbolo "a", "b", "c" ΠΈ "D" mga code nga makatagbaw sa lagda sa prefix.
a
0
b
10
c
110
d
111
Uban niini nga pag-encode, ang string "abacdab" ma-encode ingon 00100100011010 (0|0|10|0|100|011|0|10). Ug dinhi 00100100011010 makahimo na kami sa dili klaro nga pag-decode ug pagbalik sa among orihinal nga hilo "abacdab".
Huffman coding
Karon nga nahisgotan na nato ang variable length encoding ug ang prefix rule, atong hisgotan ang Huffman encoding.
Ang pamaagi gibase sa paghimo sa binary nga mga kahoy. Diha niini, ang node mahimong final o internal. Sa sinugdan, ang tanan nga mga node giisip nga mga dahon (terminal), nga nagrepresentar sa simbolo mismo ug ang gibug-aton niini (nga mao, ang frequency sa panghitabo). Ang mga internal nga node naglangkob sa gibug-aton sa karakter ug nagtumong sa duha ka kaliwat nga node. Pinaagi sa kinatibuk-ang kasabutan, gamay 0 nagrepresentar sa pagsunod sa wala nga sanga, ug 1 - sa tuo. sa puno nga kahoy N dahon ug N-1 internal nga mga node. Girekomenda nga kung maghimo usa ka kahoy nga Huffman, ang wala gigamit nga mga simbolo ilabay aron makuha ang labing kaayo nga mga code sa gitas-on.
Maggamit mi og priority queue sa paghimo og Huffman tree, diin ang node nga adunay pinakaubos nga frequency hatagan og pinakataas nga prayoridad. Ang mga lakang sa pagtukod gihulagway sa ubos:
- Paghimo ug leaf node para sa matag karakter ug idugang kini sa priority queue.
- Samtang adunay labaw pa sa usa ka sheet sa pila, buhata ang mosunod:
- Kuhaa ang duha ka node nga adunay pinakataas nga prayoridad (labing ubos nga frequency) gikan sa pila;
- Paghimo og usa ka bag-ong internal nga node, diin kining duha ka mga node mahimong mga bata, ug ang frequency sa panghitabo mahimong katumbas sa gidaghanon sa mga frequency niining duha ka mga node.
- Pagdugang og bag-ong node sa priority queue.
- Ang nahabilin nga node mao ang gamut, ug kini makompleto ang pagtukod sa kahoy.
Hunahunaa nga kita adunay pipila ka teksto nga naglangkob lamang sa mga karakter "abakada" ΠΈ "ug", ug ang ilang frequency frequency mao ang 15, 7, 6, 6, ug 5, matag usa. Sa ubos mao ang mga ilustrasyon nga nagpakita sa mga lakang sa algorithm.
Ang usa ka agianan gikan sa gamut ngadto sa bisan unsang end node magtipig sa labing maayo nga prefix code (nailhan usab nga Huffman code) nga katumbas sa karakter nga may kalabutan sa katapusan nga node.
Huffman nga kahoy
Sa ubos imong makit-an ang pagpatuman sa Huffman compression algorithm sa C++ ug 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);
}
}Mubo nga sulat: ang memorya nga gigamit sa input string mao ang 47 * 8 = 376 bits ug ang na-encode nga string kay 194 bits lang i.e. data gi-compress sa mga 48%. Sa C++ nga programa sa ibabaw, gigamit namo ang string class aron tipigan ang na-encode nga string aron mahimo nga mabasa ang programa.
Tungod kay ang episyente nga priority queue data structures nagkinahanglan matag insertion O(log(N)) panahon, apan sa usa ka bug-os nga binary nga kahoy uban sa N mga dahon nga anaa 2N-1 nodes, ug ang Huffman tree usa ka kompleto nga binary tree, unya ang algorithm modagan O(Nlog(N)) oras, diin N - Mga karakter.
Mga Tinubdan:
Source: www.habr.com