C++ 哈夫曼樹對文件壓縮、加密實現(xiàn)代碼
更新時間：2017年08月18日 09:00:35 作者：lld951027
這篇文章主要介紹了C++ 哈夫曼樹對文件壓縮、加密實現(xiàn)代碼,具有一定的參考價值，感興趣的小伙伴們可以參考一下
在以前寫LZW壓縮算法的時候，遇到很多難受的問題，基本上都在哈夫曼編碼中解決了，雖然寫這代碼很費神，但還是把代碼完整的碼出來了，畢竟哈夫曼這個思想確實很牛逼。哈夫曼樹很巧妙的解決了當(dāng)時我在LZW序列化的時候想解決的問題，就是壓縮后文本的分割。比如用lzw編碼abc，就是1,2,3。但這個在存為文件的時候必須用分割符把1,2,3分割開，非常浪費空間，否則會和12 23 123 產(chǎn)生二義性。而哈夫曼樹，將所有char分布在葉節(jié)點上，在還原的時候，比如1101110，假設(shè)110是葉節(jié)點，那么走到110的時候就可以確定，已經(jīng)走到盡頭，回到根節(jié)點繼續(xù)走，這樣就避免了字符的分割，全部用1010101010101這樣的路徑表示字符，可以將8位壓縮為1個char進行存儲。在構(gòu)造樹的時候，將出現(xiàn)率高的char放在上面，這樣路徑就很短，自然就節(jié)省了存儲空間。雖然哈夫曼壓縮效率不是最高的，但還算比較樂觀的。
哈夫曼除了壓縮以外還可以用于加密，在將文本用哈夫曼編碼時，需持久化生成的char計數(shù)鏈表結(jié)構(gòu)，這樣才能還原出樹結(jié)構(gòu)，而解碼時路徑正是依賴于樹結(jié)構(gòu)的。也就是說，這種編碼是屬于約定形式的編碼，在編碼時用原文本產(chǎn)生樹結(jié)構(gòu)，而存儲的是樹路徑，解碼的時候缺少樹或樹結(jié)構(gòu)與原先不相符都是無法完成解碼的，就好比，我用10代表a，你存的是10，你將10解釋為 b或c等等都是不正確的。由于轉(zhuǎn)換為了char存儲，所以還需持久化最后填充的數(shù)目、文本長度，才能還原出原先的01表示的文本格式
這個代碼有一定缺陷，由于當(dāng)時考慮的是對文本進行處理，當(dāng)文件中有char='\0' 時會出現(xiàn)錯誤，這個代碼打的很費神，就不繼續(xù)修復(fù)了，如有需要，可自行更改，解決的辦法應(yīng)該挺多的
先來個運行圖：
源代碼
#include<iostream>
#include<sstream>
#include<fstream>
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<first->count){
lnode->next=first;
first=lnode;
}
else{
L_Node* iter=first;
while(iter->next!=0&&iter->next->count<lnode->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<<':'<<first->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<length;i++){
array[(unsigned char)content[i]]++;
}
for(int i=0;i<256;i++){
if(array[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<<endl;
}
delete first;
}
void PreOrderTraversal(Node* node,char* track,int branch,char** table){
if(node!=0){
char* track2=0;
if(branch==0){
track2=new char[strlen(track)+2];
sprintf(track2,"%s0\0",track);
}
else if(branch==1){
track2=new char[strlen(track)+2];
sprintf(track2,"%s1\0",track);
}
else{
track2=new char[strlen(track)+1];
sprintf(track2,"%s\0",track);
}
if(node->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<<endl;
PreOrderTraversal(node->left);
PreOrderTraversal(node->right);
}
}
char* Encode(const char* content,char** table,int length){
stringstream ss;
for(int i=0;i<length;i++){
if((unsigned char)content[i]==0){
}
else{
ss<<table[(unsigned char)content[i]];
}
}
char* encoded_content=new char[ss.str().length()+1];
memcpy(encoded_content,ss.str().c_str(),ss.str().length());
encoded_content[ss.str().length()]=0;
return encoded_content;
}
int BinToDec(char* bin_content){
int number=0;
int cur=1;
for(int i=7;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<fill_count;i++){
temp1[i]='0';
}
sprintf(temp,"%s%s",bin_content,temp1);
temp[length+fill_count]=0;
bin_content=temp;
}
length+=fill_count;
save_length=length/8;
char* text=new char[length/8+1];
for(int i=0;i<length;i+=8){
char temp[8];
memcpy(temp,bin_content+i,8);
text[i/8]=(char)BinToDec(temp);
}
text[length/8]=0;
if(fill_count>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<length;i++){
int number=text[i];
char* bin=DecToBin(number);
memcpy(content+pos,bin,8);
pos+=8;
delete bin;
}
content[8*length-fill_count]=0;
return content;
}
char* Decode(const char* encode_content,Node* tree){
stringstream ss;
Node* node=tree;
for(int i=0;i<strlen(encode_content);i++){
if(encode_content[i]=='0'){
node=node->left;
}
else if(encode_content[i]=='1'){
node=node->right;
}
if(node->data!=0){
ss<<node->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<<encode_content<<endl;
delete content;
ReleaseTable(table);//release table when encode finished
int fill_count;
int save_length;
char* save_text=BinToCharText(encode_content,fill_count,save_length);//convert encoded bin text to char text and save these text to file
delete encode_content;
char head_info[32];
sprintf(head_info,"%d %d ",fill_count,save_length);
WriteFile("encoded_content.txt",head_info,strlen(head_info));
WriteFile("encoded_content.txt",save_text,save_length,true);
delete save_text;
save_text=ReadFile("encoded_content.txt",fill_count,save_length);//read fill_count、save_length、encoded char text from file
char* bin_text= CharTextToBin(save_text,fill_count,save_length);//convert char text to bin text
delete save_text;
char* decode_content=Decode(bin_text,root);//decode by bin_text and tree
cout<<decode_content<<endl;
delete bin_text;
delete decode_content;
PostOrderTraversal(root);//release tree
return 0;
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了C++變量引用的概念介紹，簡單提到了與指針概念的不同，通過代碼場景分析給大家介紹的非常詳細(xì),需要的朋友可以參考下2021-08-08
這篇文章主要為大家詳細(xì)介紹了單線程會不會導(dǎo)致死鎖，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
這篇文章主要介紹了C++ const和指針，關(guān)于使用const來修飾指針，有兩種不同的方式。第一種是讓指針指向一個常量對象，這樣可以防止使用該指針進行修改指向的值。第二種則是將指針本身聲明為常量，可以防止改變指針指向的位置，下面來看看文章的詳細(xì)內(nèi)容2021-11-11
所謂缺省參數(shù)，顧名思義，就是在聲明函數(shù)的某個參數(shù)的時候為之指定一個默認(rèn)值，在調(diào)用該函數(shù)的時候如果采用該默認(rèn)值，你就無須指定該參數(shù)。C++ 允許多個函數(shù)擁有相同的名字，只要它們的參數(shù)列表不同就可以，這就是函數(shù)的重載，借助重載，一個函數(shù)名可以有多種用途2022-06-06
這篇文章主要介紹了C++炸彈小游戲,本文給大家分享游戲代碼,代碼簡單易懂通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-08-08
這篇文章主要為大家分享了C語言UDP傳輸系統(tǒng)的源碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-02-02
這篇文章主要為大家詳細(xì)介紹了如何通過C++實現(xiàn)獲取郵件文件中的附件,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-01-01
這篇文章主要介紹了C語言實現(xiàn)二叉樹遍歷的迭代算法,包括二叉樹的中序遍歷、先序遍歷及后序遍歷等,是非常經(jīng)典的算法,需要的朋友可以參考下2014-09-09
C++類結(jié)構(gòu)體與json相互轉(zhuǎn)換
這篇文章主要介紹的是C++類結(jié)構(gòu)體與json相互轉(zhuǎn)換，json字符串一般使用的是開源的類庫Newtonsoft.Json，方法十分簡潔，下面就隨小編一起看下面文章內(nèi)容吧2021-09-09
這篇文章主要介紹了C語言中的符號常量EOF,文中還介紹了EOF的驗證和打印方法,需要的朋友可以參考下2015-11-11