赫夫曼编码对文件进行压缩与解密

作者 : 开心源码 本文共5931个字,预计阅读时间需要15分钟 发布时间: 2022-05-14 共283人阅读

理论

赫夫曼树

先有赫夫曼树,才有赫夫曼编码。所以,首先简单详情一下什么是赫夫曼树。

假设一共五个叶子节点,分别是2、3、5、7、8

那么生成的赫夫曼树就是下面这样:

赫夫曼树.png

  1. 赫夫曼树也叫最优二叉树,它的每一个结点具备一个权值。权值越大的结点离根节点越近,这样子从根节点到每一个叶子结点的所有带权路径的和(WPL)最小。

  2. 假设叶子结点为 n, 则总结点数 = 2*n-1

    由于:
    叶子节点的度为 0,其余节点的度为2。
    有:
    (总结点数 – 叶子节点数)x 2 = 边数
    又由于:
    总结点数 – 1 = 边数
    综上:
    总结点数 = 2 x 叶子节点数 – 1

  3. 按照叶子节点的数量和权值,以一种特定的规则,自下而上地建立一颗赫夫曼树。

  4. 可任意交换赫夫曼树中兄弟结点的位置,带权路径和(WPL)不变。

  5. 代码实现(具体见附加代码中的相关构造函数):

  • 采用顺序结构来存储,也就是结构数组。
  • 数组大小为二倍的结点数减一(2*n-1), 每个元素表示一个结点。
  • 先录入 n 个叶子节点,再每次找到权值最小的两个无双亲的结点进行合并。
  • 合并成的新结点加入到数组后面,直到生成2*n-1个元素

赫夫曼编码

  1. 对于字符串“ABACCDA”

  2. 以字符出现频率作为权值,则:

  3. A: 3, B: 1,C: 2, D:1

  4. 建立赫夫曼树:

    赫夫曼树2.png

  5. 如图, 若从根结点,到叶子结点。每次向左为0,向右为1。如此每一个叶子节点都对应一个独一无二的编码,叫做赫夫曼编码。

  6. A: 1
    B: 000
    C: 01
    D: 001

  7. 原字符串就变成了
    1 000 1 01 01 001 1

  8. 代码实现(介绍见附加代码):

对于每一个叶子节点,从叶节点开始,顺着结构中 parent 的下标,遍历到根节点。
期间假如当前节点是当前节点父节点的左儿子,字符串增加一个0
否则增加一个1
遍历到根节点时,将形成的字符串逆置strrev。
对于存储得到的字符串,可以用指针数组来存。char *huffmanCode[n];

应用

