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

理论

赫夫曼树

先有赫夫曼树，才有赫夫曼编码。所以，首先简单介绍一下什么是赫夫曼树。

假设一共五个叶子节点，分别是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 1e4

char *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);    //建立哈夫曼编码HC
void   output_HC(void);         //打印编码表
void   Encrypt(void);           //生成加密文件
void   Decode(void);            //生成解密文件23
char*  creat_Path(char *name);  //生成路径名称
int get_Min(HuffmanTree ht, int k);//得到前k个无父节点的最小权重节点
int found_Char(char ch);        //查找输入字符所对应的HC下标
int Check(void);                //将解密文件与源文件比较
void Continue(void);            //输出是否继续操作对话框

int
main()
{
    printf("---------------欢迎进入文件编码与解码程序---------------\n");
    printf("                                    ----by 方宁 20.05.09\n\n");
    printf("请输入你所需要进行操作的文件路径：\n");

    scanf("%s", path);      //主函数中获取一次操作路径
    work();
    return 0;
}

//清屏，和重新调用主菜单
void
Continue(void)
{
    char    str[5];
    printf("是否继续进行操作?(yes/no)\n");
    scanf("%s", str);
    if(strcmp(str, "yes") == 0){
        system("cls");
        work();
    }
    else{
        printf("欢迎您的使用，再见\n");
        Sleep(1000);
    }
}

//对指定文件进行哈夫曼编码
void
Coding(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-1
HuffmanTree
build_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;
}

int
get_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;
}

//建立哈夫曼编码，存储在指针数组中
void
Huffman_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);
    }
}

void
output_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');
}

//建立加密文件夹，将字符转化成哈夫曼码，写入文件
void
Encrypt(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;
}

//从根节点遍历到叶子节点作为一个字符解码结束
void
Decode(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);
}

//选项三，对比源文件和解密后的文件是否一致
int
Check(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);
}

///操作主界面
void
work(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文件，进行解密后，再与原文对比：
解码文件
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,311评论 6赞 481
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,339评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 152,671评论 0赞 342
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,252评论 1赞 279
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,253评论 5赞 371
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,031评论 1赞 285
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,340评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,973评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,466评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,937评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,039评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,701评论 4赞 323
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,254评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,259评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,485评论 1赞 262
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,497评论 2赞 354
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,786评论 2赞 345