Roimh thús an chúrsa Tá aistriúchán ar ábhar úsáideach eile ullmhaithe againn duit.
Is algartam comhbhrú sonraí é códú Huffman a fhoirmíonn an smaoineamh bunúsach maidir le comhbhrú comhaid. San Airteagal seo beimid ag caint faoi ionchódú fad seasta agus athraitheach, cóid uath-díchódaithe, rialacha réimír, agus tógáil crann Huffman.
Tá a fhios againn go ndéantar gach carachtar a stóráil mar sheicheamh 0s agus 1s agus go bhfuil 8 ngiotán ann. Tugtar ionchódú fad seasta air seo toisc go n-úsáideann gach carachtar an líon seasta céanna giotán stórála.
Ligean le rá go bhfuil an téacs a thugtar. Conas is féidir linn an méid spáis a theastaíonn chun carachtar amháin a stóráil a laghdú?
Is é an bunsmaoineamh ná ionchódú faid athraitheach. Is féidir linn úsáid a bhaint as go bhfeictear carachtair áirithe i dtéacs níos minice ná a chéile () algartam a fhorbairt a léireoidh an t-ord céanna carachtair i níos lú giotán. In ionchódú faid athraitheach, sannaimid líon athraitheach giotán do charachtair ag brath ar mhinicíocht a dtarlaíonn siad i dtéacs ar leith. I ndeireadh na dála, ní fhéadfaidh roinnt carachtair ach 1 ghiotán a thógáil, agus féadfaidh carachtair eile 2 ghiotán, 3 nó níos mó a thógáil. Is í an fhadhb le hionchódú faid athraitheach ach díchódú na seicheamh ina dhiaidh sin.
Conas, agus seicheamh giotán ar eolas agat, an féidir leat é a dhíchódú gan athbhrí?
Smaoinigh ar an líne "aabacdab". Tá 8 gcarachtar aige, agus le hionchódú fad seasta beidh 64 giotán ag teastáil chun é a stóráil. Tabhair faoi deara go bhfuil an minicíocht siombail "a", "b", "c" и "D" cothrom le 4, 2, 1, 1 faoi seach. Déanaimis iarracht a shamhlú "aabacdab" i níos lú giotán, ag baint leasa as an bhfíric go "chun" tharlaíonn níos minice ná "B"Agus "B" tharlaíonn níos minice ná "c" и "D". Tosóimid trí chódú "chun" ag baint úsáide as giotán amháin comhionann le 0, "B" sannfaimid cód dhá ghiotán do 11, agus ag baint úsáide as trí ghiotán 100 agus 011 déanfaimid ionchódú "c" и "D".
Mar thoradh air sin, gheobhaidh muid:
a
0
b
11
c
100
d
011
Dá bhrí sin an líne "aabacdab" déanfaimid cód mar 00110100011011 (0|0|11|0|100|011|0|11)ag baint úsáide as na cóid atá curtha ar fáil thuas. Mar sin féin, beidh an fhadhb is mó i díchódaithe. Nuair a dhéanaimid iarracht an teaghrán a dhíchódú 00110100011011, gheobhaidh muid toradh débhríoch, mar is féidir é a léiriú mar:
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
...
etc
Chun an débhríocht seo a sheachaint, ní mór dúinn a chinntiú go sásaíonn ár n-ionchódú coincheap mar riail réimír, rud a thugann le tuiscint gur féidir na cóid a dhíchódú ar bhealach uathúil amháin. Cinntíonn riail na réimíre nach réimír cód ar bith eile. Ciallaíonn cód na giotáin a úsáidtear chun carachtar ar leith a léiriú. Sa sampla thuas 0 is réimír 011, a sháraíonn riail an réimír. Mar sin, má shásaíonn ár gcóid riail an réimír, is féidir linn a dhíchódú gan athbhrí (agus a mhalairt).
Déanaimis athchuairt ar an sampla thuas. An uair seo déanfaimid siombailí a shannadh "a", "b", "c" и "D" cóid a shásaíonn riail na réimíre.
a
0
b
10
c
110
d
111
Ag baint úsáide as an ionchódú seo, an teaghrán "aabacdab" beidh ionchódaithe mar 00100100011010 (0|0|10|0|100|011|0|10). Ach an 00100100011010 is féidir linn anois díchódú gan athbhrí agus filleadh ar ár mbunteaghrán "aabacdab".
Huffman códaithe
Anois go dtuigimid ionchódú faid athraitheach agus riail na réimíre, déanaimis labhairt faoi ionchódú Huffman.
Tá an modh bunaithe ar chrainn dhénártha a chruthú. Sa sé, is féidir le nód a bheith críochnaitheach nó inmheánach. Ar dtús, meastar go bhfuil duilleoga (foircinn) ag gach nóid, rud a léiríonn an tsiombail féin agus a meáchan (is é sin, minicíocht an tharla). Cuimsíonn na nóid inmheánacha meáchan an charachtair agus tagraíonn siad do dhá nód comharba. Trí chomhaontú ginearálta, giotán «0» ionann ag leanúint na brainse clé, agus «1» - ar dheis. I gcrann iomlán N duilleoga agus N-1 nóid inmheánacha. Agus crann Huffman á thógáil, moltar go gcaithfí siombailí nach bhfuil in úsáid chun cóid an fhad is fearr a fháil.
Bainfimid úsáid as scuaine tosaíochta chun crann Huffman a thógáil, áit a dtabharfar an tosaíocht is airde don nód leis an minicíocht is ísle. Déantar cur síos ar na céimeanna tógála thíos:
- Cruthaigh nód duille do gach siombail agus cuir leis an scuaine tosaíochta iad.
- Cé go bhfuil níos mó ná leathán amháin sa scuaine, déan na rudaí seo a leanas:
- Bain an dá nód tosaíochta is airde (minicíocht is ísle) as an scuaine;
- Cruthaigh nód inmheánach nua, áit a mbeidh an dá nód seo mar chomharbaí, agus beidh an minicíocht tarlaithe comhionann le suim minicíochtaí an dá nód seo.
- Cuir nód nua leis an scuaine tosaíochta.
- Is é an t-aon nód atá fágtha ná an nód fréimhe, agus críochnóidh sé seo tógáil an chrainn.
Samhlóimis go bhfuil téacs éigin againn nach bhfuil ann ach carachtair "a B C D" и "agus", agus is iad a minicíochtaí tarlaithe ná 15, 7, 6, 6 agus 5, faoi seach. Anseo thíos tá léaráidí a léiríonn céimeanna an algartam.
Stórálfaidh an cosán ón bhfréamh go dtí aon nód duille an cód réimír optamach (ar a dtugtar cód Huffman freisin) a fhreagraíonn don charachtar a bhaineann leis an nód duille sin.
Crann Huffman
Anseo thíos gheobhaidh tú cur i bhfeidhm an algartam comhbhrú Huffman i C ++ agus 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);
}
}Tabhair faoi deara: is í an chuimhne a úsáideann an teaghrán ionchuir ná 47 * 8 = 376 giotán agus ní thógann an teaghrán ionchódaithe ach 194 giotán i.e. tá sonraí comhbhrúite thart ar 48%. Sa chlár C++ thuas, táimid ag baint úsáide as an rang teaghrán chun teaghrán ionchódaithe a stóráil chun an clár a dhéanamh inléite.
Toisc go n-éilíonn struchtúir sonraí scuaine tosaíochta éifeachtúla in aghaidh an chur isteach O(log(N)) am, agus i gcrann dénártha iomlán le N duilleoga i láthair 2N-1 nóid, agus is crann dénártha iomlán é an crann Huffman, ansin oibríonn an algartam i O(Nlog(N)) am, cá N - Carachtair.
Foinsí:
Foinse: will.com