题意:huffman编码,不懂看coolshell大神的博文,要求输出最优码长和原始码长以及比值。(原始码长就是每个字符都是按8个长度算)
分析:本来huffman编码还好,但是用建树敲完一遍调了半天,实在蛋疼(果然我编码能力太渣)。
于是我开始想不建树的算法,想了半天,终于YY出一个算法 = =。
(借用coolshell的例子来说)
字符 |
次数 |
‘b’ |
3 |
‘e’ |
4 |
‘p’ |
2 |
‘ ‘ |
2 |
‘o’ |
2 |
‘r’ |
1 |
‘!’ |
1 |
第一次建树就是这样:
这时r和!的两个字符合并,构成子树的码长就是2,出现在字符串中的字母数是2。
第二次:
此时第一次建的树下降一层,每个字符的码长都会增加1,而这时这棵子树的码长就变成原来的码长+字符数了。而现在的树就是左子树+右子树,码长和字符数都要处理下。
依次类推,到最后一个数时的码长就是huffman编码需要的码长了。
总结起来就是不用建树,直接模拟计算码长的过程。
刚开始每个数都是一棵树,字符数和码长都是它在字符串中出现的次数,因为此时是独立的,每个字符的码长都是1。然后每次找字符数最小的两个合并,被合并的两棵树就会下降一层,也就是说它每个字符串的码长都增加1,那总码长就增加了它的字符数了。而合并时就是将俩树处理过后的码长和字符数分别相加。
这样合并到最后一棵树,全部字符就会整合成一棵树(不会表现出来),求出来的就是字符串huffman的总码长了。
代码:
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: live2068.cpp
* Create Date: 2013-09-08 20:06:27
* Descripton: not-tree
*/
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <iostream>
using namespace std;
const int MAXN = 1000;
struct Alpha {
int num; // alpha num of the sub-tree
int len; // length of the sub-tree
bool friend operator < (const Alpha& a, const Alpha& b) {
return a.num > b.num;
}
} a[27];
string s;
priority_queue<Alpha> q;
int main() {
while (cin >> s && s != "END") {
while (!q.empty())
q.pop();
memset(a, 0, sizeof(a));
int l = s.size();
for (int i = 0; i < l; i++)
if (s[i] == '_')
a[26].num++;
else
a[s[i] - 'A'].num++;
for (int i = 0; i < 27; i++)
if (a[i].num)
q.push(a[i]);
Alpha tmp, t1, t2;
if (q.size() == 1) {
printf("%d %d 8.0\n", l * 8, l);
continue;
}
while (q.size() != 1) {
t1 = q.top();
q.pop();
t2 = q.top();
q.pop();
tmp.num = t1.num + t2.num; // 字符数=两棵树字符数和
tmp.len = tmp.num + t1.len + t2.len; // 总码长=两棵树的(码长数+字符数)的和
q.push(tmp);
}
printf("%d %d %.1lf\n", l * 8, tmp.len, double(l * 8) / tmp.len);
}
return 0;
}
分享到:
相关推荐
自己实现的Huffman编码,压缩率接近50%,使用字节流写入文件。解码时读取字节流,将字节流转化为二进制串,匹配字符解压。使用I have a dream作为测试文件。
Huffman编码C++源代码 Huffman编码C++源代码
使用文件保存初始的文本数据及最终的结果。 文件名为inputfile1.txt的文件保存的...统计inputfile1.txt中各字符的出现频率,并据此构造Huffman树,编制Huffman编码;根据已经得到的编码,对01形式的编码段进行译码。
(2) 在Huffman编码后,要将编码表和英文文章编码结果保存到文件中,编码结果必须是二进制形式,即0 1的信息用比特位表示,不能用字符’0’和’1’表示。 (3) 提供读编码文件生成原文件的功能。
收集来的Quake3 自适应huffman编码分析,备份一份
实验三、Huffman编码(二叉树) 实验目的:熟练掌握二叉树应用(Huffman编码)的基本算法实现。 实现功能:对输入的一串电文字符实现Huffman编码,再对Huffman编码生成的代码串进行译码,输出电文字符串。实现...
c语言的huffman编码及编码效率计算,采用两种编码方式,可选择
图像的Huffman编码 有注释 希望对大家有用!!!!
Huffman编码的测试文件 包括图像 文本 音频和压缩文件
基于Matlab的图像huffman编码的实现,将图像转换为灰度图,并压缩,求其压缩比和时间
简单图解释Huffman编码构成过程,简单易懂
Huffman树 及 Huffman编码 演示程序 以画图的方法形象的表示了树的构成,解决了普通控制台应用程序对树的结构表达不清的问题 编译器 VS2008
本程序实现了利用 Huffman 编码对图像进行无损压缩和解压缩。Huffman 编码是一种基于字符出现频率构建相应前缀码的无损数据压缩算法。 使用方法: 1. 需要安装 OpenCV 和 Numpy 库: pip install opencv-python ...
非常适合大学数据结构课上使用。强烈推荐!~
huffman 编码的matlab程序 >> p=[0.4 0.3 0.2 0.1]; >> [h,H,L]=huffman(p) h = 0 10 111 110 H = 1.8464 L = 1.9000
Huffman编码的程序代码, #include #include #include #include //极大值用于生成Huffman树 #define MAXSIZE 100000000 //用于生成相应叶子节点Huffman编码的二维字符数组 typedef char* HCode; //Huffman树节点 ...
包含huffman编码java实现源程序、该java程序的javadoc文档、huffman编码简单原理ppt
本文对于如何实现这一编码和解码进行了描述,并给出了它们的C语言实现过程。
1、随机产生一组不少于1000码元的二进制序列并进行Huffman编码与解码;利用Matlab, C或者其他编程语言计算信源Huffman编码的平均码长和编码效率; 2、选择一篇较长的自然科学文章(英文、不少于10页),以扩展的...