构造哈夫曼算法

㈠ 哈夫曼树的构造算法

/*-------------------------------------------------------------------------
*Name:哈夫曼编码源代码。
*Date:2011.04.16
*Author:JeffreyHill+Jezze(解码部分)
*在Win-TC下测试通过
*实现过程：着先通过HuffmanTree()函数构造哈夫曼树，然后在主函数main()中
*自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在
*父结点左侧，则置码为0,若在右侧,则置码为1。最后输出生成的编码。
*------------------------------------------------------------------------*/
#include<stdio.h>
#include<stdlib.h>

#defineMAXBIT100
#defineMAXVALUE10000
#defineMAXLEAF30
#defineMAXNODEMAXLEAF*2-1

typedefstruct
{
intbit[MAXBIT];
intstart;
}HCodeType;/*编码结构体*/
typedefstruct
{
intweight;
intparent;
intlchild;
intrchild;
intvalue;
}HNodeType;/*结点结构体*/

/*构造一颗哈夫曼树*/
voidHuffmanTree(HNodeTypeHuffNode[MAXNODE],intn)
{
/*i、j：循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
inti,j,m1,m2,x1,x2;
/*初始化存放哈夫曼树数组HuffNode[]中的结点*/
for(i=0;i<2*n-1;i++)
{
HuffNode[i].weight=0;//权值
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
HuffNode[i].value=i;//实际值，可根据情况替换为字母
}/*endfor*/

/*输入n个叶子结点的权值*/
for(i=0;i<n;i++)
{
printf("Pleaseinputweightofleafnode%d:
",i);
scanf("%d",&HuffNode[i].weight);
}/*endfor*/

/*循环构造Huffman树*/
for(i=0;i<n-1;i++)
{
m1=m2=MAXVALUE;/*m1、m2中存放两个无父结点且结点权值最小的两个结点*/
x1=x2=0;
/*找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树*/
for(j=0;j<n+i;j++)
{
if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
}/*endfor*/
/*设置找到的两个子结点x1、x2的父结点信息*/
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;

printf("x1.weightandx2.weightinround%d:%d,%d
",i+1,HuffNode[x1].weight,HuffNode[x2].weight);/*用于测试*/
printf("
");
}/*endfor*/
/*for(i=0;i<n+2;i++)
{
printf("Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d
",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
}*///测试
}/*endHuffmanTree*/

//解码
voiddecodeing(charstring[],HNodeTypeBuf[],intNum)
{
inti,tmp=0,code[1024];
intm=2*Num-1;
char*nump;
charnum[1024];
for(i=0;i<strlen(string);i++)
{
if(string[i]=='0')
num[i]=0;
else
num[i]=1;
}
i=0;
nump=&num[0];

while(nump<(&num[strlen(string)]))
{tmp=m-1;
while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
{

if(*nump==0)
{
tmp=Buf[tmp].lchild;
}
elsetmp=Buf[tmp].rchild;
nump++;

}

printf("%d",Buf[tmp].value);
}


}


intmain(void)
{

HNodeTypeHuffNode[MAXNODE];/*定义一个结点结构体数组*/
HCodeTypeHuffCode[MAXLEAF],cd;/*定义一个编码结构体数组，同时定义一个临时变量来存放求解编码时的信息*/
inti,j,c,p,n;
charpp[100];
printf("Pleaseinputn:
");
scanf("%d",&n);
HuffmanTree(HuffNode,n);


for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1)/*父结点存在*/
{
if(HuffNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;/*求编码的低一位*/
c=p;
p=HuffNode[c].parent;/*设置下一循环条件*/
}/*endwhile*/

/*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/
for(j=cd.start+1;j<n;j++)
{HuffCode[i].bit[j]=cd.bit[j];}
HuffCode[i].start=cd.start;
}/*endfor*/

/*输出已保存好的所有存在编码的哈夫曼编码*/
for(i=0;i<n;i++)
{
printf("%d'sHuffmancodeis:",i);
for(j=HuffCode[i].start+1;j<n;j++)
{
printf("%d",HuffCode[i].bit[j]);
}
printf("start:%d",HuffCode[i].start);

printf("
");

}
/*for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
printf("%d",HuffCode[i].bit[j]);
}
printf("
");
}*/
printf("Decoding?PleaseEntercode:
");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return0;
}

http://www.cnblogs.com/Jezze/archive/2011/12/23/2299884.html

㈡ 哈夫曼算法简介

看官们建议在看我的这篇文章之前，先看一下RlE算法  这个是计算机压缩算法的入门级，如果连这个算法的思想都不清楚的，请私聊我，单独讲解

简单说一下rle=字符乘以重复数量

举个例子，aaaaaabbbbbb的rlu就是a6b6

说回哈夫曼算法

第一  统计每个字符出现的次数

第二  将出现次数最少的字符连线并求数量和

第三  重复第二步完成哈夫曼树

第四  将哈夫曼树的左边的边写上0，右边的边也写上  1 

第五  从根节点开始沿着边去将数字写在对应的字符下面

这样一个哈夫曼编码就完成了

#include <iostream>

#include <iomanip>

using namespace std;

//哈夫曼树的存储表示

typedef struct

{

    int weight;    // 权值

    int parent, lChild, rChild;    // 双亲及左右孩子的下标

}HTNode, *HuffmanTree;

// 选择权值最小的两颗树

void SelectMin(HuffmanTree hT, int n, int &s1, int &s2)

{

    s1 = s2 = 0;

    int i;

    for(i = 1; i < n; ++ i){

        if(0 == hT[i].parent){

            if(0 == s1){

                s1 = i;

            }

            else{

                s2 = i;

                break;

            }

        }

    }

    if(hT[s1].weight > hT[s2].weight){

        int t = s1;

        s1 = s2;

        s2 = t;

    }

    for(i += 1; i < n; ++ i){

        if(0 == hT[i].parent){

            if(hT[i].weight < hT[s1].weight){

                s2 = s1;

                s1 = i;

            }else if(hT[i].weight < hT[s2].weight){

                s2 = i;

            }

        }

    }

}

// 构造有n个权值（叶子节点）的哈夫曼树

void CreateHufmanTree(HuffmanTree &hT)

{

    int n, m;

    cin >> n;

    m = 2*n - 1;

    hT = new HTNode[m + 1];    // 0号节点不使用

    for(int i = 1; i <= m; ++ i){

        hT[i].parent = hT[i].lChild = hT[i].rChild = 0;

    }

    for(int i = 1; i <= n; ++ i){

        cin >> hT[i].weight;    // 输入权值

    }

    hT[0].weight = m;    // 用0号节点保存节点数量

    /****** 初始化完毕, 创建哈夫曼树 ******/

    for(int i = n + 1; i <= m; ++ i){

        int s1, s2;

        SelectMin(hT, i, s1, s2);

        hT[s1].parent = hT[s2].parent = i;

        hT[i].lChild = s1; hT[i].rChild = s2;    // 作为新节点的孩子

        hT[i].weight = hT[s1].weight + hT[s2].weight;    // 新节点为左右孩子节点权值之和

    }

}

int HuffmanTreeWPL_(HuffmanTree hT, int i, int deepth)

{

    if(hT[i].lChild == 0 && hT[i].rChild == 0){

        return hT[i].weight * deepth;

    }

    else{

        return HuffmanTreeWPL_(hT, hT[i].lChild, deepth + 1) + HuffmanTreeWPL_(hT, hT[i].rChild, deepth + 1);

    }

}

// 计算WPL（带权路径长度）

int HuffmanTreeWPL(HuffmanTree hT)

{

    return HuffmanTreeWPL_(hT, hT[0].weight, 0);

}

// 输出哈夫曼树各节点的状态

void Print(HuffmanTree hT)

{

    cout << "index weight parent lChild rChild" << endl;

    cout << left;    // 左对齐输出

    for(int i = 1, m = hT[0].weight; i <= m; ++ i){

        cout << setw(5) << i << " ";

        cout << setw(6) << hT[i].weight << " ";

        cout << setw(6) << hT[i].parent << " ";

        cout << setw(6) << hT[i].lChild << " ";

        cout << setw(6) << hT[i].rChild << endl;

    }

}

// 销毁哈夫曼树

void DestoryHuffmanTree(HuffmanTree &hT)

{

    delete[] hT;

    hT = NULL;

}

int main()

{

    HuffmanTree hT;

    CreateHufmanTree(hT);

    Print(hT);

    cout << "WPL = " << HuffmanTreeWPL(hT) << endl;

    DestoryHuffmanTree(hT);

    return 0;

}

㈢ 哈夫曼树构造算法中j<n+i是什么意思

先看一下哈夫曼树的构造规则是：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

用数据表示哈夫曼树的话，首先有n个权值点，其初始化就是从 0 到 n -1，先从这里面查找两个权值最小的结点，就是遍历一遍，把最小的值取出来。X1 和X2 要记录着两个权值在哪个位置。
然后把这两个权值加起来的和放回到数组n的位置，然后继续遍历这个数据，现在是从0 到n了，当然原来X1 和X2位置的两个点不用管，已经有父节点了。继续上述过程直到只有一个节点位置。

如 1 2 3 4 5 6构造哈夫曼树，先初始化parent 为 -1
1 2 3 4 5 6
parent -1 -1 -1 -1 -1 -1
先从上述中选取两个权值最小的节点 1 和 2，构造树变为3，放到数组6的位置，原权值序列变为：
1 2 3 4 5 6 3
parent 6 6 -1 -1 -1 -1 -1
继续选取 两个最小权值且parent为-1的点。找到3 和 3，放到数组7的位置，权值序列变为：
1 2 3 4 5 6 3 6
parent 6 6 7 -1 -1 -1 7 -1
继续选取 两个最小权值且parent为-1的点。找到4 和5，到数组8的位置，权值序列变为：
1 2 3 4 5 6 3 6 9
parent 6 6 7 8 8 -1 7 -1 -1
继续选取 两个最小权值且parent为-1的点。找到6 和6，到数组9的位置，权值序列变为：
1 2 3 4 5 6 3 6 9 12
parent 6 6 7 8 8 9 7 9 -1 -1
继续选取 两个最小权值且parent为-1的点。找到9 和12，到数组10的位置，权值序列变为：
1 2 3 4 5 6 3 6 9 12 21
parent 6 6 7 8 8 9 7 9 10 10 -1
结束
所以你说的j < n + i，由于每次选取两个权值的点权值和做为新的节点放在数组后面，当然下一次循环的时候要多一次循环。
X1 和X2要记录下选择两个权值，将其父节点的位置设置为新的权值点位置。

㈣ 哈夫曼树的构造是什么

哈夫曼树构造：结构化的Huffman算法生成的Huffman树子树都是有序的，所以一般生成Huffman树时都为节点排序，即使这样结果也不唯一。

哈夫曼静态编码：它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。

历史

1951年，哈夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。

导师罗伯特·法诺（Robert Fano）出的学期报告题目是：查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。

哈夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。

1952年，于论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Rendancy Codes）中发表了这个编码方法。

㈤ 哈夫曼的如何构造

然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方法就是哈夫曼算法。一般的数据结构的书中都可以找到其描述： 重复二和三两步，直到集合F中只有一棵二叉树为止。
用C语言实现上述算法，可用静态的二叉树或动态的二叉树。若用动态的二叉树可用以下数据结构： struct tree{
float weight; /*权值*/
union{
char leaf; /*叶结点信息字符*/
struct tree *left; /*树的左结点*/
};
struct tree *right; /*树的右结点*/
};
struct forest{ /*F集合，以链表形式表示*/
struct tree *ti; /* F中的树*/
struct forest *next; /* 下一个结点*/
};
例：若字母A，B，C，D出现的概率为：0.75,0.54,0.28,0.43；则相应的权值为：75，54，28，43。
构造好哈夫曼树后，就可根据哈夫曼树进行编码。例如：上面的字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。例如：a,b,c,d的编码为：0，10，110，111，对于编码串：1010就翻译为bb。刚才进行哈夫曼编码的规则是从根结点到叶结点（包含原信息）的路径，向左孩子前进编码为0，向右孩子前进编码为1，当然你也可以反过来规定。

㈥ 请描述哈夫曼算法，并用图描述构造哈夫曼树的过程。

1. 根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn}，其中每棵二叉树Ti中只有一个带权wi的根结点，左右子树均空。
2. 在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3. 在F中删除这两棵树，并将新的二叉树加入F中。
4. 重复前两步（2和3），直到F中只含有一棵树为止。该树即为哈夫曼树
帮你贴过来了，网络
这东西实际用法是可以减少树的访问次数，因为他把频率高的点放在比较靠近根节点的地方，频率低的在下面，这样访问速度快。举个例子，比如四个点，他们的使用频率分别是1,2,3,4，然后构成的树就是
4
0 3
0 2
0 1
补：打不出树形结构...