hongchh 发表于 2016-8-16 17:08:55

一个简单的Huffman编码实现

本帖最后由 hongchh 于 2016-8-16 17:26 编辑

问题描述：
有一组字符集{c1, c2, …, cn}，在使用这组字符集的过程中，通过统计发现每个字符都有其相应的出现频率，假设对应的频率为{f1, f2, …, fn}。现在需要对这些字符进行二进制编码，我们希望的编码结果如下：每个字符都有其独一无二的编码；编码长度是变长的，频率大的字符使用更少的二进制位进行编码，频率小的字符则使用比较多的二进制位进行编码，使得最终的平均编码长度达到最短；每个字符的编码都有特定的前缀，一个字符的编码不可能会是另一个字符的前缀，这样我们可以在读取编码时，当读取的二进制位可以对应一个字符时，就读取出该字符。举个例子，假如我们有字符集{‘a’, ‘b’, ‘c’}，字符’a’的编码为001，字符’b’的编码为010，那么此时c的编码不能为00或者01，这样我们才能识别’a’和’c’或者’b’和’c’。
解决方案：
Huffman编码，详细的算法介绍和实现细节请参考下面博客{:5_91:}
博客地址： http://blog.csdn.net/hongchh/article/details/52218338
**** Hidden Message *****

cosmosh73 发表于 2016-9-3 00:59:38

看看

薇薇 发表于 2016-10-9 14:58:20

棒棒的，加油

薇薇 发表于 2016-10-9 21:21:15

表示实在是该好好学习哈夫曼编码的了

xgeng 发表于 2016-10-18 20:31:57

谢谢分享

豪情壮志 发表于 2016-10-20 09:58:03

谢谢楼主~

暴力书生 发表于 2016-10-26 20:04:11

顶~加油

zndownload 发表于 2016-12-30 20:18:47

这个有用，数据压缩算法方面

小鸟游家族 发表于 2018-3-19 15:14:01

看看

lijialijialijia 发表于 2018-4-16 19:33:10

AA

溯影 发表于 2018-4-21 21:21:21

学习一下，希望这种技术贴都可以被顶起来！！！

JCSY 发表于 2018-10-28 14:45:07

what

ALIEN_NoT 发表于 2018-11-3 18:46:19

zhichi

FFISH 发表于 2018-11-18 18:11:58

学习

Hariki 发表于 2020-11-2 14:45:59

看看

云端之梦 发表于 2020-11-24 22:26:14

#include <stdio.h>
#include <stdlib.h>
typedef char * * Huffmancode;
typedef struct
{
        int parent,lchild,rchild;
        int weight;
}Htnode,*Huffmantree;

int Select(Huffmantree HT,int end,int *s1,int *s2)//end保存数组最后一个
{
        int i=1;
        int min1,min2;
       
        while(HT.parent!=0&&i<end)//s1保存较小的
        {       
                i++;
        }
        min1=HT.weight;
        *s1=i;
        i++;
        while(HT.parent!=0&&i<end)
                i++;
        if(HT.weight<min1)
        {
                min2=min1;
                *s2=*s1;
                min1=HT.weight;
                *s1=i;
        }
        else
        {
                min2=HT.weight;
                *s2=i;
        }
        for(int j=i+1;j<end;j++)
        {
                if(HT.parent!=0)
                {
                        continue;
                }
                if(HT.weight<min1)
                {
                        min2=min1;
                        *s2=*s1;
                        min1=HT.weight;
                        *s1=j;
                }
                if(HT.weight>min1&&HT.weight<min2)
                {
                        min2=HT.weight;
                        *s2=j;
                }
        }
        return 0;
}
int CreatHTfumantree(Huffmantree *HT,Huffmancode &HC,int *w,int n)//n为叶子节点数
{

        if(n<=1)
                return 1;
        int m=2*n-1;//m为总节点数
        *HT=(Huffmantree)malloc((m+1)*sizeof(Htnode));//0号位置不用
        Huffmantree p=*HT;
        for(int i=1;i<=n;i++)
        {
                (p+i)->weight=*(w+i-1);
                (p+i)->parent=0;
                (p+i)->rchild=0;
                (p+i)->lchild=0;
        }
        for( i=n+1;i<=m;i++)
        {
                (p+i)->weight=0;
                (p+i)->lchild=0;
                (p+i)->rchild=0;
                (p+i)->parent=0;
        }
        for( i=n+1;i<=m;i++)
        {
                int s1,s2;
                Select(*HT,i-1,&s1,&s2);
                (*HT).parent=i;
                (*HT).parent=i;
                (*HT).lchild=s1;
                (*HT).rchild=s2;
                (*HT).weight=(*HT).weight+(*HT).weight;
        }
       
        return 0;
}


int main()
{
        return 0;
}

Tiｚ 发表于 2021-11-30 11:29:48

谢谢分享
页: [1]
查看完整版本: 一个简单的Huffman编码实现