浙江财经大学
信息管理与工程学院

哈夫曼编码

本文由 Ocrosoft 于 2016-12-23 0:47:37 发表

排序不稳定,导致编码与手动编码不一定一致(哈夫曼编码不唯一)

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define rep(a,v,b) for(int a=v;a<b;a++)
#define repe(a,v,b) for(int a=v;a<=b;a++)
#define pre(a,v,b) for(int a=v;a>b;a--)
#define pree(a,v,b) for(int a=v;a>=b;a--)
#define lowbit(x) x&-x
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 27;
const int MOD = 1000000007;
int gcd(int a, int b)
{
 if (!b)return a;
 return gcd(b, a%b);
}
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约,成为马猴烧酒吧 (◕‿‿◕)*/
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
using namespace std;
class binary_tree
{
public:
 int first;
 char second;
 string codec;
 binary_tree *parent, *leftChild, *rightChild;
public:
 bool greater(const binary_tree* other)const { return first > other->first; }
 binary_tree() { second = '?'; parent = leftChild = rightChild = nullptr; codec = ""; }
 binary_tree(int first, char second) { this->first = first; this->second = second; parent = leftChild = rightChild = nullptr; codec = ""; }
 binary_tree(int first, binary_tree* leftChild, binary_tree* rightChild) { this->first = first; this->leftChild = leftChild; this->rightChild = rightChild; codec = ""; }
};
class PointerComparer
{
public:
 PointerComparer() {}
 bool operator ()(const binary_tree* bt1, const binary_tree* bt2)const { return bt1->greater(bt2); }
};
map<char, int> mp;
priority_queue<binary_tree*, vector<binary_tree*>, PointerComparer> q;
map<char, string> codecs;
string s;
binary_tree *root;
bool debug = false;
binary_tree* buildTree(string s)
{
 /*创建二叉树*/
 for (string::iterator it = s.begin(); it != s.end(); it++)
 !mp.count(*it) ? mp[*it] = 1 : mp[*it]++;
 for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++)
 {
 q.push(new binary_tree(it->second, it->first));
 if (debug)cout << it->first << "\t" << it->second << endl;
 }
 while (q.size() != 1)
 {
 binary_tree *x = q.top(); q.pop();
 binary_tree *y = q.top(); q.pop();
 q.push(new binary_tree(x->first + y->first, x, y));
 }
 if (debug)cout << "-----------------------------" << endl;
 return q.top();
}
void codec(binary_tree *root)
{
 /*生成字符编码*/
 if (root->leftChild != nullptr)
 {
 root->leftChild->codec = root->codec + "0";
 codec(root->leftChild);
 }
 if (root->rightChild != nullptr)
 {
 root->rightChild->codec = root->codec + "1";
 codec(root->rightChild);
 }
 if (root->leftChild == nullptr&&root->rightChild == nullptr)
 {
 codecs[root->second] = root->codec;
 if (debug)cout << root->second << "\t" << root->codec << endl;
 }
}
string encrypt(string s)
{
 /*编码*/
 string res = "";
 for (string::iterator it = s.begin(); it != s.end(); it++)
 res += codecs[*it];
 return res;
}
string decrypt(binary_tree* root, string s)
{
 string ret = "";
 binary_tree* p = root;
 for (string::iterator it = s.begin(); it != s.end();)
 {
 if (*it++ == '0')
 {
 p = ((p->leftChild) ? p : root)->leftChild;
 if (!(p->leftChild))ret += p->second;
 }
 else
 {
 p = ((p->rightChild) ? p : root)->rightChild;
 if (!(p->rightChild))ret += p->second;
 }
 }
 return ret;
}
int main()
{
 /*
 速度测试
 freopen("in.txt", "r", stdin);
 freopen("out.txt", "w", stdout);
 auto clockS = clock();
 cin >> s;
 codec(buildTree(s));
 cout << encrypt(s) << endl;
 auto clockE = clock();
 cout << clockE - clockS << endl;
 结果:一百万字符(1MB),48s
 */
 string op;
 while (cin >> op)
 {
 if (op == "/se") { cin >> s; root = buildTree(s); codec(root); cout << "Finished." << endl; break; }
 else if (op == "?debug")cout << "调试模式:" << (debug ? "开启" : "关闭") << endl;
 else if (op == "/debug") { cin >> op; debug = op == "on" ? 1 : 0; }
 else if (op == "/ex") { return 0; }
 else cout << "/se string\t\t以种子进行初始化\n?debug\t\t\t是否为调试模式\n/debug on/off\t\t开启或关闭调试模式\n/ex\t\t\t退出" << endl;
 }
 while (cin >> op)
 {
 if (op == "/de") { cin >> s; cout << decrypt(root, s) << endl; }
 else if (op == "/en") { cin >> s; cout << encrypt(s) << endl; }
 else if (op == "/ex") { return 0; }
 else cout << "/de string\t\t解码\n/en string\t\t编码\n/ex\t\t\t退出" << endl;
 }
 return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » 哈夫曼编码

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址