Курс башталганга чейин Сиз үчүн дагы бир пайдалуу материалдын котормосун даярдады.
Хаффман коддоосу - бул файлдарды кысуунун негизги идеясын түзгөн маалыматтарды кысуу алгоритми. Бул макалада биз туруктуу жана өзгөрүлмө узундуктагы коддоо, уникалдуу чечмелөөчү коддор, префикс эрежелери жана Хаффман дарагын куруу жөнүндө сүйлөшөбүз.
Ар бир символ 0 жана 1 ырааттуулугу катары сакталып, 8 битти ээлей турганын билебиз. Бул белгиленген узундуктагы коддоо деп аталат, анткени ар бир символ сактоо үчүн бирдей сандагы биттерди колдонот.
Бизге текст берилди дейли. Бир символду сактоо үчүн талап кылынган мейкиндикти кантип азайта алабыз?
Негизги идея - өзгөрмө узундуктагы коддоо. Биз тексттеги кээ бир белгилердин башкаларга караганда көбүрөөк кездешүүсүн колдоно алабыз () символдордун бирдей ырааттуулугун азыраак бит менен чагылдыра турган алгоритмди иштеп чыгуу. Өзгөрмө узундуктагы коддоодо биз символдор берилген текстте канчалык көп кездешкенине жараша биттердин өзгөрүлмө санын дайындайбыз. Акыр-аягы, кээ бир символдор 1 биттен аз болушу мүмкүн, ал эми башкалары 2 бит, 3 же андан көп болушу мүмкүн. Өзгөрмө узундуктагы коддоо көйгөйү ырааттуулуктун кийинки декоддоосунда гана.
Кантип, биттердин ырааттуулугун билип, аны ачык чечмелей алат?
линиясын карап көрөлү "abacdab". Ал 8 белгиден турат жана белгиленген узундукту коддоодо аны сактоо үчүн 64 бит керек болот. белги жыштыгы экенин белгилей кетүү керек "а", "б", "в" и "D" тиешелүүлүгүнө жараша 4, 2, 1, 1ге барабар. Келгиле, элестеткенге аракет кылалы "abacdab" азыраак бит, фактыны колдонуп "to" караганда көп кездешет "Б"жана "Б" караганда көп кездешет "c" и "D". Келиңиз, коддоодон баштайлы "to" бир бит 0гө барабар, "Б" биз эки биттик кодду 11 дайындайбыз, ал эми үч бит 100 жана 011ди колдонуу менен биз коддойбуз "c" и "D".
Натыйжада, биз алабыз:
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, бул префикс эрежесин бузган. Демек, биздин коддор префикс эрежесин канааттандырса, анда биз уникалдуу түрдө чечмелей алабыз (жана тескерисинче).
Келгиле, жогорудагы мисалды кайра карап көрөлү. Бул жолу биз символдорду дайындайбыз "а", "б", "в" и "D" префикс эрежесин канааттандырган коддор.
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 ички түйүндөр. Хаффман дарагын курууда оптималдуу узундуктун коддорун алуу үчүн пайдаланылбаган символдордон баш тартуу сунушталат.
Биз Huffman дарагын куруу үчүн артыкчылыктуу кезекти колдонобуз, мында эң төмөнкү жыштыгы бар түйүнгө эң жогорку артыкчылык берилет. курулуш этаптары төмөндө сүрөттөлгөн:
- Ар бир белги үчүн жалбырак түйүнүн түзүп, аларды артыкчылыктуу кезекке кошуңуз.
- Кезекте бирден ашык барак бар болсо, төмөнкүнү аткарыңыз:
- Эң артыкчылыктуу (төмөн жыштык) эки түйүндү кезектен алып салуу;
- Жаңы ички түйүн түзүңүз, анда бул эки түйүн балдар болот жана пайда болуу жыштыгы бул эки түйүндүн жыштыктарынын суммасына барабар болот.
- Артыкчылыктуу кезекке жаңы түйүн кошуңуз.
- Жалгыз калган түйүн тамыр болот жана бул дарактын курулушун аяктайт.
Элестеткиле, бизде бир гана тамгалардан турган текст бар "а", "б", "в", "д" и "жана", жана алардын пайда болуу жыштыгы тиешелүүлүгүнө жараша 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++ программасында биз программаны окула турган кылуу үчүн коддолгон сапты сактоо үчүн string классын колдонобуз.
Анткени эффективдүү приоритеттүү кезектеги маалымат структуралары ар бир киргизүүнү талап кылат O(log(N)) убакыт, бирок толук бинардык дарак менен N жалбырактары бар 2N-1 түйүндөр, ал эми Хаффман дарагы толук экилик дарак болсо, анда алгоритм ишке кирет O(Nlog(N)) убакыт, кайда N - Каармандар.
булагы:
Source: www.habr.com