哈夫曼编码压缩原理：由于每个字符在内存中都是以ASCII码进行存储，所以每个字符都占用了八个01位，利用哈夫曼树对每个字符进行01编码，根据字符在文章中出现的频率调整01串长度，出现频率高的字符在哈夫曼树中的权重大，编码后01串短，从而使得最终计算出的平均编码长度小于8，在本代码中平均编码长度约为4.72，压缩率约为59%，从而达到压缩文本的目的。



// HuffmanEncode.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<string>
int length;  //文章长度
//定义结构体统计单个字符出现次数
struct Char_Frequency
{
    char c;
    int Frequency;
};
Char_Frequency a[10000];   //建立结构体数组 存储每个字符的出现次数
                           /*从文本文件中统计各字符出现次数*/
void Char_Probability_Fromfile(FILE *fp)
{
    length = 0;
    for (int i = 0; i < 100; i++)   //对结构体数组初始化
    {
        a[i].c = NULL;
        a[i].Frequency = 0;
    }
    char ch;
    while (fscanf(fp, "%c", &ch) == 1)
    {
        length++;
        int i = 0, flag = 0;
        while (a[i].c != NULL)
        {
            if (a[i].c == ch)
            {
                a[i].Frequency++;
                flag = 1;
            }
            i++;
        }
        if (!flag)
        {
            a[i].c = ch;
            a[i].Frequency = 1;
        }
    }

}
/*哈夫曼树存储结构*/
typedef struct {
    int weight;
    char c;
    int lchild;
    int rchild;
    int parent;
}HTNODE;
typedef HTNODE HuffmanT[10000];
HuffmanT T;
/*初始化哈夫曼树*/
void InitHT()
{
    for (int i = 0; i < 100; i++)
    {
        T[i].c = NULL;
        T[i].lchild = -1;
        T[i].rchild = -1;
        T[i].parent = -1;
        T[i].weight = NULL;
    }
}
/*为哈夫曼树加载权值*/
void InputW(int n)
{
    for (int i = 0; i < n; i++)
    {
        T[i].c = a[i].c;
        T[i].weight = a[i].Frequency;
    }
    for (int i = 0; i < n; i++)
    {
        printf("权重初始为：%c %ld\n", T[i].c, T[i].weight);
    }
}
/*找到两个最小权值节点*/
void SelectMin(int n, int *p1, int *p2)
{

    int i, j;
    for (i = 0; i < n; i++)
    {
        if (T[i].parent == -1)
        {
            *p1 = i;
            break;
        }
    }
    for (j = i + 1; j < n; j++)
    {
        if (T[j].parent == -1)
        {
            *p2 = j;
            break;
        }
    }
    for (i = 0; i < n; i++)
    {
        if ((T[*p1].weight > T[i].weight) && (T[i].parent == -1) && (*p2 != i))
            *p1 = i;
    }
    for (j = 0; j < n; j++)
    {
        if ((T[*p2].weight > T[j].weight) && (T[j].parent == -1) && (*p1 != j))
            *p2 = j;
    }
}
/*哈夫曼树构造算法,n为有权值的节点个数*/
void CreateHT(int n)
{
    int i, p1, p2;
    InitHT();
    InputW(n);
    for (i = n; i < 2 * n; i++)
    {
        SelectMin(i, &p1, &p2);
        T[p1].parent = T[p2].parent = i;
        T[i].lchild = p1;
        T[i].rchild = p2;
        T[i].weight = T[p1].weight + T[p2].weight;
    }

}
/*哈夫曼编码表的存储结构*/
typedef struct {
    char ch;
    char bits[1000];
}CodeNode;
typedef CodeNode HuffmanCode[100000];
HuffmanCode H;
/*哈夫曼编码算法实现*/
void CharSetHuffmanEncoding(int n)
{
    int c, p, i;
    char cd[10000];
    int start;
    cd[n] = '\0';
    for (i = 0; i < n; i++)
    {
        H[i].ch = T[i].c;
        start = n;


        c = i;
        while ((p = T[c].parent) >0)
        {
            cd[--start] = (T[p].lchild == c) ? '0' : '1';
            c = p;
        }
        strcpy(H[i].bits, &cd[start]);
    }
}
char copy[100000000];
/*编码写入文件*/
void Encode(int n)
{
    FILE *fp = fopen("D:\\test2.txt", "r");
    FILE *fp2 = fopen("D:\\test2w.txt", "w");
    char ch;
    while (fscanf(fp, "%c", &ch) == 1)
    {
        for (int i = 0; i < n; i++)
        {
            if (H[i].ch == ch)
            {
                fprintf(fp2, "%s", H[i].bits);
                strcat(copy, H[i].bits);
            }
        }
    }
}
/*解码写入文件*/
void Decode(int n)
{

    FILE *fp = fopen("D:\\decode.txt", "w");
    int root,p, i, j = 0;
    p = root = 2 * n - 1;
    for (i = 0; i < strlen(copy); i++)
    {
        if (copy[i] == '0')
        {
            p = T[p].lchild;
        }
        else if (copy[i] == '1')
        {
            p = T[p].rchild;
        }
        if (T[p].lchild == -1 && T[p].rchild == -1)
        {

            fprintf(fp, "%c", T[p].c);
            p = root;
        }
    }


}
/*求压缩率*/
void Encode_Rate(int n)
{
    float WPL=0;
    for (int i = 0; i < n; i++)
    {
        WPL += (float)strlen(H[i].bits)*((float)((float)a[i].Frequency / (float)length));
    }

    printf("压缩率为:    %f\n", WPL/8.00);

}




