POJ1521-huffman编码

约定不等于承诺〃 2023-06-20 09:05 112阅读 0赞

来源:https://vjudge.net/problem/POJ-1521

输入:输入文件将包含一个文本字符串列表,每行一个。文本字符串将仅包含大写字母数字字符和下划线(用于代替空格)。输入的结尾将由仅包含单词“END”作为文本字符串的行发出信号。 输出 对于输入中的每个文本字符串,输出8位ASCII编码的位长度,最佳无前缀可变长度编码的位长度,以及精确到一个小数点的压缩率。

样例输入:
AAAAABCD
THE_CAT_IN_THE_HAT
END

样例输出:
64 13 4.9
144 51 2.8

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. string s;
  4. int len;
  5. int a[100];//统计出现频率
  6. int main(){
  7. while(true){
  8. priority_queue<int,vector<int>,greater<int> >Q;
  9. memset(a,0,sizeof(a));//重新赋0
  10. cin>>s;
  11. if(s=="END"){
  12. break;
  13. }
  14. len=s.size();
  15. int asc=len*8;//ascll编码长度
  16. //统计频率
  17. for(int i=0;i<s.size();i++){
  18. if(s[i]=='_'){
  19. a[26]++;
  20. }
  21. a[s[i]-'A']++;
  22. }
  23. //进入队列
  24. for(int i=0;i<=26;i++){
  25. if(a[i]>0){
  26. Q.push(a[i]);
  27. }
  28. }
  29. int total=0;//huffman编码长度
  30. while(true){
  31. int sum=0;
  32. sum=sum+Q.top();
  33. Q.pop();
  34. sum=sum+Q.top();
  35. Q.pop();
  36. Q.push(sum);
  37. total=total+sum;
  38. if(Q.size()==1){
  39. break;
  40. }
  41. }
  42. printf("%d %d %.1lf\n",asc,total,(double)asc/total);
  43. }
  44. }

发表评论

表情:
评论列表 (有 0 条评论,112人围观)

还没有评论,来说两句吧...

相关阅读

    相关 Huffman 编码压缩算法

    前两天发布那个[rsync算法][rsync]后,想看看数据压缩的算法,知道一个经典的压缩算法Huffman算法。相信大家应该听说过 [David Huffman][] 和他的

    相关 Huffman编码

    扫码关注公众号免费阅读全文:冰山烈焰的黑板报 ![在这里插入图片描述][20200906232656299.jpg_pic_center] 1. 概念 我们来学习一