Sebelum kursus bermula menyediakan untuk anda terjemahan bahan berguna yang lain.
Pengekodan Huffman ialah algoritma pemampatan data yang merumuskan idea asas pemampatan fail. Dalam artikel ini, kita akan bercakap tentang pengekodan panjang tetap dan berubah-ubah, kod unik yang boleh dinyahkod, peraturan awalan dan membina pokok Huffman.
Kita tahu bahawa setiap aksara disimpan sebagai urutan 0 dan 1 dan mengambil 8 bit. Ini dipanggil pengekodan panjang tetap kerana setiap aksara menggunakan bilangan bit tetap yang sama untuk disimpan.
Katakan kita mempunyai teks. Bagaimanakah kita boleh mengurangkan jumlah ruang yang diperlukan untuk menyimpan satu aksara?
Idea utama ialah pengekodan panjang berubah-ubah. Kita boleh menggunakan fakta bahawa sesetengah aksara dalam teks berlaku lebih kerap daripada yang lain () untuk membangunkan algoritma yang akan mewakili jujukan aksara yang sama dalam bit yang lebih sedikit. Dalam pengekodan panjang berubah-ubah, kami menetapkan aksara bilangan bit yang berubah-ubah, bergantung pada kekerapan ia muncul dalam teks tertentu. Akhirnya, sesetengah aksara mungkin mengambil masa serendah 1 bit, manakala yang lain mungkin mengambil 2 bit, 3 atau lebih. Masalah dengan pengekodan panjang berubah-ubah hanyalah penyahkodan seterusnya bagi jujukan.
Bagaimana, mengetahui urutan bit, menyahkodnya dengan jelas?
Pertimbangkan baris "abacdab". Ia mempunyai 8 aksara, dan apabila mengekodkan panjang tetap, ia memerlukan 64 bit untuk menyimpannya. Perhatikan bahawa kekerapan simbol "a", "b", "c" ΠΈ "D" sama dengan 4, 2, 1, 1 masing-masing. Cuba kita bayangkan "abacdab" lebih sedikit bit, menggunakan fakta bahawa "ke" berlaku lebih kerap daripada "B"Dan "B" berlaku lebih kerap daripada "c" ΠΈ "D". Mari mulakan dengan pengekodan "ke" dengan satu bit sama dengan 0, "B" kami akan memberikan kod dua bit 11, dan menggunakan tiga bit 100 dan 011 kami akan mengekod "c" ΠΈ "D".
Hasilnya, kita akan mendapat:
a
0
b
11
c
100
d
011
Jadi garisan "abacdab" kami akan mengekod sebagai 00110100011011 (0|0|11|0|100|011|0|11)menggunakan kod di atas. Walau bagaimanapun, masalah utama adalah dalam penyahkodan. Apabila kita cuba menyahkod rentetan 00110100011011, kami mendapat hasil yang tidak jelas, kerana ia boleh diwakili 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 mengelakkan kekaburan ini, kami mesti memastikan pengekodan kami memenuhi konsep seperti peraturan awalan, yang seterusnya membayangkan bahawa kod hanya boleh dinyahkod dalam satu cara yang unik. Peraturan awalan memastikan tiada kod merupakan awalan bagi yang lain. Dengan kod, kami maksudkan bit yang digunakan untuk mewakili watak tertentu. Dalam contoh di atas 0 ialah awalan 011, yang melanggar peraturan awalan. Jadi, jika kod kami memenuhi peraturan awalan, maka kami boleh menyahkod secara unik (dan sebaliknya).
Mari kita lihat semula contoh di atas. Kali ini kita akan menetapkan untuk simbol "a", "b", "c" ΠΈ "D" kod yang memenuhi peraturan awalan.
a
0
b
10
c
110
d
111
Dengan pengekodan ini, rentetan "abacdab" akan dikodkan sebagai 00100100011010 (0|0|10|0|100|011|0|10). Tetapi 00100100011010 kami sudah boleh menyahkod dengan jelas dan kembali kepada rentetan asal kami "abacdab".
Pengekodan Huffman
Memandangkan kita telah menangani pengekodan panjang berubah-ubah dan peraturan awalan, mari kita bercakap tentang pengekodan Huffman.
Kaedah ini berdasarkan penciptaan pokok binari. Di dalamnya, nod boleh sama ada muktamad atau dalaman. Pada mulanya, semua nod dianggap daun (terminal), yang mewakili simbol itu sendiri dan beratnya (iaitu, kekerapan kejadian). Nod dalaman mengandungi berat watak dan merujuk kepada dua nod keturunan. Dengan persetujuan umum, bit Β«0Β» mewakili mengikuti cawangan kiri, dan Β«1Β» - di sebelah kanan. dalam pokok penuh N daun dan N-1 nod dalaman. Adalah disyorkan bahawa apabila membina pokok Huffman, simbol yang tidak digunakan dibuang untuk mendapatkan kod panjang optimum.
Kami akan menggunakan baris gilir keutamaan untuk membina pokok Huffman, di mana nod dengan kekerapan terendah akan diberi keutamaan tertinggi. Langkah-langkah pembinaan diterangkan di bawah:
- Buat nod daun untuk setiap aksara dan tambahkannya pada baris gilir keutamaan.
- Walaupun terdapat lebih daripada satu helaian dalam baris gilir, lakukan perkara berikut:
- Keluarkan dua nod dengan keutamaan tertinggi (frekuensi terendah) daripada baris gilir;
- Buat nod dalaman baharu, di mana kedua-dua nod ini akan menjadi kanak-kanak, dan kekerapan kejadian akan sama dengan jumlah frekuensi kedua-dua nod ini.
- Tambahkan nod baharu pada baris gilir keutamaan.
- Satu-satunya nod yang tinggal ialah akar, dan ini akan melengkapkan pembinaan pokok itu.
Bayangkan kita mempunyai beberapa teks yang hanya terdiri daripada aksara "a", "b", "c", "d" ΠΈ "dan", dan kekerapan kejadiannya ialah 15, 7, 6, 6, dan 5, masing-masing. Di bawah adalah ilustrasi yang mencerminkan langkah-langkah algoritma.
Laluan dari akar ke mana-mana nod akhir akan menyimpan kod awalan optimum (juga dikenali sebagai kod Huffman) yang sepadan dengan aksara yang dikaitkan dengan nod akhir itu.
Pokok Huffman
Di bawah anda akan menemui pelaksanaan algoritma pemampatan Huffman dalam 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);
}
}Nota: memori yang digunakan oleh rentetan input ialah 47 * 8 = 376 bit dan rentetan yang dikodkan hanya 194 bit i.e. data dimampatkan sebanyak kira-kira 48%. Dalam program C++ di atas, kami menggunakan kelas rentetan untuk menyimpan rentetan yang dikodkan untuk menjadikan atur cara boleh dibaca.
Kerana struktur data baris gilir keutamaan yang cekap memerlukan setiap sisipan O(log(N)) masa, tetapi dalam pokok binari yang lengkap dengan N daun hadir 2N-1 nod, dan pokok Huffman ialah pokok binari yang lengkap, kemudian algoritma berjalan masuk O(Nlog(N)) masa, di mana N - Watak.
Sumber:
Sumber: www.habr.com