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

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

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

一、哈夫曼压缩原理
    我们知道计算机中的文件采用二进制编码,为了使文件尽可能的缩短(压缩),可以对文件中每个字节出现的次数进行统计,设法让出现次数多的字节的二进制码短些,而让那些很少出现的字节的二进制码长一些,这便使整个文件编码之后的总长度的平均期望长度降低,从而达到无损压缩数据的目的。哈夫曼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...

    电镀生产线中西门子S7-300 PLC控制程序详解及其应用

    内容概要:本文详细介绍了应用于电镀生产线的西门子S7-300 PLC控制系统的程序设计、硬件配置以及调试过程中积累的实际经验。主要内容涵盖温度控制、条码记录、行车定位、故障排查等方面的技术细节。文中展示了多个关键功能模块的具体实现方法,如PID温度控制、条码数据处理、行车定位判断等,并分享了一些实用的调试技巧和注意事项。此外,还讨论了硬件配置中的重要细节,如模块地址分配、网络拓扑设计等。 适合人群:从事自动化控制领域的工程师和技术人员,尤其是对PLC编程有一定基础的人群。 使用场景及目标:适用于需要深入了解和掌握电镀生产线自动化控制技术的专业人士。目标是帮助读者理解S7-300 PLC在电镀生产线中的具体应用,提高实际项目的开发效率和可靠性。 其他说明:文章不仅提供了详细的程序代码示例,还分享了许多来自一线的真实案例和实践经验,对于解决实际工程中的问题具有很高的参考价值。

    COMSOL仿真中固体超声导波的二维建模与分析:基于汉宁窗调制的200kHz正弦激励信号

    内容概要:本文详细介绍了使用COMSOL Multiphysics进行固体超声导波的二维仿真过程。作者通过建立一个10mm×100mm的铝板模型,应用汉宁窗调制的5周期200kHz正弦激励信号,研究了超声导波在铝板中的传播特性及其模式转换现象。文中涵盖了从模型构建、材料参数设置、网格划分、边界条件设定、激励信号施加到求解设置以及结果分析的完整流程。特别强调了汉宁窗调制的作用,即减少频谱泄漏并提高信号质量。 适合人群:从事超声检测、材料科学、物理学等相关领域的研究人员和技术人员,尤其是那些希望深入了解COMSOL仿真工具及其在超声导波研究中应用的人群。 使用场景及目标:适用于需要精确模拟超声波在固体介质中传播的研究项目,旨在验证理论预测、优化实验设计、评估不同材料和结构对超声波的影响。此外,还可以用于教学目的,帮助学生掌握COMSOL软件的操作方法和超声导波的基础知识。 其他说明:文中提供了详细的参数设置指导和代码片段,有助于读者快速复现仿真过程。同时,作者分享了一些实用技巧,如如何正确设置网格大小、选择合适的窗函数等,以确保仿真结果的准确性。

    离职人员分析仪表盘.xlsx

    离职人员分析仪表盘.xlsx

    基于LabVIEW的多功能虚拟函数信号发生器设计与信号分析

    内容概要:本文详细介绍了如何利用LabVIEW搭建一个多功能的虚拟函数信号发生器及其信号分析功能。首先,文章展示了如何通过LabVIEW的前面板和程序框图创建各种常见波形(如正弦波、方波、三角波等),并深入探讨了波形生成的具体实现方法,包括三角波的周期性和斜率计算、白噪声的生成以及自定义公式的解析。接着,文章讨论了信号处理的关键技术,如自相关分析、频谱分析、积分和微分运算,并提供了具体的实现代码和注意事项。此外,文中还分享了一些实用的经验和技术细节,如避免频谱泄漏的方法、处理多频波的技术、防止内存泄漏的措施等。 适用人群:从事信号处理、电子工程、自动化控制等领域的工作技术人员,尤其是那些熟悉或希望学习LabVIEW编程的人士。 使用场景及目标:适用于实验室环境或教学环境中,用于替代传统物理信号发生器进行信号生成和分析实验。主要目标是提高信号生成和分析的灵活性和便捷性,减少对昂贵硬件设备的依赖。 其他说明:本文不仅提供了详细的代码示例,还分享了许多作者在实践中积累的经验教训,帮助读者更好地理解和应用LabVIEW进行信号处理。

    线性代数_矩阵运算_方程组解释_MIT公开课笔记用途_1742822302.zip

    线性代数

    大雾至尊版V56泛滥无密码.zip

    大雾至尊版V56泛滥无密码.zip

    员工生日关怀方案.doc

    员工生日关怀方案

    试用期情况跟踪表.xls

    试用期情况跟踪表.xls

    员工激励机制与技巧.doc

    员工激励机制与技巧

    员工晋升的自我评价.doc

    员工晋升的自我评价.doc

    基于51单片机protues仿真的多功能婴儿车控制器(仿真图、源代码、AD原理图)

    基于51单片机protues仿真的多功能婴儿车控制器(仿真图、源代码、AD原理图) 该设计为51单片机protues仿真的多功能婴儿车控制器,实现温湿度,音乐,避障,声音监测控制; 1、温湿度检测,婴儿尿湿时会有提醒。 2、声音检测,当婴儿啼哭时也会有提醒。 3、小车避障,小车遇到障碍会后退左转。 4、音乐播放。 5、仿真图、源代码、AD原理图;

    【计算机求职笔试】编程语言基础、数据结构与算法、系统设计等核心考点解析及备考建议介绍了计算机求职笔试

    内容概要:本文档详细介绍了计算机求职笔试的内容与解答,涵盖编程语言基础、数据结构与算法、编程实践与调试、系统设计与软件工程以及综合题型与开放题五个方面。编程语言基础部分强调了语法规则、数据类型与运算符、面向对象编程的核心概念;数据结构与算法部分讲解了常见数据结构(如线性结构、树与图、哈希表)和高频算法(如排序算法、动态规划、递归与回溯);编程实践与调试部分关注编码能力和调试技巧;系统设计与软件工程部分探讨了设计模式、模块化设计、数据库与网络知识;综合题型与开放题部分则提供了场景题和逻辑思维题的示例。最后给出了备考建议,包括知识体系构建、刷题策略和模拟实战的方法。 适合人群:即将参加计算机相关职位笔试的求职者,特别是对编程语言、数据结构、算法设计有初步了解的应届毕业生或初级工程师。 使用场景及目标:①帮助求职者系统复习计算机基础知识,提升笔试通过率;②通过例题和解答加深对编程语言、数据结构、算法的理解;③提供模拟实战环境,提高时间管理和抗压能力。 阅读建议:建议按照文档提供的知识体系顺序进行系统复习,重点攻克高频题型,利用在线平台刷题练习,并结合实际项目经验进行综合应用,同时注意时间管理和抗压能力的训练。

    SecureCRT安装包

    SecureCRT安装包

    物流业人才流失与紧缺现象的对策研究.docx

    物流业人才流失与紧缺现象的对策研究

    招聘渠道费用仪表盘P10.pptx

    招聘渠道费用仪表盘P10.pptx

    五相永磁同步电机Simulink中PI双闭环SVPWM矢量控制建模与优化

    内容概要:本文详细介绍了五相永磁同步电机在Simulink环境下的PI双闭环SVPWM矢量控制建模过程及其优化方法。首先阐述了五相电机相比三相电机的优势,如更小的转矩脉动和更强的容错能力。接着探讨了复杂的Simulink模型搭建,涉及电机本体模块、坐标变换模块、SVPWM模块和PI调节器模块等多个组件。文中提供了具体的Clark变换和PI调节器的代码示例,解释了双闭环控制的工作原理,并详细描述了SVPWM与十扇区划分的具体实现方式。最后展示了模型的性能表现,包括良好的波形质量和快速的动态响应特性。 适合人群:从事电机控制领域的研究人员和技术人员,尤其是对五相永磁同步电机和Simulink建模感兴趣的读者。 使用场景及目标:适用于希望深入了解五相永磁同步电机控制原理并掌握具体实现方法的研究人员和技术人员。目标是帮助读者理解五相电机的特殊性和复杂性,掌握PI双闭环SVPWM矢量控制的建模技巧,提高电机控制系统的设计水平。 其他说明:文章不仅提供了理论知识,还包括了大量的代码片段和实践经验分享,有助于读者更好地理解和应用相关技术。

    员工离职交接表-模板.doc

    员工离职交接表-模板.doc

Global site tag (gtag.js) - Google Analytics