قبل از شروع دوره ترجمه ای از مطالب مفید دیگری را برای شما آماده کرده است.
کدگذاری هافمن یک الگوریتم فشرده سازی داده است که ایده اولیه فشرده سازی فایل را فرموله می کند. در این مقاله در مورد رمزگذاری با طول ثابت و متغیر، کدهای قابل رمزگشایی منحصر به فرد، قوانین پیشوند و ساخت درخت هافمن صحبت خواهیم کرد.
می دانیم که هر کاراکتر به صورت دنباله ای از 0 و 1 ذخیره می شود و 8 بیت را اشغال می کند. این رمزگذاری با طول ثابت نامیده می شود زیرا هر کاراکتر از همان تعداد ثابت بیت برای ذخیره استفاده می کند.
فرض کنید به ما متن داده شده است. چگونه می توانیم فضای مورد نیاز برای ذخیره یک کاراکتر را کاهش دهیم؟
ایده اصلی رمزگذاری طول متغیر است. ما می توانیم از این واقعیت استفاده کنیم که برخی از کاراکترها در متن بیشتر از بقیه وجود دارند () برای ایجاد الگوریتمی که همان دنباله کاراکترها را در بیت های کمتری نشان دهد. در رمزگذاری طول متغیر، بسته به تعداد دفعات ظاهر شدن آنها در یک متن، تعداد بیت متغیری به کاراکترها اختصاص می دهیم. در نهایت، برخی از کاراکترها ممکن است کمتر از 1 بیت طول بکشد، در حالی که برخی دیگر ممکن است 2 بیت، 3 یا بیشتر. مشکل رمزگذاری طول متغیر فقط رمزگشایی بعدی دنباله است.
چگونه با دانستن دنباله بیت ها، آن را بدون ابهام رمزگشایی می کنیم؟
خط را در نظر بگیرید "اباداب". دارای 8 کاراکتر است و هنگام رمزگذاری یک طول ثابت، برای ذخیره آن به 64 بیت نیاز دارد. توجه داشته باشید که فرکانس نماد "الف"، "ب"، "ج" и "د" به ترتیب برابر با 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
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 برای ذخیره رشته کدگذاری شده استفاده می کنیم تا برنامه قابل خواندن باشد.
زیرا ساختارهای داده صف اولویت کارآمد به هر درج نیاز دارند O(log(N)) زمان، اما در یک درخت باینری کامل با N برگ های حاضر 2N-1 گره ها، و درخت هافمن یک درخت باینری کامل است، سپس الگوریتم اجرا می شود O(Nlog(N)) زمان، کجا N - شخصیت ها.
منابع:
منبع: www.habr.com