用赫夫曼树进行字符串的编码

哈夫曼编码python一、什么是哈夫曼编码？哈夫曼编码（Huffman Coding）是一种可变长度编码（Variable Length Code），它可以将不同长度的字符编码成等长的二进制串，从而实现数据压缩的目的。

哈夫曼编码是由David A. Huffman在1952年发明的，它是一种贪心算法，可以得到最优解。

二、哈夫曼编码原理1.字符频率统计在进行哈夫曼编码之前，需要先统计每个字符出现的频率。

通常使用一个字典来存储每个字符和其出现的次数。

2.构建哈夫曼树根据字符出现频率构建一个二叉树，其中频率越高的字符离根节点越近。

构建过程中需要用到一个优先队列（Priority Queue），将每个节点按照频率大小加入队列中，并将队列中前两个节点合并为一个新节点，并重新加入队列中。

重复这个过程直到只剩下一个节点，即根节点。

3.生成哈夫曼编码从根节点开始遍历哈夫曼树，在遍历过程中，左子树走0，右子树走1，直到叶子节点。

将路径上经过的0和1分别表示为0和1位二进制数，并把这些二进制数拼接起来，就得到了该字符的哈夫曼编码。

三、哈夫曼编码Python实现下面是一个简单的Python实现：1.字符频率统计```pythonfrom collections import Counterdef get_char_frequency(text):"""统计每个字符出现的频率"""return Counter(text)```2.构建哈夫曼树```pythonimport heapqclass HuffmanNode:def __init__(self, char=None, freq=0, left=None, right=None): self.char = charself.freq = freqself.left = leftself.right = rightdef __lt__(self, other):return self.freq < other.freqdef build_huffman_tree(char_freq):"""根据字符频率构建哈夫曼树"""nodes = [HuffmanNode(char=c, freq=f) for c, f inchar_freq.items()]heapq.heapify(nodes)while len(nodes) > 1:node1 = heapq.heappop(nodes)node2 = heapq.heappop(nodes)new_node = HuffmanNode(freq=node1.freq+node2.freq, left=node1, right=node2)heapq.heappush(nodes, new_node)return nodes[0]```3.生成哈夫曼编码```pythondef generate_huffman_codes(node, code="", codes={}): """生成哈夫曼编码"""if node is None:returnif node.char is not None:codes[node.char] = codegenerate_huffman_codes(node.left, code+"0", codes) generate_huffman_codes(node.right, code+"1", codes)return codes```四、使用哈夫曼编码进行压缩使用哈夫曼编码进行压缩的方法很简单，只需要将原始数据中的每个字符用对应的哈夫曼编码替换即可。

数据结构实验报告实验名称：实验3——哈夫曼编码学生姓名：班级：班内序号：学号：日期：2013年11月24日1．实验要求利用二叉树结构实现赫夫曼编/解码器。

基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。

3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。

5、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

