Download code

Jump to: navigation, search

Back to Huffman_coding_(C_Plus_Plus)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

huffman.cc

 1 /* The authors of this work have released all rights to it and placed it
 2 in the public domain under the Creative Commons CC0 1.0 waiver
 3 (http://creativecommons.org/publicdomain/zero/1.0/).
 4 
 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 
13 Retrieved from: http://en.literateprograms.org/Huffman_coding_(C_Plus_Plus)?oldid=16057
14 */
15 
16 #include "huffman.h"
17 #include <map>
18 #include <iostream>
19 #include <ostream>
20 #include <algorithm>
21 #include <iterator>
22 #include <string>
23 
24 std::ostream& operator<<(std::ostream& os, std::vector<bool> vec)
25 {
26   std::copy(vec.begin(), vec.end(), std::ostream_iterator<bool>(os, ""));
27   return os;
28 }
29 
30 int main()
31 {
32   std::map<char, double> frequencies;
33   frequencies['e'] = 0.124167;
34   frequencies['a'] = 0.0820011;
35   frequencies['t'] = 0.0969225;
36   frequencies['i'] = 0.0768052;
37   frequencies['n'] = 0.0764055;
38   frequencies['o'] = 0.0714095;
39   frequencies['s'] = 0.0706768;
40   frequencies['r'] = 0.0668132;
41   frequencies['l'] = 0.0448308;
42   frequencies['d'] = 0.0363709;
43   frequencies['h'] = 0.0350386;
44   frequencies['c'] = 0.0344391;
45   frequencies['u'] = 0.028777;
46   frequencies['m'] = 0.0281775;
47   frequencies['f'] = 0.0235145;
48   frequencies['p'] = 0.0203171;
49   frequencies['y'] = 0.0189182;
50   frequencies['g'] = 0.0181188;
51   frequencies['w'] = 0.0135225;
52   frequencies['v'] = 0.0124567;
53   frequencies['b'] = 0.0106581;
54   frequencies['k'] = 0.00393019;
55   frequencies['x'] = 0.00219824;
56   frequencies['j'] = 0.0019984;
57   frequencies['q'] = 0.0009325;
58   frequencies['z'] = 0.000599;
59   Hufftree<char, double> hufftree(frequencies.begin(), frequencies.end());
60   for (char ch = 'a'; ch <= 'z'; ++ch)
61   {
62     std::cout << ch << ": " << hufftree.encode(ch) << "\n";
63   }
64   std::string source = "literateprogramming";
65   std::cout << source << "\n";
66 
67   std::vector<bool> encoded = hufftree.encode(source.begin(), source.end());
68   std::cout << encoded << "\n";
69 
70   std::string destination;
71   hufftree.decode(encoded, std::back_inserter(destination));
72   std::cout << destination << "\n";
73 }


hijacker
hijacker
hijacker
hijacker

