Πριν την έναρξη του μαθήματος ετοίμασε για εσάς μια μετάφραση άλλου χρήσιμου υλικού.
Η κωδικοποίηση Huffman είναι ένας αλγόριθμος συμπίεσης δεδομένων που διατυπώνει τη βασική ιδέα της συμπίεσης αρχείων. Σε αυτό το άρθρο, θα μιλήσουμε για κωδικοποίηση σταθερού και μεταβλητού μήκους, μοναδικά αποκωδικοποιήσιμους κωδικούς, κανόνες προθέματος και κατασκευή ενός δέντρου Huffman.
Γνωρίζουμε ότι κάθε χαρακτήρας αποθηκεύεται ως ακολουθία 0 και 1 και καταλαμβάνει 8 bit. Αυτό ονομάζεται κωδικοποίηση σταθερού μήκους επειδή κάθε χαρακτήρας χρησιμοποιεί τον ίδιο σταθερό αριθμό bit για αποθήκευση.
Ας πούμε ότι έχουμε ένα κείμενο. Πώς μπορούμε να μειώσουμε τον χώρο που απαιτείται για την αποθήκευση ενός μεμονωμένου χαρακτήρα;
Η κύρια ιδέα είναι η κωδικοποίηση μεταβλητού μήκους. Μπορούμε να χρησιμοποιήσουμε το γεγονός ότι ορισμένοι χαρακτήρες στο κείμενο εμφανίζονται πιο συχνά από άλλους () για να αναπτύξετε έναν αλγόριθμο που θα αναπαριστά την ίδια ακολουθία χαρακτήρων σε λιγότερα bit. Στην κωδικοποίηση μεταβλητού μήκους, εκχωρούμε στους χαρακτήρες έναν μεταβλητό αριθμό bit, ανάλογα με το πόσο συχνά εμφανίζονται σε ένα δεδομένο κείμενο. Τελικά, ορισμένοι χαρακτήρες μπορεί να χρειαστούν μόλις 1 bit, ενώ άλλοι μπορεί να χρειαστούν 2 bit, 3 ή περισσότερα. Το πρόβλημα με την κωδικοποίηση μεταβλητού μήκους είναι μόνο η επακόλουθη αποκωδικοποίηση της ακολουθίας.
Πώς, γνωρίζοντας την ακολουθία των bit, την αποκωδικοποιούμε ξεκάθαρα;
Σκεφτείτε τη γραμμή "abacdab". Έχει 8 χαρακτήρες και όταν κωδικοποιεί ένα σταθερό μήκος, θα χρειαστεί 64 bit για να το αποθηκεύσει. Σημειώστε ότι η συχνότητα συμβόλων "α", "β", "γ" и "ΡΕ" ισούται με 4, 2, 1, 1 αντίστοιχα. Ας προσπαθήσουμε να φανταστούμε "abacdab" λιγότερα bits, χρησιμοποιώντας το γεγονός ότι "προς το" εμφανίζεται συχνότερα από "ΣΙ"Και "ΣΙ" εμφανίζεται συχνότερα από "εναντίον" и "ΡΕ". Ας ξεκινήσουμε με την κωδικοποίηση "προς το" με ένα bit ίσο με 0, "ΣΙ" θα εκχωρήσουμε έναν κωδικό δύο bit 11 και χρησιμοποιώντας τρία bit 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
...
κλπ.
Για να αποφευχθεί αυτή η ασάφεια, πρέπει να διασφαλίσουμε ότι η κωδικοποίησή μας ικανοποιεί μια τέτοια έννοια όπως κανόνας προθέματος, το οποίο με τη σειρά του σημαίνει ότι οι κωδικοί μπορούν να αποκωδικοποιηθούν μόνο με έναν μοναδικό τρόπο. Ο κανόνας του προθέματος διασφαλίζει ότι κανένας κώδικας δεν είναι πρόθεμα άλλου. Με τον όρο κώδικα, εννοούμε τα bit που χρησιμοποιούνται για την αναπαράσταση ενός συγκεκριμένου χαρακτήρα. Στο παραπάνω παράδειγμα 0 είναι πρόθεμα 011, το οποίο παραβιάζει τον κανόνα του προθέματος. Έτσι, εάν οι κώδικές μας ικανοποιούν τον κανόνα του προθέματος, τότε μπορούμε να αποκωδικοποιήσουμε μοναδικά (και το αντίστροφο).
Ας ξαναδούμε το παραπάνω παράδειγμα. Αυτή τη φορά θα ορίσουμε για σύμβολα "α", "β", "γ" и "ΡΕ" κωδικούς που ικανοποιούν τον κανόνα του προθέματος.
a
0
b
10
c
110
d
111
Με αυτήν την κωδικοποίηση, η συμβολοσειρά "abacdab" θα κωδικοποιηθεί ως 00100100011010 (0|0|10|0|100|011|0|10). Αλλά η 00100100011010 θα είμαστε ήδη σε θέση να αποκωδικοποιήσουμε αναμφίβολα και να επιστρέψουμε στην αρχική μας συμβολοσειρά "abacdab".
Κωδικοποίηση Huffman
Τώρα που ασχοληθήκαμε με την κωδικοποίηση μεταβλητού μήκους και τον κανόνα του προθέματος, ας μιλήσουμε για την κωδικοποίηση Huffman.
Η μέθοδος βασίζεται στη δημιουργία δυαδικών δέντρων. Σε αυτό, ο κόμβος μπορεί να είναι είτε τελικός είτε εσωτερικός. Αρχικά, όλοι οι κόμβοι θεωρούνται φύλλα (τερματικά), τα οποία αντιπροσωπεύουν το ίδιο το σύμβολο και το βάρος του (δηλαδή τη συχνότητα εμφάνισης). Οι εσωτερικοί κόμβοι περιέχουν το βάρος του χαρακτήρα και αναφέρονται σε δύο κόμβους καταγωγής. Κατά γενική συμφωνία, λίγο «0» αντιπροσωπεύει μετά τον αριστερό κλάδο και «1» - στα δεξιά. σε γεμάτο δέντρο N φύλλα και Ν-1 εσωτερικούς κόμβους. Συνιστάται κατά την κατασκευή ενός δέντρου Huffman, τα αχρησιμοποίητα σύμβολα να απορρίπτονται για να λάβετε κωδικούς βέλτιστου μήκους.
Θα χρησιμοποιήσουμε μια ουρά προτεραιότητας για να δημιουργήσουμε ένα δέντρο Huffman, όπου ο κόμβος με τη χαμηλότερη συχνότητα θα έχει την υψηλότερη προτεραιότητα. Τα βήματα κατασκευής περιγράφονται παρακάτω:
- Δημιουργήστε έναν κόμβο φύλλου για κάθε χαρακτήρα και προσθέστε τον στην ουρά προτεραιότητας.
- Ενώ υπάρχουν περισσότερα από ένα φύλλα στην ουρά, κάντε τα εξής:
- Αφαιρέστε τους δύο κόμβους με την υψηλότερη προτεραιότητα (χαμηλότερη συχνότητα) από την ουρά.
- Δημιουργήστε έναν νέο εσωτερικό κόμβο, όπου αυτοί οι δύο κόμβοι θα είναι παιδιά και η συχνότητα εμφάνισης θα είναι ίση με το άθροισμα των συχνοτήτων αυτών των δύο κόμβων.
- Προσθέστε έναν νέο κόμβο στην ουρά προτεραιότητας.
- Ο μόνος κόμβος που απομένει θα είναι η ρίζα και αυτό θα ολοκληρώσει την κατασκευή του δέντρου.
Φανταστείτε ότι έχουμε κάποιο κείμενο που αποτελείται μόνο από χαρακτήρες "Α Β Γ Δ" и "και", και οι συχνότητες εμφάνισής τους είναι 15, 7, 6, 6 και 5, αντίστοιχα. Παρακάτω υπάρχουν εικόνες που αντικατοπτρίζουν τα βήματα του αλγορίθμου.
Μια διαδρομή από τη ρίζα σε οποιονδήποτε τερματικό κόμβο θα αποθηκεύσει τον βέλτιστο κωδικό προθέματος (επίσης γνωστό ως κώδικας Huffman) που αντιστοιχεί στον χαρακτήρα που σχετίζεται με αυτόν τον τελικό κόμβο.
Δέντρο Huffman
Παρακάτω θα βρείτε την υλοποίηση του αλγόριθμου συμπίεσης Huffman σε 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 bit και η κωδικοποιημένη συμβολοσειρά είναι μόνο 194 bit, δηλ. Τα δεδομένα συμπιέζονται κατά περίπου 48%. Στο παραπάνω πρόγραμμα C++, χρησιμοποιούμε την κλάση συμβολοσειράς για να αποθηκεύσουμε την κωδικοποιημένη συμβολοσειρά για να κάνουμε το πρόγραμμα αναγνώσιμο.
Επειδή οι αποτελεσματικές δομές δεδομένων ουράς προτεραιότητας απαιτούν ανά εισαγωγή O(log(N)) χρόνο, αλλά σε ένα πλήρες δυαδικό δέντρο με N φύλλα παρόντα 2N-1 κόμβους, και το δέντρο Huffman είναι ένα πλήρες δυαδικό δέντρο, τότε ο αλγόριθμος εκτελείται O(Nlog(N)) ώρα, πού N - Χαρακτήρες.
Πηγές:
Πηγή: www.habr.com