Курс басталғанға дейін Сізге басқа пайдалы материалдың аудармасын дайындады.
Хаффман кодтауы - файлдарды қысудың негізгі идеясын тұжырымдайтын деректерді қысу алгоритмі. Бұл мақалада біз тұрақты және айнымалы ұзындықты кодтау, бірегей декодталатын кодтар, префикс ережелері және Хаффман ағашын құру туралы айтатын боламыз.
Біз әрбір таңба 0 және 1 тізбегі ретінде сақталатынын және 8 бит алатынын білеміз. Бұл бекітілген ұзындықты кодтау деп аталады, себебі әрбір таңба сақтау үшін биттердің бірдей тіркелген санын пайдаланады.
Бізге мәтін берілді делік. Бір таңбаны сақтау үшін қажет орын көлемін қалай азайтуға болады?
Негізгі идея - айнымалы ұзындықты кодтау. Мәтіндегі кейбір кейіпкерлердің басқаларға қарағанда жиі кездесетінін пайдалана аламыз () таңбалардың бірдей тізбегін азырақ битпен көрсететін алгоритмді әзірлеу. Айнымалы ұзындықты кодтауда таңбаларға берілген мәтінде қаншалықты жиі кездесетініне байланысты биттердің айнымалы санын тағайындаймыз. Сайып келгенде, кейбір таңбалар 1 биттен аз болуы мүмкін, ал басқалары 2 бит, 3 немесе одан да көп болуы мүмкін. Айнымалы ұзындықты кодтауға қатысты мәселе тек дәйектілікті кейінгі декодтау болып табылады.
Биттер тізбегін біле отырып, оны бір мәнді түрде қалай декодтау керек?
Сызықты қарастырыңыз «абакдаб». Оның 8 таңбасы бар және бекітілген ұзындықты кодтау кезінде оны сақтау үшін 64 бит қажет болады. Таңба жиілігін ескеріңіз «а», «б», «в» и «D» сәйкесінше 4, 2, 1, 1-ге тең. Елестетуге тырысайық «абакдаб» бұл фактіні пайдалана отырып, аз бит «дейін» қарағанда жиі кездеседі «В»мен «В» қарағанда жиі кездеседі «в» и «D». Кодтаудан бастайық «дейін» бір бит 0-ге тең, «В» біз екі разрядты кодты 11 тағайындаймыз және үш бит 100 және 011 көмегімен кодтаймыз «в» и «D».
Нәтижесінде біз аламыз:
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, бұл префикс ережесін бұзады. Сонымен, егер біздің кодтарымыз префикс ережесін қанағаттандырса, онда біз бірегей түрде декодтауға болады (және керісінше).
Жоғарыдағы мысалды қайталап көрейік. Бұл жолы біз белгілерді тағайындаймыз «а», «б», «в» и «D» префикс ережесін қанағаттандыратын кодтар.
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 тілдерінде Huffman қысу алгоритмінің орындалуын таба аласыз:
#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(лог(N)) уақыт, бірақ толық екілік ағашта N жапырақтары бар 2N-1 түйіндер, ал Хаффман ағашы толық екілік ағаш болып табылады, содан кейін алгоритм іске қосылады O(Nlog(N)) уақыт, қайда N - Кейіпкерлер.
Көздер:
Ақпарат көзі: www.habr.com