Alohan'ny hanombohan'ny fampianarana nomanina ho anao fandikan-teny hafa mahasoa.
Huffman coding dia algorithm famatrarana data izay mamolavola ny hevitra fototra momba ny famatrarana rakitra. Ato amin'ity lahatsoratra ity dia hiresaka momba ny fakan-doko raikitra sy miovaova ny halavany, kaody tokana azo decodable, fitsipiky ny prefix ary fananganana hazo Huffman.
Fantatsika fa ny tarehintsoratra tsirairay dia voatahiry ho filaharan'ny 0 sy 1 ary maka 8 bits. Antsoina hoe encoding halavana raikitra izany satria ny tarehin-tsoratra tsirairay dia mampiasa ny isa mitovy amin'ny bits hotehirizina.
Andeha atao hoe nomena lahatsoratra isika. Ahoana no ahafahantsika mampihena ny habaka ilaina amin'ny fitahirizana litera tokana?
Ny hevi-dehibe dia ny fiovaovan'ny halavany. Azontsika atao ny mampiasa ny hoe misy litera sasany ao amin'ny lahatsoratra miseho matetika kokoa noho ny hafa () mba hamolavola algorithm izay haneho ny filaharan'ireo endri-tsoratra mitovy amin'ny bitika kely kokoa. Amin'ny fanovΓ na ny halavany miovaova, dia asiana tarehin-tsoratra isan-karazany bits, miankina amin'ny impiry isehoany amin'ny lahatsoratra iray. Amin'ny farany, ny endri-tsoratra sasany dia mety haka 1 bit, raha ny hafa kosa mety haka 2 bit, 3 na mihoatra. Ny olana amin'ny fanamafisam-peo miovaova ny halavany dia ny decoding manaraka ny filaharana ihany.
Ahoana ny fahafantarana ny filaharan'ny bits, decode azy tsy misy dikany?
Diniho ilay tsipika "abacdab". Manana tarehin-tsoratra 8 izy io, ary rehefa manodinkodina ny halavany raikitra dia mila 64 bit ny fitahirizana azy. Mariho fa ny matetika famantarana "a", "b", "c" ΠΈ "D" mitovy amin'ny 4, 2, 1, 1. Andeha isika haka sary an-tsaina "abacdab" bitika kely kokoa, mampiasa ny zava-misy fa "to" mitranga matetika kokoa noho ny "B"ary "B" mitranga matetika kokoa noho ny "c" ΠΈ "D". Andeha isika hanomboka amin'ny coding "to" miaraka amin'ny bit mitovy amin'ny 0, "B" hanendry kaody roa-bit 11 isika, ary mampiasa telo bit 100 sy 011 dia hadika "c" ΠΈ "D".
Ho vokany, dia hahazo:
a
0
b
11
c
100
d
011
Ka ny tsipika "abacdab" ho encode ho 00110100011011 (0|0|11|0|100|011|0|11)mampiasa ny kaody etsy ambony. Na izany aza, ny olana lehibe dia ny decoding. Rehefa manandrana mamadika ny tady isika 00110100011011, mahazo valiny tsy mazava isika, satria azo aseho toy izao:
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
...
sy ny sisa.
Mba hialana amin'izany tsy mazava izany, dia tsy maintsy miantoka isika fa mahafeno ny foto-kevitra toy ny hoe ny encoding ataontsika fitsipika mialoha, izay midika kosa fa ny kaody dia tsy azo vakiana amin'ny fomba tokana ihany. Ny fitsipiky ny prefix dia miantoka fa tsy misy kaody misy tovan'ny hafa. Amin'ny kaody, ny bits ampiasaina hanehoana toetra manokana no tiana holazaina. Ao amin'ny ohatra etsy ambony 0 dia prefix 011, izay mandika ny fitsipiky ny prefix. Noho izany, raha mahafeno ny fitsipiky ny prefix ny kaodinay, dia afaka mamadika manokana (sy ny mifamadika amin'izany).
Andeha hojerentsika ny ohatra etsy ambony. Amin'ity indray mitoraka ity dia hanendry marika isika "a", "b", "c" ΠΈ "D" kaody mahafeno ny fitsipiky ny prefix.
a
0
b
10
c
110
d
111
Miaraka amin'ity encoding ity, ny string "abacdab" dia horaisina ho 00100100011010 (0|0|10|0|100|011|0|10). ary eto 00100100011010 efa ho afaka mamadika tsy misy dikany isika ary miverina amin'ny tady voalohany "abacdab".
Huffman coding
Ankehitriny isika dia efa niresaka momba ny fanaingoana ny halavany miovaova sy ny fitsipiky ny prefix, andao hiresaka momba ny fanodinkodinana Huffman.
Ny fomba dia mifototra amin'ny famoronana hazo binary. Ao anatin'izany, ny node dia mety ho farany na anatiny. Tany am-boalohany, ny nodes rehetra dia heverina ho ravina (terminal), izay maneho ny marika sy ny lanjany (izany hoe ny matetika ny fisehoan-javatra). Ny node anatiny dia misy ny lanjan'ny toetra ary manondro ireo node taranaka roa. Amin'ny fifanarahana ankapobeny, bit "0" maneho ny manaraka ny sampana havia, ary "1" - etsy ankavanana. amin'ny hazo feno N ravina ary N-1 nodes anatiny. Amporisihina fa rehefa manangana hazo Huffman dia ariana ireo marika tsy ampiasaina mba hahazoana kaody halavana tsara indrindra.
Hampiasa filaharana laharam-pahamehana izahay hananganana hazo Huffman, izay homena ny laharam-pahamehana ambony indrindra ny node manana matetika ambany indrindra. Ny dingana fanorenana dia voalaza eto ambany:
- Mamorona node ravina ho an'ny toetra tsirairay ary ampio amin'ny filaharana laharam-pahamehana.
- Raha misy takelaka mihoatra ny iray ao amin'ny filaharana dia ataovy izao manaraka izao:
- Esory amin'ny filaharana ireo node roa manana ny laharam-pahamehana ambony indrindra (frequency ambany indrindra);
- Mamorona node anatiny vaovao, izay ho ankizy ireo node roa ireo, ary ny fatran'ny fisehoan-javatra dia hitovy amin'ny fitambaran'ny fatran'ireo node roa ireo.
- Manampia node vaovao amin'ny filaharana laharam-pahamehana.
- Ny fotony sisa tavela, ary izany no hamita ny fanorenana ny hazo.
Alaivo sary an-tsaina hoe manana lahatsoratra tsy misy tarehin-tsoratra fotsiny isika "a", "b", "c", "d" ΠΈ "sy", ary 15, 7, 6, 6, ary 5, tsirairay avy, ny fahitan'izy ireo. Ireto ambany ireto ny sary mampiseho ny dingan'ny algorithm.
Ny lalana avy amin'ny fakany mankany amin'ny node farany dia hitahiry ny kaody prefix tsara indrindra (fantatra amin'ny anarana hoe kaody Huffman) mifanaraka amin'ny toetra mifandray amin'io node farany io.
Hazo Huffman
Ho hitanao eto ambany ny fampiharana ny algorithm compression Huffman amin'ny C++ sy 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);
}
}Fanamarihana: ny fitadidiana ampiasain'ny tady fampidirana dia 47 * 8 = 376 bits ary ny tady voakodia dia 194 bit fotsiny izany hoe. Ny angon-drakitra dia voatsindry eo amin'ny 48%. Ao amin'ny programa C ++ etsy ambony, dia mampiasa ny kilasin'ny string izahay mba hitahiry ny tady voakodia mba hahatonga ny programa ho azo vakina.
Satria ny rafitra angon-drakitra filaharana laharam-pahamehana mahomby dia mitaky isaky ny fampidirana O(log(N)) fotoana, fa ao anaty hazo mimari-droa feno miaraka amin'ny N ravina misy 2N-1 nodes, ary ny hazo Huffman dia hazo mimari-droa feno, avy eo dia miditra ny algorithm O(Nlog(N)) fotoana, aiza N - Karazana.
loharanom-baovao:
Source: www.habr.com