Para fillimit të kursit përgatiti për ju një përkthim të një materiali tjetër të dobishëm.
Kodimi Huffman është një algoritëm i kompresimit të të dhënave që formulon idenë bazë të kompresimit të skedarit. Në këtë artikull, ne do të flasim për kodimin me gjatësi fikse dhe të ndryshueshme, kodet unike të dekodueshme, rregullat e parashtesave dhe ndërtimin e një peme Huffman.
Ne e dimë se çdo karakter ruhet si një sekuencë prej 0 dhe 1 dhe merr 8 bit. Ky quhet kodim me gjatësi fikse sepse çdo karakter përdor të njëjtin numër fiks të biteve për të ruajtur.
Le të themi se na është dhënë tekst. Si mund ta zvogëlojmë sasinë e hapësirës që kërkohet për të ruajtur një karakter të vetëm?
Ideja kryesore është kodimi me gjatësi të ndryshueshme. Mund të përdorim faktin që disa karaktere në tekst shfaqen më shpesh se të tjerët () për të zhvilluar një algoritëm që do të përfaqësojë të njëjtën sekuencë karakteresh në më pak bit. Në kodimin me gjatësi të ndryshueshme, ne u caktojmë karaktereve një numër të ndryshueshëm bitësh, në varësi të asaj se sa shpesh shfaqen në një tekst të caktuar. Përfundimisht, disa karaktere mund të marrin vetëm 1 bit, ndërsa të tjerë mund të marrin 2 bit, 3 ose më shumë. Problemi me kodimin me gjatësi të ndryshueshme është vetëm dekodimi i mëpasshëm i sekuencës.
Si, duke ditur sekuencën e biteve, ta deshifroni atë pa mëdyshje?
Merrni parasysh linjën "abacdab". Ai ka 8 karaktere dhe kur kodon një gjatësi fikse, do t'i duhen 64 bit për ta ruajtur atë. Vini re se frekuenca e simbolit "a", "b", "c" и "D" është e barabartë me 4, 2, 1, 1 respektivisht. Le të përpiqemi të imagjinojmë "abacdab" më pak bit, duke përdorur faktin se "te" ndodh më shpesh se "B"Dhe "B" ndodh më shpesh se "c" и "D". Le të fillojmë me kodimin "te" me një bit të barabartë me 0, "B" ne do të caktojmë një kod dy-bitësh 11, dhe duke përdorur tre bit 100 dhe 011 do të kodojmë "c" и "D".
Si rezultat, ne do të marrim:
a
0
b
11
c
100
d
011
Pra, linja "abacdab" ne do të kodojmë si 00110100011011 (0|0|11|0|100|011|0|11)duke përdorur kodet e mësipërme. Megjithatë, problemi kryesor do të jetë në dekodimin. Kur përpiqemi të dekodojmë vargun 00110100011011, do të marrim një rezultat të paqartë, pasi ai mund të përfaqësohet si:
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
...
etj
Për të shmangur këtë paqartësi, duhet të sigurohemi që kodimi ynë të përmbushë një koncept të tillë si rregulli i prefiksit, që nga ana tjetër nënkupton se kodet mund të deshifrohen vetëm në një mënyrë unike. Rregulli i prefiksit siguron që asnjë kod nuk është parashtesë e një tjetri. Me kod, nënkuptojmë bitet e përdorura për të përfaqësuar një karakter të caktuar. Në shembullin e mësipërm 0 është një parashtesë 011, e cila shkel rregullin e prefiksit. Pra, nëse kodet tona plotësojnë rregullin e prefiksit, atëherë ne mund të deshifrojmë në mënyrë unike (dhe anasjelltas).
Le të rishikojmë shembullin e mësipërm. Këtë herë do të caktojmë për simbolet "a", "b", "c" и "D" kodet që plotësojnë rregullin e prefiksit.
a
0
b
10
c
110
d
111
Me këtë kodim, vargu "abacdab" do të kodohet si 00100100011010 (0|0|10|0|100|011|0|10). Dhe këtu 00100100011010 ne tashmë do të jemi në gjendje të deshifrojmë pa mëdyshje dhe të kthehemi në vargun tonë origjinal "abacdab".
Kodimi i Huffman
Tani që kemi trajtuar kodimin me gjatësi të ndryshueshme dhe rregullin e prefiksit, le të flasim për kodimin Huffman.
Metoda bazohet në krijimin e pemëve binare. Në të, nyja mund të jetë ose përfundimtare ose e brendshme. Fillimisht, të gjitha nyjet konsiderohen gjethe (terminale), të cilat përfaqësojnë vetë simbolin dhe peshën e tij (d.m.th., shpeshtësinë e shfaqjes). Nyjet e brendshme përmbajnë peshën e karakterit dhe i referohen dy nyjeve pasardhëse. Me marrëveshje të përgjithshme, pak «0» paraqet ndjekjen e degës së majtë, dhe «1» - ne te djathte. në pemë të plotë N gjethet dhe N-1 nyjet e brendshme. Rekomandohet që kur ndërtoni një pemë Huffman, simbolet e papërdorura të hidhen për të marrë kodet e gjatësisë optimale.
Ne do të përdorim një radhë prioritare për të ndërtuar një pemë Huffman, ku nyja me frekuencën më të ulët do të ketë përparësinë më të lartë. Hapat e ndërtimit përshkruhen më poshtë:
- Krijoni një nyje fletë për çdo karakter dhe shtoni ato në radhën e përparësisë.
- Ndërsa ka më shumë se një fletë në radhë, bëni sa më poshtë:
- Hiqni dy nyjet me prioritetin më të lartë (frekuencën më të ulët) nga radha;
- Krijoni një nyje të re të brendshme, ku këto dy nyje do të jenë fëmijë, dhe frekuenca e shfaqjes do të jetë e barabartë me shumën e frekuencave të këtyre dy nyjeve.
- Shtoni një nyje të re në radhën e përparësisë.
- E vetmja nyje e mbetur do të jetë rrënja, dhe kjo do të përfundojë ndërtimin e pemës.
Imagjinoni që kemi një tekst që përbëhet vetëm nga karaktere "a", "b", "c", "d" и "dhe", dhe frekuencat e shfaqjes së tyre janë përkatësisht 15, 7, 6, 6 dhe 5. Më poshtë janë ilustrimet që pasqyrojnë hapat e algoritmit.
Një shteg nga rrënja në çdo nyje fundore do të ruajë kodin prefiks optimal (i njohur gjithashtu si kodi Huffman) që korrespondon me karakterin e lidhur me atë nyje fundore.
Pema Huffman
Më poshtë do të gjeni zbatimin e algoritmit të kompresimit Huffman në C++ dhe 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);
}
}Shenim: memoria e përdorur nga vargu hyrës është 47 * 8 = 376 bit dhe vargu i koduar është vetëm 194 bit d.m.th. të dhënat janë të ngjeshura me rreth 48%. Në programin C++ të mësipërm, ne përdorim klasën e vargut për të ruajtur vargun e koduar për ta bërë programin të lexueshëm.
Sepse strukturat efikase të të dhënave të radhës prioritare kërkojnë për futje O(log(N)) kohë, por në një pemë të plotë binare me N gjethet e pranishme 2N-1 nyjet, dhe pema Huffman është një pemë e plotë binare, atëherë algoritmi funksionon O(Nlog(N)) koha, ku N - Personazhet.
Burimet:
Burimi: www.habr.com