Пеш аз оғози курс тарчумаи боз як материали муфидро барои шумо тайёр кард.
Рамзгузории Ҳуффман як алгоритми фишурдани маълумот аст, ки идеяи асосии фишурдани файлро таҳия мекунад. Дар ин мақола, мо дар бораи рамзгузории дарозии собит ва тағйирёбанда, рамзҳои беҳамто, қоидаҳои префикс ва сохтани дарахти Ҳуффман сӯҳбат хоҳем кард.
Мо медонем, ки ҳар як аломат ҳамчун пайдарпаии 0 ва 1 нигоҳ дошта мешавад ва 8 битро мегирад. Ин рамзгузории дарозии собит номида мешавад, зеро ҳар як аломат барои нигоҳдорӣ ҳамон як миқдори собит битҳоро истифода мебарад.
Фарз мекунем, ки ба мо матн дода шудааст. Чӣ тавр мо метавонем миқдори ҷойро барои нигоҳ доштани як аломат кам кунем?
Идеяи асосӣ рамзгузории дарозии тағирёбанда мебошад. Мо метавонем аз он истифода кунем, ки баъзе аломатҳо дар матн нисбат ба дигарон бештар меоянд () барои таҳияи алгоритме, ки ҳамон пайдарпаии аломатҳоро дар битҳои камтар ифода мекунад. Дар рамзгузории дарозии тағирёбанда, мо ба аломатҳо шумораи тағирёбандаи битҳоро вобаста ба он, ки онҳо дар матни додашуда чанд маротиба пайдо мешаванд, таъин мекунем. Дар ниҳоят, баъзе аломатҳо метавонанд то 1 бит гиранд, дар ҳоле ки дигарон метавонанд 2 бит, 3 ё бештар аз он гиранд. Мушкилот бо рамзгузории дарозии тағирёбанда танҳо рамзгузории минбаъдаи пайдарпай аст.
Чӣ тавр бо донистани пайдарпайии битҳо, онро ба таври равшан рамзкушоӣ кунед?
Хатро баррасӣ кунед "abacdab". Он дорои 8 аломат аст ва ҳангоми рамзгузории дарозии муқарраршуда барои нигоҳ доштани он 64 бит лозим аст. Дар хотир доред, ки басомади рамз "а", "б", "в" и "Д" мутаносибан ба 4, 2, 1, 1 баробар аст. Биёед кӯшиш кунем, ки тасаввур кунем "abacdab" бит камтар, бо истифода аз он, ки "ба" назар ба он бештар ба амал меояд "В"ва "В" назар ба он бештар ба амал меояд "в" и "Д". Биёед бо рамзгузорӣ оғоз кунем "ба" бо як бит баробар ба 0, "В" мо рамзи ду-битаи 11 таъин мекунем ва бо истифода аз се битҳои 100 ва 011 мо рамзгузорӣ мекунем "в" и "Д".
Дар натиҷа, мо ба даст меорем:
a
0
b
11
c
100
d
011
Пас, хати "abacdab" ҳамчун рамзгузорӣ мекунем 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
Бо ин рамзгузорӣ, сатр "abacdab" ҳамчун рамзгузорӣ карда мешавад 00100100011010 (0|0|10|0|100|011|0|10). Аммо 00100100011010 мо аллакай қодир хоҳем буд, ки ба таври равшан рамзкушоӣ кунем ва ба сатри аслии худ баргардем "abacdab".
Рамзгузории Ҳуффман
Акнун, ки мо бо рамзгузории дарозии тағирёбанда ва қоидаи префикс кор кардем, биёед дар бораи рамзгузории Ҳуффман сӯҳбат кунем.
Ин усул ба эҷоди дарахтони бинарӣ асос ёфтааст. Дар он гиреҳ метавонад ниҳоӣ ё дохилӣ бошад. Дар аввал, ҳама гиреҳҳо баргҳо (терминалҳо) ҳисобида мешаванд, ки худи рамз ва вазни онро (яъне басомади пайдоиш) ифода мекунанд. Гиреҳҳои дохилӣ вазни аломатро дар бар мегиранд ва ба ду гиреҳи насл ишора мекунанд. Бо созишномаи умумӣ, каме "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++ дар боло, мо синфи сатрро истифода мебарем, то сатри рамзшударо нигоҳ дорем, то барнома хонда шавад.
Зеро сохторҳои навбатии самараноки маълумот барои як воридкунӣ талаб мекунанд O(log(N)) вақт, балки дар як дарахти дуӣ пурра бо N баргҳо мавҷуданд 2N-1 гиреҳҳо ва дарахти Ҳуффман як дарахти мукаммали бинарӣ аст, пас алгоритм кор мекунад O(Nlog(N)) вақт, дар куҷо N - Ҳарфҳо.
Манбаъҳо:
Манбаъ: will.com