赫夫曼编码

简介: 本文主要讲赫夫曼编码

问题 J: 赫夫曼编码

题目描述


赫夫曼编码能够产生最短的报文。以报文“ABCDABCDABCABDABAA”为例,A编为0,B对应10,C对应110,D对应111,整体的报文长度为35位二进制。相比于定长的ASCII码,压缩比达到了18*8/35=4.1。


输入


输入有一系列的字符串组成,每个字符串占据一行。字符串仅包含大写字母和下划线。字符串“END” 表示处理结束,不应对其处理。


输出


对每一个字符串,输出其ASCII编码的比特位长度,赫夫曼编码的比特位长度,以及二者之比,精确到小数点后一位。


样例输入


ABCDABCDABCABDABAA

AAAAAAAAAAAAAAAAAA

END


样例输出


144 35 4.1

144 18 8.0


#include <stdio.h> 
#include <string.h> 
#define N 5000000 
#define inf 100000000 
struct node 
{ 
    int val;  
    int left,right,parent; 
}p[1000]; 
int f[N];  
int len[N]; 
char str[N]; 
int data[N];    
void hufuman(int n) 
{ 
    int i,flag;
  int min1,min2,pos1,pos2;
  //最小节点,次小节点,最小节点标记,次小节点标记
    for(i =0; i < n; i++) 
    { 
        p[i].val = f[i];  //权值
        p[i].parent =-1;  //赋初值
        p[i].left =-1;  //赋初值
        p[i].right =-1;  //赋初值
    } 
    while(1) 
    { 
        int mark1=0,mark2=0; 
        min1=min2=inf; 
        for(i =0; i<n; i++) //找出最小的两个节点     
        { 
            if(p[i].parent==-1&& p[i].val<min1) 
            { 
                if(min1!= min2) 
                { 
                    min2 = min1; //将次小节点赋值给min2
                    pos2 = pos1; //标记跟着变化
                    mark2 =1; //标记 
                } 
                min1 = p[i].val; //将最小节点赋值给min1
                pos1 = i; //标记跟着变化
                mark1 =1; //标记 
            } 
            else
                if(p[i].parent ==-1&& p[i].val<min2) 
        { 
                    min2 = p[i].val; //将次小节点赋值给min2
                    pos2 = i; //标记跟着变化
                    mark2 =1; //标记
        } 
    } 
        if(mark1 ==0|| mark2 ==0) //已经没有节点
            break; 
        p[n].val=min1+min2; //父母节点的权值
        p[pos1].parent=n; 
        p[pos2].parent=n; 
        p[n].left=pos1;  //左子树
        p[n].right=pos2; //右子树
        p[n].parent=-1; 
        n++; 
    } 
    for(i =0;i<n; i++) //计算赫夫曼编码长度过程
    { 
        if(p[i].right!=-1||p[i].left!=-1)         
            break; 
        flag=i; 
        len[i]=1; 
        while(p[flag].parent!=-1) //一直向上搜,直到顶层
        { 
            len[i]++;  
            flag=p[flag].parent;    
        } 
    } 
    return; 
} 
int main() 
{ 
    int i; 
    while(scanf("%s",str)!=EOF) 
    { 
        if(!strcmp(str,"END"))    
            break; 
        memset(data,0,sizeof(data)); 
        memset(f,0,sizeof(f)); 
        int ll=strlen(str); 
        for(i=0;i<ll;i++) 
            data[(int)str[i]]++;     
        int num =0; 
        for(i=0;i<128;i++) //将字母的频数存入f数组
        { 
            if(data[i] !=0) 
            { 
                f[num++]=data[i];    
            } 
        } 
        if(num==1) //只有1种字母的情况
        { 
            printf("%d %d 8.0\n",strlen(str)*8,f[0]); 
            continue; 
        } 
        hufuman(num); 
        int sum=0; 
        for(i =0; i < num; i++) 
        { 
            if(len[i] !=1) 
                sum+=(len[i]-1)*f[i]; 
        } 
        printf("%d %d %.1lf\n", strlen(str)*8,sum, ll*8/(double)sum); 
    } 
    return 0; 
} 
相关文章
|
3月前
|
中间件
gin中间件(Use)不能写在响应函数之后的原因——源码分析
gin中间件(Use)不能写在响应函数之后的原因——源码分析
83 0
|
数据采集 算法 数据挖掘
【数据挖掘实战】——中医证型的关联规则挖掘(Apriori算法)
项目地址:Datamining_project: 数据挖掘实战项目代码
672 0
|
机器学习/深度学习 算法 自动驾驶
【强化学习】常用算法之一 “PPO”
强化学习是一种通过智能体与环境的互动来学习最优行为策略的机器学习方法。相较于监督学习和无监督学习,强化学习的特点在于具有延迟奖赏和试错机制。在强化学习中,智能体通过选择动作来影响环境,并且从环境中获得奖励作为反馈。强化学习的目标是通过与环境的交互,使得智能体能够学会最优的行为策略。PPO算法属于策略优化(Policy Optimization)算法家族,是由OpenAI在2017年提出的。与其他策略优化算法相比,PPO算法具有较高的样本利用率和较好的收敛性能。
1065 1
【强化学习】常用算法之一 “PPO”
|
数据采集 人工智能 自然语言处理
大规模、高性能,清华、聆心智能推出中文开放域对话预训练开源模型OPD
大规模、高性能,清华、聆心智能推出中文开放域对话预训练开源模型OPD
294 0
|
NoSQL 网络协议 算法
Redis客户端Lettuce深度分析介绍(上)
Spring Boot自2.0版本开始默认使用Lettuce作为Redis的客户端(注1)。Lettuce客户端基于Netty的NIO框架实现,对于大多数的Redis操作,只需要维持单一的连接即可高效支持业务端的并发请求 —— 这点与Jedis的连接池模式有很大不同。同时,Lettuce支持的特性更加全面,且其性能表现并不逊于,甚至优于Jedis。本文通过分析Lettuce的特性和内部实现(基于6.0版本),及其与Jedis的对照比较,对这两种客户端,以及Redis服务端进行深度探讨。
51505 8
Redis客户端Lettuce深度分析介绍(上)
|
Web App开发 JSON 自然语言处理
WebUI自动化测试框架搭建之需求整理、详细设计、框架设计
WebUI自动化测试框架搭建之需求整理、详细设计、框架设计
1149 0
|
JSON 数据格式 Python
pydantic的高阶玩法
`pydantic`是一个Python的数据验证和转换库,它的特点是轻量、快速、可扩展、可配置。笔者常用的用于数据接口schema定义与检查。 具体的基本用法本文不再做过多的介绍,可以参考[pydantic官方文档](https://docs.pydantic.dev/)。本文主要是结合实际项目开发中遇到的问题和解题思路,介绍一些`pydantic`的高阶玩法。
366 0
|
Java 关系型数据库 MySQL
浅析PropertySource 基本使用
org.springframework.context.annotation.PropertySource 是一个注解,可以标记在类上、接口上、枚举上,在运行时起作用。而@Repeatable(value = PropertySources.class) 表示在PropertySources 中此注解时可以重复使用的。
浅析PropertySource 基本使用
|
测试技术