Foar it begjin fan 'e kursus Wy hawwe in oersetting fan in oar nuttich materiaal foar jo taret.
Huffman-kodearring is in datakompresjealgoritme dat it basisidee fan bestânkompresje formuleart. Yn dit artikel sille wy prate oer fêste en fariabele lingte kodearring, unyk dekodearje koades, prefix regels, en Huffman beam konstruksje.
Wy witte dat elk karakter wurdt opslein as in folchoarder fan 0s en 1s en beslacht 8 bits. Dit wurdt kodearring mei fêste lingte neamd, om't elk karakter itselde fêste oantal opslachbits brûkt.
Litte wy sizze dat de tekst wurdt jûn. Hoe kinne wy de hoemannichte romte ferminderje dy't nedich is om ien karakter te bewarjen?
It basisidee is kodearring mei fariabele lingte. Wy kinne it feit brûke dat guon karakters faker yn tekst ferskine as oaren () om in algoritme te ûntwikkeljen dat deselde folchoarder fan karakters yn minder bits sil fertsjintwurdigje. By kodearring mei fariabele lingte tawize wy in fariabel oantal bits oan karakters ôfhinklik fan de frekwinsje fan har foarkommen yn in opjûne tekst. Uteinlik kinne guon karakters mar 1 bit nimme, wylst oaren 2 bits, 3 of mear kinne nimme. It probleem mei kodearring fan fariabele lingte is allinich de folgjende dekodearring fan 'e folchoarder.
Hoe kinne jo, mei in sekwinsje fan bits, it unambigu ûntsiferje?
Tink oan de line "aabacdab". It hat 8 karakters, en mei kodearring fan fêste lingte sil it 64 bits nedich wêze om it op te slaan. Tink derom dat it symboal frekwinsje "a", "b", "c" и "D" is lyk oan 4, 2, 1, 1 respektivelik. Litte wy ús besykje foar te stellen "aabacdab" yn minder bits, profitearje fan it feit dat "nei" komt faker foar as "B"en "B" komt faker foar as "c" и "D". Wy sille begjinne mei kodearring "nei" mei ien bit gelyk oan 0, "B" wy sille in twa-bit koade tawize oan 11, en mei trije bits 100 en 011 sille wy kodearje "c" и "D".
As gefolch krije wy:
a
0
b
11
c
100
d
011
De line dus "aabacdab" wy sille koade it as 00110100011011 (0|0|11|0|100|011|0|11)mei help fan boppesteande koades. It wichtichste probleem sil lykwols wêze yn dekodearring. As wy besykje de tekenrige te ûntsiferjen 00110100011011, sille wy in dûbelsinnich resultaat krije, om't it kin wurde fertsjintwurdige as:
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
...
en sa fierder.
Om dizze dûbelsinnigens te foarkommen, moatte wy derfoar soargje dat ús kodearring foldocht oan in konsept lykas foarheaksel regel, wat op syn beurt ymplisearret dat de koades kinne wurde dekodearre op mar ien unike wize. De prefix-regel soarget derfoar dat gjin koade in foarheaksel is fan in oar. Mei koade bedoele wy de bits dy't brûkt wurde om in bepaald karakter te fertsjintwurdigjen. Yn it boppesteande foarbyld 0 is in foarheaksel 011, dy't yn striid is mei de prefix-regel. Dus, as ús koades foldogge oan de prefix regel, dan kinne wy unambiguous dekodearje (en oarsom).
Litte wy it hjirboppe foarbyld opnij besjen. Dizze kear sille wy tawize foar symboalen "a", "b", "c" и "D" koades dy't foldogge oan de prefix regel.
a
0
b
10
c
110
d
111
Mei help fan dizze kodearring, de tekenrige "aabacdab" wurdt kodearre as 00100100011010 (0|0|10|0|100|011|0|10). En hjir 00100100011010 wy kinne no unambiguous ûntsiferje en weromgean nei ús oarspronklike tekenrige "aabacdab".
Huffman kodearring
No't wy kodearring fan fariabele lingte en de prefixregel begripe, litte wy prate oer Huffman-kodearring.
De metoade is basearre op it meitsjen fan binêre beammen. Dêryn kin in knooppunt definityf as yntern wêze. Yn it earstoan wurde alle knooppunten beskôge as blêden (einen), dy't it symboal sels en har gewicht (dat is de frekwinsje fan foarkommen) fertsjintwurdigje. De ynterne knopen befetsje it gewicht fan it karakter en ferwize nei twa opfolgjende knopen. By algemiene oerienkomst, bytsje "0" fertsjintwurdiget folgjende de linker tûke, en "1" - rjochts. Yn folle beam N blêden en N-1 ynterne knopen. It is oan te rieden dat by it bouwen fan in Huffman-beam net brûkte symboalen wurde wegere om koades fan optimale lingte te krijen.
Wy sille in prioriteitswachtrige brûke om in Huffman-beam te bouwen, wêrby't it knooppunt mei de leechste frekwinsje de heechste prioriteit wurdt jûn. De boustappen wurde hjirûnder beskreaun:
- Meitsje in blêdknooppunt foar elk symboal en foegje se ta oan 'e prioriteitswachtrige.
- Wylst d'r mear dan ien blêd yn 'e wachtrige is, doch it folgjende:
- Fuortsmite de twa heechste prioriteit (leechste frekwinsje) knopen út de wachtrige;
- Meitsje in nij ynterne knooppunt, wêrby't dizze twa knooppunten de opfolgers sille wêze, en de frekwinsje fan foarkommen sil gelyk wêze oan 'e som fan' e frekwinsjes fan dizze twa knooppunten.
- Foegje in nij knooppunt ta oan de prioriteitswachtrige.
- De ienige oerbleaune knooppunt sil de woartel knooppunt wêze, en dit sil de bou fan 'e beam foltôgje.
Litte wy ús foarstelle dat wy wat tekst hawwe dy't allinich út karakters bestiet "a", "b", "c", "d" и "en", en harren foarkommende frekwinsjes binne respektivelik 15, 7, 6, 6 en 5. Hjirûnder binne yllustraasjes dy't de stappen fan it algoritme wjerspegelje.
It paad fan 'e woartel nei in blêdknooppunt sil de optimale foarheakselkoade opslaan (ek wol in Huffman-koade neamd) dy't oerienkomt mei it karakter ferbûn mei dat blêdknooppunt.
Huffman beam
Hjirûnder fine jo in ymplemintaasje fan it Huffman-kompresjealgoritme yn C ++ en 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);
}
}Tink derom: it ûnthâld brûkt troch de ynfier tekenrige is 47 * 8 = 376 bits en de kodearre tekenrige nimt mar 194 bits i.e. gegevens wurde komprimearre troch likernôch 48%. Yn it boppesteande C ++ programma brûke wy de tekenrige klasse om in kodearre tekenrige op te slaan om it programma lêsber te meitsjen.
Omdat effisjinte prioriteit wachtrige gegevens struktueren fereaskje per ynfoegje O(log(N)) tiid, en yn in folsleine binêre beam mei N blêden oanwêzich 2N-1 knooppunten, en de Huffman-beam is in folsleine binêre beam, dan wurket it algoritme yn O(Nlog(N)) tiid, wêr N - Karakters.
Boarne:
Boarne: www.habr.com