应用源码

  1. 先在桌面建立一个 txt 文本,文件里面阔以随意写一段文章(我这不支持对中文字符加密,你们阔以自行拓展)。
  2. 而后运行下面这段又臭又长的代码,输入路径文本所在路径,而后按照提醒进行操作就行了。
  3. 最终相同路径下会产生一个加密文件和一个解密后的文件。
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <windows.h>#include <limits.h>#define MAX 1e4char *HC[150];//指针数组,哈夫曼编码,按顺序对应哈夫曼树。int input_Data[150], number; //字符串的频率, 种类数char path[100]; //路径typedef struct Node{    char value;    int weight;    int lchild;    int rchild;    int parent;}HTNode, *HuffmanTree;HuffmanTree   HT = NULL;void   work(void);              //输出交互界面void   Coding(void);            //对文件进行编码HuffmanTree   build_Huffman_Tree(void);//建立哈夫曼树void   Huffman_Coding(void);    //建立哈夫曼编码HCvoid   output_HC(void);         //打印编码表void   Encrypt(void);           //生成加密文件void   Decode(void);            //生成解密文件23char*  creat_Path(char *name);  //生成路径名称int get_Min(HuffmanTree ht, int k);//得到前k个无父节点的最小权重节点int found_Char(char ch);        //查找输入字符所对应的HC下标int Check(void);                //将解密文件与源文件比较void Continue(void);            //输出能否继续操作对话框intmain(){    printf("---------------欢迎进入文件编码与解码程序---------------\n");    printf("                                    ----by 方宁 20.05.09\n\n");    printf("请输入你所需要进行操作的文件路径:\n");    scanf("%s", path);      //主函数中获取一次操作路径    work();    return 0;}//清屏,和重新调用主菜单voidContinue(void){    char    str[5];    printf("能否继续进行操作?(yes/no)\n");    scanf("%s", str);    if(strcmp(str, "yes") == 0){        system("cls");        work();    }    else{        printf("欢迎您的使用,再见\n");        Sleep(1000);    }}//对指定文件进行哈夫曼编码voidCoding(void){    FILE *fp = NULL;    char ch;    printf("\n文件读取中...\n");    fp = fopen( path, "r" );    if(fp == NULL){        printf("文件打开失败\n");        Sleep(1000);        exit(-1);    }    //读取文件字符,计算权值    while( (ch = fgetc(fp)) != EOF){        if(input_Data[ch - '\0'] == 0)            number++;        input_Data[ch - '\0']++;    }    fclose( fp );    printf("文件读取成功!\n\n");    printf("正在建立哈夫曼树...\n\n");    HT = build_Huffman_Tree();    printf("哈夫曼树建立成功!\n\n");    printf("进行哈夫曼编码...\n\n");    Huffman_Coding();    printf("进行哈夫曼编码成功!\n\n");    printf("---------编码表---------\n");    output_HC();    printf("对文件进行加密...\n\n");    Encrypt();    printf("文件加密成功!\n\n");}//由叶子节点(n)建立哈夫曼树,结点数:2*n-1HuffmanTreebuild_Huffman_Tree(void){    int   i  ,  k = 0;    int   total = 2*number - 1;    int   min1, min2;    HuffmanTree ht = NULL;    ht = (HuffmanTree)malloc( 2*number*sizeof(HTNode) );    if(ht == NULL){        printf("ht malloc faild\n");        Sleep(1000);        exit(-1);    }    for(i = 0; i < total; i++){        ht[i].parent = -1;        ht[i].lchild = -1;        ht[i].rchild = -1;        ht[i].weight = 0;    }    for(i = 0; i < 150; i++){        if(input_Data[i] > 0){            ht[k].value = i + '\0';            ht[k++].weight = input_Data[i];        }    }    for(; k < total; k++)    {        min1 = get_Min(ht, k);        min2 = get_Min(ht, k);        ht[min1].parent = k;        ht[min2].parent = k;        ht[k].weight = ht[min1].weight + ht[min2].weight;        ht[k].lchild = min1;        ht[k].rchild = min2;    }    return ht;}intget_Min(HuffmanTree ht,  int k){    int i = 0, min;    while( ht[i].parent != -1)        i++;    min = i;    i++;    for(; i < k; i++)    {        if( ht[i].parent == -1 && ht[i].weight < ht[min].weight )            min = i;    }    ht[min].parent = -2;    return min;}//建立哈夫曼编码,存储在指针数组中voidHuffman_Coding(void){    char   str[number];    int    p , i;    int father;    int current;    //由叶子节点到根节点,产生路径串的逆strrev    for(i = 0; i < number; i++)    {        father = HT[i].parent;        current = i;        p = 0;        while( HT[current].parent != -1 ){            if( HT[father].lchild == current )                str[p++] = '0';            else                str[p++] = '1';            current = father;            father = HT[current].parent;        }        str[p] = '\0';        strrev(str);        HC[i] = NULL;        HC[i] = (char *)malloc( (strlen(str)+1)*sizeof(char) );        if(HC[i] == NULL){            printf("HC[%d] malloc faild\n", i);            Sleep(1000);            exit(-1);        }        //HC[0] = '\0';        strcpy(HC[i], str);    }}voidoutput_HC(void){    int i;    for(i = 0; i < number; i++)        printf("'%c': %s\n", HT[i].value, HC[i]);    /**调试打印哈夫曼树,无误    for(i = 0; i < number*2-1; i++){        if(i < number)            printf("'%c': %s\n", HT[i].value, HC[i]);        printf("%d. %d %d %d %d\n",i, HT[i].parent, HT[i].lchild, HT[i].rchild, HT[i].weight);    }    **/    putchar('\n');}//建立加密文件夹,将字符转化成哈夫曼码,写入文件voidEncrypt(void){    char ch;    FILE *fp1 = NULL, *fp2 = NULL; //加密文件,原文件    fp1 = fopen( creat_Path("加密.txt"), "w+" );    if(fp1 == NULL){        printf("加密文件打开失败\n");        Sleep(1000);        exit(-1);    }    fp2 = fopen( path, "r");    if(fp2 == NULL){        printf("原文件打开失败\n");        Sleep(1000);        exit(-1);    }    while( (ch = fgetc(fp2)) != EOF ){        int i = found_Char(ch);        if(i != -1)            fputs(HC[i] , fp1);        else            fputc('#', fp1);    //假如有找不到的字符,用输出#表示    }    fclose(fp1);    fclose(fp2);}int found_Char(char ch){    int i;    for(i = 0; i < number; i++){        if(HT[i].value == ch)            return i;    }    return -1;}//从根节点遍历到叶子节点作为一个字符解码结束voidDecode(void){    FILE *fp1, *fp2;    int   root = 2*number - 2;    int   current = root;    char ch;    printf("正在进行解码...\n");    fp1 = fopen( creat_Path("解密.txt"), "w+" );    if(fp1 == NULL){        printf("解密文件打开失败\n");        Sleep(1000);        exit(-1);    }    fp2 = fopen( creat_Path("加密.txt"), "r" );    if(fp2 == NULL){        printf("加密文件打开失败\n");        Sleep(1000);        exit(-1);    }    while( (ch = fgetc(fp2)) != EOF )    {        if(ch == '0')            current = HT[current].lchild;        else if(ch == '1')            current = HT[current].rchild;        else            continue;        if(current < number){            fputc(HT[current].value, fp1);            current = root;        }    }    fclose(fp1);    fclose(fp2);    printf("解码成功\n");    Sleep(1000);}//选项三,比照源文件和解密后的文件能否一致intCheck(void){    FILE *fp_source, *fp_decode;    char ch1, ch2;    fp_source = fopen(path, "r");    fp_decode = fopen(creat_Path("解密"), "r");    while( (ch1 = fgetc(fp_decode)) != EOF ){        ch2 = fgetc(fp_source);        if(ch1 != ch2){            printf("解密字符 '%c' 与原字符 '%c' 匹配错误\n", ch1, ch2);            return 0;        }    }    return 1;    fclose(fp_source);    fclose(fp_decode);}///操作主界面voidwork(void){    char   ch;    printf("\n请输入你要进行的操作:\n");    printf("1. 编码      2. 解码     3. 校验\n");    getchar();    scanf("%c", &ch);    switch(ch)    {        case '1':            Coding();            break;        case '2':            Decode();            break;        case '3':            printf("正在进行校验...\n");            if(Check())                printf("解密文件与源文件一致\n");            else                printf("解密文件与源文件不一致\n");            Sleep(1000);            break;        default:            printf("输入有误,程序结束\n");            Sleep(1000);            return;    }    Continue();}//修改客户输入的路径,产生新的路径。char*creat_Path(char *name){    char *path2 = NULL;    int p;    path2 = (char *)malloc( 100*sizeof(char) );    path2[0] = '\0';    strcat(path2, path);    p = strlen(path2) - 1;    while( path2[p-1] != 92 )        p--;    path2[p] = '\0';    strcat(path2, name);    return path2;}

运行结果截图

  1. 生成的加密文件内容,与源文件进行比照。

对文件进行赫夫曼编码图

  1. 对加密后的01文件,进行解密后,再与原文比照:

解码文件

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 赫夫曼编码对文件进行压缩与解密

发表回复