Asanayambe maphunziro anakukonzerani kumasulira kwa nkhani ina yothandiza.
Huffman coding ndi data compression algorithm yomwe imapanga lingaliro loyambira la compression ya mafayilo. M'nkhaniyi, tikambirana za ma encoding okhazikika komanso osinthika, ma code osinthika mwapadera, malamulo oyambira, ndikumanga mtengo wa Huffman.
Tikudziwa kuti munthu aliyense amasungidwa ngati 0 ndi 1 ndipo amatenga 8 bits. Izi zimatchedwa encoding yautali wokhazikika chifukwa munthu aliyense amagwiritsa ntchito manambala omwewo kuti asungidwe.
Tinene kuti tapatsidwa malemba. Kodi tingachepetse bwanji danga lofunika kusunga munthu mmodzi?
Lingaliro lalikulu ndikusindikiza kutalika kosiyanasiyana. Titha kugwiritsa ntchito mfundo yoti zilembo zina m'mawuwa zimapezeka nthawi zambiri kuposa zina () kupanga aligorivimu yomwe idzayimire mndandanda womwewo wa zilembo m'tinthu tating'ono. Mu encoding yautali wosiyanasiyana, timagawira zilembo kuchuluka kwa ma bits, kutengera momwe amawonekera pafupipafupi palemba lomwe laperekedwa. Pamapeto pake, zilembo zina zimatha kutenga pang'ono ngati 1 bit, pomwe zina zimatha kutenga 2 bits, 3 kapena kupitilira apo. Vuto la kabisidwe kautali wosiyanasiyana ndi kungosankhira motsatira motsatizana.
Kodi, podziwa kutsatizana kwa ma bits, mungasinthe bwanji mosadziwika bwino?
Taganizirani mzerewu "abale". Ili ndi zilembo 8, ndipo ikayika utali wokhazikika, imafunika ma bits 64 kuti isunge. Dziwani kuti pafupipafupi chizindikiro "a", "b", "c" ΠΈ "D" zikufanana ndi 4, 2, 1, 1 motsatana. Tiyeni tiyese kulingalira "abale" pang'ono, pogwiritsa ntchito mfundo yakuti "ku" zimachitika pafupipafupi kuposa "B"ndi "B" zimachitika pafupipafupi kuposa "c" ΠΈ "D". Tiyeni tiyambe ndi coding "ku" ndi chidutswa chimodzi chofanana ndi 0, "B" Tidzagawira nambala ziwiri 11, ndipo pogwiritsa ntchito magawo atatu 100 ndi 011 tidzakhazikitsa "c" ΠΈ "D".
Chifukwa chake, tipeza:
a
0
b
11
c
100
d
011
Ndiye mzere "abale" tidzalemba ngati 00110100011011 (0|0|11|0|100|011|0|11)pogwiritsa ntchito zizindikiro pamwambapa. Komabe, vuto lalikulu lidzakhala pakujambula. Pamene ife tikuyesera decode chingwe 00110100011011, timapeza zotsatira zosamveka, chifukwa zitha kuyimiridwa monga:
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
...
ndi zina zotero.
Kuti tipewe kusamvetsetsana kumeneku, tiyenera kuwonetsetsa kuti kabisidwe kathu kakukwaniritsa mfundo ngati lamulo lachiyambi, zomwe zikutanthauza kuti ma code amatha kusinthidwa mwanjira imodzi yapadera. Lamulo lachiyambi limatsimikizira kuti palibe code yomwe ili ndi chiyambi cha ina. Ndi code, tikutanthauza ma bits omwe amagwiritsidwa ntchito kuimira munthu wina. Mu chitsanzo pamwambapa 0 ndi chiyambi 011, zomwe zimaphwanya lamulo lachiyambi. Chifukwa chake, ngati ma code athu akwaniritsa lamulo lachiyambi, ndiye kuti titha kuzindikira mwapadera (ndi mosemphanitsa).
Tiyeni tionenso chitsanzo pamwambapa. Nthawi ino tigawira zizindikiro "a", "b", "c" ΠΈ "D" ma code omwe amakwaniritsa lamulo lachiyambi.
a
0
b
10
c
110
d
111
Ndi encoding iyi, chingwe "abale" idzasungidwa ngati 00100100011010 (0|0|10|0|100|011|0|10). Koma 00100100011010 titha kutsimikiza kale ndikubwerera ku chingwe chathu choyambirira "abale".
Huffman kodi
Tsopano popeza tathana ndi ma encoding a kutalika kosiyana ndi lamulo lachiyambi, tiyeni tikambirane za Huffman encoding.
Njirayi imachokera ku chilengedwe cha mitengo ya binary. Mmenemo, node ikhoza kukhala yomaliza kapena yamkati. Poyambirira, mfundo zonse zimatengedwa ngati masamba (zomaliza), zomwe zimayimira chizindikiro chokha ndi kulemera kwake (ndiko kuti, kuchuluka kwa zochitika). Manode amkati ali ndi kulemera kwa khalidwe ndipo amatchula mfundo ziwiri za mbadwa. Mwa mgwirizano wamba, pang'ono "0" imayimira kutsatira nthambi yakumanzere, ndi "1" - kumanja. mu mtengo wathunthu N masamba ndi N-1 mfundo zamkati. Ndikofunikira kuti popanga mtengo wa Huffman, zizindikilo zosagwiritsidwa ntchito zitayidwe kuti mupeze ma code aatali oyenera.
Tidzagwiritsa ntchito mzere wofunikira kuti timange mtengo wa Huffman, pomwe node yokhala ndi ma frequency otsika kwambiri idzapatsidwa patsogolo kwambiri. Zomangamanga zikufotokozedwa pansipa:
- Pangani tsamba lamtundu uliwonse ndikuwonjezera pamzere wofunikira.
- Ngakhale pali mapepala angapo pamzere, chitani zotsatirazi:
- Chotsani mfundo ziwiri zomwe zili patsogolo kwambiri (mafupipafupi otsika kwambiri) pamzere;
- Pangani node yatsopano yamkati, pomwe ma node awiriwa adzakhala ana, ndipo kuchuluka kwa zochitika kudzakhala kofanana ndi kuchuluka kwa ma frequency a mfundo ziwirizi.
- Onjezani node yatsopano pamzere woyamba.
- Node yotsalayo idzakhala muzu, ndipo izi zidzamaliza ntchito yomanga mtengowo.
Tiyerekeze kuti tili ndi malemba omwe ali ndi zilembo zokha "a", "b", "c", "d" ΠΈ "ndi", ndipo ma frequency awo ndi 15, 7, 6, 6, ndi 5, motsatana. Pansipa pali zithunzi zomwe zikuwonetsa masitepe a algorithm.
Njira yochokera ku muzu kupita ku node iliyonse yomaliza idzasunga nambala yoyenera (yomwe imadziwikanso kuti Huffman code) yogwirizana ndi mawonekedwe omaliza.
Mtengo wa Huffman
Pansipa mupeza kukhazikitsidwa kwa Huffman compression algorithm mu C++ ndi 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);
}
}Taonani: kukumbukira komwe kumagwiritsidwa ntchito ndi chingwe cholowetsa ndi 47 * 8 = 376 bits ndipo chingwe chotsekedwa ndi 194 bits i.e. deta ndi wothinikizidwa pafupifupi 48%. Mu pulogalamu ya C ++ pamwambapa, timagwiritsa ntchito kalasi ya zingwe kusunga chingwe chosungidwa kuti pulogalamuyo iwerengedwe.
Chifukwa mawonekedwe amizere ofunikira amafunikira pakuyika kulikonse O(logi(N)) nthawi, koma mu mtengo wathunthu bayinare ndi N masamba alipo 2N-1 nodes, ndipo mtengo wa Huffman ndi mtengo wathunthu wa binary, ndiye kuti algorithm imalowa mkati O(Nlog(N)) nthawi, ku N - Makhalidwe.
Zotsatira:
Source: www.habr.com