Qabel il-bidu tal-kors ippreparat għalik traduzzjoni ta’ materjal ieħor utli.
Il-kodifikazzjoni Huffman hija algoritmu tal-kompressjoni tad-dejta li jifformula l-idea bażika tal-kompressjoni tal-fajl. F'dan l-artikolu, se nitkellmu dwar kodifikazzjoni ta 'tul fiss u varjabbli, kodiċijiet dekodifikabbli unikament, regoli ta' prefiss, u bini ta 'siġra Huffman.
Aħna nafu li kull karattru huwa maħżun bħala sekwenza ta '0's u 1's u jieħu 8 bits. Dan jissejjaħ kodifikazzjoni ta 'tul fiss minħabba li kull karattru juża l-istess numru fiss ta' bits biex jaħżen.
Ejja ngħidu li aħna qed jingħataw test. Kif nistgħu nnaqqsu l-ammont ta’ spazju meħtieġ biex naħżen karattru wieħed?
L-idea ewlenija hija kodifikazzjoni ta 'tul varjabbli. Nistgħu nużaw il-fatt li xi karattri fit-test iseħħu aktar spiss minn oħrajn () biex tiżviluppa algoritmu li jirrappreżenta l-istess sekwenza ta' karattri f'inqas bits. F'kodifikazzjoni ta 'tul varjabbli, aħna nassenjaw karattri numru varjabbli ta' bits, skond kemm-il darba jidhru f'test partikolari. Eventwalment, xi karattri jistgħu jieħdu mill-inqas 1 bit, filwaqt li oħrajn jistgħu jieħdu 2 bits, 3 jew aktar. Il-problema bil-kodifikazzjoni ta 'tul varjabbli hija biss id-dekodifikazzjoni sussegwenti tas-sekwenza.
Kif, meta tkun taf is-sekwenza tal-bits, tiddekodifikaha mingħajr ambigwità?
Ikkunsidra l-linja "abacdab". Għandu 8 karattri, u meta jikkodifika tul fiss, ikollu bżonn 64 bit biex jaħżen. Innota li l-frekwenza tas-simbolu "a", "b", "ċ" и "D" ugwali 4, 2, 1, 1 rispettivament. Ejja nippruvaw nimmaġinaw "abacdab" inqas bits, bl-użu tal-fatt li "lil" iseħħ aktar spiss milli "B"U "B" iseħħ aktar spiss milli "ċ" и "D". Nibdew billi nikkodifikaw "lil" b'bit ugwali għal 0, "B" aħna se jassenjaw kodiċi ta 'żewġ bits 11, u bl-użu ta' tliet bits 100 u 011 se nikkodifikaw "ċ" и "D".
Bħala riżultat, se jkollna:
a
0
b
11
c
100
d
011
Allura l-linja "abacdab" aħna se jikkodifikaw bħala 00110100011011 (0|0|11|0|100|011|0|11)billi tuża l-kodiċi ta’ hawn fuq. Madankollu, il-problema ewlenija se tkun fid-dekodifikazzjoni. Meta nippruvaw jiddekowdja l-istring 00110100011011, niksbu riżultat ambigwu, peress li jista 'jiġi rappreżentat bħala:
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
...
eċċ
Biex tiġi evitata din l-ambigwità, irridu niżguraw li l-kodifikazzjoni tagħna tissodisfa tali kunċett bħal regola tal-prefiss, li mbagħad jimplika li l-kodiċijiet jistgħu jiġu dekodifikati biss b'mod uniku wieħed. Ir-regola tal-prefiss tiżgura li l-ebda kodiċi ma jkun prefiss ta' ieħor. B'kodiċi, nifhmu l-bits użati biex jirrappreżentaw karattru partikolari. Fl-eżempju hawn fuq 0 huwa prefiss 011, li tikser ir-regola tal-prefiss. Allura, jekk il-kodiċijiet tagħna jissodisfaw ir-regola tal-prefiss, allura nistgħu tiddekodifika b'mod uniku (u viċi versa).
Ejja nerġgħu nżuru l-eżempju ta 'hawn fuq. Din id-darba se jassenjaw għal simboli "a", "b", "ċ" и "D" kodiċijiet li jissodisfaw ir-regola tal-prefiss.
a
0
b
10
c
110
d
111
B'din il-kodifikazzjoni, is-sekwenza "abacdab" se jkun kodifikat bħala 00100100011010 (0|0|10|0|100|011|0|10). Iżda l- 00100100011010 diġà se nkunu nistgħu niddekodifikaw mingħajr ambigwità u nirritornaw għas-sekwenza oriġinali tagħna "abacdab".
Kodifikazzjoni Huffman
Issa li ttrattati l-kodifikazzjoni ta 'tul varjabbli u r-regola tal-prefiss, ejja nitkellmu dwar l-kodifikazzjoni ta' Huffman.
Il-metodu huwa bbażat fuq il-ħolqien ta 'siġar binarji. Fiha, in-nodu jista 'jkun jew finali jew intern. Inizjalment, in-nodi kollha huma kkunsidrati bħala weraq (terminals), li jirrappreżentaw is-simbolu nnifsu u l-piż tiegħu (jiġifieri, il-frekwenza tal-okkorrenza). In-nodi interni fihom il-piż tal-karattru u jirreferu għal żewġ nodi dixxendenti. Bi qbil ġenerali, bit «0» jirrappreżenta wara l-fergħa tax-xellug, u «1» - fuq il-lemin. fis-siġra sħiħa N weraq u N-1 nodi interni. Huwa rakkomandat li meta tinbena siġra Huffman, simboli mhux użati jintremew biex jinkisbu l-aħjar kodiċi ta 'tul.
Se nużaw kju prijoritarju biex nibnu siġra Huffman, fejn in-nodu bl-inqas frekwenza se jingħata l-ogħla prijorità. Il-passi tal-kostruzzjoni huma deskritti hawn taħt:
- Oħloq node tal-weraq għal kull karattru u żidhom mal-kju prijoritarju.
- Filwaqt li hemm aktar minn folja waħda fil-kju, agħmel dan li ġej:
- Neħħi ż-żewġ nodi bl-ogħla prijorità (l-inqas frekwenza) mill-kju;
- Oħloq nodu intern ġdid, fejn dawn iż-żewġ nodi se jkunu tfal, u l-frekwenza tal-okkorrenza tkun ugwali għas-somma tal-frekwenzi ta 'dawn iż-żewġ nodi.
- Żid node ġdid fil-kju prijoritarju.
- L-uniku nodu li fadal se jkun l-għerq, u dan se jlesti l-kostruzzjoni tas-siġra.
Immaġina li għandna xi test li jikkonsisti biss f'karattri "a B Ċ D" и "u", u l-frekwenzi tal-okkorrenza tagħhom huma 15, 7, 6, 6, u 5, rispettivament. Hawn taħt hemm illustrazzjonijiet li jirriflettu l-passi tal-algoritmu.
Mogħdija mill-għerq għal kwalunkwe nodu tat-tarf se taħżen l-aħjar kodiċi tal-prefiss (magħruf ukoll bħala l-kodiċi Huffman) li jikkorrispondi għall-karattru assoċjat ma 'dak in-nodu tat-tarf.
Siġra Huffman
Hawn taħt għandek issib l-implimentazzjoni tal-algoritmu tal-kompressjoni Huffman f'C++ u 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);
}
}Nota: il-memorja użata mill-sekwenza tad-dħul hija 47 * 8 = 376 bit u l-sekwenza kodifikata hija biss 194 bit i.e. id-data hija kkompressata b'madwar 48%. Fil-programm C++ ta 'hawn fuq, nużaw il-klassi string biex naħżnu l-sekwenza kodifikata biex il-programm ikun jista' jinqara.
Minħabba li l-istrutturi effiċjenti tad-data tal-kju ta 'prijorità jeħtieġu għal kull inserzjoni O(log(N)) ħin, iżda fi siġra binarja kompluta bil N weraq preżenti 2N-1 nodi, u s-siġra Huffman hija siġra binarja kompluta, allura l-algoritmu jibda O(Nlog(N)) ħin, fejn N - Karattri.
Sorsi:
Sors: www.habr.com