Przed rozpoczęciem kursu przygotowałem dla Ciebie tłumaczenie kolejnego przydatnego materiału.
Kodowanie Huffmana to algorytm kompresji danych, który formułuje podstawową ideę kompresji plików. W tym artykule omówimy kodowanie o stałej i zmiennej długości, unikalne kody dekodowalne, reguły prefiksów i budowanie drzewa Huffmana.
Wiemy, że każdy znak jest przechowywany jako ciąg zer i jedynek i zajmuje 0 bitów. Nazywa się to kodowaniem o stałej długości, ponieważ każdy znak używa tej samej stałej liczby bitów do przechowywania.
Powiedzmy, że otrzymaliśmy tekst. Jak możemy zmniejszyć ilość miejsca potrzebnego do przechowywania pojedynczego znaku?
Główną ideą jest kodowanie o zmiennej długości. Możemy wykorzystać fakt, że niektóre znaki w tekście występują częściej niż inne () w celu opracowania algorytmu, który będzie reprezentował tę samą sekwencję znaków w mniejszej liczbie bitów. W kodowaniu o zmiennej długości przypisujemy znakom zmienną liczbę bitów, w zależności od tego, jak często występują w danym tekście. W końcu niektóre znaki mogą zająć zaledwie 1 bit, podczas gdy inne mogą zająć 2 bity, 3 lub więcej. Problem z kodowaniem o zmiennej długości polega tylko na późniejszym dekodowaniu sekwencji.
Jak, znając kolejność bitów, jednoznacznie ją zdekodować?
Rozważ linię „abakdab”. Ma 8 znaków, a podczas kodowania o stałej długości będzie potrzebować 64 bitów, aby go zapisać. Zwróć uwagę, że częstotliwość symboli „a”, „b”, „c” и "D" równa się odpowiednio 4, 2, 1, 1. Spróbujmy sobie wyobrazić „abakdab” mniej bitów, wykorzystując fakt, że "do" występuje częściej niż "B"I "B" występuje częściej niż "vs" и "D". Zacznijmy od kodowania "do" z jednym bitem równym 0, "B" przypiszemy dwubitowy kod 11, a trzema bitami 100 i 011 zakodujemy "vs" и "D".
W efekcie otrzymamy:
a
0
b
11
c
100
d
011
Więc linia „abakdab” będziemy kodować jako 00110100011011 (0|0|11|0|100|011|0|11)używając powyższych kodów. Jednak głównym problemem będzie dekodowanie. Kiedy próbujemy odszyfrować ciąg 00110100011011, otrzymamy niejednoznaczny wynik, ponieważ można go przedstawić jako:
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
...
itd.
Aby uniknąć tej dwuznaczności, musimy upewnić się, że nasze kodowanie spełnia taką koncepcję jak reguła prefiksu, co z kolei oznacza, że kody mogą być dekodowane tylko w jeden unikalny sposób. Reguła przedrostka zapewnia, że żaden kod nie jest przedrostkiem innego. Przez kod rozumiemy bity używane do reprezentowania określonego znaku. W powyższym przykładzie 0 jest przedrostkiem 011, co narusza zasadę przedrostka. Tak więc, jeśli nasze kody spełniają regułę przedrostka, możemy jednoznacznie dekodować (i odwrotnie).
Wróćmy do powyższego przykładu. Tym razem przeznaczymy na symbole „a”, „b”, „c” и "D" kody spełniające regułę przedrostka.
a
0
b
10
c
110
d
111
Przy takim kodowaniu string „abakdab” zostanie zakodowany jako 00100100011010 (0|0|10|0|100|011|0|10). Ale 00100100011010 będziemy już mogli jednoznacznie rozszyfrować i powrócić do naszego pierwotnego ciągu „abakdab”.
kodowanie Huffmana
Teraz, gdy omówiliśmy kodowanie o zmiennej długości i regułę przedrostka, porozmawiajmy o kodowaniu Huffmana.
Metoda opiera się na tworzeniu drzew binarnych. W nim węzeł może być końcowy lub wewnętrzny. Początkowo wszystkie węzły są uważane za liście (terminale), które reprezentują sam symbol i jego wagę (czyli częstotliwość występowania). Węzły wewnętrzne zawierają wagę postaci i odnoszą się do dwóch węzłów potomnych. Za ogólną zgodą, bit «0» reprezentuje podążanie za lewą gałęzią i «1» - po prawej. w pełnym drzewie N liście i N-1 węzły wewnętrzne. Zaleca się, aby podczas konstruowania drzewa Huffmana odrzucić nieużywane symbole w celu uzyskania kodów o optymalnej długości.
Za pomocą kolejki priorytetów zbudujemy drzewo Huffmana, gdzie najwyższy priorytet będzie miał węzeł o najniższej częstotliwości. Etapy budowy opisano poniżej:
- Utwórz węzeł liścia dla każdej postaci i dodaj je do kolejki priorytetowej.
- Gdy w kolejce znajduje się więcej niż jeden arkusz, wykonaj następujące czynności:
- Usuń dwa węzły o najwyższym priorytecie (najniższej częstotliwości) z kolejki;
- Utwórz nowy węzeł wewnętrzny, w którym te dwa węzły będą dziećmi, a częstotliwość występowania będzie równa sumie częstotliwości tych dwóch węzłów.
- Dodaj nowy węzeł do kolejki priorytetowej.
- Jedynym pozostałym węzłem będzie korzeń, co zakończy budowę drzewa.
Wyobraź sobie, że mamy jakiś tekst, który składa się tylko ze znaków „a”, „b”, „c”, „d” и "i", a częstość ich występowania to odpowiednio 15, 7, 6, 6 i 5. Poniżej znajdują się ilustracje przedstawiające kroki algorytmu.
Ścieżka od korzenia do dowolnego węzła końcowego będzie przechowywać optymalny kod prefiksu (znany również jako kod Huffmana) odpowiadający znakowi powiązanemu z tym węzłem końcowym.
Drzewo Huffmana
Poniżej znajdziesz implementację algorytmu kompresji Huffmana w C++ i Javie:
#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);
}
}Uwaga: pamięć używana przez ciąg wejściowy to 47 * 8 = 376 bitów, a zakodowany ciąg to tylko 194 bity, tj. dane są kompresowane o około 48%. W powyższym programie C++ używamy klasy string do przechowywania zakodowanego łańcucha, aby program był czytelny.
Ponieważ wydajne struktury danych kolejki priorytetowej wymagają jednego wstawienia O(log(N)) czas, ale w kompletnym drzewie binarnym z N obecne liście 2N-1 węzłów, a drzewo Huffmana jest kompletnym drzewem binarnym, wówczas algorytm działa O(Nlog(N)) czas, gdzie N - Postacie.
Źródła:
Źródło: www.habr.com