Antaŭ la komenco de la kurso pretigis por vi tradukon de alia utila materialo.
Huffman-kodigo estas datumkunprema algoritmo, kiu formulas la bazan ideon de dosierkunpremo. En ĉi tiu artikolo, ni parolos pri fiksa kaj ŝanĝiĝema kodado, unike malkodeblaj kodoj, prefiksaj reguloj kaj konstruado de Huffman-arbo.
Ni scias, ke ĉiu signo estas konservita kiel sekvenco de 0'oj kaj 1'oj kaj okupas 8 bitojn. Ĉi tio estas nomita fikslonga kodado ĉar ĉiu karaktero uzas la saman fiksan nombron da bitoj por stoki.
Ni diru, ke ni ricevas tekston. Kiel ni povas redukti la kvanton de spaco necesa por stoki ununuran signon?
La ĉefa ideo estas ŝanĝiĝema kodado. Ni povas uzi la fakton, ke iuj signoj en la teksto aperas pli ofte ol aliaj () evoluigi algoritmon kiu reprezentos la saman sekvencon de karakteroj en malpli da bitoj. En ŝanĝiĝema kodado, ni atribuas al signoj varian nombron da bitoj, depende de kiom ofte ili aperas en difinita teksto. Eventuale, iuj signoj povas preni eĉ nur 1 biton, dum aliaj povas preni 2 bitojn, 3 aŭ pli. La problemo kun ŝanĝiĝema kodado estas nur la posta malkodado de la sekvenco.
Kiel, sciante la sinsekvon de bitoj, malkodi ĝin malambigue?
Konsideru la linion "abacdab". Ĝi havas 8 signojn, kaj dum kodado de fiksa longo, ĝi bezonos 64 bitojn por konservi ĝin. Notu, ke la simbolfrekvenco "a", "b", "c" и "D" egalas 4, 2, 1, 1 respektive. Ni provu imagi "abacdab" malpli da pecoj, uzante la fakton ke "al" okazas pli ofte ol "B"kaj "B" okazas pli ofte ol "c" и "D". Ni komencu per kodigo "al" kun unu bito egala al 0, "B" ni asignos du-bitan kodon 11, kaj uzante tri bitojn 100 kaj 011 ni kodos "c" и "D".
Kiel rezulto, ni ricevos:
a
0
b
11
c
100
d
011
Do la linio "abacdab" ni kodos kiel 00110100011011 (0|0|11|0|100|011|0|11)uzante la suprajn kodojn. Tamen, la ĉefa problemo estos en malkodado. Kiam ni provas malkodi la ŝnuron 00110100011011, ni ricevas ambiguan rezulton, ĉar ĝi povas esti reprezentita kiel:
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
...
kaj tiel plu.
Por eviti ĉi tiun ambiguecon, ni devas certigi, ke nia kodado kontentigas tian koncepton kiel prefiksa regulo, kiu siavice implicas ke la kodoj nur povas esti malkoditaj en unu unika maniero. La prefiksa regulo certigas, ke neniu kodo estas prefikso de alia. Per kodo, ni signifas la bitojn uzatajn por reprezenti apartan signon. En la supra ekzemplo 0 estas prefikso 011, kiu malobservas la prefiksan regulon. Do, se niaj kodoj kontentigas la prefiksan regulon, tiam ni povas unike malkodi (kaj inverse).
Ni rerigardu la supran ekzemplon. Ĉi-foje ni asignos por simboloj "a", "b", "c" и "D" kodoj kiuj kontentigas la prefiksan regulon.
a
0
b
10
c
110
d
111
Kun ĉi tiu kodado, la ĉeno "abacdab" estos kodita kiel 00100100011010 (0|0|10|0|100|011|0|10). Sed 00100100011010 ni jam povos malambigue malkodi kaj reveni al nia origina ĉeno "abacdab".
Huffman-kodigo
Nun, ke ni traktis varialongan kodigon kaj la prefiksan regulon, ni parolu pri Huffman-kodado.
La metodo baziĝas sur la kreado de binaraj arboj. En ĝi, la nodo povas esti aŭ fina aŭ interna. Komence, ĉiuj nodoj estas konsiderataj folioj (terminaloj), kiuj reprezentas la simbolon mem kaj ĝian pezon (tio estas, la ofteco de apero). La internaj nodoj enhavas la pezon de la karaktero kaj rilatas al du descendaj nodoj. Laŭ ĝenerala interkonsento, iom "0" reprezentas sekvante la maldekstran branĉon, kaj "1" - dekstre. en plena arbo N folioj kaj N-1 internaj nodoj. Estas rekomendite ke dum konstruado de Huffman-arbo, neuzataj simboloj estu forĵetitaj por akiri optimumajn longokodojn.
Ni uzos prioritatan vicon por konstrui Huffman-arbon, kie la nodo kun la plej malalta ofteco ricevos la plej altan prioritaton. La konstruaj paŝoj estas priskribitaj malsupre:
- Kreu folian nodon por ĉiu karaktero kaj aldonu ilin al la prioritata vico.
- Dum estas pli ol unu folio en la atendovico, faru la jenon:
- Forigu la du nodojn kun la plej alta prioritato (plej malalta frekvenco) el la atendovico;
- Kreu novan internan nodon, kie ĉi tiuj du nodoj estos infanoj, kaj la ofteco de okazo estos egala al la sumo de la frekvencoj de ĉi tiuj du nodoj.
- Aldonu novan nodon al la prioritata atendovico.
- La sola restanta nodo estos la radiko, kaj ĉi tio kompletigos la konstruadon de la arbo.
Imagu, ke ni havas iun tekston kiu konsistas nur el signoj "a", "b", "c", "d" и "kaj", kaj iliaj aperfrekvencoj estas 15, 7, 6, 6, kaj 5, respektive. Malsupre estas ilustraĵoj kiuj reflektas la paŝojn de la algoritmo.
Pado de la radiko ĝis iu finnodo stokos la optimuman prefiksan kodon (ankaŭ konatan kiel la Huffman-kodon) egalrilatantan al la karaktero asociita kun tiu finnodo.
Huffman-arbo
Malsupre vi trovos la efektivigon de la Huffman kunprema algoritmo en C++ kaj 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);
}
}Notu: la memoro uzata de la eniga ĉeno estas 47 * 8 = 376 bitoj kaj la kodita ĉeno estas nur 194 bitoj t.e. datumoj estas kunpremitaj je ĉirkaŭ 48%. En la C++-programo supre, ni uzas la string klason por stoki la kodita string por fari la programon legebla.
Ĉar efikaj prioritataj vicodatenstrukturoj postulas per enmeto O(log(N)) tempo, sed en kompleta binara arbo kun N ĉeestas folioj 2N-1 nodoj, kaj la Huffman-arbo estas kompleta binara arbo, tiam la algoritmo eniras O(Nlog(N)) tempo, kie N - Karakteroj.
Fontoj:
fonto: www.habr.com