`
128kj
  • 浏览: 613448 次
  • 来自: ...
社区版块
存档分类
最新评论

哈夫曼压缩与解压缩学习笔记(一)

阅读更多
前言
   看了两个哈夫曼压缩程序,学习了一把,选一个压缩和解压缩效率高的作些笔记.

一、哈夫曼压缩原理
    我们知道计算机中的文件采用二进制编码,为了使文件尽可能的缩短(压缩),可以对文件中每个字节出现的次数进行统计,设法让出现次数多的字节的二进制码短些,而让那些很少出现的字节的二进制码长一些,这便使整个文件编码之后的总长度的平均期望长度降低,从而达到无损压缩数据的目的。哈夫曼uffman于1952年提出一种编码方法(算法),该方法完全依据字符(字节)出现概率来生成字符的二进制编码,而且可以证明 Huffman 算法在无损压缩算法中是最优的, 一般就叫作Huffman编码。Huffman 原理简单,实现起来也不困难,得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合, Huffman 压缩是非常好的选择。


二、哈夫曼树及哈夫曼编码生成步骤:

① 扫描要压缩的文件,对字节出现的频率进行计算统计。
② 把字节按出现的频率进行排序,组成一个队列。
③ 把出现频率(权值)最低的两个字节作为叶子节点,它们的权值之和为根节点组成一棵树。

④ 把上面叶子节点的两个字节从队列中移除,并把它们组成的根节点加入到队列。

⑤ 把队列重新进行排序。重复步骤 ③④⑤ 直到队列中只有一个节点为止。

⑥ 把这棵树上的根节点定义为 0 (可自行定义 0 或 1 )左边为 0 ,右边为 1 。这样就可以得到每个叶子节点的哈夫曼编码了。

例:假设有一段文件"ASCTASCTAAAAACCTTT",其中用到4个不同字符A,C,S,T,它们在文件中出现的次数分别为 7 , 2 , 4 , 5 。把 7 , 2 , 4 , 5 当做 4 个叶子的权值用上述方法构造的哈夫曼树如图所示。



   在树中令所有左分支取编码为 0 ,令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列,就得这个叶子结点所代表的字符的二进制编码(哈夫曼编码),如上图所示。

    这些编码拼成的文件"01111101001111101000000110110101010"不会混淆,因为每个字符的编码均不是其他编码的前缀,这种编码称做前缀编码。

三、压缩和解压缩文件
   哈夫曼编码生成以后,所谓的压缩文件不过是将文件中每一个字节读出后用其哈夫曼编码替换,满八位后写入压缩文件,不满八位的读出下一字节凑成八位,这样边读边写,直到文件末尾.
   解压缩过程与压缩过程相反,从压缩文件中读一字节(八位)缓存,然后一位一位的解码,直到读到一个哈夫曼编码,用其对应的字节数据替换写入解压文件,这样边读边解码边写,直到文件末尾.
   当然写压缩文件内容前,要先写入码表(原文件的编码信息:字节----频率)用于解压缩时还原哈夫曼树及哈夫曼编码。

四、代码学习
 (1)BitUtils.java 定义用到的常量
  
  public interface BitUtils {
    public static final int BITS_PER_BYTES = 8;
    public static final int DIFF_BYTES = 256;
    public static final int EOF = 256;
  }

 (2)CharCounter.java
   这个类用于字节计数。其带参构造函数打开一个流文件,从流中读取每一个字节,统计每个字节出现的次数(频数),存于数组tehCounts中,其charCountSum()方法统计流文件中总的字节数
import java.io.*;

public class CharCounter {//字节计数器
         private int [ ] theCounts = new int[ BitUtils.DIFF_BYTES + 1 ];
	 public CharCounter( )
	    {
	    }
	    
	    public CharCounter( InputStream input ) throws IOException
	    {
	        int ch;
             //从流中读一个字节,返回0到255范围内的int字节值

	      while( ( ch = input.read( ) ) != -1 ) 
                 theCounts[ ch ]++;//计数
	    }
	    
	    public int getCount( int ch )//获取字节ch的频数
	    {
	        return theCounts[ ch & 0xff ];
	    }
	    
	    public void setCount( int ch, int count )//设置字节ch的频数
	    {
	        theCounts[ ch & 0xff ] = count;
	    }
	    public long charCountSum()//统计流中所有字节数
	    {
	    	long sum=0;
	    	int count=theCounts.length;
	    	int i=0;
	    	while(i<count)
	    	{
	    		sum=sum+theCounts[i];
	    		i++;
	    	}
	    	return sum;
	    }
	    
	}

  


末完待续......
  • 大小: 3.3 KB
1
1
分享到:
评论

相关推荐

    MFCHuffmanZip

    5. **压缩与解压缩流程**:在压缩过程中,原始文件先被分块,然后对每个块应用Huffman编码,生成的二进制流写入新的文件。解压缩则需要逆向执行这个过程,读取压缩文件中的二进制流,解码成原始的字符序列,最后重建...

    数据结构笔记的记录和心得

    其他树结构包括平衡树(如AVL树和红黑树)以及哈夫曼树(用于数据压缩)。 3. **图数据结构**:图由节点(或顶点)和连接节点的边构成,可以表示复杂的关系。图可以是无向的(边没有方向)或有向的(边有方向)。图...

    ACM 经验 笔记 很有用的经验指导

    - **哈夫曼树**:压缩编码,如 poj3253。 - **堆**:用于优先队列和最值问题。 - **Trie 树**:高效存储和查找字符串,分为静态建树和动态建树。 4. **简单搜索**: - **深度优先搜索(DFS)**:poj2488、poj...

    计算机硬件控制_驱动级键盘鼠标同步_PS2接口UDP协议多机协同_基于rabirdwinio和pynput的跨设备输入共享系统_实现多台Windows电脑的键盘鼠标同步操作_支持.zip

    计算机硬件控制_驱动级键盘鼠标同步_PS2接口UDP协议多机协同_基于rabirdwinio和pynput的跨设备输入共享系统_实现多台Windows电脑的键盘鼠标同步操作_支持

    嵌入式八股文面试题库资料知识宝典-TCPIP协议栈.zip

    嵌入式八股文面试题库资料知识宝典-TCPIP协议栈.zip

    少儿编程scratch项目源代码文件案例素材-开膛手杰克.zip

    少儿编程scratch项目源代码文件案例素材-开膛手杰克.zip

    基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型

    基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型,个人经导师指导并认可通过的高分设计项目,评审分99分,代码完整确保可以运行,小白也可以亲自搞定,主要针对计算机相关专业的正在做大作业的学生和需要项目实战练习的学习者,可作为毕业设计、课程设计、期末大作业,代码资料完整,下载可用。 基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型基于深度学习CNN网络+pytorch框架实现遥感图像滑坡识别源码+数据集+训练好的模型基于深度学习CNN网络+pytorch框架实现

    电力弹簧技术在主动配电网规划与运行优化调度中的应用研究

    内容概要:本文详细探讨了电力弹簧技术在主动配电网规划及运行优化调度中的应用。首先介绍了电力弹簧技术作为智能电网调控手段的优势,如自适应性强、响应速度快、节能环保等。接着阐述了主动配电网规划的目标和策略,包括优化电网结构、提高能源利用效率和降低故障风险。随后讨论了运行优化调度的原则和方法,强调了实时监测、智能调度策略以及优化调度模型的重要性。最后通过实际案例分析展示了电力弹簧技术在提升电网稳定性、可靠性和能效方面的显著效果,展望了其广阔的应用前景。 适合人群:从事电力系统规划、运行管理的研究人员和技术人员,以及对智能电网感兴趣的学者和学生。 使用场景及目标:适用于希望深入了解电力弹簧技术及其在主动配电网规划和运行优化调度中具体应用的专业人士。目标是掌握电力弹簧技术的工作原理、优势及其在实际项目中的实施方法。 其他说明:本文不仅提供了理论分析,还有具体的案例支持,有助于读者全面理解电力弹簧技术的实际应用价值。

    嵌入式八股文面试题库资料知识宝典-C语言思维导图.zip

    嵌入式八股文面试题库资料知识宝典-C语言思维导图.zip

    电路教学与科研案例的结合—以最大功率传输定理为例.pdf

    电路教学与科研案例的结合—以最大功率传输定理为例.pdf

    【HarmonyOS文件系统】分布式架构下的多设备协同与文件管理:构建万物互联新生态

    内容概要:本文深入介绍了HarmonyOS文件系统及其在万物互联时代的重要性。HarmonyOS自2019年发布以来,逐步覆盖多种智能设备,构建了庞大的鸿蒙生态。文件系统作为其中的“数字管家”,不仅管理存储资源,还实现多设备间的数据协同。文章详细介绍了常见的文件系统类型,如FAT、NTFS、UFS、EXT3和ReiserFS,各自特点和适用场景。特别强调了HarmonyOS的分布式文件系统(hmdfs),它通过分布式软总线技术,打破了设备界限,实现了跨设备文件的无缝访问。此外,文章对比了HarmonyOS与Android、iOS文件系统的差异,突出了其在架构、跨设备能力和安全性方面的优势。最后,从开发者视角讲解了开发工具、关键API及注意事项,并展望了未来的技术发展趋势和对鸿蒙生态的影响。 适合人群:对操作系统底层技术感兴趣的开发者和技术爱好者,尤其是关注物联网和多设备协同的用户。 使用场景及目标:①理解HarmonyOS文件系统的工作原理及其在多设备协同中的作用;②掌握不同文件系统的特性和应用场景;③学习如何利用HarmonyOS文件系统进行应用开发,提升跨设备协同和数据安全。 阅读建议:本文内容详实,涵盖了从基础概念到高级开发技巧的多个层次,建议读者结合自身需求,重点关注感兴趣的部分,并通过实践加深理解。特别是开发者可参考提供的API示例和开发技巧,尝试构建基于HarmonyOS的应用。

    嵌入式八股文面试题库资料知识宝典-海康嵌入式笔试题.zip

    嵌入式八股文面试题库资料知识宝典-海康嵌入式笔试题.zip

    三电平有源电力滤波器仿真:基于瞬时无功功率理论的双闭环控制与SVPWM调制技术

    内容概要:本文详细介绍了基于瞬时无功功率理论的三电平有源电力滤波器(APF)仿真研究。主要内容涵盖并联型APF的工作原理、三相三电平NPC结构、谐波检测方法(ipiq)、双闭环控制策略(电压外环+电流内环PI控制)以及SVPWM矢量调制技术。仿真结果显示,在APF投入前后,电网电流THD从21.9%降至3.77%,显著提高了电能质量。 适用人群:从事电力系统研究、电力电子技术开发的专业人士,尤其是对有源电力滤波器及其仿真感兴趣的工程师和技术人员。 使用场景及目标:适用于需要解决电力系统中谐波污染和无功补偿问题的研究项目。目标是通过仿真验证APF的有效性和可行性,优化电力系统的电能质量。 其他说明:文中提到的仿真模型涉及多个关键模块,如三相交流电压模块、非线性负载、信号采集模块、LC滤波器模块等,这些模块的设计和协同工作对于实现良好的谐波抑制和无功补偿至关重要。

    基于环比增长的销售统计分析——2019年中青杯全国数学建模竞赛C题.pdf

    基于环比增长的销售统计分析——2019年中青杯全国数学建模竞赛C题.pdf

    嵌入式八股文面试题库资料知识宝典-linux面试题.zip

    嵌入式八股文面试题库资料知识宝典-linux面试题.zip

    嵌入式八股文面试题库资料知识宝典-linux常见面试题.zip

    嵌入式八股文面试题库资料知识宝典-linux常见面试题.zip

    基于Matlab的小电流接地系统单相故障仿真分析及其应对策略研究

    内容概要:本文探讨了小电流接地系统在配电网络中的应用,特别是在单相故障情况下的仿真分析。文中介绍了小电流接地系统的背景和发展现状,重点讨论了两种常见的接地方式——中性点不接地和中性点经消弧线圈接地。利用Matlab作为仿真工具,作者构建了详细的电路模型,模拟了单相故障的发生过程,并通过多个结果图表展示了故障电流、电压波形及系统运行状态。此外,文章还包括了详细的设计说明书和PPT介绍,帮助读者全面理解仿真过程和技术细节。 适合人群:从事电力系统研究、维护的技术人员,尤其是关注配电网络安全和稳定的工程师。 使用场景及目标:适用于希望深入了解小电流接地系统的工作原理和故障处理机制的专业人士。通过本研究,读者可以掌握如何使用Matlab进行电力系统仿真,评估不同接地方式的效果,优化配电网络的安全性能。 其他说明:随文附带完整的仿真工程文件、结果图、设计说明书及PPT介绍,便于读者进一步探索和实践。

    少儿编程scratch项目源代码文件案例素材-激烈的殴斗.zip

    少儿编程scratch项目源代码文件案例素材-激烈的殴斗.zip

    嵌入式八股文面试题库资料知识宝典-小米嵌入式软件工程师笔试题目解析.zip

    嵌入式八股文面试题库资料知识宝典-小米嵌入式软件工程师笔试题目解析.zip

    车辆主动避撞技术:紧急制动与紧急转向策略及其临界安全距离分析

    内容概要:本文详细探讨了车辆主动避撞技术中的两种常见策略——纵向紧急制动避撞和横向紧急转向避撞。首先介绍了这两种避撞策略的基本概念,接着深入分析了临界纵向安全距离的概念及其对避撞模式选择的影响。文中特别强调了五次多项式换道轨迹模型在计算横向紧急转向避撞安全距离中的应用。最后,通过一个简化的程序实现了避撞策略的模拟和可视化展示,帮助读者更好地理解不同避撞方式的应用场景和技术细节。 适合人群:汽车工程技术人员、交通安全研究人员、自动驾驶开发者。 使用场景及目标:适用于研究和开发车辆主动避撞系统的专业人士,旨在提高对避撞策略的理解,优化避撞算法的设计,提升行车安全性。 其他说明:文章不仅提供了理论分析,还结合了具体的数学模型和程序实现,使读者能够从多个角度全面掌握车辆避撞技术的关键要素。

Global site tag (gtag.js) - Google Analytics