ኮርሱ ከመጀመሩ በፊት የሌላ ጠቃሚ ቁሳቁስ ትርጉም ተዘጋጅቶልዎታል.
ሃፍማን ኮድ ማድረግ የፋይል መጭመቂያ መሰረታዊ ሀሳብን የሚያዘጋጅ የውሂብ መጭመቂያ ስልተ-ቀመር ነው። በዚህ ጽሑፍ ውስጥ ስለ ቋሚ እና ተለዋዋጭ ርዝመት ኢንኮዲንግ, ልዩ የሆኑ ዲኮዲድ ኮዶች, ቅድመ ቅጥያ ደንቦች እና የሃፍማን ዛፍን ስለመገንባት እንነጋገራለን.
እያንዳንዱ ቁምፊ እንደ 0's እና 1's ተከታታይነት እንደሚከማች እና 8 ቢት እንደሚወስድ እናውቃለን። ይህ ቋሚ ርዝመት ኢንኮዲንግ ይባላል ምክንያቱም እያንዳንዱ ቁምፊ ለማከማቸት ተመሳሳይ ቋሚ የቢት ቁጥሮች ይጠቀማል።
ጽሑፍ ተሰጥቶናል እንበል። ነጠላ ቁምፊን ለማከማቸት የሚያስፈልገውን የቦታ መጠን እንዴት መቀነስ እንችላለን?
ዋናው ሃሳብ ተለዋዋጭ ርዝመት ኢንኮዲንግ ነው. በጽሁፉ ውስጥ ያሉ አንዳንድ ቁምፊዎች ከሌሎቹ በበለጠ በብዛት መከሰታቸውን ልንጠቀምበት እንችላለን () ተመሳሳዩን የቁምፊዎች ቅደም ተከተል በጥቂት ቢት የሚወክል አልጎሪዝም ለማዘጋጀት። በተለዋዋጭ ርዝመት ኢንኮዲንግ ውስጥ፣ በአንድ ጽሑፍ ውስጥ ምን ያህል ጊዜ እንደሚታዩ ላይ በመመስረት፣ ቁምፊዎችን ተለዋዋጭ የቢት ብዛት እንመድባለን። ውሎ አድሮ፣ አንዳንድ ቁምፊዎች እስከ 1 ቢት ትንሽ ሊወስዱ ይችላሉ፣ ሌሎች ደግሞ 2 ቢት፣ 3 ወይም ከዚያ በላይ ሊወስዱ ይችላሉ። በተለዋዋጭ ርዝመት ኢንኮዲንግ ላይ ያለው ችግር የተከታታይ ዲኮድ መፍታት ብቻ ነው።
የቢትን ቅደም ተከተል በማወቅ፣ በማያሻማ ሁኔታ እንዴት ዲኮድ ያድርጉት?
መስመሩን አስቡበት "አባባድ". 8 ቁምፊዎች አሉት፣ እና ቋሚ ርዝመት ሲገለበጥ እሱን ለማስቀመጥ 64 ቢት ያስፈልገዋል። የምልክት ድግግሞሽ መሆኑን ልብ ይበሉ "a", "b", "c" и "መ" በቅደም ተከተል 4 ፣ 2 ፣ 1 ፣ 1 እኩል ነው። ለመገመት እንሞክር "አባባድ" ያንን እውነታ በመጠቀም ጥቂት ቢት "ለ" በተደጋጋሚ ይከሰታል "ለ"ና "ለ" በተደጋጋሚ ይከሰታል "ሐ" и "መ". በኮድ እንጀምር "ለ" አንድ ቢት ከ 0 ጋር እኩል ነው ፣ "ለ" ባለ ሁለት ቢት ኮድ 11 እንመድባለን እና ሶስት ቢት 100 እና 011 በመጠቀም ኢንኮድ እናደርጋለን "ሐ" и "መ".
በውጤቱም, እኛ እናገኛለን:
a
0
b
11
c
100
d
011
ስለዚህ መስመር "አባባድ" እንደ ኮድ እናስቀምጣለን 00110100011011 (0|0|11|0|100|011|0|11)ከላይ ያሉትን ኮዶች በመጠቀም. ይሁን እንጂ ዋናው ችግር ዲኮዲንግ ላይ ይሆናል. ሕብረቁምፊውን መፍታት ስንሞክር 00110100011011, በሚከተለው ሊወከል ስለሚችል አሻሚ ውጤት እናገኛለን.
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
...
እና የመሳሰሉት.
ይህንን አሻሚነት ለማስቀረት፣ የእኛ ኢንኮዲንግ እንደ ፅንሰ-ሀሳብን የሚያረካ መሆኑን ማረጋገጥ አለብን ቅድመ ቅጥያ ደንብ, ይህም በተራው ደግሞ ኮዶች ሊፈቱ የሚችሉት በአንድ ልዩ መንገድ ብቻ ነው. ቅድመ ቅጥያ ደንቡ ምንም ኮድ የሌላው ቅድመ ቅጥያ አለመሆኑን ያረጋግጣል። ኮድ ስንል፣ የተወሰነ ገጸ ባህሪን ለመወከል የሚያገለግሉትን ቢት ማለታችን ነው። ከላይ ባለው ምሳሌ 0 ቅድመ ቅጥያ ነው። 011ቅድመ ቅጥያ ደንቡን የሚጥስ። ስለዚህ፣ ኮዶቻችን የቅድመ-ቅጥያ ደንቡን ካሟሉ፣ ከዚያ በልዩ ሁኔታ ዲኮድ ማድረግ እንችላለን (እና በተቃራኒው)።
ከላይ ያለውን ምሳሌ እንድገመው። በዚህ ጊዜ ምልክቶችን እንመድባለን "a", "b", "c" и "መ" ቅድመ ቅጥያ ደንቡን የሚያረኩ ኮዶች።
a
0
b
10
c
110
d
111
በዚህ ኢንኮዲንግ፣ ሕብረቁምፊው። "አባባድ" እንደ ኢንኮድ ይደረጋል 00100100011010 (0|0|10|0|100|011|0|10). ግን 00100100011010 አስቀድመን በማያሻማ ሁኔታ ኮድ መፍታት እና ወደ መጀመሪያው ሕብረቁምፊችን መመለስ እንችላለን "አባባድ".
ሃፍማን ኮድ ማድረግ
አሁን ከተለዋዋጭ ርዝመት ኢንኮዲንግ እና ከቅድመ-ቅጥያ ህግ ጋር ተወያይተናል፣ እስቲ ስለ ሃፍማን ኢንኮዲንግ እንነጋገር።
ዘዴው በሁለትዮሽ ዛፎች መፈጠር ላይ የተመሰረተ ነው. በውስጡ, መስቀለኛ መንገድ የመጨረሻ ወይም ውስጣዊ ሊሆን ይችላል. መጀመሪያ ላይ ሁሉም አንጓዎች እንደ ቅጠሎች (ተርሚናሎች) ይቆጠራሉ, እሱም ምልክቱን እራሱ እና ክብደቱን (ይህም የድግግሞሽ ድግግሞሽ). ውስጣዊ አንጓዎች የቁምፊውን ክብደት ይይዛሉ እና ሁለት የዘር ኖዶችን ያመለክታሉ. በአጠቃላይ ስምምነት, ቢት «0» የግራውን ቅርንጫፍ መከተልን ይወክላል, እና «1» - በስተቀኝ በኩል. ሙሉ ዛፍ ውስጥ N ቅጠሎች እና N-1 የውስጥ አንጓዎች. የሃፍማን ዛፍ በሚገነቡበት ጊዜ ጥሩ የርዝመት ኮዶችን ለማግኘት ጥቅም ላይ ያልዋሉ ምልክቶችን መጣል ይመከራል።
የሃፍማን ዛፍ ለመገንባት ቅድሚያ ወረፋ እንጠቀማለን, አነስተኛ ድግግሞሽ ያለው መስቀለኛ መንገድ ከፍተኛ ቅድሚያ የሚሰጠው ይሆናል. የግንባታ ደረጃዎች ከዚህ በታች ተብራርተዋል.
- ለእያንዳንዱ ቁምፊ የቅጠል መስቀለኛ መንገድ ይፍጠሩ እና ወደ ቅድሚያ ወረፋ ያክሏቸው።
- በወረፋው ውስጥ ከአንድ በላይ ሉህ ሲኖር የሚከተሉትን ያድርጉ።
- ሁለቱን አንጓዎች በከፍተኛ ቅድሚያ (ዝቅተኛ ድግግሞሽ) ከወረፋው ላይ ያስወግዱ;
- አዲስ የውስጥ መስቀለኛ መንገድ ይፍጠሩ, እነዚህ ሁለት አንጓዎች ልጆች ይሆናሉ, እና የድግግሞሹ ድግግሞሽ ከእነዚህ ሁለት አንጓዎች ድግግሞሽ ድምር ጋር እኩል ይሆናል.
- ወደ ቅድሚያ ወረፋ አዲስ መስቀለኛ መንገድ ያክሉ።
- ብቸኛው የቀረው መስቀለኛ መንገድ ሥሩ ይሆናል, ይህ ደግሞ የዛፉን ግንባታ ያጠናቅቃል.
ቁምፊዎችን ብቻ የያዘ ጽሑፍ እንዳለን አስብ "ኤ ቢ ሲ ዲ" и "እና", እና የእነሱ ክስተት ድግግሞሾች 15, 7, 6, 6 እና 5 ናቸው. ከታች ያሉት የአልጎሪዝም ደረጃዎችን የሚያንፀባርቁ ምሳሌዎች ናቸው.
ከሥሩ ወደ ማንኛውም የፍጻሜ መስቀለኛ መንገድ የሚወስደው መንገድ ከዚያ የመጨረሻ መስቀለኛ መንገድ ጋር ከተገናኘው ቁምፊ ጋር የሚዛመደውን ምርጥ ቅድመ ቅጥያ ኮድ (እንዲሁም ሃፍማን ኮድ በመባልም ይታወቃል) ያከማቻል።
የሃፍማን ዛፍ
ከዚህ በታች የሃፍማን መጭመቂያ ስልተ ቀመር በC++ እና 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);
}
}ማስታወሻ: በግቤት ሕብረቁምፊው የሚጠቀመው ማህደረ ትውስታ 47 * 8 = 376 ቢት እና ኮድ የተደረገው ሕብረቁምፊ 194 ቢት ብቻ ነው ማለትም. መረጃው በ 48% ገደማ የታመቀ ነው. ከላይ ባለው የC++ ፕሮግራም ፕሮግራሙ ሊነበብ የሚችል ለማድረግ ኢንኮድ የተደረገውን ሕብረቁምፊ ለማስቀመጥ የstring ክፍልን እንጠቀማለን።
ምክንያቱም ቀልጣፋ የቅድሚያ ወረፋ ውሂብ መዋቅሮች በእያንዳንዱ ማስገባት ያስፈልጋቸዋል ኦ(ሎግ(N)) ጊዜ, ነገር ግን ጋር ሙሉ ሁለትዮሽ ዛፍ ውስጥ N ቅጠሎች ይገኛሉ 2N-1 አንጓዎች፣ እና የሃፍማን ዛፍ ሙሉ ሁለትዮሽ ዛፍ ነው፣ ከዚያ አልጎሪዝም ወደ ውስጥ ይገባል። ኦ(Nlog(N)) ጊዜ ፣ የት N - ገጸ-ባህሪያት.
ምንጮች:
ምንጭ: hab.com