Kabla ya kuanza kwa kozi imekuandalia tafsiri ya nyenzo nyingine muhimu.
Usimbaji wa Huffman ni algorithm ya ukandamizaji wa data ambayo huunda wazo la msingi la compression ya faili. Katika makala haya, tutazungumza juu ya usimbaji wa urefu uliowekwa na unaobadilika, misimbo inayoweza kusimbua kipekee, sheria za kiambishi awali, na kujenga mti wa Huffman.
Tunajua kuwa kila herufi huhifadhiwa kama mfuatano wa 0 na 1 na huchukua biti 8. Hii inaitwa usimbaji wa urefu usiobadilika kwa sababu kila herufi hutumia nambari isiyobadilika sawa ya biti kuhifadhi.
Wacha tuseme tumepewa maandishi. Je, tunawezaje kupunguza kiasi cha nafasi inayohitajika kuhifadhi mhusika mmoja?
Wazo kuu ni usimbaji wa urefu tofauti. Tunaweza kutumia ukweli kwamba baadhi ya wahusika katika maandishi hutokea mara nyingi zaidi kuliko wengine () kuunda algoriti ambayo itawakilisha mlolongo sawa wa wahusika katika biti chache. Katika usimbaji wa urefu tofauti, tunawapa wahusika idadi tofauti ya bits, kulingana na mara ngapi zinaonekana katika maandishi fulani. Hatimaye, baadhi ya wahusika wanaweza kuchukua kidogo kama biti 1, wakati wengine wanaweza kuchukua biti 2, 3 au zaidi. Shida ya usimbaji wa urefu tofauti ni utatuzi unaofuata wa mlolongo.
Jinsi gani, kujua mlolongo wa bits, usimbue bila utata?
Fikiria mstari "babu". Ina herufi 8, na wakati wa kusimba urefu uliowekwa, itahitaji bits 64 ili kuihifadhi. Kumbuka kwamba mzunguko wa ishara "a", "b", "c" ΠΈ "D" sawa na 4, 2, 1, 1 mtawalia. Hebu jaribu kufikiria "babu" bits chache, kwa kutumia ukweli kwamba "kwa" hutokea mara nyingi zaidi kuliko "B"Na "B" hutokea mara nyingi zaidi kuliko "c" ΠΈ "D". Wacha tuanze kwa kuweka msimbo "kwa" na biti moja sawa na 0, "B" tutaweka msimbo wa biti-mbili 11, na kwa kutumia biti tatu 100 na 011 tutasimba "c" ΠΈ "D".
Kama matokeo, tutapata:
a
0
b
11
c
100
d
011
Hivyo mstari "babu" tutaandika kama 00110100011011 (0|0|11|0|100|011|0|11)kwa kutumia nambari zilizo hapo juu. Walakini, shida kuu itakuwa katika kusimbua. Tunapojaribu kusimbua kamba 00110100011011, tunapata matokeo ya utata, kwani inaweza kuwakilishwa kama:
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
...
nk
Ili kuepuka utata huu, ni lazima tuhakikishe kwamba usimbaji wetu unakidhi dhana kama vile kanuni ya kiambishi awali, ambayo ina maana kwamba misimbo inaweza tu kusimbua kwa njia moja ya kipekee. Kanuni ya kiambishi awali huhakikisha kwamba hakuna msimbo ni kiambishi awali cha mwingine. Kwa kificho, tunamaanisha biti zinazotumiwa kuwakilisha mhusika fulani. Katika mfano hapo juu 0 ni kiambishi awali 011, ambayo inakiuka kanuni ya kiambishi awali. Kwa hivyo, ikiwa misimbo yetu inakidhi kanuni ya kiambishi awali, basi tunaweza kusimbua kipekee (na kinyume chake).
Wacha tuangalie tena mfano hapo juu. Wakati huu tutagawa kwa alama "a", "b", "c" ΠΈ "D" misimbo inayokidhi kanuni ya kiambishi awali.
a
0
b
10
c
110
d
111
Kwa usimbaji huu, kamba "babu" itasimbwa kama 00100100011010 (0|0|10|0|100|011|0|10). Lakini 00100100011010 tayari tutaweza kusimbua bila utata na kurudi kwenye mfuatano wetu wa asili "babu".
Huffman coding
Sasa kwa kuwa tumeshughulikia usimbaji wa urefu tofauti na kanuni ya kiambishi awali, hebu tuzungumze kuhusu usimbaji wa Huffman.
Njia hiyo inategemea kuundwa kwa miti ya binary. Ndani yake, node inaweza kuwa ya mwisho au ya ndani. Hapo awali, nodi zote zinachukuliwa kuwa majani (vituo), ambavyo vinawakilisha ishara yenyewe na uzito wake (yaani, mzunguko wa tukio). Nodi za ndani zina uzito wa mhusika na hurejelea nodi mbili za uzao. Kwa makubaliano ya jumla, kidogo Β«0Β» inawakilisha kufuata tawi la kushoto, na Β«1Β» - upande wa kulia. kwenye mti mzima N majani na N-1 nodi za ndani. Inapendekezwa kuwa wakati wa kuunda mti wa Huffman, alama ambazo hazijatumiwa zitupwe ili kupata misimbo ya urefu bora.
Tutatumia foleni ya kipaumbele ili kujenga mti wa Huffman, ambapo nodi yenye mzunguko wa chini kabisa itapewa kipaumbele cha juu. Hatua za ujenzi zimeelezewa hapa chini:
- Unda nodi ya majani kwa kila herufi na uwaongeze kwenye foleni ya kipaumbele.
- Ingawa kuna zaidi ya laha moja kwenye foleni, fanya yafuatayo:
- Ondoa nodes mbili na kipaumbele cha juu (mzunguko wa chini kabisa) kutoka kwenye foleni;
- Unda nodi mpya ya ndani, ambapo nodi hizi mbili zitakuwa watoto, na mzunguko wa tukio utakuwa sawa na jumla ya masafa ya nodi hizi mbili.
- Ongeza nodi mpya kwenye foleni ya kipaumbele.
- Node iliyobaki pekee itakuwa mzizi, na hii itakamilisha ujenzi wa mti.
Fikiria kuwa tuna maandishi ambayo yana wahusika pekee "a", "b", "c", "d" ΠΈ "na", na masafa yao ya kutokea ni 15, 7, 6, 6, na 5, kwa mtiririko huo. Chini ni vielelezo vinavyoonyesha hatua za algorithm.
Njia kutoka kwa mzizi hadi nodi yoyote ya mwisho itahifadhi nambari mojawapo ya kiambishi awali (pia inajulikana kama nambari ya Huffman) inayolingana na herufi inayohusishwa na nodi hiyo ya mwisho.
Mti wa Huffman
Hapo chini utapata utekelezaji wa algorithm ya compression ya Huffman katika C++ na 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);
}
}Kumbuka: kumbukumbu inayotumiwa na kamba ya pembejeo ni 47 * 8 = bits 376 na kamba iliyosimbwa ni bits 194 tu i.e. data imebanwa na takriban 48%. Katika mpango wa C ++ hapo juu, tunatumia darasa la kamba kuhifadhi kamba iliyosimbwa ili kufanya programu isomeke.
Kwa sababu miundo ya data ya foleni ya kipaumbele inahitaji kila uwekaji O(logi(N)) wakati, lakini katika mti kamili wa binary na N majani yaliyopo 2N-1 nodi, na mti wa Huffman ni mti kamili wa binary, kisha algorithm inaingia O(Nlog(N)) wakati, wapi N - Wahusika.
Vyanzo:
Chanzo: mapenzi.com