Sebelum memulai kursus disiapkan untuk Anda terjemahan dari materi bermanfaat lainnya.
Pengkodean Huffman adalah algoritma kompresi data yang merumuskan ide dasar kompresi file. Pada artikel ini, kita akan berbicara tentang pengkodean panjang tetap dan variabel, kode yang dapat didekodekan secara unik, aturan awalan, dan membangun pohon Huffman.
Kita tahu bahwa setiap karakter disimpan sebagai urutan 0 dan 1 dan membutuhkan 8 bit. Ini disebut pengkodean panjang tetap karena setiap karakter menggunakan jumlah bit tetap yang sama untuk disimpan.
Katakanlah kita diberi teks. Bagaimana kita bisa mengurangi jumlah ruang yang dibutuhkan untuk menyimpan satu karakter?
Ide utamanya adalah pengkodean panjang variabel. Kita dapat menggunakan fakta bahwa beberapa karakter dalam teks muncul lebih sering daripada yang lain () untuk mengembangkan algoritme yang akan mewakili urutan karakter yang sama dalam bit yang lebih sedikit. Dalam pengkodean panjang variabel, kami menetapkan karakter sejumlah bit, tergantung pada seberapa sering mereka muncul dalam teks tertentu. Pada akhirnya, beberapa karakter mungkin hanya membutuhkan 1 bit, sementara yang lain mungkin membutuhkan 2 bit, 3 atau lebih. Masalah dengan pengkodean panjang variabel hanya decoding berikutnya dari urutan.
Bagaimana, mengetahui urutan bit, mendekodekannya dengan jelas?
Pertimbangkan garisnya "abacdab". Ini memiliki 8 karakter, dan saat menyandikan panjang tetap, diperlukan 64 bit untuk menyimpannya. Perhatikan bahwa simbol frekuensi "a", "b", "c" ΠΈ "D" masing-masing sama dengan 4, 2, 1, 1. Coba kita bayangkan "abacdab" bit lebih sedikit, menggunakan fakta bahwa "untuk" lebih sering terjadi daripada "B"Dan "B" lebih sering terjadi daripada "c" ΠΈ "D". Mari kita mulai dengan pengkodean "untuk" dengan satu bit sama dengan 0, "B" kami akan menetapkan kode dua bit 11, dan menggunakan tiga bit 100 dan 011 kami akan menyandikan "c" ΠΈ "D".
Hasilnya, kita akan mendapatkan:
a
0
b
11
c
100
d
011
Jadi garis "abacdab" kami akan mengkodekan sebagai 00110100011011 (0|0|11|0|100|011|0|11)menggunakan kode-kode di atas. Namun, masalah utamanya adalah decoding. Saat kami mencoba memecahkan kode string 00110100011011, kami mendapatkan hasil yang ambigu, karena dapat direpresentasikan sebagai:
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
...
dan lain-lain
Untuk menghindari ambiguitas ini, kita harus memastikan bahwa penyandian kita memenuhi konsep seperti aturan awalan, yang pada gilirannya menyiratkan bahwa kode hanya dapat didekodekan dengan satu cara unik. Aturan awalan memastikan bahwa tidak ada kode yang merupakan awalan dari yang lain. Yang kami maksud dengan kode adalah bit yang digunakan untuk mewakili karakter tertentu. Pada contoh di atas 0 adalah awalan 011, yang melanggar aturan awalan. Jadi, jika kode kita memenuhi aturan awalan, maka kita dapat mendekode secara unik (dan sebaliknya).
Mari kita lihat kembali contoh di atas. Kali ini kami akan menetapkan untuk simbol "a", "b", "c" ΠΈ "D" kode yang memenuhi aturan awalan.
a
0
b
10
c
110
d
111
Dengan pengkodean ini, string "abacdab" akan dikodekan sebagai 00100100011010 (0|0|10|0|100|011|0|10). Tapi 00100100011010 kita sudah dapat mendekode dengan jelas dan kembali ke string asli kita "abacdab".
Pengkodean Huffman
Sekarang kita telah berurusan dengan pengkodean panjang variabel dan aturan awalan, mari kita bicara tentang pengkodean Huffman.
Metode ini didasarkan pada pembuatan pohon biner. Di dalamnya, node bisa final atau internal. Awalnya, semua node dianggap sebagai daun (terminal), yang mewakili simbol itu sendiri dan bobotnya (yaitu frekuensi kejadian). Node internal berisi bobot karakter dan mengacu pada dua node keturunan. Dengan kesepakatan umum, sedikit Β«0Β» mewakili mengikuti cabang kiri, dan Β«1Β» - di kanan. di pohon penuh N daun dan N-1 node internal. Direkomendasikan bahwa ketika membuat pohon Huffman, simbol-simbol yang tidak terpakai dibuang untuk mendapatkan kode panjang yang optimal.
Kita akan menggunakan antrian prioritas untuk membangun pohon Huffman, dimana node dengan frekuensi terendah akan diberikan prioritas tertinggi. Langkah-langkah konstruksi dijelaskan di bawah ini:
- Buat simpul daun untuk setiap karakter dan tambahkan ke antrean prioritas.
- Meskipun terdapat lebih dari satu lembar dalam antrean, lakukan hal berikut:
- Hapus dua node dengan prioritas tertinggi (frekuensi terendah) dari antrian;
- Buat simpul internal baru, di mana kedua simpul ini akan menjadi anak-anak, dan frekuensi kemunculannya akan sama dengan jumlah frekuensi kedua simpul ini.
- Tambahkan node baru ke antrian prioritas.
- Simpul yang tersisa hanya akan menjadi akar, dan ini akan menyelesaikan pembangunan pohon.
Bayangkan kita memiliki beberapa teks yang hanya terdiri dari karakter "a", "b", "c", "d" ΠΈ "dan", dan frekuensi kemunculannya masing-masing adalah 15, 7, 6, 6, dan 5. Di bawah ini adalah ilustrasi yang mencerminkan langkah-langkah algoritma.
Sebuah path dari root ke setiap node akhir akan menyimpan kode awalan yang optimal (juga dikenal sebagai kode Huffman) yang sesuai dengan karakter yang terkait dengan node akhir tersebut.
Pohon Huffman
Di bawah ini Anda akan menemukan penerapan algoritma kompresi Huffman di C++ dan 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);
}
}Catatan: memori yang digunakan oleh string input adalah 47 * 8 = 376 bit dan string yang disandikan hanya 194 bit yaitu data dikompresi sekitar 48%. Dalam program C++ di atas, kami menggunakan kelas string untuk menyimpan string yang disandikan agar program dapat dibaca.
Karena struktur data antrian prioritas yang efisien memerlukan per penyisipan HAI(catatan(N)) waktu, tetapi dalam pohon biner lengkap dengan N daun hadir 2N-1 node, dan pohon Huffman adalah pohon biner lengkap, maka algoritme berjalan masuk HAI(Nlog(N)) waktu, dimana N - Karakter.
Sumber:
Sumber: www.habr.com