Anvan kou a kòmanse prepare pou ou yon tradiksyon yon lòt materyèl itil.
Huffman kodaj se yon algorithm konpresyon done ki fòmile lide debaz nan konpresyon dosye. Nan atik sa a, nou pral pale sou kodaj longè fiks ak varyab, kòd inikman dekodaj, règ prefiks, ak bati yon pye bwa Huffman.
Nou konnen chak karaktè yo estoke kòm yon sekans 0 ak 1 epi li pran 8 bit. Yo rele sa kodaj longè fiks paske chak karaktè sèvi ak menm kantite fiks Bits pou estoke.
Ann di nou resevwa tèks. Ki jan nou ka diminye kantite espas ki nesesè pou estoke yon karaktè sèl?
Lide prensipal la se kodaj longè varyab. Nou ka itilize lefèt ke kèk karaktè nan tèks la parèt pi souvan pase lòt () pou devlope yon algorithm ki pral reprezante menm sekans karaktè nan mwens bit. Nan kodaj longè varyab, nou bay karaktè yo yon kantite varyab de bit, tou depann de konbyen fwa yo parèt nan yon tèks bay yo. Evantyèlman, kèk karaktè ka pran ti jan 1 ti jan, pandan ke lòt moun ka pran 2 ti jan, 3 oswa plis. Pwoblèm nan ak kodaj longè varyab se sèlman dekodaj ki vin apre a nan sekans lan.
Ki jan, konnen sekans nan Bits, dekode li san anbigwite?
Konsidere liy lan "abacdab". Li gen 8 karaktè, epi lè kode yon longè fiks, li pral bezwen 64 Bits nan magazen li. Remake byen ke frekans senbòl la "a", "b", "c" и "D" egal 4, 2, 1, 1 respektivman. Ann eseye imajine "abacdab" mwens Bits, lè l sèvi avèk lefèt ke "a" rive pi souvan pase "B"Ak "B" rive pi souvan pase "c" и "D". Ann kòmanse pa kodaj "a" ak yon ti jan egal a 0, "B" nou pral bay yon kòd de-bit 11, epi lè l sèvi avèk twa ti 100 ak 011 nou pral kode. "c" и "D".
Kòm yon rezilta, nou pral jwenn:
a
0
b
11
c
100
d
011
Se konsa, liy lan "abacdab" nou pral kode kòm 00110100011011 (0|0|11|0|100|011|0|11)lè l sèvi avèk kòd ki anwo yo. Sepandan, pwoblèm prensipal la pral nan dekodaj. Lè nou eseye dekode fisèl la 00110100011011, nou jwenn yon rezilta ambigu, paske li ka reprezante kòm:
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
...
elatriye
Pou evite anbigwite sa a, nou dwe asire ke kodaj nou satisfè tankou yon konsèp tankou règ prefiks, ki an vire implique ke kòd yo ka sèlman dekode nan yon fason inik. Règ prefiks la asire ke pa gen okenn kòd se yon prefiks yon lòt. Pa kòd, nou vle di Bits yo itilize pou reprezante yon karaktè patikilye. Nan egzanp ki anwo a 0 se yon prefiks 011, ki vyole règ prefiks la. Se konsa, si kòd nou yo satisfè règ la prefiks, Lè sa a, nou ka inikman dekode (ak vis vèrsa).
Ann revize egzanp ki anwo a. Fwa sa a, nou pral bay senbòl yo "a", "b", "c" и "D" kòd ki satisfè règ prefiks la.
a
0
b
10
c
110
d
111
Avèk kodaj sa a, fisèl la "abacdab" pral kode kòm 00100100011010 (0|0|10|0|100|011|0|10). Men, nan 00100100011010 nou pral deja kapab dekode san anbigwite epi retounen nan fisèl orijinal nou an "abacdab".
Huffman kodaj
Kounye a ke nou te fè fas ak kodaj longè varyab ak règ la prefiks, ann pale sou kodaj Huffman.
Metòd la baze sou kreyasyon pye bwa binè. Nan li, ne a ka swa final oswa entèn. Okòmansman, tout nœuds yo konsidere kòm fèy (tèminal), ki reprezante senbòl nan tèt li ak pwa li yo (ki se, frekans nan ensidan an). Nœuds entèn yo genyen pwa karaktè a epi refere a de nœuds desandan yo. Pa akò jeneral, ti jan «NAN» reprezante swiv branch gòch la, epi «NAN» - sou bò dwat la. nan pye bwa plen N fèy ak N-1 nœuds entèn yo. Li rekòmande ke lè konstwi yon pye bwa Huffman, senbòl ki pa itilize yo dwe jete pou jwenn kòd longè optimal.
Nou pral sèvi ak yon keu priyorite pou konstwi yon pye bwa Huffman, kote yo pral bay ne ki pi ba frekans lan pi gwo priyorite. Etap konstriksyon yo dekri anba a:
- Kreye yon ne fèy pou chak karaktè epi ajoute yo nan keu priyorite a.
- Pandan ke gen plis pase yon fèy nan keu a, fè bagay sa yo:
- Retire de nœuds ki gen pi gwo priyorite (frekans ki pi ba) nan keu a;
- Kreye yon nouvo ne entèn, kote de nœuds sa yo pral timoun, ak frekans ensidan an pral egal a sòm total frekans de nœuds sa yo.
- Ajoute yon nouvo ne nan keu priyorite a.
- Sèl ne ki rete a pral rasin lan, e sa pral konplete konstriksyon pye bwa a.
Imajine ke nou gen kèk tèks ki gen sèlman karaktè "a", "b", "c", "d" и "ak", ak frekans ensidan yo se 15, 7, 6, 6, ak 5, respektivman. Anba a se ilistrasyon ki reflete etap algorithm la.
Yon chemen ki soti nan rasin lan rive nan nenpòt nod final la pral estoke kòd prefiks optimal (ke yo rele tou kòd Huffman) ki koresponn ak karaktè ki asosye ak ne final sa a.
Pye bwa Huffman
Anba a ou pral jwenn aplikasyon an nan algorithm konpresyon Huffman nan C++ ak 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);
}
}Remak: memwa a itilize pa fisèl la opinyon se 47 * 8 = 376 Bits ak fisèl la kode se sèlman 194 Bits i.e. done yo konprese pa apeprè 48%. Nan pwogram C++ ki anwo a, nou itilize klas fisèl la pou konsève fisèl kode a pou fè pwogram nan lizib.
Paske efikas priyorite keu done estrikti mande pou chak ensèsyon O (log (N)) tan, men nan yon pye bwa binè konplè ak N fèy prezan 2N-1 nœuds, ak pye bwa a Huffman se yon pye bwa binè konplè, Lè sa a, algorithm la kouri nan O(Nlog(N)) tan, kote N - Karaktè.
Sous:
Sous: www.habr.com