int main()
{
    FILE *fp = fopen("D:\\test2.txt", "r");
    Char_Probability_Fromfile(fp);
    int i = 0;
    while (a[i].c != NULL)
    {
        printf("%c %d      %d", a[i].c, a[i].c, a[i].Frequency);
        printf("\n");
        i++;
    }
    printf("i为：%d\n", i);

    CreateHT(i);
    int n = 0;
    while (T[n].weight != NULL)
    {
        printf("序号：%d  %c 权重：%d  父母：%d 左儿子：%d  右儿子：%d \n", n, T[n].c, T[n].weight, T[n].parent, T[n].lchild, T[n].rchild);
        n++;
    }
    printf("-------\n");

    CharSetHuffmanEncoding(i);
    n = 0;

    Encode(i);
    Decode(i);

    printf("\n");
    Encode_Rate(i);





    return 0;
}





附上运行结果图片：



压缩译码前：



压缩译码后：



译码后，恢复原文：

现在我们大家在网络上看到的视频，受限于带宽和服务器，视频网站上的视频其实都是经过压缩才最终被我们看到的。如果单纯传输视频文件，数据量会非常恐怖，以常见的1920*1080的30帧视频为例，其一帧画面中所包含的信息量就为；
1920*1080=2073600个像素
每个像素越是三字节，再乘以30，就是一亿八千多万的字节，换算成MB/s的话就是177MB/s，这还是没有计算声音信息的情况下，这显然不是我们的网络可以承载的数据量，如果可以将视频中无用的信息剔除，就可以大大提升视频的效率。所以，我们需要来压缩视频。
视频的压缩方式也分为帧内编码和帧间压缩编码，而我们看到的网络视频多是由帧间编码压缩，互联网目前最常见的帧间压缩视频编码格式是H.264。在H.264压缩标准中I帧、P帧、B帧用于表示传输的视频画面。
I帧
I帧又叫做帧内编码帧，它带有全部的独立信息且可不需要参考其它的帧独立进行解码，视频序列中的第一个帧始终都是I帧，因为它是关键帧。
P帧
又叫帧间预测编码帧，它的解码需要参考前一帧画面（前一帧有可能是I、P帧）。视频中的每一个像素都有它对应的信息，而下一帧中的像素相比于上一帧有部分会有变化而部分没有，没有变化的部分会直接复制上一帧的信息，而有变化的部分则需要通过解计算得出。与I帧相比，P帧通常占用更少的数据量。
B帧
B帧又称叫双向预测编码帧，顾名思义它不仅会像I帧一样参考前一帧的信息，也会参考下一帧通过前后画面的与本帧数据的叠加取得最终的画面。B帧压缩率高，但是对解码性能要求较高。
我们所看到的视频就是由这些帧加上计算得出的，但是其实这种方式有一个很大的弊端，就是帧信息全部靠计算得出，如果播放器性能过低，或者画面中有大量随机移动的无法预测的信息是就会出现画质急剧下降和卡顿的问题。
想要避免这个问题，我们可以使用可变码率（VBR）的方式,顾名思义，在一段视频中码率是动态变化的，在比较复杂、随机运动的场景下（打斗、舞蹈等）提高码率，在简单的场景下降低码率，合理的利用资源，同时也平衡了画质和体积。
除此之外还有恒定码率（CBR）和恒定质量（CRF）的方式，顾名思义CBR就是视频的全程并不会改变码率而是以渲染前的预设决定；而CRF就是在渲染前固定一个视频的质量，它也会动态改变视频的码率，但相比VBR不同的是它是以画质为第一优先级，最终的文件大小不受控制。
而直播的情况和视频也略有区别，直播相当于实时串流，为了让观众获得更流畅的观感往往就会使用渲染速度快但是画面质量相对较低的方式，而视频制作到上传是有一段时间的，制作者可以选择需要的时间更长但是最终得出画质更好的渲染方式，所以相同的编码格式和码率、分辨率的情况下网络视频和直播的画质可能也会天差地别
码率
码率的常见单位为Mbp/s，其实就是Mbit/s的意思，也就是说一秒钟8Mbp/s的视频将会产生1MB的数据（未计算音频数据）。高码率的视频会越接近未压缩过的画质，但是过高的码率也会带来数据冗余的问题，其实编码的核心就是如何在较小的文件体积下保留更多的画面和声音信息。
视频在经过编码压缩时可能会降低码率，过低的码率会造成画面中出现马赛克，既画面中一些区域的色阶劣化，而造成颜色混乱导致看不清细节的情况（如新闻中犯罪嫌疑人的头像经常使用）。这是因为每个像素都需要保留相应的信息，而降低码率后也相应的降低了其保留的信息，而没有信息的像素只能向周围的像素共享信息，这样就会显得颜色混乱，画面惨不忍睹。但是在码率恒定的情况下，我们可以通过降低分辨率也就是每帧画面中像素数量来规避马赛克，因为像素越少，就越不需要共享像素来渲染。
码率其实也不是视频中单独存在的个体，它也会受分辨率、编码格式的影响。比如H.264的进阶版本H.265，效率很高，在高分辨率下可以比H.264节约很多带宽，但同时也会带来更高的解码压力。而码率和分辨率的配合也相当重要，高分低码会造成画面中的马赛克；而高码低分则会丢失大量细节，导致AV画质。所以如何在文件体积、解码难易度和画面质量间取舍，就只能看你自己了。

	