huffman.h

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Huffman_coding_(C_Plus_Plus)?oldid=16057
 14 */
 15 
 16 #ifndef HUFFMAN_H_INC
 17 #define HUFFMAN_H_INC
 18 
 19 #include <vector>
 20 #include <map>
 21 #include <queue>
 22 
 23 template<typename DataType, typename Frequency> class Hufftree
 24 {
 25 public:
 26     template<typename InputIterator>
 27      Hufftree(InputIterator begin, InputIterator end);
 28 
 29   ~Hufftree() { delete tree; }
 30   template<typename InputIterator>
 31    std::vector<bool> encode(InputIterator begin, InputIterator end);
 32 
 33   std::vector<bool> encode(DataType const& value)
 34   {
 35     return encoding[value];
 36   }
 37   template<typename OutputIterator>
 38    void decode(std::vector<bool> const& v, OutputIterator iter);
 39 
 40 private:
 41   class Node;
 42   Node* tree;
 43 
 44   typedef std::map<DataType, std::vector<bool> > encodemap;
 45   encodemap encoding;
 46   class NodeOrder;
 47 
 48 };
 49 
 50 template<typename DataType, typename Frequency>
 51 struct Hufftree<DataType, Frequency>::Node
 52 {
 53   Frequency frequency;
 54   Node* leftChild;
 55   union
 56   {
 57     Node* rightChild; // if leftChild != 0
 58     DataType* data;  // if leftChild == 0
 59   };
 60 
 61   Node(Frequency f, DataType d):
 62     frequency(f),
 63     leftChild(0),
 64     data(new DataType(d))
 65   {
 66   }
 67   Node(Node* left, Node* right):
 68     frequency(left->frequency + right->frequency),
 69     leftChild(left),
 70     rightChild(right)
 71   {
 72   }
 73   ~Node()
 74   {
 75     if (leftChild)
 76     {
 77       delete leftChild;
 78       delete rightChild;
 79     }
 80     else
 81     {
 82       delete data;
 83     }
 84   }
 85   void fill(std::map<DataType, std::vector<bool> >& encoding,
 86             std::vector<bool>& prefix)
 87   {
 88     if (leftChild)
 89     {
 90       prefix.push_back(0);
 91       leftChild->fill(encoding, prefix);
 92       prefix.back() = 1;
 93       rightChild->fill(encoding, prefix);
 94       prefix.pop_back();
 95     }
 96     else
 97       encoding[*data] = prefix;
 98   }
 99 };
100 template<typename DataType, typename Frequency>
101  template<typename InputIterator>
102  Hufftree<DataType, Frequency>::Hufftree(InputIterator begin,
103                                          InputIterator end):
104    tree(0)
105 {
106   std::priority_queue<Node*, std::vector<Node*>, NodeOrder> pqueue;
107   while (begin != end)
108   {
109     Node* dataNode = new Node(begin->second, begin->first);
110     pqueue.push(dataNode);
111     ++begin;
112   }
113   while (!pqueue.empty())
114   {
115     Node* top = pqueue.top();
116     pqueue.pop();
117     if (pqueue.empty())
118     {
119       tree = top;
120     }
121     else
122     {
123       Node* top2 = pqueue.top();
124       pqueue.pop();
125       pqueue.push(new Node(top, top2));
126     }
127   }
128   std::vector<bool> bitvec;
129   tree->fill(encoding, bitvec);
130 }
131 template<typename DataType, typename Frequency>
132 struct Hufftree<DataType, Frequency>::NodeOrder
133 {
134   bool operator()(Node* a, Node* b)
135   {
136     if (b->frequency < a->frequency)
137       return true;
138     if (a->frequency < b->frequency)
139       return false;
140     if (!a->leftChild && b->leftChild)
141       return true;
142     if (a->leftChild && !b->leftChild)
143       return false;
144     if (a->leftChild && b->leftChild)
145     {
146       if ((*this)(a->leftChild, b->leftChild))
147         return true;
148       if ((*this)(b->leftChild, a->leftChild))
149         return false;
150       return (*this)(a->rightChild, b->rightChild);
151     }
152     return *(a->data) < *(b->data);
153   }
154 };
155 template<typename DataType, typename Frequency>
156  template<typename InputIterator>
157  std::vector<bool> Hufftree<DataType, Frequency>::encode(InputIterator begin,
158                                                          InputIterator end)
159 {
160   std::vector<bool> result;
161   while (begin != end)
162   {
163     typename encodemap::iterator i = encoding.find(*begin);
164     result.insert(result.end(), i->second.begin(), i->second.end());
165     ++begin;
166   }
167   return result;
168 }
169 template<typename DataType, typename Frequency>
170  template<typename OutputIterator>
171  void Hufftree<DataType, Frequency>::decode(std::vector<bool> const& v,
172                                             OutputIterator iter)
173 {
174   Node* node = tree;
175   for (std::vector<bool>::const_iterator i = v.begin(); i != v.end(); ++i)
176   {
177     node = *i? node->rightChild : node->leftChild;
178     if (!node -> leftChild)
179     {
180       *iter++ = *(node->data);
181       node = tree;
182     }
183   }
184 }
185 
186 #endif
187 


hijacker
hijacker
hijacker
hijacker