Bago magsimula ang kurso naghanda para sa iyo ng pagsasalin ng isa pang kapaki-pakinabang na materyal.
Ang Huffman coding ay isang data compression algorithm na bumubuo ng pangunahing ideya ng file compression. Sa artikulong ito, pag-uusapan natin ang tungkol sa fixed at variable na haba na pag-encode, mga natatanging na-decodable na code, mga panuntunan ng prefix, at pagbuo ng Huffman tree.
Alam namin na ang bawat character ay naka-imbak bilang isang sequence ng 0's at 1's at tumatagal ng hanggang 8 bits. Ito ay tinatawag na fixed length encoding dahil ang bawat character ay gumagamit ng parehong nakapirming bilang ng mga bit upang iimbak.
Sabihin na nating binigyan tayo ng text. Paano natin mababawasan ang dami ng espasyong kailangan para mag-imbak ng isang character?
Ang pangunahing ideya ay variable length encoding. Maaari naming gamitin ang katotohanan na ang ilang mga character sa teksto ay nangyayari nang mas madalas kaysa sa iba () upang bumuo ng isang algorithm na kumakatawan sa parehong pagkakasunud-sunod ng mga character sa mas kaunting mga bit. Sa variable length encoding, nagtatalaga kami ng mga character ng variable na bilang ng mga bit, depende sa kung gaano kadalas lumalabas ang mga ito sa isang naibigay na text. Sa kalaunan, ang ilang mga character ay maaaring tumagal ng kasing liit ng 1 bit, habang ang iba ay maaaring tumagal ng 2 bits, 3 o higit pa. Ang problema sa variable length encoding ay ang kasunod na pag-decode ng sequence.
Paano, alam ang pagkakasunud-sunod ng mga bit, decode ito nang hindi malabo?
Isaalang-alang ang linya "abacdab". Mayroon itong 8 character, at kapag nag-encode ng isang nakapirming haba, kakailanganin nito ng 64 bits upang maiimbak ito. Tandaan na ang dalas ng simbolo "a", "b", "c" ΠΈ "D" katumbas ng 4, 2, 1, 1 ayon sa pagkakabanggit. Subukan nating isipin "abacdab" mas kaunting mga piraso, gamit ang katotohanan na "sa" nangyayari nang mas madalas kaysa sa "B"At "B" nangyayari nang mas madalas kaysa sa "c" ΠΈ "D". Magsimula tayo sa coding "sa" na may isang bit na katumbas ng 0, "B" magtatalaga kami ng two-bit code 11, at gamit ang tatlong bits 100 at 011 ay i-encode namin "c" ΠΈ "D".
Bilang resulta, makakakuha tayo ng:
a
0
b
11
c
100
d
011
Kaya ang linya "abacdab" i-encode namin bilang 00110100011011 (0|0|11|0|100|011|0|11)gamit ang mga code sa itaas. Gayunpaman, ang pangunahing problema ay sa pag-decode. Kapag sinubukan naming i-decode ang string 00110100011011, nakakakuha kami ng hindi maliwanag na resulta, dahil maaari itong katawanin bilang:
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
...
at iba pa
Upang maiwasan ang kalabuan na ito, dapat nating tiyakin na ang ating pag-encode ay nakakatugon sa gayong konsepto bilang tuntunin ng prefix, na nagpapahiwatig naman na ang mga code ay maaari lamang ma-decode sa isang natatanging paraan. Tinitiyak ng panuntunan ng prefix na walang code ang prefix ng isa pa. Sa pamamagitan ng code, ang ibig naming sabihin ay ang mga bit na ginamit upang kumatawan sa isang partikular na character. Sa halimbawa sa itaas 0 ay isang unlapi 011, na lumalabag sa panuntunan ng prefix. Kaya, kung natutugunan ng aming mga code ang panuntunan ng prefix, maaari naming natatanging decode (at vice versa).
Balikan natin ang halimbawa sa itaas. Sa pagkakataong ito ay magtatalaga tayo para sa mga simbolo "a", "b", "c" ΠΈ "D" mga code na nakakatugon sa panuntunan ng prefix.
a
0
b
10
c
110
d
111
Sa encoding na ito, ang string "abacdab" ie-encode bilang 00100100011010 (0|0|10|0|100|011|0|10). Ngunit ang 00100100011010 magagawa na nating malinaw na mag-decode at bumalik sa ating orihinal na string "abacdab".
Huffman coding
Ngayong napag-usapan na natin ang variable length encoding at ang panuntunan ng prefix, pag-usapan natin ang tungkol sa pag-encode ng Huffman.
Ang pamamaraan ay batay sa paglikha ng mga binary tree. Sa loob nito, ang node ay maaaring maging pangwakas o panloob. Sa una, ang lahat ng mga node ay itinuturing na mga dahon (terminal), na kumakatawan sa simbolo mismo at ang bigat nito (iyon ay, ang dalas ng paglitaw). Ang mga panloob na node ay naglalaman ng bigat ng karakter at tumutukoy sa dalawang descendant node. Sa pamamagitan ng pangkalahatang kasunduan, bit "0" kumakatawan sa pagsunod sa kaliwang sangay, at "1" - sa kanan. sa buong puno N dahon at N-1 panloob na mga node. Inirerekomenda na kapag gumagawa ng Huffman tree, ang mga hindi ginagamit na simbolo ay itapon upang makakuha ng pinakamainam na mga code ng haba.
Gagamit kami ng priority queue para bumuo ng Huffman tree, kung saan ang node na may pinakamababang frequency ay bibigyan ng pinakamataas na priyoridad. Ang mga hakbang sa pagtatayo ay inilarawan sa ibaba:
- Gumawa ng leaf node para sa bawat character at idagdag ang mga ito sa priority queue.
- Habang mayroong higit sa isang sheet sa pila, gawin ang sumusunod:
- Alisin ang dalawang node na may pinakamataas na priyoridad (pinakamababang dalas) mula sa pila;
- Gumawa ng bagong panloob na node, kung saan ang dalawang node na ito ay magiging mga bata, at ang dalas ng paglitaw ay magiging katumbas ng kabuuan ng mga frequency ng dalawang node na ito.
- Magdagdag ng bagong node sa priority queue.
- Ang tanging natitirang node ay ang ugat, at ito ay makumpleto ang pagtatayo ng puno.
Isipin na mayroon kaming ilang teksto na binubuo lamang ng mga character "a B C D" ΠΈ "at", at ang kanilang mga frequency ng paglitaw ay 15, 7, 6, 6, at 5, ayon sa pagkakabanggit. Nasa ibaba ang mga larawang nagpapakita ng mga hakbang ng algorithm.
Ang isang path mula sa ugat hanggang sa anumang dulong node ay mag-iimbak ng pinakamainam na prefix code (kilala rin bilang Huffman code) na naaayon sa karakter na nauugnay sa dulong node na iyon.
Puno ng Huffman
Sa ibaba makikita mo ang pagpapatupad ng Huffman compression algorithm sa C++ at 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);
}
}Tandaan: ang memory na ginamit ng input string ay 47 * 8 = 376 bits at ang naka-encode na string ay 194 bits lamang i.e. ang data ay na-compress ng halos 48%. Sa C++ program sa itaas, ginagamit namin ang string class para iimbak ang naka-encode na string para gawing nababasa ang program.
Dahil ang mahusay na priyoridad na mga istruktura ng data ng pila ay nangangailangan sa bawat pagpasok O(log(N)) oras, ngunit sa isang kumpletong binary tree na may N mga dahon na naroroon 2N-1 nodes, at ang Huffman tree ay isang kumpletong binary tree, pagkatapos ay tumatakbo ang algorithm O(Nlog(N)) oras, saan N - Mga tauhan.
Pinagmulan:
Pinagmulan: www.habr.com