数据流压缩原理实现（huffman编码，LZ77压缩算法)

一、数据压缩的原理

规则压缩：已知数据的排列组合模式，通过抽象用数学公式来表示。比如矢量图，3D模型的顶点数据等。

对于未知规则的数据：则是采用一种更高效的编码来代替原有数据的编码。一种方法是找出数据中那些重复出现的字符串，然后用更短的符号代替。

比如有一条句子中大量出现了以下短语：

“中华人民共和国”

如果通过一种映射关系，用"中国"来代替它，则就缩短了5个字符，如果用"华"来代替，则缩短了6个字符。

只要保证前后的队应关系，可以用任意字符来代替那些重复出现的字符。

本质上，“压缩”就是找出文件内容的概率分布，将那些出现概率高的部分代为更短的形式。所以内容越是重复的文件，可以压缩的更小。

比如 "ABABABABABABAB" 可以通过一种编码压缩成 "7AB"

相应地，如果内容毫无重复，就很难压缩。极端情况就是，遇到那些均匀分布的随机字符，可能往往一个字符都压缩不了。

比如任意排列的10个阿拉伯数字。 (5271839406）就是无法压缩的；再比如，无理数(Π)也很难压缩。

1. 压缩极限

香农极限定理：假设一个串可以用N种符号来编码表示，每种符号出现的概率为 $p_n$

定义信息熵：表示编码这段信息需要的二进制比特数。

1）下面是一个例子。假定两个文件都包含1024个符号，在ASCII码的情况下，它的长度是相等的，都是1KB。

甲文件的内容50%是a, 30%是b， 20%是c，文本里只有abc, 则根据上面信息熵的定义。平均每个符号要占用1.49个二进制位。

计算过程如下

2）比如每个字节的概率是0~255，均匀分布每个数值出现的概率是1/256 ，如果一段文字的字节值是平均分布，则 pn = 1/ 256, 计算出极限位8 （bit).

2. Deflate压缩算法

deflate是zip压缩文件的默认算法。其实deflate不光用在zip文件，7z，xz等其他压缩文件中都使用。它是一种压缩数据流的算法。任何需要流式压缩的地方都可以使用。

deflate算法下的压缩器有三种压缩模型：

1）不压缩数据，对于已经压缩过的数据，这是一种明智的选择。

2）压缩，先用LZ77，然后再用huffman编码。在这个模型中压缩的树是Deflate规范定义的，所以不需要额外空间来存储这个树。

3）压缩，先用LZ77，然后用huffman编码。压缩树是由压缩器生成的，并于数据一起存储。

数据被分割成不同的块，每个快使用单一的压缩模式 。如果压缩器要在这三种压缩模式中互相切换，必须先结束当前的快，重新开始一个新的块。

3. 信息熵

数据为何是可以压缩的？因为数据都会表现出一定的特性，称为信息熵。（也就是上面的香农极限定理）绝大多数的数据锁表现出来的容量往往大于其信息熵锁建议的最佳容量。

也就是数据会存在一定的冗余性，我们可以把冗余的数据采用更少的位对频繁出现的字符进行标记，也可以基于数据的一些特性基于字典编码，代替重复多余的短语。

二. LZ77算法原理

Ziv 和 Lempel 于 1977 年发表题为“顺序数据压缩的一个通用算法（A Universal Algorithm for Sequential Data Compression ）。 LZ77 压缩算法采用字典的方式进行压缩，
是一个简单但十分高效的数据压缩算法。其方式就是把数据中一些可以组织成短语(最长字符)的字符加入字典，然后再有相同字符出现采用标记来代替字典中的短语，如此通
过标记代替多数重复出现的方式以进行压缩。要理解这种算法，需先了解 3 个关键词:短语字典，滑动窗口和向前缓冲区。

1. 关键词术语

a. 向前缓冲区

每次读取数据的时候，先把一部分数据预载入前向缓冲区。为移入滑动窗口做准备。

b. 滑动窗口

一旦数据通过缓冲区࿰

using System.IO.Compression; using System.Linq; using System.Runtime.Serialization.Formatters.Binary; using Sy...

一、压缩原理压缩原理其实很简单，就是找出那些重复出现的字符串，然后用更短的符号代替，从而达到缩短字符串的目的。比如，有一篇文章大量使用"中华人民共和国"这个词语，我们用"中国"代替，就缩短了 5 个字符，如果用"华"代替，就缩短了6个字符。事实上，只要保证对应关系，可以用任意字符代替那些重复出现的字符串本质上，所谓" 压缩 "就是找出文件内容的概率分布，将那些出现概率高的部分代替成更短的形式。所以：内容越是重复的文件，就可以压缩地越小。比如，"ABABABABABABAB"可以压缩成"7AB"

{************************************************************************** TStream.Create之后，其position的值自动设置为0，其他操作必须人工干预position，否则position的取值为上一次操作之后的位置。关键点： 数据流 存入内容之前必须确定编码格式，至于想用何种编码并不重要，但必须明确的设置，否则在进行压缩、编码之后，还原原文时会有问题，按道理用默认编码是一样的，可是若没有明确设置流的存储编码就是有问题，这个问题困扰了我整整两个星期，啥办法都尝试过直到写出这个才算解决了。但至于用默认编码为何不行，现在还未弄明白，希望有网友能解惑。 ***************************************************************************}

import java.io.ByteArrayInputStream; import java.io.ByteArrayOutputStream; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream;... 哈夫曼树（ HuffMan Tree ）是用来压缩数据的一种数据结构，它适合压缩数据重复率较高的情况。文本A：123456789，这串文本重复率为0，因为每个字符都是唯一的，没有重复率而言；文本B：111222334，这串文本重复率明显较A高，适合用哈夫曼树压缩。问题与分析现在想把“aaaabbbccdeefffgggg”这个字符串保存到硬盘上，如果直接保存，它会占用多大空间？回顾一下，每个英文字母都可以用一个ASCII码表示，例如 a=97，b=98，…… 而每个ASCII码是 1

相关链接： Java 压缩技术（一） ZLib Java 压缩技术（二） ZIP 压缩 ——Java原生实现 Java 压缩技术（三） ZIP解压缩 ——Java原生实现 Java 压缩技术（四） GZIP——Java原生实现 Java 压缩技术（五） GZIP相关——浏览器解析Java 压缩技术（六） BZIP2——Commons 实现 Java 压缩技术（七） TAR——Commons 实现 ...