|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
最近几天在搞Huffman coding。现在给出两个版本的解决方案都是使用了优先队列。输入数据的运算量是N，Huffman树的运算量是RlogR。第一个版本有decode，但是decode需要根据writeTrie的结果来建立树，进而decode。采用preorder(前序)遍历。
（一）由Java翻译成的C++，但是有所修改（vc6.0亲测可行）
Huffman.cpp#include <iostream>
#include <string>
#include "GPQ.h"
const int R = 256;
class Huffman
{
class Node
{
public:
const char _ch;
const int _freq;
Node *_left, *_right;
Node(char ch, int freq, Node* left, Node* right)
: _ch(ch), _freq(freq), _left(left), _right(right)
{}
bool isLeaf() { return !_left && !_right; }
bool compareTo(Node *that) { return _freq > that->_freq; }
};
struct buf
{
buf(): _id(-1) {}
int index() { _id++; return _id; }
int _id;
}id;
public:
void expand(std::string& trie, std::string& s, int N)
{
id._id = -1;
Node *root = readTrie(trie);
id._id = -1;
for (int i = 0; i < N; ++i)
{
Node *x = root;
while (!(x->isLeaf()))
{
if(s[id.index()] == '0')
x = x->_left;
else x = x->_right;
}
std::cout << x->_ch;
}
}
void writeTrie(Node* x)
{
if(x->isLeaf())
{
std::cout << 1;
std::cout << x->_ch;
return;
}
std::cout << 0;
writeTrie(x->_left);
writeTrie(x->_right);
}
Node* readTrie(std::string& trie)
{
if(trie[id.index()] == '1')
{
char c = trie[id.index()];
Node *fresh = new Node(c, 0, 0, 0);
return fresh;
}
Node *x = readTrie(trie);
Node *y = readTrie(trie);
Node *fresh = new Node('\0', 0, x, y);
return fresh;
}
void compress(std::string& s)
{
// Tabulate frequency counts.
int freq[R] = {0};
for (int i = 0; i < s.size(); ++i)
freq[s[i]]++;
// Build Huffman code trie.
Node *root = buildTrie(freq);
std::string *st = new std::string [R];
buildCode(st, root, "");
// Print trie for decoder (recursive).
writeTrie(root);
std::cout << std::endl;
// Use Huffman code to encode input.
for (int id = 0; id < s.length(); id++)
{
std::string code = st[s[id]];
std::cout << s[id] << " ";
std::cout << code << std::endl;
}
}
private:
Node* buildTrie(int *freq)
{
GenericPQ<Node*> pq(R);
for (int i = 0; i < R; i++)
if (freq[i] > 0)
pq.insert(new Node(i, freq[i], 0, 0));
while (pq.size() > 1)
{
Node *x = pq.pop();
Node *y = pq.pop();
Node *parent = new Node('\0', x->_freq + y->_freq, x, y);
pq.insert(parent);
}
return pq.pop();
}
std::string* buildCode(Node* root)
{
std::string *st = new std::string[R];
buildCode(st, root, "");
return st;
}
void buildCode(std::string *st, Node *x, std::string s)
{
if(x->isLeaf()) { st[x->_ch] = s; return; }
buildCode(st, x->_left, s + '0');
buildCode(st, x->_right, s + '1');
}
};
int main()
{
Huffman code;
std::string sample = "ABRACADABRA!";
std::string trie = "01A001D01!1C01R1B";
std::string coder = "0111110010110100011111001010";
code.compress(sample);
code.expand(trie, coder, 12);
return 0;
}
#if !defined (GPQ_H)
#define GPQ_H
template<class T>
class GenericPQ{
private:
T *_pq; // heap-ordered complete binary tree
int _N; // in pq[1..N] with pq[0] unused
public:
GenericPQ(int capacity);
~GenericPQ();
bool isEmpty() { return _N == 0; }
void insert(T x);
int size() { return _N; }
T pop();
private:
void swim(int k);
void sink(int k);
//Compare and exchange methods for heap implementations
bool comp(int i, int j) { return _pq[i]->compareTo(_pq[j]); }
void swap(int i, int j)
{
T ex = _pq[i];
_pq[i] = _pq[j];
_pq[j] = ex;
}
};
template<class T>
GenericPQ<T>::GenericPQ(int capacity)
:_N(0)
{
_pq = new T[capacity+1];
}
template<class T>
GenericPQ<T>::~GenericPQ(void)
{
delete [] _pq;
}
/** Bottom-up reheapify (swim) implementation */
template<class T>
void GenericPQ<T>::swim(int k)
{
while (k > 1 && comp(k/2, k))
{
swap(k, k/2);
k = k/2;
}
}
template<class T>
void GenericPQ<T>::insert(T x)
{
_pq[++_N] = x;
swim(_N);
}
/** Top-down reheapify (sink) implementation **/
template<class T>
void GenericPQ<T>::sink(int k)
{
while (2*k <= _N)
{
int j = 2*k;
if (j < _N && comp(j, j+1)) j++;
if (!comp(k, j)) break;
swap(k, j);
k = j;
}
}
template<class T>
T GenericPQ<T>::pop()
{
T min = _pq[1]; // Retrieve max key from top.
swap(1, _N--); // Exchange with last item.
sink(1); // Avoid loitering.
_pq[_N+1] = 0; // Restore heap property.
return min;
}
#endif
#include <iostream>
#include <queue>
#include <map>
#include <climits> // for CHAR_BIT
#include <iterator>
#include <algorithm>
const int UniqueSymbols = 1 << CHAR_BIT;
const char* SampleString = "this is an example for huffman encoding";
typedef std::vector<bool> HuffCode;
typedef std::map<char, HuffCode> HuffCodeMap;
class INode
{
public:
const int f;
virtual ~INode() {}
protected:
INode(int f) : f(f) {}
};
class InternalNode : public INode
{
public:
INode *const left;
INode *const right;
InternalNode(INode* c0, INode* c1) : INode(c0->f + c1->f), left(c0), right(c1) {}
~InternalNode()
{
delete left;
delete right;
}
};
class LeafNode : public INode
{
public:
const char c;
LeafNode(int f, char c) : INode(f), c(c) {}
};
struct NodeCmp
{
bool operator()(const INode* lhs, const INode* rhs) const { return lhs->f > rhs->f; }
};
INode* BuildTree(const int (&frequencies)[UniqueSymbols])
{
std::priority_queue<INode*, std::vector<INode*>, NodeCmp> trees;
for (int i = 0; i < UniqueSymbols; ++i)
{
if(frequencies[i] != 0)
trees.push(new LeafNode(frequencies[i], (char)i));
}
while (trees.size() > 1)
{
INode* childR = trees.top();
trees.pop();
INode* childL = trees.top();
trees.pop();
INode* parent = new InternalNode(childR, childL);
trees.push(parent);
}
return trees.top();
}
void GenerateCodes(const INode* node, const HuffCode& prefix, HuffCodeMap& outCodes)
{
if (const LeafNode* lf = dynamic_cast<const LeafNode*>(node))
{
outCodes[lf->c] = prefix;
}
else if (const InternalNode* in = dynamic_cast<const InternalNode*>(node))
{
HuffCode leftPrefix = prefix;
leftPrefix.push_back(false);
GenerateCodes(in->left, leftPrefix, outCodes);
HuffCode rightPrefix = prefix;
rightPrefix.push_back(true);
GenerateCodes(in->right, rightPrefix, outCodes);
}
}
int main()
{
// Build frequency table
int frequencies[UniqueSymbols] = {0};
const char* ptr = SampleString;
while (*ptr != '\0')
++frequencies[*ptr++];
INode* root = BuildTree(frequencies);
HuffCodeMap codes;
GenerateCodes(root, HuffCode(), codes);
delete root;
for (HuffCodeMap::const_iterator it = codes.begin(); it != codes.end(); ++it)
{
std::cout << it->first << " ";
std::copy(it->second.begin(), it->second.end(),
std::ostream_iterator<bool>(std::cout));
std::cout << std::endl;
}
return 0;
}
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2014-2-28 22:19:33
置顶卡
千斤顶
显身卡
楼主