哈夫曼树压缩代码 2010-10-24 [分类: 编程 ] [ 标签: 算法 ] 代码如下,并不复杂,完全按照哈夫曼树的形式实现的,对这个源代码的压缩比率在75%左右,还有个小问题,注释略: #include <iostream> #include <fstream> #include <vector> #include <string> #include <algorithm> struct THalfNode { char c; int weight; struct THalfNode *left; struct THalfNode *right; THalfNode(); static FreeTree(THalfNode *root); static DisplayTree(THalfNode *root, int ident, std::ostream& ostrm); }; struct THalfTab { char c; std::string code; bool operator == (char cmp); bool operator == (const std::string& s); }; THalfNode * CreateHalfMan(std::istream &ins); std::vector<THalfNode *>::iterator GetMinHalf(std::vector<THalfNode *>& halfNodes); void CreateHalfTable(THalfNode *root, std::vector<THalfTab>& halfTab, std::string code); void EncodeFile(std::istream& inf, std::ostream& ouf, std::vector<THalfTab>& halfTab); std::string GetCode(std::vector<THalfTab>& halfTab, char c); void DecodeFile(std::istream& halfFileI, std::ostream& onf, std::vector<THalfTab>& halfTab); char GetChar(std::vector<THalfTab>& halfTab, const std::string& s); unsigned char bitone[8] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}; unsigned char bitzero[8] = {0xFE, 0xFD, 0xFB, 0xF7, 0xEF, 0xDF, 0xBF, 0x7F}; /////////////////// bool THalfTab::operator == (char cmp) { return this->c == cmp; } bool THalfTab::operator == (const std::string& s) { return this->code == s; } THalfNode::THalfNode() :c(0), left(NULL), right(NULL), weight(1) {} THalfNode::FreeTree(THalfNode *root) { if (root) { FreeTree(root->left); FreeTree(root->right); delete root; } } THalfNode::DisplayTree(THalfNode *root, int ident, std::ostream& ostrm) { if (root) { DisplayTree(root->left, ident + 1, ostrm); int i; for(i = 0; i < ident; ++i) ostrm << "\t"; ostrm << root->c << " * " << root->weight << "\n"; DisplayTree(root->right, ident + 1, ostrm); } } std::string GetCode(std::vector<THalfTab>& halfTab, char c) { std::vector<THalfTab>::iterator it; it = std::find(halfTab.begin(), halfTab.end(), c); if (it != halfTab.end()) return it->code; else return ""; } int main() { std::ifstream inf("hafman.cpp", std::ios_base::binary); std::ofstream log("log.txt"); std::vector<THalfTab> halfTab; std::ofstream halfFileO("halfFile", std::ios_base::binary); std::ifstream halfFileI; std::ofstream onf("halfman.txt", std::ios_base::binary); THalfNode *root = CreateHalfMan(inf); THalfNode::DisplayTree(root, 0, log); CreateHalfTable(root, halfTab, ""); int i; for(i = 0; i < halfTab.size(); ++i) Â Â std::cout << i << "\t" << halfTab[i].c << "\t" << halfTab[i].code << "\n"; THalfNode::FreeTree(root); inf.close(); std::ifstream inf2("hafman.cpp", std::ios_base::binary); EncodeFile(inf2, halfFileO, halfTab); halfFileO.close(); halfFileI.open("halfFile", std::ios_base::binary); DecodeFile(halfFileI, onf, halfTab); } THalfNode * CreateHalfMan(std::istream &ins) { if (!ins.good()) return NULL; //Get all the nodes std::vector<THalfNode *> halfNodes; std::vector<THalfNode *>::iterator halfIt; THalfNode *p = new THalfNode; p->weight = 1; ins.read(&(p->c), 1); while(ins.good()) { for(halfIt = halfNodes.begin(); halfIt != halfNodes.end(); ++halfIt) if ((*halfIt)->c == p->c) break; if (halfIt == halfNodes.end()) halfNodes.push_back(p); else { ++((*halfIt)->weight); delete p; } p = new THalfNode; p->weight = 1; ins.read(&(p->c), 1); } //Create HalfMan std::vector<THalfNode *>::iterator min1, min2; while(halfNodes.size() > 1) { THalfNode *n = new THalfNode; n->c = 4; min1 = GetMinHalf(halfNodes); n->weight = (*min1)->weight; n->left = *min1; halfNodes.erase(min1, min1 + 1); min2 = GetMinHalf(halfNodes); n->weight += (*min2)->weight; n->right = *min2; halfNodes.erase(min2, min2 + 1); Â Â halfNodes.push_back(n); } return *halfNodes.begin(); } std::vector<THalfNode *>::iterator GetMinHalf(std::vector<THalfNode *>& halfNodes) { std::vector<THalfNode *>::iterator halfIt, halfMin = halfNodes.begin(); for(halfIt = halfNodes.begin(); halfIt != halfNodes.end(); ++halfIt) { if ((*halfIt)->weight < (*halfMin)->weight) halfMin = halfIt; } return halfMin; } void CreateHalfTable(THalfNode *root, std::vector<THalfTab>& halfTab, std::string code) { THalfTab ht; if (root->left != NULL) CreateHalfTable(root->left, halfTab, code + "0"); if (root->right != NULL) CreateHalfTable(root->right, halfTab, code + "1"); if (root->left == NULL && root->right == NULL)//Leave node { ht.c = root->c; ht.code = code; halfTab.push_back(ht); } } void EncodeFile(std::istream& inf, std::ostream& ouf, std::vector<THalfTab>& halfTab) { if (!inf.good()) return; if (!ouf.good()) return; char c; unsigned char buf = 0; int p = 0; std::string code; inf.read(&(c), 1); while(inf.good()) { code = GetCode(halfTab, c); int i; for(i = 0; i < code.size(); ++i) { if (p == 8) { p = 0; ouf.write((char *)&buf, 1); buf = 0; } if (code[i] == '1') buf = buf | bitone[p]; else if (code[i] == '0') buf = buf & bitzero[p]; else return; ++p; } inf.read(&(c), 1); } ouf.write((char *)&buf, 1);//如果buf没有填满,那么存在问题 } void DecodeFile(std::istream& halfFileI, std::ostream& onf, std::vector<THalfTab>& halfTab) { unsigned char buf; char c; std::string code; int i; halfFileI.read((char *)&buf, 1); while(halfFileI.good()) { for(i = 0; i < 8; ++i) { if ((buf & bitone[i]) > 0) code = code + "1"; else code = code + "0"; c = GetChar(halfTab, code); if (c != 0) { code = ""; onf.write(&c, 1); } } halfFileI.read((char *)&buf, 1); } } char GetChar(std::vector<THalfTab>& halfTab, const std::string& s) { std::vector<THalfTab>::iterator it; it = std::find(halfTab.begin(), halfTab.end(), s); if (it != halfTab.end()) return it->c; else return 0; } [原文在百度空间已经关闭] 标签集合/Tag clouds C++ Symbain 轻松汇编 算法 论文学习 资治通鉴 Delphi 编程之美 Poco MFC Linux IFC 知乎 汇编 数据分析 交叉编译 poco j2me android XML Java DTD 飞信 零宽断言 诺基亚 联系人 编程 真值表 池西木 正则表达式 多线程 命令行 优化 stream configure cmake VIM UiAutomator TDD Symbian Sqlite SourceInsight Python MPAndroidChart Kotlin Flutter Dokka Chatgpt