引言
在上一期，我们介绍了什么是哈夫曼树以及哈夫曼树的构建过程，本期我们接着介绍哈夫曼树的用途。
字符编码压缩
哈夫曼树的应用很广，哈夫曼编码就是其在电讯通信中的应用之一。广泛地用于数据文件压缩的十分有效的编码方法，其压缩率通常在 20% ～ 90% 之间。
在电讯通信业务中，通常用二进制编码来表示字母或其他字符，并用这样的编码来表示字符序列。
在计算机当中，因为计算机不是人，不能识别图像、声音、视频等内容，对于计算机来讲，它只能认识二进制的 0 和 1 ，在数字电子电路中，逻辑门的实现直接应用了二进制，因此现代的计算机和依赖计算机的设备里都用到二进制。
我们在计算机上看到的一切的图像、声音、视频等内容，都是由二进制的方式进行存储的。
简单来讲，我们把信息转化为二进制的过程可以称之为编码，在计算机的世界里，编码有很多种格式，比如我们常见的：ASCII 、 Unicode 、 GBK 、 GB2312 、 GB18030 、 UTF-8 、 UTF-16 等等。
编码方式从长度上来分大致可以分为两个大类：
定长编码：定长仅表明段与段之间长度相同，但没说明是多长。
变长编码：变长就是段与段之间的长度不相同，同样也不定义具体有多长。
在最初的设计中， ASCII 编码就是采用的定长编码的方案，使用定长一字节来表示一个字符。
举个栗子，假如我们对 「hello」 进行编码，使用定长编码，为了方便，采用了十进制，主要是因为我懒，原理与二进制是一样的。
字符
编码
h
00
e
01
l
02
o
03
假设我们现在有个文件，内容是 00000001 ，假如定长 2 位(这里的位指十进制的位)是唯一的编码方案，用它去解码，就会得到 「hhhe」 (可以对比上面的编码， 00 代表 h ，所以前 6 个 0 转化成 3 个 h ，后面的 01 则转化成 e )。
但是，如果定长 2 位不是唯一的编码方案呢？如上图中的定长 4 位方案，如果我们误用定长 4 位去解码，结果就只能得到「he」( 0000 转化为 h ， 0001 转化为 e )
随着时代的发展，不仅老美要对他们的英文进行编码，我们中国人也要对汉字进行编码，而早期的 ASCII 码的方案只有一个字节，对我们汉字而言是远远不够的，所以在我们的汉字编码方案 GB2312 中，汉字是使用两个字节来表示的(这也是迫不得已的事，一字节压根不够用) 。
再多说一句，实际上我们的 GB2312 是一种变长的编码方案，主要是为了兼容一个字节的 ASCII 码。
随着计算机在全世界的推广，各种编码方案都出来了，彼此之间的转换也带来了诸多的问题。采用某种统一的标准就势在必行了，于是乎天上一声霹雳， Unicode 粉墨登场！
不过 Unicode 对于只需要使用到一个字节的 ASCII 码来讲，让他们使用 Unicode ，多少还是不是很愿意的。
比如 「he」 两个字符，用 ASCII 只需要保存成 6865 ( 16 进制)，现在则成了 00680065 ，前面多的那两个 0 (用作站位) ，基本上可以说是毫无意义，用 Unicode 编码的文本，原来可能只有 1KB 大小，现在要变成 2KB ，体积成倍的往上涨。
最终， Unicode 编码方案逐渐演化成了变长的 UTF-8 编码方案，并且 UTF-8 是可以和 ASCII 码进行兼容。
UTF-8 因为能兼容 ASCII 而受到广泛欢迎，但在保存中文方面，要用 3 个字节，有的甚至要 4 个字节，所以在保存中文方面效率并不算太好，与此相对， GB2312 ， GBK 之类用两字节保存中文字符效率上会高，同时它们也都兼容 ASCII ，所以在中英混合的情况下还是比 UTF-8 要好，但在国际化方面及可扩展空间上则不如 UTF-8 了。
所以如果有进军国际的想法，那么最好还是使用 UTF-8 编码。
哈弗曼编码
哈弗曼编码是一种不定长的编码方式，是由麻省理工学院的哈夫曼博所发明，这种编码方式实现了两个重要目标：
任何一个字符编码，都不是其他字符编码的前缀。
信息编码的总长度最小。
干巴巴的，还是接着举例子：
如果我们对 「ABACCDA」 进行编码，假设 A, B, C, D 的编码分别为 00, 01,10, 11。
那么 「ABACCDA」 编码后的结果是 「00010010101100」 (共 14 位)，我们解码的时候只需要每两位进行拆分，就可以恢复编码前的信息了。
那我们如果用哈弗曼编码的方式进行编码呢？
第一件事情是要确定每个字母的权值(出现频率)， 「ABACCDA」 这个字符串中 A, B, C, D 的权值(出现的频率)分别为 0.43, 0.14, 0.29, 0.14 。
有了权值，我们可以构造一个哈弗曼树了，感兴趣的同学可以自己画一下，下面这个是我画的：
编码的结果就显而易见了：A：0， C：10， B：110， D：111 。
刚才那个 「ABACCDA」 编码后的结果就是 「0110010101110」 (共 13 位)。
上面我们知道了哈夫曼编码如何编码，那么我们拿到了一个经过哈弗曼编码后的代码，如何进行译码工作呢？
首先还是要知道每个字母的权重是多少，然后画出来这个哈弗曼树，接下来，就可以对照着这个哈弗曼树进行译码工作了。
在译码的过程中，若编码是 「0」 ，则向左走。若编码是 「1」 ，则向右走，一旦到达叶子结点，则译出一个字符。然后不停的重复，直到这个编码的结束，就是我们需要的原内容了。
参考
https://www.cnblogs.com/wkfvawl/p/9783271.html
https://my.oschina.net/goldenshaw/blog/307708
感谢阅读

