W przeddzień rozpoczęcia kursu przygotowaliśmy dla Was 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 stałej i zmiennej długości, kody jednoznacznie dekodowalne, zasady prefiksowe oraz budowę drzewa Huffmana.
Wiemy, że każdy znak jest przechowywany jako sekwencja zer i jedynek i zajmuje 8 bitów. Nazywa się to kodowaniem stałej długości, ponieważ każdy znak używa tej samej, stałej liczby bitów do przechowywania.
Załóżmy, że mamy tekst. W jaki sposób możemy zmniejszyć ilość miejsca wymaganego do przechowywania jednego znaku?
Podstawowa idea polega na kodowaniu zmiennej długości. Możemy wykorzystać fakt, że niektóre znaki w tekście występują częściej niż inne (), aby opracować algorytm, który będzie reprezentował tę samą sekwencję znaków mniejszą liczbą bitów. Przy kodowaniu zmiennej długości przypisujemy znakom zmienną liczbę bitów w zależności od częstotliwości ich występowania w danym tekście. Ostatecznie niektóre znaki mogą zajmować zaledwie 1 bit, inne 2 bity, 3 lub więcej. Problem z kodowaniem zmiennej długości polega jedynie na późniejszym dekodowaniu sekwencji.
Jak, znając sekwencję bitów, można ją jednoznacznie dekodować?
Rozważmy ciąg „aabacdab”. Zawiera on 8 znaków, a przy kodowaniu stałej długości do jego przechowania potrzebnych będzie 64 bity. Zauważmy, że częstotliwość znaków „a”, „b”, „c” i „d” wynosi 4, 2, 1, 1 odpowiednio. Spróbujmy reprezentować „aabacdab” mniejszą liczbą bitów, korzystając z faktu, że „a” występuje częściej niż „b”, a „b” występuje częściej niż „c” i „d”. Zaczniemy od zakodowania „a” przy pomocy jednego bita, równego 0, „b” przypiszemy kod dwubitowy 11, a za pomocą trzech bitów 100 i 011 zakodujemy „c” i „d”.
W efekcie otrzymamy:
a
0
b
11
c
100
d
011
W ten sposób ciąg „aabacdab” zakodujemy jako 00110100011011 (0|0|11|0|100|011|0|11), używając kodów przedstawionych powyżej. Jednak głównym problemem będzie dekodowanie. Kiedy spróbujemy zdekodować 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 niejednoznaczności, musimy zapewnić, że nasze kodowanie spełnia takie pojęcie jak reguła prefiksu, co z kolei oznacza, że kody mogą być dekodowane w jedyny unikalny sposób. Reguła prefiksu zapewnia, że żaden kod nie będzie prefiksem innego. Przez kod rozumiemy bity używane do reprezentacji konkretnego znaku. W podanym przykładzie 0 to jest prefiks 011, co narusza regułę prefiksu. Tak więc, jeśli nasze kody spełniają regułę prefiksu, to dekodowanie może być przeprowadzone jednoznacznie (i odwrotnie).
Przyjrzyjmy się powyższemu przykładzie ponownie. Tym razem przypiszemy znakom „a”, „b”, „c” i „d” kody, które spełniają regułę prefiksu.
a
0
b
10
c
110
d
111
Korzystając z takiego kodowania, ciąg „aabacdab” zostanie zakodowany jako 00100100011010 (0|0|10|0|100|011|0|10). A teraz 00100100011010 będziemy już mogli jednoznacznie dekodować i wrócić do naszego pierwotnego ciągu „aabacdab”.
Kodowanie Huffmana
Teraz, gdy zrozumieliśmy kodowanie o zmiennej długości i regułę prefiksu, porozmawiajmy o kodowaniu Huffmana.
Metoda opiera się na tworzeniu drzew binarnych. W nim węzeł może być liściem lub wewnętrznym. Początkowo wszystkie węzły są uważane za liście (końcowe), które reprezentują sam znak i jego wagę (czyli częstość występowania). Węzły wewnętrzne zawierają wagę znaku i odnoszą się do dwóch węzłów-dziedziców. Zgodnie z ogólnym ustaleniem, bit "0" reprezentuje podążanie lewą gałęzią, a "1" - prawą. W pełnym drzewie N liści i N-1 węzłów wewnętrznych. Zaleca się, aby podczas budowania drzewa Huffmana odrzucać nieużywane znaki, aby uzyskać kody optymalnej długości.
Będziemy używać kolejki priorytetowej do budowania drzewa Huffmana, gdzie węzłowi o najniższej częstotliwości przypisany jest najwyższy priorytet. Poniżej opisano kroki budowy:
- Utwórz węzeł-liść dla każdego znaku i dodaj je do kolejki priorytetowej.
- Dopóki w kolejce jest więcej niż jeden liść, wykonaj następujące kroki:
- Usuń dwa węzły o najwyższym priorytecie (najniższej częstotliwości) z kolejki;
- Utwórz nowy węzeł wewnętrzny, gdzie te dwa węzły będą dziedzicami, 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.
- Ostatni pozostały węzeł będzie węzłem głównym, na tym kończy się budowa drzewa.
Załóżmy, że mamy pewien tekst, który składa się tylko z symboli „a”, „b”, „c”, „d” i „e”, a częstotliwości ich wystąpień wynoszą odpowiednio 15, 7, 6, 6 i 5. Poniżej znajdują się ilustracje, które odzwierciedlają kroki algorytmu.
Ścieżka od korzenia do dowolnego węzła końcowego będzie przechowywać optymalny kod prefiksowy (znany również jako kod Huffy), odpowiadający symbolowi związanym z tym węzłem końcowym.
Drzewo Huffy’ego
Poniżej znajdziesz implementację algorytmu kompresji Huffy’ego w językach C++ i 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;
// Węzeł drzewa
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
{
// Przechodzi przez drzewo Huffmana i zapisuje kody Huffmana
// w mapie.
public static void encode(Node root, String str,
Map huffmanCode)
{
if (root == null)
return;
// znaleziono węzeł liściowy
if (root.left == null && root.right == null) {
huffmanCode.put(root.ch, str);
}
encode(root.left, str + "0", huffmanCode);
encode(root.right, str + "1", huffmanCode);
}
// Przechodzi przez drzewo Huffmana i dekoduje zakodowany ciąg
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// znaleziono węzeł liściowy
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;
}
// Buduje drzewo Huffmana i kod Huffmana oraz dekoduje podany tekst wejściowy
public static void buildHuffmanTree(String text)
{
// zlicza częstotliwość występowania każdego znaku
// i zapisuje w mapie
Map 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);
}
// Tworzy kolejkę priorytetową do przechowywania aktywnych węzłów drzewa Huffmana
// Zauważ, że najwyżej priorytetowy element ma najniższą częstotliwość
PriorityQueue pq = new PriorityQueue(
(l, r) -> l.freq - r.freq);
// Tworzy węzeł liściowy dla każdego znaku i dodaje go
// do kolejki priorytetowej.
for (Map.Entry entry : freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
// robi do momentu, gdy w kolejce jest więcej niż jeden węzeł
while (pq.size() != 1)
{
// Usuwa dwa węzły o najwyższym priorytecie
// (najniższej częstotliwości) z kolejki
Node left = pq.poll();
Node right = pq.poll();
// Tworzy nowy węzeł wewnętrzny z tymi dwoma węzłami jako dziećmi
// i z częstotliwością równą sumie częstotliwości dwóch węzłów.
// Dodaje nowy węzeł do kolejki priorytetowej.
int sum = left.freq + right.freq;
pq.add(new Node(' ', sum, left, right));
}
// korzeń przechowuje wskaźnik do korzenia drzewa Huffmana
Node root = pq.peek();
// przechodzi przez drzewo Huffmana i zapisuje kody Huffmana w mapie
Map huffmanCode = new HashMap();
encode(root, "", huffmanCode);
// drukuje kody Huffmana
System.out.println("Kody Huffmana to :\n");
for (Map.Entry entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("\nOryginalny ciąg to :\n" + text);
// drukuje zakodowany ciąg
StringBuilder sb = new StringBuilder();
for (int i = 0 ; i < text.length(); i++) {
sb.append(huffmanCode.get(text.charAt(i)));
}
System.out.println("\nZakodowany ciąg to :\n" + sb);
// przechodzi przez drzewo Huffmana ponownie i tym razem
// dekoduje zakodowany ciąg
int index = -1;
System.out.println("\nZdekodowany ciąg to: \n");
while (index < sb.length() - 2) {
index = decode(root, index, sb);
}
}
public static void main(String[] args)
{
String text = "Kodowanie Huffmana to algorytm kompresji danych.";
buildHuffmanTree(text);
}
}Uwaga: Pamięć używana przez ciąg wejściowy wynosi 47 * 8 = 376 bitów, a zakodowany ciąg zajmuje tylko 194 bity, co oznacza, że dane są kompresowane o około 48%. W programie w C++ używamy klasy string do przechowywania zakodowanego ciągu, aby ułatwić czytanie programu.
Ponieważ efektywne struktury danych kolejki priorytetowej wymagają czasu na wstawienie O(log(N)) czas, a w pełnym drzewie binarnym z N liśćmi znajduje się 2N-1 węzłów, a drzewo Huffmana to pełne drzewo binarne, więc algorytm działa w czasie O(Nlog(N)) gdzie N to liczba symboli.
Źródła:
Źródło: habr.com
