最优哈夫曼编码

有一段字符串，要求每个字符用01编码，该怎么样编码才会保证不会出错？

显然只有当一个字符的编码串为另一个字符的串的前缀时才会出错，即a=111，b=11，那么111111就不知道是什么了

如果将这些串塞进trie树里面，显然，所有串都包含一个叶子节点，即：一个叶子代表一个串

最优哈夫曼编码

如果你已经知道了每个字符出现的数量，怎么样找到最优的方式使编码后的串的长度最短？

上面的图可以看出，离root越远，长度越长

而且，上图中A下面不可能再有延伸，也就是说最下面一层至少为2个点

想法：

每个字符对长度的贡献为：c*l，c为出现次数，l为编码后的长度
那么就相当于将叶子点赋值，向上合并

比如AABBBCCCC，那么A的c为2，B为3，C为4，sum=22+32+4*1

这个过程可以分解为合并AB这两个点变成AB的父节点，答案加上两个点的权值，再合并到父结点

c[lson]*l[son]+c[rson]*l[son]==(c[lson]+c[rson])*(l[son]-1)+(c[lson]+c[rson])

类似于石子合并，因为每次合并需要加一次值，所以显然贪心每次合并两个最小的ans最优

例题： http://acm.hdu.edu.cn/showproblem.php?pid=2527

问是否可以找到长度小于等于n的编码方式

#include<bits/stdc++.h>
using namespace std;
#define debug(i) printf("# %d\n",i)
int read(){
    int a;scanf("%d",&a);return a;
}

char x[1000009];
int main(){
    int t;while(scanf("%d",&t)!=EOF)
    while(t--){
        int n;scanf("%d%s",&n,x);
        int co[30];
        memset(co,0,sizeof(co));
        int len=strlen(x);
        for(int i=0;i<len;i++){
            co[x[i]-'a']++;
        }
        priority_queue<int,vector<int>,greater<int> >Q;
        for(int i=0;i<30;i++){
            if(co[i])Q.push(co[i]);
        }
        if(Q.size()==1){
            if(Q.top()<=n)printf("yes\n");
            else printf("no\n");
            continue;
        }
        int ans=0;
        while(Q.size()>1){
            int sum=0;
            sum+=Q.top();Q.pop();
            sum+=Q.top();Q.pop();
            ans+=sum;Q.push(sum);
        }
        if(ans<=n)printf("yes\n");
        else printf("no\n");
    }
}

最优哈夫曼编码

相关推荐