Prieš kurso pradžią paruošė jums kitos naudingos medžiagos vertimą.
Huffman kodavimas yra duomenų glaudinimo algoritmas, suformuluojantis pagrindinę failų glaudinimo idėją. Šiame straipsnyje kalbėsime apie fiksuoto ir kintamo ilgio kodavimą, unikaliai dekoduojamus kodus, priešdėlių taisykles ir Huffmano medžio kūrimą.
Žinome, kad kiekvienas simbolis išsaugomas kaip 0 ir 1 seka ir užima 8 bitus. Tai vadinama fiksuoto ilgio kodavimu, nes kiekvienas simbolis naudoja tą patį fiksuotą bitų skaičių saugojimui.
Tarkime, kad turime tekstą. Kaip galime sumažinti vietos, reikalingos vienam simboliui saugoti?
Pagrindinė idėja yra kintamo ilgio kodavimas. Galime pasinaudoti tuo, kad kai kurie simboliai tekste pasitaiko dažniau nei kiti (), kad sukurtumėte algoritmą, kuris pavaizduotų tą pačią simbolių seką mažiau bitų. Kintamo ilgio koduotėje mes priskiriame simboliams kintamą bitų skaičių, priklausomai nuo to, kaip dažnai jie rodomi tam tikrame tekste. Galiausiai kai kurie simboliai gali užtrukti tik 1 bitą, o kiti gali užtrukti 2 bitus, 3 ar daugiau. Kintamo ilgio kodavimo problema yra tik vėlesnis sekos dekodavimas.
Kaip, žinant bitų seką, vienareikšmiškai iššifruoti?
Apsvarstykite liniją "abacdab". Jis turi 8 simbolius, o koduojant fiksuotą ilgį, jam išsaugoti reikės 64 bitų. Atkreipkite dėmesį, kad simbolio dažnis "a", "b", "c" и "D" lygus atitinkamai 4, 2, 1, 1. Pabandykime įsivaizduoti "abacdab" mažiau bitų, pasinaudojant tuo „iki“ pasitaiko dažniau nei "B"Ir "B" pasitaiko dažniau nei "c" и "D". Pradėkime nuo kodavimo „iki“ su vienu bitu lygiu 0, "B" priskirsime dviejų bitų kodą 11, o naudodami tris bitus 100 ir 011 užkoduosime "c" и "D".
Dėl to gausime:
a
0
b
11
c
100
d
011
Taigi linija "abacdab" užkoduosime kaip 00110100011011 (0|0|11|0|100|011|0|11)naudojant aukščiau nurodytus kodus. Tačiau pagrindinė problema bus dekoduojant. Kai bandome iššifruoti eilutę 00110100011011, gauname dviprasmišką rezultatą, nes jį galima pavaizduoti taip:
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
...
ir tt
Norėdami išvengti šios dviprasmybės, turime užtikrinti, kad mūsų kodavimas atitiktų tokią sąvoką kaip priešdėlio taisyklė, o tai savo ruožtu reiškia, kad kodus galima iššifruoti tik vienu unikaliu būdu. Priešdėlio taisyklė užtikrina, kad joks kodas nebūtų kito priešdėlis. Kodu reiškia bitus, naudojamus tam tikram simboliui pavaizduoti. Aukščiau pateiktame pavyzdyje 0 yra priešdėlis 011, kuris pažeidžia priešdėlio taisyklę. Taigi, jei mūsų kodai atitinka priešdėlio taisyklę, galime vienareikšmiškai iššifruoti (ir atvirkščiai).
Peržiūrėkime aukščiau pateiktą pavyzdį. Šį kartą skirsime simboliams "a", "b", "c" и "D" kodai, atitinkantys priešdėlio taisyklę.
a
0
b
10
c
110
d
111
Naudojant šį kodavimą, eilutė "abacdab" bus užkoduotas kaip 00100100011010 (0|0|10|0|100|011|0|10). Tačiau 00100100011010 jau galėsime vienareikšmiškai iššifruoti ir grįžti prie savo pradinės eilutės "abacdab".
Huffmano kodavimas
Dabar, kai išnagrinėjome kintamo ilgio kodavimą ir priešdėlio taisyklę, pakalbėkime apie Huffmano kodavimą.
Metodas pagrįstas dvejetainių medžių kūrimu. Jame mazgas gali būti galutinis arba vidinis. Iš pradžių visi mazgai laikomi lapais (gnybtais), kurie atspindi patį simbolį ir jo svorį (ty atsiradimo dažnį). Vidiniuose mazguose yra simbolio svoris ir jie nurodo du palikuonius mazgus. Bendru susitarimu, bit «0» reiškia po kairiosios šakos ir «1» - dešinėje. pilname medyje N lapai ir N-1 vidiniai mazgai. Kuriant Huffmano medį rekomenduojama atsisakyti nepanaudotų simbolių, kad būtų gauti optimalūs ilgio kodai.
Mes naudosime prioritetinę eilę, kad sukurtume Huffmano medį, kur mažiausią dažnį turinčiam mazgui bus suteiktas didžiausias prioritetas. Statybos etapai aprašyti žemiau:
- Kiekvienam simboliui sukurkite lapo mazgą ir pridėkite juos prie prioritetinės eilės.
- Kol eilėje yra daugiau nei vienas lapas, atlikite šiuos veiksmus:
- Pašalinkite iš eilės du didžiausio prioriteto (mažiausio dažnio) mazgus;
- Sukurkite naują vidinį mazgą, kuriame šie du mazgai bus vaikai, o atsiradimo dažnis bus lygus šių dviejų mazgų dažnių sumai.
- Pridėkite naują mazgą prie prioritetinės eilės.
- Vienintelis likęs mazgas bus šaknis, ir tai užbaigs medžio statybą.
Įsivaizduokite, kad turime tekstą, kurį sudaro tik simboliai "a", "b", "c", "d" и "ir", o jų atsiradimo dažniai yra atitinkamai 15, 7, 6, 6 ir 5. Žemiau pateikiamos iliustracijos, atspindinčios algoritmo veiksmus.
Kelias nuo šaknies iki bet kurio galinio mazgo išsaugos optimalų priešdėlio kodą (taip pat žinomą kaip Huffmano kodas), atitinkantį simbolį, susietą su tuo galutiniu mazgu.
Huffmano medis
Žemiau rasite Huffman glaudinimo algoritmo įgyvendinimą C++ ir 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);
}
}Pastaba: įvesties eilutės naudojama atmintis yra 47 * 8 = 376 bitai, o užkoduota eilutė yra tik 194 bitai, t.y. duomenys suglaudinami apie 48 proc. Aukščiau pateiktoje C++ programoje naudojame eilučių klasę, kad išsaugotume užkoduotą eilutę, kad programa būtų skaitoma.
Kadangi efektyvios prioritetinės eilės duomenų struktūros reikalauja vieno įterpimo O(log(N)) laiko, bet pilname dvejetainiame medyje su N esami lapai 2N-1 mazgų, o Huffmano medis yra pilnas dvejetainis medis, tada paleidžiamas algoritmas O(Nlog(N)) laikas, kur N - Personažai.
Šaltiniai:
Šaltinis: www.habr.com