基于哈夫曼树的数据压缩算法 10C

A

基于哈夫曼树的数据压缩算法

时间限制(C/C++):1000MS/3000MS 运行内存限制:65536KByte
总提交:445 测试通过:131

描述

输入一串字符串,根据给定的字符串中字符出现的频率建立相应哈夫曼树,构造哈夫曼编码表,在此基础上可以对待压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。

输入

多组数据,每组数据一行,为一个字符串(只考虑26个小写字母即可)。当输入字符串为“0”时,输入结束。

输出

每组数据输出2n+4行(n为输入串中字符类别的个数)。第一行为统计出来的字符出现频率(只输出存在的字符,格式为:字符:频度),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第二行至第2n行为哈夫曼树的存储结构的终态(形如教材139页表5.2(b),一行当中的数据用空格分隔)。第2n+2行为每个字符的哈夫曼编码(只输出存在的字符,格式为:字符:编码),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第2n+3行为编码后的字符串,第2n+4行为解码后的字符串(与输入的字符串相同)。

样例输入
aaaaaaabbbbbccdddd
aabccc
0

样例输出
a:7 b:5 c:2 d:4
1 7 7 0 0
2 5 6 0 0
3 2 5 0 0
4 4 5 0 0
5 6 6 3 4
6 11 7 2 5
7 18 0 1 6
a:0 b:10 c:110 d:111
00000001010101010110110111111111111
aaaaaaabbbbbccdddd
a:2 b:1 c:3
1 2 4 0 0
2 1 4 0 0
3 3 5 0 0
4 3 5 2 1
5 6 0 3 4
a:11 b:10 c:0
111110000
aabccc

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
数据结构实验——基于哈夫曼树的数据压缩算法
/* 注:输入为多行字符串,以“0”结尾;例:abc def 0 此程序无法执行由单个字符组成的字符串。 */ #include<iostream> #include<string> #include<map> using namespace std; typedef struct { int weight; int parent,lchild,rch...
【数据结构】基于哈夫曼树的数据压缩算法
描述 输入一串字符串,根据给定的字符串中字符出现的频率建立相应哈夫曼树,构造哈夫曼编码表,在此基础上可以对待压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。 输入 多组数据,每组数据一行,为一个字符串(只考虑26个小写字母即可)。当输入字符串为“0”时,输入结束。 输出 每组数据输出2n+3行(n为输入串中字符类别的个数)。第一行为统计出来的字符出现频率(只输出存在...
基于算术编码的数据压缩算法
用C语言实现的数据压缩算法,算法不难,压缩数据还行。
数据压缩算法—2无损压缩算法
几个常见的编码算法 (一) 字典算法   字典算法是最为简单的压缩算法之一。它是把文本中出现频率比较多的单词或词汇组合做成一个对应的字典列表,并用特殊代码来表示这个单词或词汇。例如:   有字典列表:   00=Chinese   01=People   02=China   源文本:I am a Chinese people,I am from China 压缩后的编码为:I am a 00 0...
数据压缩算法
数据压缩算法 一、 概念: 数据压缩是指在不丢失有用信息的前提下,缩减数据量以减少存储空间,提高其传输、存储和处理效率,或按照一定的算法对数据进行重新组织,减少数据的冗余和存储的空间的一种技术方法。 在计算机科学和信息论中,数据压缩或者源编码是按照特定的编码机制用比未经编码少的数据位元(或者其他信息相关的单元)表示信息的过程。 二、 算法编码(哈夫曼压缩算法编码): 哈夫曼压缩算法编码是
哈夫曼树+双缓冲实现压缩算法(已更新)
认识哈夫曼树之前首先我们简单的来了解一下二叉树,不难理解,二叉树就是每个节点都只有2个子节点的树状结构,也就分为父节点(parent node)、左子树(left child)和右子树(right child)。每个节点最多只能有2个节点,当然也可以更少,比如只有左节点没有右节点或者相反,没有子节点的节点我们称之为叶节点,有子树的称之为根节点。 二叉树相关就先介绍到这里,我们...
基于压缩感知的心电数据压缩算法的设计
本文利用压缩感知算法对心电数据信号进行压缩,从而实现心电数据的高压缩率与高精度。从压缩感知算法的原理可知,稀疏字典能够反映某类数据的结构信息,因此,针对心电数据这一具有特殊结构的数据,利用压缩感知算法探索其内在的结构,能够更加符合心电数据的变化规律。本文通过实验在MIT-BIH数据库上进行验证,对比了传统的压缩算法,证明本文提出的算法在均方根误差和压缩率上都能取得较好的效果。
基于ccsds标准的无损数据压缩算法
根据ccsds标准编写的无损数据压缩算法
一种基于复合编码的心电数据压缩算法
本文提出了一种复合心电数据压缩方法,该算法根据ECG数据的特征变化,提取出每路ECG 的心 搏模板,从而把信号分成三部分:心搏模板、残差、位置参数。在保证恢复信号低失真的情况下,先对残余误差进行 LADT编码,再利用Huffman的无损压缩方法进行全部数据二次压缩。与其它压缩方法相比,在同样的信息损失 下,该算法可获得更高的数据压缩比。本文提出的方法,也可应用到图像数据和其它数据的压缩中。
基于GDI图片压缩算法
基于GDI图片压缩算法头文件#include "stdafx.h" #include <Windows.h> #include <GdiPlus.h> #pragma comment( lib, "GdiPlus.lib" ) using namespace Gdiplus;质量压缩bool GetEncoderClsid(const WCHAR* pszFormat, CLSID* pClsid)
基于四叉树的分形压缩算法
压缩算法,挺有用的。希望有人能用倒。。。。。。
基于哈夫曼编码的压缩算法的Python实现
1.背景 离散数学老师布置了一份大作业,作业题目就是用自己喜欢的编程语言来实现课上所学的哈夫曼编码算法(Huffman Coding)。哈夫曼编码是一种采用变长编码表来表示数据的编码方式。其详细介绍详见下方引自维基百科的引文。 在计算机数据处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短...
基于QT的MP3压缩算法
1、基于QT开发 2、直接将采集到的音频流数据进行MP3编码
基于声音压缩算法的毕业论文
声音压缩的论文,可用于毕业设计,附有部分程序代码
基于哈夫曼编码的压缩算法的实现
哈夫曼编码取决于哈夫曼树。 将要压缩的字符串,将每个字出现的频率作为依据,构造一颗哈夫曼树,频率越大的字越是靠近树的根结点,因此它的编码也就越短。因此,频率高的字用短码,频率低的字用长码。根据这样的码表可以实现压缩字符串了。 本程序采用C#实现。 基本上是演示了哈夫曼编码压缩的原理。由于是演示代码,因此不必太纠结与效率。本程序效率必定不高。 根据码表组成的二进制码,按...
哈夫曼树(基于优先队列最小堆)
实验三、哈夫曼编码 一、实验内容输入一段文本,计算其中每一个字符的哈夫曼编码,输出编码后文本的长度。哈夫曼编码作为一种变长编码方式,在文件/图像压缩领域有着重要的应用。 二、设计思路给定n个树叶的权值,改造带权路径总长最短的最优二叉树的算法由哈夫曼给出。a. 对个权值进行排序,满足b. 计算作为中间节点的权,的左儿子是,右儿子是. 在权序列中删除, 加入. 若, 结束,否则转a.       树的...
基于C++数据结构 哈夫曼树
template <class T> void HTree<T>::CreateHuffman(int n){ //w存放n个字符的权值(均>0),构造赫夫曼树HT int i,m,s1,s2,w;HTNode<T> *p;//w放权值的临时变量 if (n<=1) throw "error!"; m=2*n-1;//注:有n个字符,其构造成一颗Huffman树后,将有n+n-1个结点. HT=new HTNode<T>[m+1];//0号单元未使用 for(p=HT+1,i=1;i<=n;++i,++p) { //初始化Huffman树的各叶子结点 cout<<"请输入第"<<i<<"个字符的权值(1-26是字母的,27是空格符的权值):"; cin>>w; (*p).weight=w; (*p).lchild=0; (*p).rchild=0; (*p).parent=0; }
基于哈夫曼树的文件压缩
一个编程小白成功的完成了哈夫曼树的文件压缩,过程可以说是很艰辛了。好啦~废话就不多说了,下面开始正式的讲解,过程+代码。工具:Dev-c++ 语言:C++刚开始我拿到这个题目,真心是蒙啊,因为我连什么是哈夫曼都不知道(可以看出我是小白了吧)。先说一下整个过程:1.从文件中读取叶子个数,及权值(即相同字母的个数)。比如说文件中内容是abcdabcaba,叶子个数为4,分别是a,b,c,d,权值依次为...
基于哈夫曼树的编码和译码
1.实验要求: 利用哈夫曼编码:要传输一些数据(比如英文单词), 设计一个利用哈夫曼算法的编码系统, 为这些单词编码, 并在接收端进行译码. 基本要求: (1).将需要传输的数据存放在数据文件data.txt 中. (2).读入数据文件并为其编码, 将编码后的内容存入文件code.txt中. (3).读入code.txt, 译码, 并将译码后的内容输出在屏幕上. 2.基本思路: (1).编码: 统...
LZO数据压缩算法库
LZO是致力于解压速度的一种数据压缩算法,LZO是Lempel-Ziv-Oberhumer的缩写。这个算法是无损算法,参考实现程序是线程安全的。 LZO库实现了许多有下述特点的算法: • 解压简单,速度非常快。 • 解压不需要内存。 • 压缩相当地快。 • 压缩需要64 kB的内存。 • 允许在压缩部分以损失压缩速度为代价提高压缩率,解压速度不会降低。 • 包括生成预先压缩数据的压缩级别,这样可以得到相当有竞争力的压缩比。 • 另外还有一个只需要8 kB内存的压缩级别。 • 算法是线程安全的。 • 算法是无损的。
ctw数据压缩算法源代码
ctw数据压缩算法源代码,采用c++语言编写
BWT数据压缩算法
在全文检索中通常要对索引进行压缩存储,在压缩之前如果对文本进行一定的可逆变换能够使之更易压缩,BWT就是这样一种变换.     通过一个例子来介绍BWT,假设一段待转换的文本为:ababc, 则BWT的过程如下:   在T后插入结束符#得到新的文本串T#,循环左移,每次一位,得到一个|T#|行的矩阵,按首字母排序得到M   F = first column of M ...
数据压缩算法及性能求教
求教下:rn现在什么文件压缩算法 性价比比较高?rn就是:性能好,压缩比大,无损。
轨迹数据压缩算法
数据 P0,107.605,137.329 P1,122.274,169.126 P2,132.559,179.311 P3,153.324,184.276 P4,171.884,174.654 P5,186.408,168.634 P6,196.566,145.204 P7,200.549,127.877 P8,211.391,118....
LZW 数据压缩算法
LZW 数据压缩算法 作者:Mark Nelson
ZLIB数据压缩算法源码
ZLIB数据压缩算法源码ZLIB数据压缩算法源码ZLIB数据压缩算法源码ZLIB数据压缩算法源码
多通道数据采集系统数据压缩算法
多通道数据采集系统数据压缩算法,基于LZW算法
[求助]j2me数据压缩算法
请问j2me下有没有数据压缩算法啊?
ppm数据压缩算法源代码
ppm是一种无损数据压缩算法,源代码采用c语言编写。
数据压缩算法-游程编码RLE
了解一下数据压缩算法: 压缩算法主要分为两类1.有损压缩    2.无损压缩 有损压缩有很多种,这里说一下无损压缩。 无损压缩算法:行程编码(游程编码)[RLE(RUN-LENGTH ENCODING)]  ,哈夫曼编码。 RLE算法 游程编码:例如:信息单元0304,03表示其后的象素个数是3个,04表示这些象素使用的是颜色索引表中的第五项的值。压缩数据展开后就是04 04 0
通用数据压缩算法 pDF
通用数据压缩算法 PDF文件 一种高效的通用数据压缩算法
数据压缩算法开题报告
该文档描述了数据压缩算法的应用的一个课题的开题报告
LZW数据压缩算法的原理分析
LZW数据压缩算法的原理分析,定义,简介,举例演示,适用范围,算法流程等等
数据压缩算法 lz77
lz77算法Lempel和Ziv于1977年发表论文 至今,几乎我们日常使用的所有通用压缩工具,象ARJ,PKZip,WinZip,LHArc,RAR,GZip,ACE,ZOO,TurboZip,Compress,JAR„„甚至许多硬件如网络设备中内置的压缩算法,无一例外,都可以最终归结为这两个以色列人的犹太人杰出贡献。 这里我做了两张图  详细讲解了 lz77数据压缩算法的具体步骤,以及给出
lz78数据压缩算法
主要讲基于LZ78的数据压缩算法,其中包含LZ78算法中用到的几个术语和符号、LZ78的编码思想及LZ78编码的具体算法步骤。
数据压缩算法LZO
一、什么是LZO  LZO是致力于解压速度的一种数据压缩算法,LZO 是 Lempel-Ziv-Oberhumer 的缩写。这个算法是无损算法,参考实现程序是线程安全的。实现它的一个自由软件工具是lzop。最初的库是用 ANSI C 编写、并且遵从 GNU通用公共许可证发布的。现在 LZO 有用于 Perl、Python 以及 Java的各种版本。代码版权的所有者是 Markus F. X. J
浅析数据压缩算法
数据压缩是减少信息传输量最经济直接的办法,所以这篇文章将讲解一些经典的数据压缩算法。 一 热身:基因组 对于生物学的基因研究中,A、C、T、G是是用来表示生物DNA的四种碱基,对基因序列的处理实际上是对这四种碱基的处理,因此为了解决这种字符种类较少且固定的字符序列,我们可以用双位编码(用2bit位可以表示四中字符)压缩来解决这个问题。在这种方法中,只需要建立字母表即可对字符序列进行压缩和展开。
哈夫曼树哈夫曼树
哈夫曼树,C语言写哈夫曼树的压缩解压缩程序
基于C++实现的LZW压缩算法
1 特点 基于C++实现的LZW压缩算法,特点如下所示: 使用stl::map键值对作为字典存储 感觉算是简单的文件操作 字典无限长,字典自生长。但是字典只能解析存储ascii编码之类存在,中文符号之类的碰到就挂 2 逻辑设计 2.1 总体思路 点击此处下载文档和源码 ...
基于OBDD的灰度图像无损压缩算法
基于OBDD的灰度图像无损压缩算法基于OBDD的灰度图像无损压缩算法
相关热词 c# stream 复制 android c# c#监测窗口句柄 c# md5 引用 c# 判断tabtip 自己写个浏览器程序c# c# 字符串变成整数数组 c#语言编程写出一个方法 c# 转盘抽奖 c#选中treeview