内存数据库
内存数据库就是将数据放在内存中直接操作的数据库，它利用内存的读写速度比磁盘快、内存是随机访问而磁盘是顺序访问这两个特点，将数据保存在内存中，在内存中模仿建立表结构和索引结构并针对内存特性进行优化，相比从磁盘上访问，内存数据库访问较快。
关系型数据库
数据库是指按照一定数据结构和模型来组织、存储和管理数据的仓库。采用关系模型建立起来的数据库叫做关系数据库。关系数据库是建立在集合代数基础上，应用数学方法来处理数据库中的数据。现实世界中的各种实体以及实体之间的各种联系均用关系模型来表示。
实时数据库
实时数据库概述
实时数据库是采用实时数据模型建立起来的数据库，用于处理不断更新的快速变化的数据及具有时间限制的事务处理。实时数据库技术是实时系统和数据库技术相结合的产物，利用数据库技术来解决实时系统中的数据管理问题，同时利用实时技术为实时数据库提供时间驱动调和资源分配算法。主要应用于工业监控，如：电力、石化、化工、钢铁、冶金、造纸、交通控制和证券金融等工业领域的监控。。概括地讲，实时数据库系统有如下特点：
时间约束：
实时数据库是其数据和事务都有明确的时间限制的数据库。在实时系统中，具有时间约束的数据主要是来自于外部的动态数据，以及由这些数据求导出的新的数据。数据库中的数据必须如实反映现场设备的运行情况。
事务调度：
实时数据库系统的正确性不仅依赖于事务的逻辑结果，而且依赖于该逻辑结果所产生的时间。事务调度既要考虑事务的执行时间，也要考虑事务的截止期、紧迫程度等因素。
数据存储：
实时数据库主要承担系统所有实时数据的存储和管理，为相关的功能提供快速、正确的实时信息。为了达到实时性，实时数据库在系统运行过程中，应常驻内存，以保证读取速度。对于实时性要求不高的数据可存放在外存储空间。因此，在实时数据库设计时，要妥善处理时间与存储空间的矛盾，以保证系统的实时性。
数据在线压缩：
在实际的数据存储中，实时数据库还要解决如何高效处理海量数据的问题。如果数据被原封不动地存储势必需要大量内存和磁盘空间以及耗费大量的时间，因此必须对实时数据进行在线压缩存储。
实时数据库的实现原理
谈到实时数据库，有些同仁还颇感神秘，我写此文结合我最近开始做的MES RTDBE实时数据库工程师培训教材来开展，逐渐解开面纱，给大家展示一个真实的实时数据库世界。
先了解概念，再深入原理。
说道实时数据库，当时诞生于美国，随着流程工业和航天工业的发展，大量的测量数据需要集成和存储，采用关系数据库难以满足速度和容量的要求，而且接口访问复杂，不适合科研和监控的需要，因此80年代中期，开始诞生了以工业监控为目的的实时数据库。
今天大家看到的一些实时数据库，如PI、Uniformance、Infoplus、InSql等工业监控类实时数据库均先后诞生于此阶段。而当时还有另外一个分支，即所谓硬实时数据库，它的采集速度和响应速度均是毫秒级的，而大家知道，今天大量应用实时数据库，主动采集速度均是秒级的，响应速度也不严格，在Windows平台下，小于40ms的响应均不准确，但当时却有这类产品，目前多用于军事和科研了。到了上世纪90年代，实时数据库在流程工业全世界范围内大行其道，源于以太网的逐步普及；主要应用于工业监控、控制和公用工程。国内的实时数据库发展较为缓慢，这和技术封锁和政治风气都有关系，到了2000年之后，国内的实时数据库逐渐展露头角，如ESP-iSYS、Agilor等与国外的PI、InfoPlus均属于大型分布式网络实时数据库。规模相对较小的，如PHD、ConRTDB、SuperInfo，在国内开始应用。由于应用场景的不同，好多企业开始还只是解决现场监控的问题，分不清RTDB与SCADA的概念，结果InSql获得了一个发展的机会。
那么，什么是实时数据库呢，过去国人老将其与SCADA搞混，倒也给SCADA一个发展的机会。实际上实时数据库是“对实时性要求高的时标型信息的数据库管理系统”，注意，这里特别提醒，是管理系统，而非单独一个数据库。实时数据库虽是系统软件，但更多是一个应用平台软件，原因是实时数据库还没有一个像SQL一样的标准，而且其功能太过综合，各厂商推出的产品功能各有侧重。但以上的膜片中至少总结了实时数据库的主要功能。
目前实时数据库已经应用到众多领域，它的应用范围还在不断扩展，业界的同仁在不断创造出实时数据库的应用模式。只要有时标型数据，实时数据库就可以在一定程度上发挥威力。
说到这里，渐渐要讲原理了。与一般认识不同，时标型数据并非仅仅指时间戳、值和质量码，还有一个很重要的属性，那就是及时性，及时性有两重含义，采样间隔和数据的新鲜度。时标型数据的价值随新鲜度降低而递减。1秒钟内的数据可以用来流程工业中的控制，5秒钟之内可以用来监视，半小时内的数据可以用来分析和优化，一天内的数据可以用来日报表，如果是半年前的数据，则只能做对比和追溯了。而得到数据的新鲜程度往往取决于采样频率，这就是为什么如此重视实时数据库的采样快速性。同时采样的频率还进一步决定了实时数据库保存信息的丰富程度。请看下一张膜片：
大家都知道采样定理，根据拉普拉斯变换，任何信号都可以被分解为频率不同、幅值不同的正弦波叠加，而如果要让采到的数据中包含一个频率的信息，则采样频率至少为此频率的2倍。所以大家不要过分关心实时数据库宣称的无损压缩，更重要的是要明白，信息的最大损失就在于采样。更简单的例子，当你以10秒钟的周期去采样，可能装置运行过程中出现了异常的超调，在5秒内又恢复了，而你的实时数据库中却根本不存在这些信息。从另一个方面讲，实时数据库中存储的数据永远是滤波后数据，实时数据库就像一个低通滤波器。
接下去，要讲到实时数据库的核心技术原理了，理解了这些原理，在设定实时数据库运行参数的时候，才能得到更好的效果。也就会明白，一个RTDBA（RTDB Administrator）的存在价值。
看看这些标题，就知道，我下面会讲很多关键的东西，之前很多Q友在群里面抱怨我不提供完整的实时数据库原理知识材料，抱歉，太忙了。不是吝惜什么或技术保密，今天，只要你努力，都可以做出一个实时数据库的核来，但从一个内核到产品的质变，是需要公司正规研发投入的，因此，原理实在不需要保密，讲个明白，大家能更好地使用实时数据库。
首先看看，任何复杂的大型实时数据库，其基本体系架构，也不外乎如图所示，通过现场适配层适配现场的各种接口，做工控的都知道，这是一个复杂的工作。然后通过实时核心，完成数据的采集、实时计算、报警计算、其它处理，实时数据被不断泵入磁盘历时存储，形成可追溯的历时信息，同时通过向应用层提供各种适配接口，支持各种开发语言和各种应用需求的访问。认识好这个基础架构，下面看核心原理，就思路清晰了。
总的来说，目前工业通讯、传输的协议种类繁多，主要有两方面原因：
1、历史遗留；
2、人为垄断；
二者的合力就是上边这张膜片的内容，搭建看看，难啊，很多时候，为了不付出厂商提出的巨额接口或接口板卡费用，广大的业界同仁采取编程口、打印口等极端方式，以获得可以接受的性价比。在协议载体上，主要是串行和以太两种，当然在串行通讯中又有很多专用总线分支，例如Profibus等。以太网通讯技术已经势如破竹，所以，前途光明，但另一个困扰更大，就是封闭的协议，目前大部分厂商都宣称自己开放了，但开放的是上层，而非底层。虽然，至少可以做到采用OPC访问实时数据库，但要想简单地将For InSql的接口用于Agilor，则很难，这就是底层没有协议的问题。
谈到接口，小型实时数据库（许多是号称自己是实时数据库的组态软件）均采用了以上的架构，即将核心和接口做在一起，用户使用起来较为简单，但如果出现任何一个不稳定的接口或局部异常，那整个实时数据库就崩溃了。另外对于大型应用，这种结构也较难扩展。对于大型分布式实时数据库，基本按照如下的配置：
接口软件被独立出来，即可以与实时数据库核心集中部署在1台计算机上，也可以与部署在接口机上，在大规模应用的时候，接口的负载不会影响核心的稳定，同时任意一个接口出现Crash，都不会导致实时数据库整体宕机。从而提供了更好的可扩展性和稳定性。
谈到影响接口效率的因素，主要如下：
首先协议如果慢，那是没招了，这主要可以看看DDE协议，在OPC出现前，也曾经红火了一段时间，DDE使计算机上跨进程数据可以方便通讯，但这种通讯协议本身效率很低。计算机再快，容量不能大幅度上升，几百个位号就很不错了。就这一点，就决定了其退出了历史舞台。第二在于网络状况。没有有效地组网，以太网也会十分缓慢。有效的带宽变低，使得快速协议也变得缓慢而不稳定。网络状况有两方面：
1、物理结构合理性，多少次经验告诉我们，没有合理组织的以太网，往往导致数据的阻塞，梳理以太网就像控制交通流量，任何地方出现瓶颈，都会导致数据缓慢；
2、病毒，尤其是占用大量带宽的蠕虫，一旦感染了这个，接口中断就很有可能了。设备效率也一样关键，经常出现DCS工作压力很大了，这时再看其通讯，就很难了。针对这种情况往往应该增加通讯卡件来提高效率；工作站负载也是影响大型系统接口效率的关键，很多大型系统的OPC都在工作站上，这时，如果工作站负载很重，OPC能分到的运行时间不足，又会影响效率，最终数据传输还是很缓慢，而且不稳定。OPC并非什么好协议，只不过因是中立国出的协议而如此广泛被使用罢了。如果这些都没有问题，那么最终协议总归协议，实现协议交互的软件质量还十分关键，在实施中，我们也经常会碰到因为质量不好的OPC，效率低、稳定性差导致整个系统不稳定的。
知道了以上内容，现场遇到问题，应逐个排除，不要一开始就责怪实时数据库不好，只有对症下药地解决问题，才能获得高效的系统。
接下去的内容将更加精彩，我们将探寻接口内部的奥秘，先给大家一张预览图：
谈到这里，就要谈到实时数据库为做到实时的考虑了。为了做到实时，实时数据库采取了“实时”的反面-》“缓存”，缓存是为了提高交互效率，从而使整体更加实时，这点后面将详细介绍。那么一个接口程序内部有什么呢？主要有两部分：现场接口协议栈和位号分组。当然，对于小型的接口，位号分组被省略了。位号分组是按照实时数据库组态的要求，按不同的频率采集实时数据。分组的优势在于降低了位号采集的工作量。要知道很多协议是慢速的（如串口协议）。如果实时数据库中仅要求5秒钟的采样频率，而下端却不作区分，按最快的频率采集，则往往效率就会降低，甚至影响到配置为高速采集的其它位号。因此，分组往往是必须的。协议栈则不用解释，大家都知道必须实现的。实现的好，则效率高、稳定性好。实时数据库接口中有定时器，在Windows平台上能获得的最高定时精度为40ms，因此采样周期高于40ms，没有意义。一般主动采集的频率都是1赫兹以下的（慢于1秒/次），更加快速的时候，均采用主动通知的方法，即当数据变化的时候，主动向实时数据库内核发送变化的数据，以达到更高效率。接口就简单介绍到这里，要明确的是，对于主动采集方式下，接口相当于多了一层缓存，在今后的讲解中，大家会发现，实时数据库的效率和缓存的层次多少很有关系。
简单谈谈分布式技术，大型分布式实时数据库都采用了一定的分布式技术，采用的技术不同，局限性也不同。COM/DCOM被熟知，被业界认同，是微软主要分布式技术，因此被广泛应用。但逃不出DCOM安全性的魔障，与Windows权限捆绑紧密。而且对于连接效率低的时候容易出错。跨平台能力则更是彻底不具备了。J2EE很好，但效率有些低，最近JAVA6出现后，效率已经有了显著提升。甚至比.Net快，但作为底层研发来说，采用J2EE很不合适，原因是其对硬件的访问能力较弱。随着以太网和工业通讯标准的提升，J2EE平台也许在工业应用上有后劲。目前多数实时数据库厂商采用了专用TCP/IP协议，优势是易跨平台，部署方便，稳定性容易掌控。但增加了掌控能力的同时也降低了对已有框架的集成，开发工作量大。从实时数据库所面向的应用场景来说，专用TCP/IP协议更加适合一些。
下面给出实时数据库的简化模型，后面的原理将结合这张图来讲解。
实时数据库被简化成由多个接口、一个接口管理模块、一个组态模块、一个实时模块、一个高速缓存和一个历史模块组成，上面覆以应用接口。这个结构基本适合大部分实时数据库，各模块运行需要的组态信息往往从组态模块中获取，高速缓存往往和历史模块、实时模块都发生关系。
接下去将讲解实时数据库的核心IO策略。
前面已经讲过了，实时数据库一般采用缓存来增加读实时数据的及时性，因此实时数据库核心中都有高速缓存，如上图所示，通过接口的采集，高速缓存的数据得到不断的更新，而当上层读位号的时候，实时数据库通过返回缓存的值来快速响应。因此，读一般是异步的。但写则一般是同步的，写意味着控制，控制意味着严格的时序性，同时，写也可能失败的，如果写是异步的，则可能以为成功了，但实际失败了，后果不堪设想。写的效率严重依赖于接口通讯效率和执行机构。如果只是修改设定值，则可以较快返回，如果直接写阀位等需要机械执行的值，那就慢了。由于缓存，则必然会产生时滞。实时数据库的采集手段使时滞不止存在于一处。假设实时数据库从OPC中采集数据，而OPC从设备上采集数据，如果OPC1秒采集一次，实时数据库5秒采集一次，实时数据库上有一个应用软件，也5秒采集一次，则此应用软件读到的数据的最大时滞为11秒（各时滞的相加和），最小时滞为5秒（几个时滞中最大的一个），在一般的情况下，时滞符合正态分布。
时滞频域的角度上来分析，实际上是波的相变。或称之为相移。相移在低速变化数据上显现的问题不是很明显，比如温度最快每分钟上升2度，影响并不明显，但对于快速开关量，则十分致命，这个很容易理解，如果时滞1秒，而开关的变化周期也接近1秒，则会出现一个现象，数据采集上来是关，实际现场则是开的，现场与采集值总是相反，如果这时进行控制，就会发现控制实效，关闭已经关闭的开关或打开已经打开的开关，没有意义。因此，实时数据库不适宜对快速开关量的控制。这是一种极端的情况，另一种则是波动较快的窄带控制，意味着必须将被控量控制在一个较窄的区域内，这时必须考虑时滞问题，如果时滞稳定，则可以按照控制理论采用抵消时滞或者前馈的方式获得较好的控制效果。而如果时滞变化很大，则通过实时数据库之上进行的控制则效果不明显了，很容易失控。
讲这些不是说实时数据库不能用于有控制的场合，知道哪些不适合，才能更加正确地使用实时数据库，应用好各种适合的场景。
谈到核心调度策略，就得讲讲多线程的核心，很少有实时数据库是单线程的，大型实时数据库中往往都有线程池，对于需要实时处理读、写、采集等任务的实时数据库核心，其调度策略必须慎重考虑。首先，为难的是往往很难判断那些任务的优先级更高。所以实时数据库内部往往通过判断位号的更新周期来间接揣测任务的优先级。虽然往往可以让多个现成自己竞争，但如果某个位号的更新周期位1秒，而另一个的更新周期为10秒，那么，可想而知，应用对1秒更新的实时数据的实时性要求高于10秒的。因此，如果有1秒的为好读任务没有完成，则不执行10秒的，对于CPU数量小于等待线程数量的时候，特别适用。另外，读即时值的任务优先级应该高于读历时值的任务，这个也可想而知的，读一段历时数据，往往不在乎晚响应几十微秒，而读实时值，则是越实时越好。这样，在实时数据库中就形成了一个内核级的读队列，任务可以被线程顺序执行，而如果低优先级的现成得以执行的时候，会检查一下是否还有更高优先级的队列中需要执行，如果有，则让出时间片。孔融让梨，保证更需要实时的任务先完成。对于写任务，往往可以和读任务并行，但CPU是昂贵资源，如果当前CPU被读占用而耽误了写，则不应该，因此，写更重要，排在更高的优先级。那么采集的优先级和读的优先级谁高呢？如果采集被滞后，那么多个可能读同一个位号的任务都将读到老的数据，因此，采集往往是一个与读优先级的最高优先级相当的任务。
具体到不同的实现者，以上的理论未必被完全的实现，有的小型和中型实时数据库甚至根本没有这些策略的实现，因为运行在其上的应用也不严格，因此也可以避繁就简。
呵呵，是不是对自己实现一个实时数据库更加有信心了？其实不那么容易，看这些原理，最重要的是帮助理解，不在于模仿，实现一个商用的实时数据库是公司的事情，个人没有必要将时间浪费到自己实现上，还是选一个合适的产品来使用。使用时通过原理来加深理解。
接下去，将讲到很多人想研究的实时数据库压缩算法，这个好像挺神秘的，我将结合PI的专利技术，旋转门压缩算法给予详细的讲解，拨开云雾见太阳，世上没有神秘的事情，只有不耐心的观众和不尽心的讲师。呵呵。
虽然今天很疲惫了，但是还是继续写吧，linkman已经开始对我不满了，呵呵。的确十分忙，但当一件事情开始做了以后，就放不下来。这里小跑一下题，
（一），关于实时数据库行业协会，网站在年底之前肯定预上线，这是我把它当作中心工作之一的。我十分期望等到网站一有，国内实时数据库行业的同仁有个平等交流的场所。
（二）Linkman一直关心标准的事情，我指的标准是数据采集接口的标准，这个标准比上层API更加重要，预计2007年底~2008年初，SUPCON将向协会成员发出第一个讨论稿。
言归正传了。说到数据压缩，无非有损和无损。无损的一般通过各类近似霍夫曼编码的方法压缩数据，二有损则是采用线性拟合的方法。实时数据是如此海量，大家真的能用的方法都用上了。无损压缩不是我讲的重点，我自己也编写过这类压缩工具，zip、rar等等，基本上是这一思路，大家另行搜索来学习。这里讲的是实时数据库中最常用的有损线性拟合算法。拟合方式很多，最著名的无过于OSI 的“旋转门”，这个太著名了，以至于很多用户都知道。到底旋转门是怎么回事呢？娓娓道来如下：
首先讲当前采集的一个数据位门轴，看着上面的膜片哦，最左下角的就是门轴，然后每新采一个点，就将这个点和门轴画一条线，就是所谓的门，当再采下一个点的时候，就从门轴向新点画一条线，作为新的门位置，看看，门就“旋转”了一定角度，然后看看从门轴到门边中所有的点是否都距离门在一个阈值内，如果是，也就是说可以用两点一线的门拟合中间若干点，显然压缩掉了大量数据。如果不行了，则将原来与门轴组成门的那个点记录下来（此点将写入历时数据库），然后将此点作为新的门轴，以此门轴与最新的点构成新的门。
这显然是一个迭代算法，而且好处是明显的，这样计算，涉及到的乘除法很少，效率应该较高。所以PI一直用这个算法作为其核心压缩算法。SUPCON采取了最小二次拟合的方法，原因是现在的计算机浮点能力大大增强，同时发现最小二次线性拟合的方法的迭代算法运算量也很小。效果和效率都很好。因此申请了专利。国内很多实时数据库迄今没有自己的算法，仍然侵犯着PI的专利，呵呵。不过这也没有什么，OSI不计较，它在国内没有申请旋转门的专利，因此“旋转门”是一个很好的教材。
所有的有损压缩算法基本类似，有的数据库还将无损和有损两种结合起来，即先有损压缩，然后再无损压缩，最终保存压缩结果，这样查询历时数据的时候多了解压过程，速度会进一步降低，但空间也进一步节省。压缩是双刃剑。我特别告诉大家，千万不要相信某些产品宣扬自己的压缩比如何高，通过以上原理知道，压缩比高的原因就是因为阈值大，阈值大，损失就多，得到的趋势反应的细节就少。一般实际应用，流程工业采用10：1的压缩很合适，超过此数据，会发现大量有用的细节都不见了。这样方法也是一种低通滤波，低通滤波伴随着时滞增大，因此不要迷信。呵呵。掌握原理，合理设定压缩阈值，才是最好的方法。
实际上，实时数据库中也使用了大量的索引技术，绝对不是关系数据库的专利，因此，接下去将讲讲索引技术：
做工控和自动化这行，年底特别紧张，因此博客有一段时间没有更新了。惭愧之至。
回到主题，谈到索引，这个技术在所有的检索系统中不可或缺的。而对于数据结构，最重要的部分之一就是索引技术。各种技术速度和面向的场景差异很大。有哈希树、哈希桶、其他散列表、二叉树等等，不胜枚举。所以本文仅仅拿出几种经典的情况出来讨论一下。
实时数据库中，用来定位一个位号，可以通过ID和名称，ID和名称都是唯一的，但因实时数据库的实现不同，一些实时数据库实现中ID是静态的，而有些实时数据库实现则会动态分配ID，即实时数据库每次启动，ID可能不同。对于名称索引，采用哈希表的方式建立索引的情况最多。了解C字符串实现的人都知道，C的字符串比较是比较低效的，因此，往往不利用最基本的C字符串建立哈希，而采取用封装成String的类对象最为键值。那么，为什么还有句柄呢？句柄往往和ID是一致的。在实时数据库的上层应用中，往往遇到的工况是多次读取一个位号值的情况，虽然句柄不保证静态唯一，但动态唯一也足以加速定位一个位号的速度。ID和句柄一般会才具数组下标或者指针地址来实现，这样定位的速度将大幅度提升。但如果句柄弄错了，则位号将定位到另一个实例上，很难发觉。因此，正确使用快速索引的方式是：
应用启动->通过位号名获取位号句柄->使用句柄快速访问位号值
至于时间戳索引，在查询历史值的时候与句柄常常同时使用。在实时数据库中，往往将数据按时间分块存储，时间戳索引此时用于定位一个块。在块内，时间戳索引的查找方式因实现有很大不同。一种高效的方式是二分法查找，效率与平衡二叉树相同，却省去了平衡二叉树的本身庞大的存储空间。
最后谈谈位号分组，很多时候要将位号分组，举个例子，如果实时数据库中每个用户访问的数据仅仅是很小的一个子集，那么实时数据库的实现中往往将这些位号分成一个组。分组过程是在用户调用数据的过程中实现的。这样，当用户再对实时数据库进行访问的时候，实时数据库核心将首先在分组中进行查询，看看所需位号是否在组中。如果一个实时数据库中有20万个位号，而一个应用日常使用的位号为3000个，那么，查询分组索引的效率要大大高于全局查找。分组其实是一种缓存索引，它的存在的确可以大大加速位号交互。
实时数据库常用压缩算法介绍
原理介绍
什么是Huffman压缩Huffman( 哈夫曼 ) 算法在上世纪五十年代初提出来了，它是一种无损压缩方法，在压缩过程中不会丢失信息熵。并且能够证明 Huffman 算法在无损压缩算法中是最优的。Huffman 原理简单，实现起来也不困难，在如今的主流压缩软件得到了广泛的应用。相应用程序、重要资料等绝对不同意信息丢失的压缩场合， Huffman 算法是非常好的选择。
怎么实现Huffman压缩哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（比如，文本文件里的字符）用一个特定长度的位序列替代。因此。在文件里出现频率高的符号，使用短的位序列。而那些非常少出现的符号。则用较长的位序列。
二叉树
在计算机科学中。二叉树是每个结点最多有两个子树的有序树。
通常子树的根被称作 “ 左子树 ” （ left subtree ）和 “ 右子树 ” （ right subtree ）。
哈夫曼编码 (Huffman Coding)
哈夫曼编码是一种编码方式，哈夫曼编码是可变字长编码 (VLC) 的一种。 uffman 于 1952 年提出一种编码方法。该方法全然依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作 Huffman 编码。
Huffman编码生成步骤
扫描要压缩的文件，对字符出现的频率进行计算。把字符按出现的频率进行排序，组成一个队列。把出现频率最低（权值）的两个字符作为叶子节点。它们的权值之和为根节点组成一棵树。把上面叶子节点的两个字符从队列中移除，并把它们组成的根节点增加到队列。把队列又一次进行排序。反复步骤 3、4、5 直到队列中仅仅有一个节点为止。把这棵树上的根节点定义为 0 （可自行定义 0 或 1 ）左边为 0 。右边为 1 。这样就能够得到每个叶子节点的哈夫曼编码了。
如 (a) 、 (b) 、 (c) 、 (d) 几个图，就能够将离散型的数据转化为树型的了。
假设假设树的左边用0 表示右边用 1 表示。则每个数能够用一个 01 串表示出来。
则能够得到相应的编码例如以下：
1–>110
2–>111
3–>10
4–>0
每个01 串，既为每个数字的哈弗曼编码。
为什么能压缩
压缩的时候当我们遇到了文本中的1 、 2 、 3 、 4 几个字符的时候，我们不用原来的存储，而是转化为用它们的 01 串来存储不久是能减小了空间占用了吗。（什么 01 串不是比原来的字符还多了吗？怎么降低？）大家应该知道的。计算机中我们存储一个 int 型数据的时候一般式占用了 2^32-1 个 01 位，由于计算机中全部的数据都是最后转化为二进制位去存储的。所以。想想我们的编码不就是仅仅含有 0 和 1 嘛，因此我们就直接将编码依照计算机的存储规则用位的方法写入进去就能实现压缩了。
比方：
1这个数字。用整数写进计算机硬盘去存储，占用了 2^32-1 个二进制位
而假设用它的哈弗曼编码去存储，仅仅有110 三个二进制位。
效果显而易见。
编码实现
流程图
编码流程
1.数据结构
CharacterWeight：记录字符值。以及其在待压缩文件里的权重。
HuffmanNode：huffman树中的节点信息。
1.程序关键步骤
Huffman树的构建
Huffman树的变量：ArrayList list；
流程图
i++i<n-1结束yesno
代码：
依据Huffman 树获得Huffman编码
从叶子节点開始网上遍历Huffman树，直到到达根节点，依据当前节点为其父节点的左儿子还是右儿子确定这一位值是0还是1。最后将依次获得的0,1字符串反转获得Huffman编码。
头文件设计
文件头长度（单位： byte）
l= 9n
当中n 为字符种类数。
文件内容的编码和写入
代码：
解码实现
流程图
数据结构
HuffmanNode：huffman树中的节点信息。
程序关键步骤
重建Huffman树。
在文件头中存放的原本就是Huffman树的节点信息。
解码
流程图
代码：
总结
网友评论