哈夫曼编码
概念：
哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。
哈夫曼编码的具体步骤如下：
1）将信源符号的概率按减小的顺序排队。
2）把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在右边，直到 最后变成概率１。
3）画出由概率１处到每个信源符号的路径，顺序记下沿路径的０和１，所得就是该符号的霍夫曼码字。
4）将每对组合的左边一个指定为0，右边一个指定为1（或相反）。
特点
Huffman码具有以下3个特点：
1.Huffman码的编码方法保证了概率大的符号对应短码，概率小的符号对应长码，而且短码得到充分利用。
2.每次缩减信源的最后两个码字总是最后一位码元不同，前面各位码元相同(二元编码情况)。
3.每次缩减信源的最长两个码字有相同的码长。
这三个特点保证了所得的Huffman码一定是最佳码。
哈夫曼编码
1.根据步骤截取核心代码
2.验证新符号位置对结果的影响，靠上（>=）比靠下（>）好（0.4,0.2,0.2,0.1,0.1）
3.事例2（0.20，0.19,0.18,0.17,0.15,0.10,0.01）做对比(平均码长，编码效率)
代码：
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <ctype.h>
#include <vector>
#include <math.h>
#include <iomanip>
#include <graphics.h>
#include <conio.h>
#include <windows.h>
#include <fstream>
#include <string>
using namespace std;
struct Node
{
int num;
double p,pa;
int L;
int x[100];
};
Node box[20];
int M;
double H,L,K,w;
int exit1;
void draw()
{
int i,j,k,posx,posy;
cleardevice();
setlinecolor(BLACK);
settextcolor(BLACK);
for(i=1;i<=M;i++){
posx=10;
posy=M*50;
k=50;
for(j=box[i].L-1;j>=0;j--){
if(box[i].x[j]==1){
line(posx,posy,posx+k,posy-k);
outtextxy(posx+k/2,posy-k/2+2, _T("1"));
posx+=k;
posy-=k;
}
else{
line(posx,posy,posx+k,posy);
outtextxy(posx+k/2-4,posy+1, _T("0"));
posx+=k;
}
k/=1.05;
}
}
}
void initialization()
{
int i,j,k;
initgraph(501,550,SHOWCONSOLE);
setbkcolor(WHITE);
cleardevice();
M=8;
box[1].p=0.4;
box[2].p=0.18;
box[3].p=0.1;
box[4].p=0.1;
box[5].p=0.07;
box[6].p=0.06;
box[7].p=0.05;
box[8].p=0.04;
}
void carry()
{
int i,j,k,n;
initialization();
exit1=0;
while(exit1==0){
for(i=1;i<=M;i++){
box[i].num=pow(2,i);
box[i].pa=box[i].p;
box[i].L=0;
}
for(i=M-1;i>=1;i--){
k=box[i].num;
for(j=M;j>=1;j--){
if(pow(2,j)<=k){
box[j].x[box[j].L]=0;
box[j].L++;
k-=pow(2,j);
}
else if(k==0){
break;
}
}
k=box[i+1].num;
for(j=M;j>=1;j--){
if(pow(2,j)<=k){
box[j].x[box[j].L]=1;
box[j].L++;
k-=pow(2,j);
}
else if(k==0){
break;
}
}
box[i].p+=box[i+1].p;
box[i].num+=box[i+1].num;
k=0;
for(j=1;j<i;j++){
if(box[i].p>=box[j].p){
//!!!概率相等时 >=为新符号在上 > 为新符号在下
k=1;
break;
}
}
if(k==1){
box[11].num=box[i].num;
box[11].p=box[i].p;
for(n=i-1;n>=j;n--){
box[n+1].num=box[n].num;
box[n+1].p=box[n].p;
}
box[j].num=box[11].num;
box[j].p=box[11].p;
}
}
for(i=1;i<=M;i++){
box[i].p=box[i].pa;
}
H=0;
for(i=1;i<=M;i++){
H-=box[i].p*log(box[i].p)/log(2);
}
L=0;
for(i=1;i<=M;i++){
L+=box[i].p*box[i].L;
}
K=0;
for(i=1;i<=M;i++){
K+=pow(0.5,box[i].L);
}
w=0;
for(i=1;i<=M;i++){
w+=(box[i].L-L)*(box[i].L-L)*box[i].p;
}
for(i=1;i<=M;i++){
cout<<"编号"<<'x'<<i;
cout<<" 概率"<<box[i].p;
cout<<" 码长"<<box[i].L;
cout<<" 码字";
for(j=box[i].L-1;j>=0;j--){
cout<<box[i].x[j];
}
cout<<endl;
}
cout<<"熵:"<<H<<endl;
cout<<"平均码长"<<L<<endl;
cout<<"编码效率"<<H/L*100.0<<'%'<<endl;
cout<<"克拉夫特值"<<K<<endl;
if(K<=1)cout<<"唯一可译码"<<endl;
else cout<<"非唯一可译码"<<endl;
cout<<"码字方差"<<w<<endl;
draw();
cout<<endl<<"按任意键继续";
_getch();
system("cls");
cout<<"请输入码数(3-10):"<<endl;
M=0;
while(M<3||M>10){
cin>>M;
}
cout<<"码数:"<<M<<endl;
for(i=1;i<=M;i++){
cout<<"请输入第"<<i<<"个码数的概率(0-1)(不必排序):"<<endl;
box[i].p=0;
while(box[i].p<=0||box[i].p>=1){
cin>>box[i].p;
}
}
for(i=0;i<M;i++){
for(j=1;j<M-i;j++){
if(box[j].p<box[j+1].p){
box[11].p=box[j+1].p;
box[j+1].p=box[j].p;
box[j].p=box[11].p;
}
}
}
system("cls");
}
}
int main()
{
carry();
}
演示视频：
赫夫曼编码，排序，取最小的两个，合并，再排序，循环。因为编码的要求，合并后的新符号需要记得是哪几个旧符号合并得来的，因为是循环的过程。直接用数组记编号，我在纸上或者说脑子里模拟不来，太麻烦。我之后在食堂，想到给每个旧符号一个初始标志数是2,4,8,16这样（也可以从1开始，1,2,4,8...），概率合并的同时，标志数相加合并，这样很明显了，不同新标志可以用一个简单的函数分解出所有唯一的旧标志数。这还是小学奥数的问题：用不同面值各一张的钱币表示所有面值的数，就是1元，2元，4元，8元这样表示。这个问题解决完，唯一的问题就是编完后的码要反过来读就好了。另外，新符号的位置影响结果也挺有趣，老师ppt和我的模拟都展示了，但并没有证明哦，有机会可以试试。
如果编多（m）元码，就是取最小的m个，合并，其他没变化了，不算复杂的改变。
多(m)元码的编码步骤
(1) 按概率从大到小排序。
(2) 挑出概率最小的m个信源符号，分别赋予码符号，并将概率的和赋予合并后的新符号， 得到。
(3) 按相同步骤计算。
(4) 直到最后一级，倒序读出码字。
问题：在码树图中，某些分枝从第一级就被砍掉，从而造成平均码长偏长的情况。
解决办法：从最后一级缩减信源倒着排，保证最后一级有m个符号。
为了保证最后一级有m个符号，信源符号数n必须满足下列条件：n=k(m-1)+m。
k表示缩减的次数，必须为整数。若不满足，补以概率为0的量。
多元码结果展示，需要补充概率为0的新符号：
代码：
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <ctype.h>
#include <vector>
#include <math.h>
#include <iomanip>
#include <graphics.h>
#include <conio.h>
#include <windows.h>
#include <fstream>
#include <string>
using namespace std;
struct Node
{
int num;
double p,pa;
int L;
int x[100];
};
Node box[101];
int M;
double H,L,K,w;
int exit1;
int Y;
void draw()
{
int i,j,k,posx,posy;
double w,pi=3.141592653;
char s[10];
cleardevice();
setlinecolor(BLACK);
settextcolor(BLACK);
for(i=1;i<=M;i++){
posx=10;
posy=250;
k=80;
for(j=box[i].L-1;j>=0;j--){
w=(-60.0+120.0/double(Y-1)*double(box[i].x[j]))*pi/180.0;
line(posx,posy,posx+k*cos(w),posy+k*sin(w));
sprintf(s, "%d", box[i].x[j]);
outtextxy(posx+k*cos(w)/2-2,posy+k*sin(w)/2+4,s);
posx+=k*cos(w);
posy+=k*sin(w);
k/=1.1;
}
}
}
void initialization()
{
int i,j,k;
initgraph(501,550,SHOWCONSOLE);
setbkcolor(WHITE);
cleardevice();
M=8;Y=2;
box[1].p=0.4;
box[2].p=0.18;
box[3].p=0.1;
box[4].p=0.1;
box[5].p=0.07;
box[6].p=0.06;
box[7].p=0.05;
box[8].p=0.04;
}
void carry()
{
int i,j,k,n,t=0;
double m;
initialization();
exit1=0;
while(exit1==0){
for(i=1;i<=M;i++){
box[i].num=pow(2,i);
box[i].pa=box[i].p;
box[i].L=0;
}
for(i=M-Y+1;i>=1;i-=(Y-1)){
for(n=i;n<i+Y;n++){
k=box[n].num;
for(j=M;j>=1;j--){
if(pow(2,j)<=k){
box[j].x[box[j].L]=n-i;
box[j].L++;
k-=pow(2,j);
}
else if(k==0){
break;
}
}
}
for(n=1;n<Y;n++){
box[i].p+=box[i+n].p;
box[i].num+=box[i+n].num;
}
k=0;
for(j=1;j<i;j++){
if(box[i].p>=box[j].p){
//!!!概率相等时 >=为新符号在上 > 为新符号在下
k=1;
break;
}
}
if(k==1){
box[100].num=box[i].num;
box[100].p=box[i].p;
for(n=i-1;n>=j;n--){
box[n+1].num=box[n].num;
box[n+1].p=box[n].p;
}
box[j].num=box[100].num;
box[j].p=box[100].p;
}
}
M-=t;
for(i=1;i<=M;i++){
box[i].p=box[i].pa;
}
H=0;
for(i=1;i<=M;i++){
H-=box[i].p*log(box[i].p)/log(double(Y));
}
L=0;
for(i=1;i<=M;i++){
L+=box[i].p*box[i].L;
}
K=0;
for(i=1;i<=M;i++){
K+=pow(1.0/double(Y),box[i].L);
}
w=0;
for(i=1;i<=M;i++){
w+=(box[i].L-L)*(box[i].L-L)*box[i].p;
}
for(i=1;i<=M;i++){
cout<<"编号"<<'x'<<i;
cout<<" 概率"<<box[i].p;
cout<<" 码长"<<box[i].L;
cout<<" 码字";
for(j=box[i].L-1;j>=0;j--){
cout<<box[i].x[j];
}
cout<<endl;
}
cout<<"熵:"<<H<<endl;
cout<<"平均码长"<<L<<endl;
cout<<"编码效率"<<H/L/(log(double(2))/log(2))*100.0<<'%'<<endl;
cout<<"克拉夫特值"<<K<<endl;
if(K<=1)cout<<"唯一可译码"<<endl;
else cout<<"非唯一可译码"<<endl;
cout<<"码字方差"<<w<<endl;
draw();
cout<<endl<<"按任意键继续";
_getch();
system("cls");
cout<<"请输入码数(3-100):"<<endl;
M=0;
while(M<3||M>100){
cin>>M;
}
cout<<"请输入编写几元码(2-10):"<<endl;
Y=0;
while(Y<3||Y>10){
cin>>Y;
}
for(t=0;t<M;t++){
m=double(M+t-Y)/double(Y-1);
if(m==int(m)){
break;
}
else{
box[M+t+1].p=0;
}
}
cout<<"码数:"<<M<<endl;
cout<<Y<<"元码"<<endl;
cout<<"自动补充"<<t<<"个概率为0的符号"<<endl;
for(i=1;i<=M;i++){
cout<<"请输入第"<<i<<"个码数的概率(0-1)(不必排序):"<<endl;
box[i].p=0;
while(box[i].p<=0||box[i].p>=1){
cin>>box[i].p;
}
}
M+=t;
for(i=0;i<M;i++){
for(j=1;j<M-i;j++){
if(box[j].p<box[j+1].p){
box[100].p=box[j+1].p;
box[j+1].p=box[j].p;
box[j].p=box[100].p;
}
}
}
system("cls");
}
}
int main()
{
carry();
}
ppt：
「艾尔登法环」梅琳娜手办开订 立体手办▪
万代「艾尔登法环」白狼战鬼手办开订 立体手办▪
「夏目友人帐」猫咪老师粘土人开订 立体手办▪
「五等分的新娘∬」中野三玖·白无垢版手办开订 立体手办▪
「海贼王」乌索普Q版手办开订 立体手办▪
良笑社「初音未来」新手办开订 立体手办▪
「黑岩射手DAWN FALL」死亡主宰手办开订 立体手办▪
「盾之勇者成名录」菲洛手办登场 立体手办▪
「魔法少女小圆」美树沙耶香手办开订 立体手办▪
「咒术回战」七海建人粘土人登场 立体手办▪
「五等分的新娘」中野二乃白无垢手办开订 立体手办▪
「为美好的世界献上祝福！」芸芸粘土人开订 立体手办▪
「公主连结 与你重逢」六星可可萝手办开订 立体手办▪
「女神异闻录5」Joker雨宫莲手办开订 立体手办▪
「间谍过家家」约尔・福杰粘土人登场 立体手办▪
「街角魔族 2丁目」吉田优子手办开订 立体手办▪
「火影忍者 疾风传」旗木卡卡西·暗部版粘土人登场 立体手办▪
「佐佐木与宫野」宫野由美粘土人开订 立体手办▪
「盾之勇者成名录」第2季拉芙塔莉雅手办开订 立体手办▪
「咒术回战」两面宿傩Q版坐姿手办开订 立体手办▪
「DATE·A·BULLET」时崎狂三手办开订 立体手办▪
「狂赌之渊××」早乙女芽亚里粘土人开订 立体手办▪
「魔道祖师」魏无羨粘土人开订 立体手办▪
「新·奥特曼」奥特曼手办现已开订 立体手办▪
扫码关注我们