中文压缩和解码程序设计与实现（huffman）

2024-06-19 10:18
文章标签 实现 设计 中文 压缩 huffman 解码程序

本文主要是介绍中文压缩和解码程序设计与实现（huffman），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本项目是利用huffman算法进行中文压缩和解码的设计与实现，huffman算法被证明是最优的结构，可以用于数据压缩

源码

/**************************************************************************************
**	this function is about to  compress a file with  chinese code
**	by using huffman method
**	NEWPLAN @ UESTC 2014.5
****************************************************************************************/
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>#define SUCCESS		1
#define FAILURE 	0
#define DICTIONRAY	0
#define INDEX 		1/*used to calculate the frequence of character has shown*******/
int array_char[256]= {0};
unsigned char amounts=0;
/*******define a strcuture to hold the tree node***************/
#pragma pack(1)
typedef struct huff
{struct huff *lchild,*rchild,*parent;int wight;unsigned char code;
} HUFF_NODE,*HUFF_NODE_PTR;
#pragma pack()/*HEAD of tree*/
HUFF_NODE_PTR HUFF_HEADER=NULL;
/*dictionary of characters maybe not been used all just for convenient*/
char* HUFF_DICTIONARY[256]= {0};
HUFF_NODE_PTR huff_pt[256];void help(void);
void version(void);
void output(char*);
void initilize(void);
int claculate(FILE*);
int create_dictiony(void);
void compress(const char*);
int file_write(char*,FILE*);
void write_dictionary(char*);
FILE* file_open(const char*);
int create_tree(HUFF_NODE_PTR* );
void decompress_func(const char*);
void decode (HUFF_NODE_PTR,FILE*);
HUFF_NODE_PTR tree_from_dic(char**);
HUFF_NODE_PTR huff_malloc(unsigned char i);
void swap_func(unsigned char *,unsigned char*);
HUFF_NODE_PTR adjusty(HUFF_NODE_PTR code[] ,size_t);//********************************************************
// Method:    main
// FullName:  main
// Access:    public
// Returns:   int
// Qualifier: the entry function
// Parameter: int argc the parameter count
// Parameter: char const * argv[] array of hold parameter
//********************************************************
int main(int argc, char const *argv[])
{initilize();if(argc<2){printf("can`t be empty file or operation\n");return FAILURE;}// if((file_index=file_open(argv[argc-1]))==NULL)if (!stricmp(argv[1],"--help")){help();return SUCCESS;}else if (!stricmp(argv[1],"--version")){version();return SUCCESS;}else if (!stricmp(argv[1],"-c")){compress(argv[2]);}else if(!stricmp(argv[1],"-z")){decompress_func(argv[2]);}elsehelp();return SUCCESS;
}//************************************
// Method:    initilize
// FullName:  initilize
// Access:    public
// Returns:   void
// Qualifier: inites
// Parameter: void
//************************************
void initilize(void)
{int calcount=0;//memset(array_char,'0',sizeof(array_char));while(calcount<256){array_char[calcount]=0;huff_pt[calcount]=NULL;HUFF_DICTIONARY[calcount]=0;calcount++;}return ;
}//************************************
// Method:    file_open
// FullName:  file_open
// Access:    public
// Returns:   FILE*
// Qualifier: open the input file
// Parameter: const char * file_name
//************************************
FILE* file_open(const char* file_name)
{FILE* file_index=NULL;if((file_index=fopen(file_name,"r"))==NULL)return NULL;return file_index;
}//******************************************************************
// Method:    claculate
// FullName:  claculate
// Access:    public
// Returns:   int
// Qualifier: calculate the frequence of character in file_index
// Parameter: FILE * file_index
//****************************************************************
int claculate(FILE* file_index)
{unsigned char temp=0;while(!feof(file_index)){/*eat file*/if(fread(&temp,sizeof(unsigned char),1,file_index))array_char[temp]++;}return SUCCESS;
}//************************************
// Method:    create_dictiony
// FullName:  create_dictiony
// Access:    public
// Returns:   int
// Qualifier:create dictionary
// Parameter: void
//************************************
int create_dictiony(void)
{int i=0;char *u=NULL;unsigned char j=0;HUFF_NODE_PTR head,currents=NULL;create_tree(&head);HUFF_HEADER=head;while(i<256){if(huff_pt[i]!=NULL){currents=huff_pt[i];j=currents->code;u=malloc(sizeof(char));assert(u!=NULL);memset(u,0,sizeof(char));while(currents->parent!=NULL){u=realloc(u,2*sizeof(char)+strlen(u));assert(u!=NULL);if(currents->parent->lchild==currents)strcat(u,"0");else if(currents->parent->rchild==currents)strcat(u,"1");else{printf("error in code\n");system("pasue");}currents=currents->parent;}/*reverse*/strrev(u);HUFF_DICTIONARY[j]=u;}i++;}return SUCCESS;
}
//************************************
// Method:    create_tree
// FullName:  create_tree
// Access:    public
// Returns:   int
// Qualifier:create tree of huffman
// Parameter: HUFF_NODE_PTR * head
//************************************
int create_tree(HUFF_NODE_PTR* head)
{size_t n=256,i,j;HUFF_NODE_PTR temp[256];memset(temp,0,sizeof(temp));for (i = 0,j=0; i < n; i++){if(array_char[i]){temp[j]			=	huff_malloc((unsigned char)i);temp[j]->wight	=	array_char[i];/*temp[j]->code is the code that contain the info of read_file*/temp[j]->code	=	i;huff_pt[i]=temp[j];j++;}}*head=adjusty(temp,j);amounts=j;return SUCCESS;
}//************************************
// Method:    file_write
// FullName:  file_write
// Access:    public
// Returns:   int
// Qualifier:create function
// Parameter: char * file_name
// Parameter: char * file_stream
// Parameter: size_t num
// Parameter: int flags
//************************************
int file_write(char* file_name,FILE* file_inputs)
{FILE* fp=NULL;int counts=0;unsigned char readdata,writedata=0,*TempPoint;char* file_w=file_name;fp=fopen(file_w,"ab+");if(!fp){printf("can`t open file %s and exit FAILURE!\n", file_name);exit(FAILURE);}while(!feof(file_inputs)){if(fread(&readdata,sizeof(unsigned char),1,file_inputs))TempPoint=(unsigned char*)HUFF_DICTIONARY[readdata];while(*TempPoint){writedata=writedata<<1;writedata|=(*TempPoint-'0');TempPoint++;counts++;if(counts==8){fwrite(&writedata,sizeof(unsigned char),1,fp);counts=0;writedata=0;}}}if(counts){writedata<<=(8-counts);fwrite(&writedata,sizeof(unsigned char),1,fp);}writedata=(unsigned char)((8-counts)%8);fwrite(&writedata,sizeof(unsigned char),1,fp);fclose(fp);return SUCCESS;
}//************************************
// Method:    huff_malloc
// FullName:  huff_malloc
// Access:    public
// Returns:   HUFF_NODE_PTR
// Qualifier:
// Parameter: unsigned char i
//************************************
HUFF_NODE_PTR huff_malloc(unsigned char i)
{HUFF_NODE_PTR temp=(HUFF_NODE_PTR)malloc(sizeof(HUFF_NODE));assert (temp!=NULL);temp->code=i;temp->parent=NULL;temp->lchild=NULL;temp->rchild=NULL;temp->wight=0;return temp;
}//************************************
// Method:    adjusty
// FullName:  adjusty
// Access:    public
// Returns:   HUFF_NODE_PTR
// Qualifier:
// Parameter: HUFF_NODE_PTR code[]
// Parameter: size_t n
//************************************
HUFF_NODE_PTR adjusty(HUFF_NODE_PTR code[],size_t n)
{assert (n<=256);int i,j=0,k=0;/* index j replcaethe lest,and index k replace the second*/HUFF_NODE_PTR temp=NULL;while(n){for(i=0; i<n; i++){if(code[k]->wight>code[i]->wight){if(code[j]->wight>code[i]->wight){k=j;j=i;}elsek=i;}}/*finished the merge*/if(j==k){if(n==1)break;k++;i=k;while(i<n){if(code[k]->wight>code[i]->wight)k=i;i++;}}temp=huff_malloc(0);/*merge two child*/temp->lchild=code[j];temp->rchild=code[k];/*child pointer point to parent*/code[j]->parent=temp;code[k]->parent=temp;temp->wight=code[j]->wight+code[k]->wight;if(j<k){code[j]=temp;if(k!=(--n))code[k]=code[n];}else{code[k]=temp;if(j!=(--n))code[j]=code[n];}k=0;j=0;}return temp;
}//************************************
// Method:    decode
// FullName:  decode
// Access:    public
// Returns:   void
// Qualifier:
// Parameter: HUFF_NODE_PTR head
// Parameter: FILE * fp
//************************************
void decode (HUFF_NODE_PTR head,FILE* fp)
{unsigned char read_code,tempcode=0,rewards=0,tp=0;int count=8,model=0;int flags=0;HUFF_NODE_PTR decode_head=head;unsigned char CHINESE[3]= {0,0,0};while(!feof(fp)){backup:count=8;/*get a 8 bits code to find the leaves*/fread(&tempcode,sizeof(unsigned char),1,fp);/*if arrive to last second character you shouldexit now !*/if(feof(fp))break;read_code=tempcode;while(decode_head){/*go to the leave note!,should to decode now*/if(!decode_head->lchild){fread(&rewards,sizeof(unsigned char),1,fp);fread(&tp,sizeof(unsigned char),1,fp);/*arrive to second character*/model++;model%=2;CHINESE[model]=decode_head->code;if(CHINESE[(model-1+2)%2]>0xa0){if(!model)swap_func(&CHINESE[0],&CHINESE[1]);printf("%s",CHINESE);CHINESE[0]=CHINESE[1]=0;}else if (CHINESE[model]<0xa0){printf("%c",CHINESE[model]);}decode_head=head;if(feof(fp)){ungetc((char)tp,fp);ungetc((char)rewards,fp);flags=1;break;}fseek(fp,-2,SEEK_CUR);}/*left child should be 1,and else the opposite*/if(read_code&0x80){decode_head=decode_head->rchild;}elsedecode_head=decode_head->lchild;read_code<<=1;count--;/*if get here means that: a unsigned char temphas been used out and we should start again!*/if(!count)goto backup;}if(flags)break;}assert(count>=rewards);while(count-rewards){if(read_code&0x80){decode_head=decode_head->rchild;}elsedecode_head=decode_head->lchild;read_code<<=1;count--;if(!decode_head->lchild){model++;model%=2;CHINESE[model]=decode_head->code;if(CHINESE[(model-1+2)%2]>0xa0){if(!model)swap_func(&CHINESE[0],&CHINESE[1]);printf("%s",CHINESE);CHINESE[0]=CHINESE[1]=0;}else if (CHINESE[model]<0xa0){printf("%c",CHINESE[model]);}decode_head=head;}}return;
}//************************************
// Method:    swap_func
// FullName:  swap_func
// Access:    public
// Returns:   void
// Qualifier:
// Parameter: unsigned char * A
// Parameter: unsigned char * B
//************************************
void swap_func(unsigned char *A,unsigned char *B)
{unsigned temp=*A;*A=*B;*B=temp;return;
}//************************************
// Method:    write_dictionary
// FullName:  write_dictionary
// Access:    public
// Returns:   void
// Qualifier: write to file keeping message
// of dictionary
// Parameter: char * file_name
//************************************
void write_dictionary(char* file_name)
{int counts=0,length;FILE* fp=fopen(file_name,"ab+");//char* file_w=(char *)malloc(strlen(file_name)+3);assert(fp!=NULL);/*write to logs*//*write the amount of characters*/fwrite(&amounts,sizeof(unsigned char),1,fp);for(; counts<256;){/*if(current dictionary is not null that means you shouldwrite it to dictionary, causing this is a pointer pointingto a series of decodehere we should write the character ,decode,and its length*/if(HUFF_DICTIONARY[counts]){fwrite(&counts,sizeof(unsigned char),1,fp);length=strlen(HUFF_DICTIONARY[counts]);fwrite(&length,sizeof(int),1,fp);fwrite(HUFF_DICTIONARY[counts],sizeof(unsigned char),length,fp);}counts++;}fclose(fp);return ;
}//************************************
// Method:    output
// FullName:  output
// Access:    public
// Returns:   void
// Qualifier:decode and output
// Parameter: char * file_name
//************************************
void output(char* file_name)
{int ch_counts=0,length=0;unsigned char ch_index=0;HUFF_NODE_PTR head_index=NULL;FILE* fp=fopen(file_name,"rb+");assert(fp!=NULL);fread(&ch_counts,sizeof(unsigned char),1,fp);while(ch_counts--){fread(&ch_index,sizeof(unsigned char),1,fp);fread(&length,sizeof(int),1,fp);free(HUFF_DICTIONARY[ch_index]);HUFF_DICTIONARY[ch_index]=(char*)malloc(length+1);memset(HUFF_DICTIONARY[ch_index],0,length+1);fread(HUFF_DICTIONARY[ch_index],sizeof(char),length,fp);}printf("\ndecode start...\n");//create_tree(&head_index);head_index = tree_from_dic(HUFF_DICTIONARY);decode(head_index,fp);printf("\ntranslation has been finished\n");return ;
}void version(void)
{printf("\nCOPYRIGHT @ NEWPLAN IN UESTC\n");printf("CURRENT VERSION IS NEWPLAN.0.1 THANKS FOR SUPPORT US!\n\n");return;
}
void help(void)
{printf("/*********************************************""*********************************\n**	by using huffman method\n""**	NEWPLAN @ UESTC 2014.5\n*******************************""***********************************************/ \n");printf("choose function to operate!\n");printf("FORMAT:\n");printf("NEWPLAN [parameter] [FILE]\n");printf("this is about compress file to a new file with FORMAT : file_name.n \n");printf("parameter:\n");printf("\t-c\t\tcheck for compress file\n");printf("\t-z\t\tcheck for decompress file\n");printf("\t--help\t\tcheck for documents\n");printf("\t--version\tcheck for version\n");return;
}void compress(const char* file_s)
{char* fw=NULL;FILE* file_index=file_open(file_s);fw=(char*)malloc(strlen(file_s)+3);assert ((file_index!=NULL)&&(fw!=NULL));memset(fw,0,strlen(file_s)+3);strcat(fw,file_s);strcat(fw,".n");claculate(file_index);create_dictiony();write_dictionary(fw);fclose(file_index);file_index=file_open(file_s);file_write(fw,file_index);return;
}void decompress_func(const char* file_s)
{char* fw=(char*)malloc(strlen(file_s)+3);assert(fw!=NULL);memset(fw,0,strlen(file_s)+3);strcat(fw,file_s);strcat(fw,".n");output(fw);return;
}HUFF_NODE_PTR tree_from_dic(char** dic_array)
{int cycle=0;char* ch_ptr=NULL;HUFF_NODE_PTR temp=NULL;HUFF_HEADER=huff_malloc(0);for (cycle = 0; cycle < 256; cycle++){if(dic_array[cycle]){temp=HUFF_HEADER;ch_ptr=dic_array[cycle];while(*ch_ptr){if(*ch_ptr=='0'){if(!temp->lchild){temp->lchild=huff_malloc(0);temp->lchild->parent=temp;}temp=temp->lchild;}else{if(!temp->rchild){temp->rchild=huff_malloc(0);temp->rchild->parent=temp;}temp=temp->rchild;}ch_ptr++;}temp->code=cycle;}}return HUFF_HEADER;
}


这篇关于中文压缩和解码程序设计与实现（huffman）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1074748。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
中文分词jieba库的使用与实景应用（一）

中文分词jieba库的使用与实景应用（一）

知识星球：https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义： 精确模式（默认模式）： 全模式： 搜索引擎模式： paddle 模式（基于深度学习的分词模式）： 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
hdu1565（状态压缩）

hdu1565（状态压缩）

本人第一道ac的状态压缩dp，这题的数据非常水，很容易过 题意：在n*n的矩阵中选数字使得不存在任意两个数字相邻，求最大值 解题思路： 一、因为在1<<20中有很多状态是无效的，所以第一步是选择有效状态，存到cnt[]数组中 二、dp[i][j]表示到第i行的状态cnt[j]所能得到的最大值，状态转移方程dp[i][j] = max(dp[i][j],dp[i-1][k]) ,其中k满足c
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注，收藏不迷路💖 Kubernetes的PodSecurityPolicy（PSP）是一个关键的安全特性，它在Pod创建之前实施安全策略，确保P
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2