Cyn dechrau'r cwrs paratoi i chi gyfieithiad o ddeunydd defnyddiol arall.
Mae codio Huffman yn algorithm cywasgu data sy'n llunio'r syniad sylfaenol o gywasgu ffeiliau. Yn yr erthygl hon, byddwn yn siarad am amgodio hyd sefydlog ac amrywiol, codau datgodadwy unigryw, rheolau rhagddodiad, ac adeiladu coeden Huffman.
Gwyddom fod pob nod yn cael ei storio fel dilyniant o 0 ac 1 ac yn cymryd 8 did. Gelwir hyn yn amgodio hyd sefydlog oherwydd bod pob nod yn defnyddio'r un nifer sefydlog o ddarnau i'w storio.
Gadewch i ni ddweud ein bod yn cael testun. Sut gallwn ni leihau faint o le sydd ei angen i storio un cymeriad?
Y prif syniad yw amgodio hyd amrywiol. Gallwn ddefnyddio'r ffaith bod rhai cymeriadau yn y testun yn digwydd yn amlach nag eraill () datblygu algorithm a fydd yn cynrychioli'r un dilyniant o nodau mewn llai o ddarnau. Mewn amgodio hyd amrywiol, rydyn ni'n neilltuo nifer amrywiol o ddarnau i nodau, yn dibynnu ar ba mor aml maen nhw'n ymddangos mewn testun penodol. Yn y pen draw, gall rhai nodau gymryd cyn lleied ag 1 did, tra gall eraill gymryd 2 did, 3 neu fwy. Dim ond datgodio dilynol y dilyniant yw'r broblem gydag amgodio hyd amrywiol.
Sut, gan wybod y dilyniant o ddarnau, ei ddadgodio'n ddiamwys?
Ystyriwch y llinell "abacdab". Mae ganddo 8 nod, ac wrth amgodio hyd sefydlog, bydd angen 64 did i'w storio. Sylwch fod yr amlder symbol "a", "b", "c" ΠΈ "D" yn hafal i 4, 2, 1, 1 yn y drefn honno. Gadewch i ni geisio dychmygu "abacdab" llai o ddarnau, gan ddefnyddio'r ffaith bod "i" yn digwydd yn amlach na "B"Ac "B" yn digwydd yn amlach na "c" ΠΈ "D". Gadewch i ni ddechrau trwy godio "i" gydag un did yn hafal i 0, "B" byddwn yn neilltuo cod dau-did 11, a chan ddefnyddio tri did 100 a 011 byddwn yn amgodio "c" ΠΈ "D".
O ganlyniad, byddwn yn cael:
a
0
b
11
c
100
d
011
Felly y llinell "abacdab" byddwn yn amgodio fel 00110100011011 (0|0|11|0|100|011|0|11)gan ddefnyddio'r codau uchod. Fodd bynnag, y brif broblem fydd dadgodio. Pan geisiwn ddadgodio'r llinyn 00110100011011, rydym yn cael canlyniad amwys, oherwydd gellir ei gynrychioli fel:
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
...
ac ati
Er mwyn osgoi'r amwysedd hwn, rhaid inni sicrhau bod ein hamgodio yn bodloni cysyniad o'r fath fel rheol rhagddodiad, sydd yn ei dro yn awgrymu mai dim ond mewn un ffordd unigryw y gellir dadgodio'r codau. Mae rheol y rhagddodiad yn sicrhau nad oes unrhyw god yn rhagddodiad o un arall. Wrth god, rydym yn golygu'r darnau a ddefnyddir i gynrychioli nod penodol. Yn yr enghraifft uchod 0 yn rhagddodiad 011, sy'n torri rheol y rhagddodiad. Felly, os yw ein codau'n bodloni'r rheol rhagddodiad, yna gallwn ddadgodio'n unigryw (ac i'r gwrthwyneb).
Gadewch i ni ailedrych ar yr enghraifft uchod. Y tro hwn byddwn yn neilltuo ar gyfer symbolau "a", "b", "c" ΠΈ "D" codau sy'n bodloni'r rheol rhagddodiad.
a
0
b
10
c
110
d
111
Gyda'r amgodio hwn, y llinyn "abacdab" yn cael ei amgodio fel 00100100011010 (0|0|10|0|100|011|0|10). Ond mae'r 00100100011010 byddwn eisoes yn gallu dadgodio'n ddiamwys a dychwelyd i'n llinyn gwreiddiol "abacdab".
Huffman codio
Nawr ein bod wedi delio ag amgodio hyd amrywiol a'r rheol rhagddodiad, gadewch i ni siarad am amgodio Huffman.
Mae'r dull yn seiliedig ar greu coed deuaidd. Ynddo, gall y nod fod naill ai'n derfynol neu'n fewnol. I ddechrau, mae pob nod yn cael ei ystyried yn ddail (terfynellau), sy'n cynrychioli'r symbol ei hun a'i bwysau (hynny yw, amlder y digwyddiad). Mae'r nodau mewnol yn cynnwys pwysau'r cymeriad ac yn cyfeirio at ddau nod disgynnol. Trwy gytundeb cyffredinol, did Β«0Β» cynrychioli dilyn y gangen chwith, a Β«1Β» - ar y dde. mewn coeden lawn N dail a N-1 nodau mewnol. Argymhellir bod symbolau nas defnyddiwyd yn cael eu taflu i gael y codau hyd gorau posibl wrth adeiladu coeden Huffman.
Byddwn yn defnyddio ciw Γ’ blaenoriaeth i adeiladu coeden Huffman, lle bydd y nod Γ’'r amlder isaf yn cael y flaenoriaeth uchaf. Disgrifir y camau adeiladu isod:
- Creu nod dail ar gyfer pob cymeriad a'u hychwanegu at y ciw blaenoriaeth.
- Tra bod mwy nag un ddalen yn y ciw, gwnewch y canlynol:
- Tynnwch y ddau nod gyda'r flaenoriaeth uchaf (amledd isaf) o'r ciw;
- Creu nod mewnol newydd, lle bydd y ddau nod hyn yn blant, a bydd amlder y digwyddiad yn hafal i swm amleddau'r ddau nod hyn.
- Ychwanegu nod newydd i'r ciw blaenoriaeth.
- Yr unig nod sy'n weddill fydd y gwreiddyn, a bydd hyn yn cwblhau adeiladu'r goeden.
Dychmygwch fod gennym ni rywfaint o destun sy'n cynnwys cymeriadau yn unig "a", "b", "c", "d" ΠΈ "a", a'u hamleddau digwydd yw 15, 7, 6, 6, a 5, yn y drefn honno. Isod mae darluniau sy'n adlewyrchu camau'r algorithm.
Bydd llwybr o'r gwraidd i unrhyw nod diwedd yn storio'r cod rhagddodiad gorau posibl (a elwir hefyd yn god Huffman) sy'n cyfateb i'r nod sy'n gysylltiedig Γ’'r nod diwedd hwnnw.
coeden Huffman
Isod fe welwch weithrediad algorithm cywasgu Huffman yn C ++ a 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);
}
}Nodyn: y cof a ddefnyddir gan y llinyn mewnbwn yw 47 * 8 = 376 did a dim ond 194 did yw'r llinyn wedi'i amgodio h.y. data yn cael ei gywasgu gan tua 48%. Yn y rhaglen C++ uchod, rydym yn defnyddio'r dosbarth llinynnol i storio'r llinyn wedi'i amgodio i wneud y rhaglen yn ddarllenadwy.
Oherwydd bod angen strwythurau data ciw blaenoriaeth effeithlon fesul mewnosodiad O(log(N)) amser, ond mewn coeden deuaidd gyflawn gyda N dail yn bresennol 2N-1 nodau, ac mae'r goeden Huffman yn goeden ddeuaidd gyflawn, yna mae'r algorithm yn rhedeg i mewn O(Nlog(N)) amser, lle N - Cymeriadau.
Ffynonellau:
Ffynhonnell: hab.com