Áður en námskeiðið hefst útbjó fyrir þig þýðingu á öðru gagnlegu efni.
Huffman erfðaskrá er gagnaþjöppunaralgrím sem mótar grunnhugmyndina um þjöppun skráa. Í þessari grein munum við tala um kóðun með föstri og breytilegri lengd, einstaklega afkóðunanlega kóða, forskeytireglur og að byggja Huffman tré.
Við vitum að hver stafur er geymdur sem röð af 0 og 1 og tekur 8 bita. Þetta er kallað kóðun með fastri lengd vegna þess að hver stafur notar sama fasta fjölda bita til að geyma.
Segjum að okkur sé gefinn texti. Hvernig getum við minnkað plássið sem þarf til að geyma einn staf?
Meginhugmyndin er kóðun með breytilegri lengd. Við getum notað þá staðreynd að sumir stafir í textanum koma oftar fyrir en aðrir () til að þróa reiknirit sem mun tákna sömu röð stafa í færri bitum. Í kóðun með breytilegri lengd úthlutum við stöfum breytilegum fjölda bita, eftir því hversu oft þeir birtast í tilteknum texta. Að lokum geta sumar persónur tekið allt að 1 bita á meðan aðrir geta tekið 2 bita, 3 eða meira. Vandamálið við kóðun með breytilegri lengd er aðeins síðari afkóðun röðarinnar.
Hvernig, með því að þekkja röð bita, afkóða hana ótvírætt?
Hugleiddu línuna "abacdab". Það hefur 8 stafi og þegar þú kóðar fasta lengd þarf það 64 bita til að geyma það. Athugaðu að táknið tíðni "a", "b", "c" и "D" jafngildir 4, 2, 1, 1 í sömu röð. Við skulum reyna að ímynda okkur "abacdab" færri bita, með því að nota þá staðreynd „til“ kemur oftar fyrir en "B"Og "B" kemur oftar fyrir en "c" и "D". Byrjum á að kóða „til“ með einum bita jafn 0, "B" við munum úthluta tveggja bita kóða 11 og með því að nota þrjá bita 100 og 011 munum við umrita "c" и "D".
Fyrir vikið munum við fá:
a
0
b
11
c
100
d
011
Svo línan "abacdab" við munum umrita sem 00110100011011 (0|0|11|0|100|011|0|11)með því að nota kóðana hér að ofan. Hins vegar verður aðal vandamálið í umskráningu. Þegar við reynum að afkóða strenginn 00110100011011, munum við fá óljósa niðurstöðu, þar sem hægt er að tákna hana sem:
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
...
o.fl.
Til að forðast þessa tvíræðni verðum við að tryggja að kóðun okkar uppfylli hugtak eins og forskeyti regla, sem aftur gefur til kynna að aðeins er hægt að afkóða kóðana á einn einstakan hátt. Forskeytsreglan tryggir að enginn kóði sé forskeyti annars. Með kóða er átt við bitana sem notaðir eru til að tákna tiltekinn staf. Í dæminu hér að ofan 0 er forskeyti 011, sem brýtur í bága við forskeytiregluna. Svo ef kóðarnir okkar uppfylla forskeytiregluna, þá getum við afkóða á einstakan hátt (og öfugt).
Við skulum endurskoða dæmið hér að ofan. Að þessu sinni munum við úthluta fyrir tákn "a", "b", "c" и "D" kóðar sem uppfylla forskeytiregluna.
a
0
b
10
c
110
d
111
Með þessari kóðun, strengurinn "abacdab" verður kóðað sem 00100100011010 (0|0|10|0|100|011|0|10). En 00100100011010 við munum nú þegar geta afkóðað ótvírætt og farið aftur í upprunalega strenginn okkar "abacdab".
Huffman kóða
Nú þegar við höfum fjallað um kóðun með breytilegri lengd og forskeytsregluna, skulum við tala um Huffman kóðun.
Aðferðin byggir á því að búa til tvöfalda tré. Í því getur hnúturinn verið annað hvort endanlegur eða innri. Upphaflega eru allir hnútar taldir laufblöð (skautanna), sem tákna táknið sjálft og þyngd þess (þ.e. tíðni þess sem gerist). Innri hnútar innihalda þyngd stafsins og vísa til tveggja afkomandi hnúta. Með almennu samkomulagi, bit «0» táknar eftir vinstri grein, og «1» - á hægri hönd. í fullu tré N lauf og N-1 innri hnúta. Mælt er með því að þegar Huffman tré er smíðað sé ónotuðum táknum fargað til að fá hámarkslengdarkóða.
Við munum nota forgangsröð til að byggja upp Huffman tré, þar sem hnúturinn með lægstu tíðnina fær hæsta forgang. Byggingarskrefunum er lýst hér að neðan:
- Búðu til laufhnút fyrir hvern staf og bættu þeim við forgangsröðina.
- Á meðan það eru fleiri en eitt blað í biðröðinni skaltu gera eftirfarandi:
- Fjarlægðu tvo hnúta með hæsta forgang (lægstu tíðni) úr biðröðinni;
- Búðu til nýjan innri hnút, þar sem þessir tveir hnútar verða börn, og tíðni tilvika verður jöfn summan af tíðnum þessara tveggja hnúta.
- Bættu nýjum hnút við forgangsröðina.
- Eini hnúturinn sem eftir verður verður rótin og þetta mun ljúka byggingu trésins.
Ímyndaðu þér að við höfum einhvern texta sem samanstendur aðeins af stöfum "a B C D" и "og", og tíðni þeirra er 15, 7, 6, 6 og 5, í sömu röð. Hér að neðan eru myndir sem endurspegla skref reikniritsins.
Slóð frá rótinni að hvaða endahnút sem er mun geyma ákjósanlegasta forskeytakóðann (einnig þekktur sem Huffman kóðann) sem samsvarar stafnum sem tengist þeim endahnút.
Huffman tré
Hér að neðan finnur þú útfærslu Huffman þjöppunaralgrímsins í C++ og 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);
}
}Ath: minnið sem inntaksstrengurinn notar er 47 * 8 = 376 bitar og kóðaði strengurinn er aðeins 194 bitar þ.e. gögnum er þjappað um 48%. Í C++ forritinu hér að ofan notum við strengjaflokkinn til að geyma kóðaða strenginn til að gera forritið læsilegt.
Vegna þess að skilvirkt forgangsröð gagnaskipulag krefst hverrar innsetningar O(log(N)) tíma, en í algjöru tvíundartré með N blöð til staðar 2N-1 hnúta og Huffman tréð er algjört tvíundartré, þá keyrir reikniritið inn O(Nlog(N)) tíma, hvar N - Persónur.
Heimildir:
Heimild: www.habr.com