Ikastaroa hasi baino lehen beste material erabilgarriaren itzulpena prestatu dizu.
Huffman kodeketa fitxategien konpresioaren oinarrizko ideia formulatzen duen datuen konpresioaren algoritmoa da. Artikulu honetan, luzera finko eta aldakorreko kodeketaz, kode esklusiboki deskodegarriez, aurrizki-arauez eta Huffman zuhaitz bat eraikitzeaz hitz egingo dugu.
Badakigu karaktere bakoitza 0 eta 1 sekuentzia gisa gordetzen dela eta 8 bit hartzen dituela. Luzera finkoko kodeketa deitzen zaio karaktere bakoitzak bit kopuru finko bera erabiltzen duelako gordetzeko.
Demagun testu bat dugula. Nola murriztu dezakegu karaktere bakarra gordetzeko behar den espazioa?
Ideia nagusia luzera aldakorreko kodeketa da. Testuko karaktere batzuk besteak baino maizago agertzen direla erabil dezakegu () karaktere-segida bera bit gutxiagotan irudikatuko duen algoritmo bat garatzeko. Luzera aldakorreko kodetzean, karaktereei bit-kopuru aldakorra esleitzen diegu, testu jakin batean zenbat maiztasunarekin agertzen diren arabera. Azkenean, karaktere batzuek bit bat baino ez dute hartu, beste batzuek, berriz, 1 bit, 2 edo gehiago. Luzera aldakorreko kodeketaren arazoa sekuentziaren ondorengo deskodetzea baino ez da.
Nola, bit-segida ezagututa, anbiguorik gabe deskodetu?
Demagun lerroa "abacdab". 8 karaktere ditu, eta luzera finko bat kodetzean, 64 bit beharko ditu gordetzeko. Kontuan izan sinboloaren maiztasuna "a", "b", "c" ΠΈ "D" 4, 2, 1, 1 berdinak dira hurrenez hurren. Saia gaitezen imajinatzen "abacdab" bit gutxiago, hori erabiliz "nora" baino maizago gertatzen da "B"Eta "B" baino maizago gertatzen da "c" ΠΈ "D". Has gaitezen kodetzen "nora" 0-ren bit batekin, "B" bi biteko 11 kodea esleituko dugu, eta 100 eta 011 hiru bit erabiliz kodetuko dugu "c" ΠΈ "D".
Ondorioz, lortuko dugu:
a
0
b
11
c
100
d
011
Beraz, lerroa "abacdab" gisa kodetuko dugu 00110100011011 (0|0|11|0|100|011|0|11)goiko kodeak erabiliz. Hala ere, arazo nagusia deskodetzea izango da. Katea deskodetzen saiatzen garenean 00110100011011, emaitza anbiguo bat lortuko dugu, honela irudika daitekeelako:
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
...
eta abar.
Anbiguotasun hori saihesteko, gure kodeketak bezalako kontzeptu bat betetzen duela ziurtatu behar dugu aurrizkiaren araua, eta horrek esan nahi du kodeak modu bakarrean soilik deskodetu daitezkeela. Aurrizkiaren arauak bermatzen du koderik ez dela beste baten aurrizkia. Kode bidez, karaktere jakin bat irudikatzeko erabiltzen diren bitak esan nahi dugu. Goiko adibidean 0 aurrizki bat da 011, aurrizkiaren araua urratzen duena. Beraz, gure kodeak aurrizkiaren araua betetzen badute, orduan modu esklusiboan deskodetu dezakegu (eta alderantziz).
Errepasa dezagun goiko adibidea. Oraingoan ikurrak esleituko ditugu "a", "b", "c" ΠΈ "D" aurrizkiaren araua betetzen duten kodeak.
a
0
b
10
c
110
d
111
Kodeketa honekin, katea "abacdab" gisa kodetuko da 00100100011010 (0|0|10|0|100|011|0|10). Baina 00100100011010 jadanik anbiguorik gabe deskodetu eta gure jatorrizko katera itzultzeko gai izango gara "abacdab".
Huffman kodeketa
Orain, luzera aldakorreko kodeketa eta aurrizkiaren araua landu ditugunean, hitz egin dezagun Huffman kodeketari buruz.
Metodoa zuhaitz bitarren sorreran oinarritzen da. Bertan, nodoa azkena edo barnekoa izan daiteke. Hasieran, nodo guztiak hostotzat hartzen dira (terminalak), sinboloa bera eta bere pisua (hau da, maiztasuna) adierazten dutenak. Barne-nodoek karakterearen pisua dute eta ondorengo bi nodo aipatzen dituzte. Akordio orokorrez, bit "0" ezkerreko adarrari jarraituz adierazten du, eta "1" - eskuinean. zuhaitz betean N hostoak eta N-1 barne-nodoak. Gomendagarria da Huffman zuhaitz bat eraikitzean, erabili gabeko ikurrak baztertzea luzera-kode optimoak lortzeko.
Lehentasun-ilara bat erabiliko dugu Huffman zuhaitz bat eraikitzeko, non maiztasun txikiena duen nodoari lehentasun handiena emango zaion. Eraikuntza-urratsak jarraian deskribatzen dira:
- Sortu hosto-nodo bat karaktere bakoitzarentzat eta gehitu lehentasun-ilarara.
- Ilaran orri bat baino gehiago dagoen bitartean, egin hau:
- Kendu lehentasun handiena duten bi nodoak (maiztasun txikiena) ilaratik;
- Sortu barne-nodo berri bat, non bi nodo horiek seme-alabak izango diren, eta agerraldiaren maiztasuna bi nodo horien maiztasunen baturaren berdina izango den.
- Gehitu nodo berri bat lehentasun-ilarara.
- Geratzen den nodo bakarra erroa izango da, eta honek zuhaitzaren eraikuntza amaituko du.
Imajinatu karaktereez soilik osatutako testu bat dugula "a", "b", "c", "d" ΠΈ "eta", eta haien agerraldi-maiztasunak 15, 7, 6, 6 eta 5 dira, hurrenez hurren. Jarraian, algoritmoaren urratsak islatzen dituzten ilustrazioak daude.
Errotik edozein amaierako nodorainoko bide batek amaierako nodo horri lotutako karaktereari dagokion aurrizki-kode optimoa gordeko du (Huffman kodea izenez ere ezaguna).
Huffman zuhaitza
Jarraian, Huffman konpresio algoritmoaren ezarpena aurkituko duzu C++ eta Javan:
#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);
}
}Oharra: sarrerako kateak erabiltzen duen memoria 47 * 8 = 376 bitekoa da eta kodetutako katea 194 bitekoa baino ez da, hau da. datuak %48 inguru konprimitzen dira. Goiko C++ programan, kate klasea erabiltzen dugu kodetutako katea gordetzeko, programa irakurgarria izan dadin.
Lehentasun-ilararen datu-egitura eraginkorrak txertatze bakoitzeko behar direlako O(log(N)) denbora, baina zuhaitz bitar oso batean N hostoak presente 2N-1 nodoak, eta Huffman zuhaitza zuhaitz bitar osoa da, orduan algoritmoa exekutatzen da O(Nlog(N)) denbora, non N - Pertsonaiak.
Iturriak:
Iturria: www.habr.com