2. 程序分析2.1存储结构：struct HNode{char c;//存字符内容int weight;int lchild, rchild, parent;};struct HCode{char data;char code[100];}; //字符及其编码结构class Huffman{private:HNode* huffTree; //Huffman树HCode* HCodeTable; //Huffman编码表public:Huffman(void);void CreateHTree(int a[], int n); //创建huffman树void CreateCodeTable(char b[], int n); //创建编码表void Encode(char *s, string *d); //编码void Decode(char *s, char *d); //解码void differ(char *,int n);char str2[100];//数组中不同的字符组成的串int dif;//str2[]的大小~Huffman(void);};结点结构为如下所示：三叉树的节点结构：struct HNode//哈夫曼树结点的结构体{ int weight;//结点权值int parent;//双亲指针int lchild;//左孩子指针int rchild;//右孩子指针char data;//字符};示意图为：int weight int parent int lchild int rchild Char c 编码表节点结构：struct HCode//编码表结构体{char data;//字符char code[100];//编码内容};示意图为：基本结构体记录字符和出现次数:struct node{int num;char data;};示意图为:2.关键算法分析(1).初始化:伪代码：1.输入需要编译的文本内容2.将输入的内容保存到数组str1中3.统计出现的字符数目,并且保存到变量count中4.统计出现的不同的字符，存到str2中，将str2的大小存到dif中时间复杂度O(n！)（2）.创建哈夫曼树算法伪代码：1.创建一个长度为2*n-1的三叉链表2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域，并将对应结点的孩子域和双亲域赋为空3.从三叉链表的第n个结点开始，3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下标x,y。

赫夫曼编码的应用实验目的和要求1.掌握赫夫曼算法；2.编写实验报告；实验内容本设计要求对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码。

实验步骤1、问题分析要实现设计要求，必须实现以下几个方面的功能●赫夫曼树的建立●赫夫曼编码的生成●编码文件的译码2、问题求解2.1赫夫曼树的建立●赫夫曼树的存储结构；#define n 100#define m 2*n-1typedef struct{unsigned int weight;unsigned int parent,lchild,rchild;}HTNode;typedef HTNode HuffmanTree[m+1];●选择双亲为0且权值最小的两个根结点的算法void select(HuffmanTree HT , int k, int *s1, int *s2)●统计字符串中字符的种类以及各类字符的个数的算法Int jsq(char *s,int cnt[],char str[]){For (i=1;i<=26;i++)Temp[i]=0;For(p=s;*p!=’\0’;p++){//统计字符的个数If(*p是字母){k=*p-64;temp[k]++;}}j=0;for (i=1,j=0;i<=26;i++)//统计字符种数if (temp[i]!=0){j++;str[j]=i+64;//将对应的字母送入数组cnt[j]=temp[i] ;//存入对应权值}Return j ;}●构造赫夫曼树void HuffmanCoding(HuffmanTree HT,HuffmanCode HC, int cnt[],char str[])//cnt[]存放字符出现的频率；str存放电文中不同类的字符2.2赫夫曼编码的生成●数据结构typedef struct{char ch;//存放编码的字符char bits[n+1];// 存放编码的位串int start;// 编码的起始位置}CodeNode;typedef CodeNode HuffmanCode[n]●赫夫曼编码算法void HuffmanEnCoding(HuffmanTree HT,HuffmanCode HC)●建立正文的编码文件codefile.txt基本思想：将要编码的字符串中的字符逐一与预先生成赫夫曼树时保存得的字符编码对照表进行比较，找到后，将该字符编码写入代码文件，直至所有的字符处理完为止void Coding (HuffmanCode HC,char *str)2.3编码文件的译码●代码文件codefile.txt的译码基本思想：读文件的编码，并与原生成的赫夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中char *decode (HuffmanCode HC)3、完整的程序清单4、程序运行测试。

c语言哈夫曼树的构造及编码一、哈夫曼树概述哈夫曼树是一种特殊的二叉树，它的构建基于贪心算法。

它的主要应用是在数据压缩和编码中，可以将频率高的字符用较短的编码表示，从而减小数据存储和传输时所需的空间和时间。

二、哈夫曼树的构造1. 哈夫曼树的定义哈夫曼树是一棵带权路径长度最短的二叉树。

带权路径长度是指所有叶子节点到根节点之间路径长度与其权值乘积之和。

2. 构造步骤(1) 将待编码字符按照出现频率从小到大排序。

(2) 取出两个权值最小的节点作为左右子节点，构建一棵新的二叉树。

(3) 将新构建的二叉树加入到原来排序后队列中。

(4) 重复上述步骤，直到队列只剩下一个节点，该节点即为哈夫曼树的根节点。

3. C语言代码实现以下代码实现了一个简单版哈夫曼树构造函数：```ctypedef struct TreeNode {int weight; // 权重值struct TreeNode *leftChild; // 左子节点指针struct TreeNode *rightChild; // 右子节点指针} TreeNode;// 构造哈夫曼树函数TreeNode* createHuffmanTree(int* weights, int n) {// 根据权值数组构建节点队列，每个节点都是一棵单独的二叉树TreeNode** nodes = (TreeNode**)malloc(sizeof(TreeNode*) * n);for (int i = 0; i < n; i++) {nodes[i] = (TreeNode*)malloc(sizeof(TreeNode));nodes[i]->weight = weights[i];nodes[i]->leftChild = NULL;nodes[i]->rightChild = NULL;}// 构建哈夫曼树while (n > 1) {int minIndex1 = -1, minIndex2 = -1;for (int i = 0; i < n; i++) {if (nodes[i] != NULL) {if (minIndex1 == -1 || nodes[i]->weight < nodes[minIndex1]->weight) {minIndex2 = minIndex1;minIndex1 = i;} else if (minIndex2 == -1 || nodes[i]->weight < nodes[minIndex2]->weight) {minIndex2 = i;}}}TreeNode* newNode =(TreeNode*)malloc(sizeof(TreeNode));newNode->weight = nodes[minIndex1]->weight + nodes[minIndex2]->weight;newNode->leftChild = nodes[minIndex1];newNode->rightChild = nodes[minIndex2];// 将新构建的二叉树加入到原来排序后队列中nodes[minIndex1] = newNode;nodes[minIndex2] = NULL;n--;}return nodes[minIndex1];}```三、哈夫曼编码1. 哈夫曼编码的定义哈夫曼编码是一种前缀编码方式，它将每个字符的编码表示为二进制串。

哈夫曼编码算法思想总结哈夫曼编码算法是一种基于字符出现频率的编码方式，其主要思想是通过建立一颗哈夫曼树来实现最优的编码方案。

哈夫曼编码算法在数据压缩领域广泛应用，在传输和存储数据时可以减小数据的体积，提高数据的传输效率。

哈夫曼编码算法的核心思想是根据字符出现的频率，对字符进行编码，使得出现频率较高的字符获得较短的编码，出现频率较低的字符获得较长的编码。

这样可以有效地减小编码后的数据长度，并且在解码的时候不会存在二义性。

哈夫曼编码算法的实现过程主要分为三个步骤：建立字符频率统计表、构造哈夫曼树、生成编码表。

首先，需要统计字符出现的频率。

扫描待编码的文本，记录每个字符出现的次数。

可以使用哈希表或者数组来实现字符与频率之间的映射关系。

其次，根据字符频率构造哈夫曼树。

通过扫描字符频率统计表，将每个字符及其频率作为叶子节点构建一颗树。

每个节点的权值为其子树中所有叶子节点的权值之和。

不断地选择权值最小的两个节点，将它们合并为一个新的节点，并更新权值。

重复这个过程，直到只剩下一个节点，即为哈夫曼树的根节点。

最后，生成编码表。

从哈夫曼树的根节点开始，向下遍历每个节点，标记左分支为0，右分支为1。

这样可以得到每个字符对应的二进制编码。

将字符及其对应的编码存储在编码表中，供解码时使用。

利用生成的编码表，可以将待编码的文本转化为哈夫曼编码。

每个字符根据编码表中的对应编码进行替换，得到编码后的二进制数据。

由于频率高的字符对应的编码较短，所以编码后的数据长度相比原始数据大大减小。

在解码时，根据哈夫曼树的结构和编码表的内容，可以还原出原始的文本数据。

从根节点开始，根据编码依次遍历哈夫曼树，根据0或者1选择左分支或者右分支。

当到达叶子节点时，找到对应的字符，并将其输出到解码后的文本中。

哈夫曼编码算法的优点是编码后的数据长度相对较短，可以实现高效的数据压缩。

在数据传输和存储过程中，可以减少带宽的占用，提高传输效率。

同时，哈夫曼编码算法的解码过程也相对简单，可以快速还原出原始的文本数据。

标题：探讨适合字母和数字组成的字符串压缩的算法一、引言现代社会中，数据量越来越大，对数据的存储和传输提出了更高的要求。

在信息技术领域中，字符串压缩算法是一种常见的处理大量文本数据的方法。

而对于由字母和数字组成的字符串，如何进行高效的压缩成为了一个具有挑战性的问题。

本文将探讨适合字母和数字组成的字符串压缩的算法，旨在寻找一种高效的压缩方法，以减小数据的存储和传输成本。

二、现有的字符串压缩算法目前已经存在许多字符串压缩算法，如Lempel-Ziv-Welch (LZW) 算法、Run-Length Encoding (RLE) 算法等，它们对于一般的字符串压缩已经有着较好的效果。

然而，对于由字母和数字组成的字符串，这些算法在压缩效果上存在一定的局限性。

在面对这种特殊类型的字符串时，需要寻找更适合的压缩算法。

三、需求分析在寻找适合字母和数字组成的字符串压缩算法之前，首先需要对压缩算法的需求进行分析。

针对这种特殊类型的字符串，我们希望压缩算法能够具有以下特点：1. 高压缩比：能够在不损失数据的情况下，尽可能减小字符串的长度，以降低存储和传输成本。

2. 快速压缩和解压：算法需要具有较高的执行效率，能够在短时间内完成压缩和解压操作。

3. 通用性：算法需要适用于不同类型的字母和数字组成的字符串，且不受数据内容的影响。

四、可能的解决方案针对上述需求，可以考虑以下几种可能的解决方案：1. Huffman 编码算法：Huffman 编码是一种经典的无损数据压缩算法，通过构建赫夫曼树，将出现频率较高的字符用较短的编码表示，从而实现对字符串的压缩。

该算法在一般的字符串压缩中效果显著，但对于字母和数字组成的字符串是否具有同样良好的压缩效果，尚需进一步研究和验证。

2. 哈夫曼编码树解码：哈夫曼编码是信息编码中常用的一种字典编码方法。

它通过构造一棵特殊的二叉树——哈夫曼树，从而使得出现频率较高的字符获得较短的编码，从而实现对字符串的压缩。

//运行测试实例#include<stdio.h>#include<string.h>#include<stdlib.h>//#include"type6.h" //类型定义//#include"jlhfms.c" //生成赫夫曼树//#include"scbmwj.c" //生成编码文件//#include"dwym.c" //电文译码//算法运行实例//1.源程序清单//(1)类型及相关变量定义#define n 100 //叶子结点数#define m 2*n-1 //赫夫曼树中结点总数typedef struct{char ch;char bits[9]; //存放编码位串int len ; //编码长度}CodeNode;typedef CodeNode HuffmanCode[n+1];typedef struct {int weight; //权值int lchild,rchild,parent; //左右孩子及双亲指针}HTNode; //树中结点类型typedef HTNode HuffmanTree[m+1]; //0号单元不用int num;//(2)建立赫夫曼树的三个函数(jlhfms.c)void select(HuffmanTree HT,int k,int &s1,int &s2){//在HT[1..K]中选择parent为0且权值最小的两个根结点//其序号分别为s1和s2,并靠引用参数带回主调函数int i,j;int min1=32767;for(i=1;i<=k;i++) //找s1if(HT[i].weight<min1&&HT[i].parent==0){j=i;min1=HT[i].weight;}s1=j; min1=32767;for(i=1;i<=k;i++) //找s2if(HT[i].weight<min1 && HT[i].parent==0 && i!=s1){j=i;min1=HT[i].weight;}s2=j;}int jsp(char*s,int cnt[],char str[]){char *p;int i,j,k;int temp[27];for(i=1;i<=26;i++)temp[i]=0;for(p=s;*p!='\0';p++){ //统计各种字符的个数if(*p>='A' && *p<='Z'){k=*p-64;temp[k]++;}}j=0;for(i=1,j=0;i<=26;i++) //统计有多少种字符if (temp[i]!=0){j++;str[j]=i+64; //送对应的字母到数组中cnt[j]=temp[i]; //存入对应字母的权值}return j;}//构造赫夫曼树void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[]) {//构造赫夫曼树HT，cnt中存放每类字符在电文中出现的频率,//str中存放电文中不同类的字符int i,s1,s2;for(i=1;i<=2*num-1;i++) //初始化HT{HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;HT[i].weight=0;}for(i=1;i<=num;i++) //输入num个叶结点的权值HT[i].weight=cnt[i];for(i=num+1;i<=2*num-1;i++){ //在HT[1..i-1]中选择parent为0且权值最小的两个根结点//其序号分别为s1和s2select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}for(i=0;i<=num;i++) //输入字符集中的字符HC[i].ch=str[i];i=1;while(i<=num)printf("字符%C,次数为：%d\n",HC[i].ch,cnt[i++]);}//(3)生成赫夫曼编码文件的两个函数(scbmwj.c)void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC){ //根据赫夫曼树HT求赫夫曼编码HCint c,p,i; //c、p分别指示HT中孩子和双亲的位置char cd[n]; //临时存放编码串int start; //指示编码在cd中的起始位置cd[num]='\0'; //最后一位放上串结束符for(i=1;i<=num;i++){start=num; //初始位置c=i; //从叶子结点HT[i]开始上溯while((p=HT[c].parent)>0) //直至上溯到HT[c]是树根为止{//若HT[C]是HT[P]的左孩子，则生成0；否则生成代码1cd[--start]=(HT[p].lchild==c)?'0':'1';c=p;}strcpy(HC[i].bits,&cd[start]);HC[i].len=num-start;}}void coding(HuffmanCode HC,char *str){ //对str所代表的字符串进行编码并写入磁盘文件FILE *fp;fp=fopen("codefile.txt","w");while(*str){ //对电文中字符逐一生成编码并写入文件for(i=1;i<=num;i++)if(HC[i].ch==*str){for(j=0;j<HC[i].len;j++)fputc(HC[i].bits[j],fp);break;}str++;}fclose(fp);}//(4) 电文的译码(dwym.c)char * decode(HuffmanCode HC){ //代码文件codefile.txt译码FILE *fp;char str[254]; //假设原文本文件不超过254个字符char *p;static char cd[n+1];int i,j,k=0,cjs;fp=fopen("codefile.txt","r");while(!feof(fp)){cjs=0; //一个字符的编码是否读结束for(i=0;i<num && cjs==0 && !feof(fp);i++){cd[i]=' ';cd[i+1]='\0'; //初始化cd串cd[i]=fgetc(fp);for(j=1;j<=num;j++)if(strcmp(HC[j].bits,cd)==0){str[k]=HC[j].ch;k++;cjs=1;break;}}}str[k]='\0';return p;}void main(){char st[254],*s,str[27];int cn[27];HuffmanTree HT;HuffmanCode HC;printf("输入需要编码的字符串（假设均为大写字母）:\n");gets(st);num=jsp(st,cn,str); //统计字符的种类及各类字符出现的频率ChuffmanTree(HT,HC,cn,str); //建立赫夫曼树HuffmanEncoding(HT,HC); //生成赫夫曼编码coding(HC,st); //建立电文赫夫曼编码文件s=decode(HC); //读编码文件译码printf("译码后的字符串:\n");printf("%s\n",s); //输出译码后字符串}。

赫夫曼编码(huffman编码)huffman编码实现：#include<iostream.h>#include<stdlib.h>#include<string.h>typedef struct//huffman树结点的类型{int weight,parent,lchild,rchild;} tnode,*tnodepointer;void select(tnodepointer HT,int n,int &s1,int &s2) //在数组HT的前n个parent=0的元素中，找出权最小的两个元素并将其下标分别赋给s1，s2{int i;s1=0;for(i=0;i<n&&HT[i].parent !=0;i++)s1=i+1;for(i=0;i<n;i++) //用s1保存权最小的元素的下标if(HT[i].weight<HT[s1].weight&&HT[i].parent==0)s1=i;s2=0;for(i=0;i<n&&(s2==s1||HT[i].parent !=0);i++)s2=i+1;for(i=0;i<n;i++) //用s2保存权次小的元素的下标if(HT[i].weight<HT[s2].weight&&HT[i].parent==0&&s 1!=i)s2=i;}char ** huffmancoding(int *w,int n) //由长度为n的权值数组w，得到其对应的huffman编码。

函数的返回值是n个字符编码的头指针组成的数组的首地址（二级指针）{tnodepointerHT=(tnodepointer)malloc((2*n-1)*sizeof(tnode));//定义存放2n-1个结点的数组for(tnodepointerTEMP=HT;TEMP<HT+n;TEMP++,w++)//将w中的权值移动到数组HT中{ //结构体变量赋值TEMP->weight =*w;TEMP->parent = 0;TEMP->lchild = 0;TEMP->rchild = 0;}for(int m=2*n-1;TEMP<HT+m;TEMP++) //初始化非叶子结点的parent项TEMP->parent =0;for(int i=n;i<2*n-1;i++) //设置各个结点的值{int s1,s2;select(HT,i,s1,s2);//在数组HT的前n个parent=0的元素中，找出权最小的两个元素并将其下标分别赋给s1，s2HT[s1].parent =i;HT[s2].parent =i;HT[i].lchild =s1;HT[i].rchild =s2;HT[i].weight =HT[s1].weight +HT[s2].weight ;}char * str=(char *)malloc(n*sizeof(char)); //str用于临时存放huffman编码char **huffmancode=(char **)malloc(n*sizeof(char *));for(i=0;i<n;i++)int start=n-1;str[start]='\0';int c=i,temp=HT[c].parent;while(temp!=0) //temp=0表示该结点为根结点{if(HT[temp].lchild ==c)str[--start]='0';elsestr[--start]='1';c=temp;temp=HT[c].parent ;}huffmancode[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(huffmancode[i],&str[start]);}free (HT);free(str);return huffmancode;}void output(char **p,int n) //输出数组p中各元素指向的字符串for(int i=0;i<n;i++)cout<<p[i]<<",";cout<<endl;}main(){ //测试int w[]={5,29,7,8,14,23,3,11};char **p=huffmancoding(w,8);cout<<"与权值对应的huffman编码为："<<endl; output(p,8);}。