C++如何实现哈夫曼树对文件压缩、加密功能-创新互联
这篇文章主要介绍了C++如何实现哈夫曼树对文件压缩、加密功能,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
公司主营业务:成都网站设计、成都做网站、移动网站开发等业务。帮助企业客户真正实现互联网宣传,提高企业的竞争能力。创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化,感谢他们对我们的高要求,感谢他们从不同领域给我们带来的挑战,让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联推出秦都免费做网站回馈大家。在以前写LZW压缩算法的时候,遇到很多难受的问题,基本上都在哈夫曼编码中解决了,虽然写这代码很费神,但还是把代码完整的码出来了,毕竟哈夫曼这个思想确实很牛逼。哈夫曼树很巧妙的解决了当时我在LZW序列化的时候想解决的问题,就是压缩后文本的分割。比如用lzw编码abc,就是1,2,3。但这个在存为文件的时候必须用分割符把1,2,3分割开,非常浪费空间,否则会和12 23 123 产生二义性。而哈夫曼树,将所有char分布在叶节点上,在还原的时候,比如1101110,假设110是叶节点,那么走到110的时候就可以确定,已经走到尽头,回到根节点继续走,这样就避免了字符的分割,全部用1010101010101这样的路径表示字符,可以将8位压缩为1个char进行存储。在构造树的时候,将出现率高的char放在上面,这样路径就很短,自然就节省了存储空间。虽然哈夫曼压缩效率不是最高的,但还算比较乐观的。
哈夫曼除了压缩以外还可以用于加密,在将文本用哈夫曼编码时,需持久化生成的char计数链表结构,这样才能还原出树结构,而解码时路径正是依赖于树结构的。也就是说,这种编码是属于约定形式的编码,在编码时用原文本产生树结构,而存储的是树路径,解码的时候缺少树或树结构与原先不相符都是无法完成解码的,就好比,我用10代表a,你存的是10,你将10解释为 b或c等等都是不正确的。由于转换为了char存储,所以还需持久化最后填充的数目、文本长度,才能还原出原先的01表示的文本格式
这个代码有一定缺陷,由于当时考虑的是对文本进行处理,当文件中有char='\0' 时会出现错误,这个代码打的很费神,就不继续修复了,如有需要,可自行更改,解决的办法应该挺多的
先来个运行图:
源代码
#include#include #include void WriteFile(char* path,const char* content,int length,bool append=false); using namespace std; struct Node{ char data; Node* left; Node* right; }; struct L_Node{ int count; Node* node; L_Node* next; }; Node* AddNode(int count,char data,L_Node*& first){ L_Node* lnode=new L_Node(); lnode->count=count; Node* node=new Node(); node->data=data; node->left=0; node->right=0; lnode->node=node; if(first==0){ first=lnode; } else{ if(lnode->count count){ lnode->next=first; first=lnode; } else{ L_Node* iter=first; while(iter->next!=0&&iter->next->count count){ iter=iter->next; } if(iter->next==0){ iter->next=lnode; lnode->next=0; } else{ lnode->next=iter->next; iter->next=lnode; } } } return node; } void SaveLNodes(L_Node* first){ stringstream ss; while(first!=0){ ss<<(int)(unsigned char)first->node->data<<':'< count<<' '; first=first->next; } WriteFile("nodes.txt",ss.str().c_str(),ss.str().length()); } void GetLNodes(L_Node*& first){ char temp[32]; ifstream in; in.open("nodes.txt",ios::in|ios::binary); while(!in.eof()){ temp[0]=0; in>>temp; if(strlen(temp)>0){ char* data=strtok(temp,":"); char* count=strtok(0,":"); AddNode(atoi(count),atoi(data),first); } } } void BuildSortedList(char* content,L_Node*& first,int length){ int array[256]={ 0 }; for(int i=0;i 0){ AddNode(array[i],(char)i,first); } } SaveLNodes(first); } void BuildTree(L_Node*& first,Node*& root){//get l1->node,l2->node,remove l1,l2,then put l3 into list,then set l3->left and l3->right if(first->next==0){ Node* node=new Node(); root=node; root->right=0; node=new Node(); node->data=first->node->data; node->left=0; node->right=0; root->left=node; delete first; return; } while(first->next!=0){ int count=first->count+first->next->count; Node* node1=first->node; L_Node* temp=first; first=first->next; delete temp; Node* node2=first->node; temp=first; delete temp; first=first->next; root=AddNode(count,0,first); root->left=node1; root->right=node2; //cout<<(int)node1->data<<':'<<(int)node2->data< data!=0){ table[(unsigned char)node->data]=track2; } PreOrderTraversal(node->left,track2,0,table); PreOrderTraversal(node->right,track2,1,table); if(node->data==0){ delete track2; } } } void PreOrderTraversal(Node* node){ if(node!=0){ cout<<(int)(unsigned char)node->data< left); PreOrderTraversal(node->right); } } char* Encode(const char* content,char** table,int length){ stringstream ss; for(int i=0;i =0;i--){ number+=(bin_content[i]-'0')*cur; cur*=2; } return number; } char* BinToCharText(const char* bin_content,int& fill_count,int& save_length){ int length=strlen(bin_content); fill_count=8-length%8; if(fill_count>0){ char* temp=new char[length+fill_count+1]; char temp1[fill_count]; for(int i=0;i 0){ delete bin_content; } return text; } char* DecToBin(int num){ char* bin=new char[8]; if(num<0){ num=256+num; } for(int i=7;i>=0;i--){ bin[i]=num%2+'0'; num/=2; } return bin; } char* CharTextToBin(char* text,int fill_count,int save_length){ int length=save_length; char* content=new char[8*length+1]; int pos=0; for(int i=0;i left; } else if(encode_content[i]=='1'){ node=node->right; } if(node->data!=0){ ss< data; node=tree; } } char* decode_content=new char[ss.str().length()+1]; memcpy(decode_content,ss.str().c_str(),ss.str().length()); decode_content[ss.str().length()]=0; return decode_content; } void ReleaseTable(char** table){ for(int i=0;i<256;i++){ if(table[i]!=0){ delete table[i]; } } } void PostOrderTraversal(Node* node){ if(node!=0){ PostOrderTraversal(node->left); PostOrderTraversal(node->right); delete node; } } char* ReadFile(char* path,long& length){ char* content=0; ifstream in; in.open(path,ios::in|ios::binary); in.seekg(0,ios::end); length=in.tellg(); content=new char[length+1]; in.seekg(0,ios::beg); int i=0; while(!in.eof()){ content[i++]=in.get(); } content[length]=0; in.close(); return content; } char* ReadFile(char* path,int& fill_count,int& save_length){ char* content=0; ifstream in; in.open(path,ios::in|ios::binary); in>>fill_count>>save_length; long cur=in.tellg()+(long)1; in.seekg(0,ios::end); long length=in.tellg()-cur; content=new char[length+1]; in.seekg(cur,ios::beg); int i=0; while(!in.eof()){ content[i++]=in.get(); } content[length]=0; in.close(); return content; } void WriteFile(char* path,const char* content,int length,bool append){ ofstream out; if(append){ out.open(path,ios::out|ios::binary|ios::app); } else{ out.open(path,ios::out|ios::binary); } out.write(content,length); out.close(); } int main(){ long length; char* content=ReadFile("content.txt",length); L_Node* first=0; BuildSortedList(content,first,length); //create nodes list and save to nodes file //GetLNodes(first);//get and recreate nodes from file Node* root=0;//used for buildtable and decode BuildTree(first,root);//build tree by nodes list and release sorted list char* table[256]={//build table,used for encode 0 }; PreOrderTraversal(root,"",-1,table);//create table char* encode_content=Encode(content,table,length);//convert content to encoded bin text cout< 感谢你能够认真阅读完这篇文章,希望小编分享的“C++如何实现哈夫曼树对文件压缩、加密功能”这篇文章对大家有帮助,同时也希望大家多多支持创新互联建站,关注创新互联网站建设公司行业资讯频道,更多相关知识等着你来学习!
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
本文题目:C++如何实现哈夫曼树对文件压缩、加密功能-创新互联
URL网址:http://scyanting.com/article/diejpc.html