问题： 给定N个带权值的叶子节点，如何构造出一个带权路径最小的二叉树？
答：哈夫曼树（Huffman Tree）
       在数据结构理论中，哈夫曼树又称为最优树，相关的知识点还有哈弗曼编码等。在正式介绍哈夫曼树之前，需要知道下面的知识点：
（1）节点路径
       按照规定，将树中一个节点到另一个节点所经历的分支，称为节点路径，比如上图中节点A到节点E的路径为ABE。
（2）路径长度
       根据上述“节点路径”的定义，将路径上的分支总数称为路径长度，比如上图中节点A到节点E的路径长度为2。
（3）节点的带权路径长度
       根据上述“节点路径”和“路径长度”的定义，将从根节点到某节点的路径长度和节点权值的乘积，称为节点的带权路径长度。比如上图中节点A到节点D的路径长度为2，权值为8，则带权路径长度为2x8=16。
（4）树的带权路径长度
        根据上述“节点的带权路径长度”的定义，将树中所有叶子节点的带权路径长度，称为树的带权路径长度。比如上图中，三个叶子节点C、D、E，对应的路径长度分别为1、2、2，对应的权值分别为4、8、3，则树的带权路径长度为：
将上述概念形式化，可以使用下面的公式进行计算：
其中了表示路径长度，w表示权值，n表示叶子节点个数。
总结：
      上文梳理了理解哈夫曼树所必须的基本概念，包含节点路径和路径长度等，下文将会讲解如何构造哈夫曼树。