哈夫曼无损压缩

① 无损压缩算法是什么样的

WinRAR是采用它自己的独创的压缩算法。
【希望你能看看最优二叉树（哈夫曼树），理解哈夫曼编码的原理，对你的这个压缩算法会有很明晰的指导和解惑作用】WinRAR是采用它自己的独创的压缩算法。

压缩处理都是以二进制的方式进行的。这和你的编码有关。只要是处理后的结果比原文档文件小，而且是可逆的还原，就是无压缩。
压缩率的大小和你的编码方式有关。

无损压缩是指重构压缩数据(还原，解压缩)，而重构数据与原来数据完全相同。该方法用于那些要求重构信号与原始信号完全一致的场合，如文本数据、程序和特殊应用场合的图像数据(如指纹图像、医学图像等)的压缩。这类算法压缩率较低，一般为1／2~1／5。典型的无损压缩算法有：Shanno-Fano编码、Huffman(哈夫曼)编码、算术编码、游程编码、LZW编码等。

基于哈夫曼编码原理的压缩算法：
哈夫曼算法的过程为：统计原始数据中各字符出现的频率；所有字符按频率降序排列；
比如有一个字符串：aaaaaaaaaabbbbbbcccd
原文件大小存储需要20个字节。如果按频率出现的次数高低，给予字符串中的每个字符不同的编码长度，就可以达到压缩的目的。
如
a编码为01（占用2个bit）
b编码为00（占用2个bit）
c编码为000,（占用3个bit）
c编码为001,（占用3个bit）
那就压缩后的总长为(2*10+2*6+3*3+1*3)/8 =5.5个字节。

另外在解码的时候，要告之对方你的编码方式，需要把编码的规则传递过去。

如果对于以上字符串，你也可以按aaaaaaaaaa编码成一个1，bbbbbb为2，ccc为3,d为4。这样压缩后的内容为最小，但是要注意一点，这时你的编码规则为最大，你要把你的编码规则发给对方的时候，有可能编编解码规则文件可能会比压缩后的内容还要大。最终结果为造成压缩后的文件比原文件还要大。

② C语言都有哪些经典的无损压缩算法

C语言经典的无损压缩算法有：哈夫曼算法、LZ。

哈夫曼算法：
哈夫曼编码是David A. Huffman于1952年发明的一种满足对编码算法要求的一种编码算法。
哈夫曼算法是利用频率信息构造一棵二叉树，频率高的离根节点近（编码长度短），频率低的离根节点远（编码长度长），手动构造方法是先将字母按照频率从小到大排序，然后不断选择当前还没有父节点的节点中权值最小的两个，构造新的父节点，父节点的值为这两个节点值的和，直到构造成一棵二叉树。

LZ算法：
LZ算法及其衍生变形算法是压缩算法的一个系列。LZ77和LZ78算法分别在1977年和1978年被创造出来。虽然他们名字差不多，但是算法方法完全不同。这一系列算法主要适用于字母数量有限的信息，比如文字、源码等。流行的GIF和PNG格式的图像，使用颜色数量有限的颜色空间，其压缩就采用了两种算法的灵活变形应用。

③ 利用huffman编码对文件进行压缩，不同文件类型压缩率有差别的原因

怎么没人回答呢 我来回答吧 我想从压缩文件的原理能得到你这个问题的答案（有点长，请耐心看，绝对长知识）： 压缩文件的运行原理 如果您从互联网上下载了许多程序和文件，可能会遇到很多ZIP文件。这种压缩机制是一种很方便的发明，尤其是对网络用户，因为它可以减小文件中的比特和字节总数，使文件能够通过较慢的互联网连接实现更快传输，此外还可以减少文件的磁盘占用空间。在下载了文件后，计算机可使用WinZip或Stuffit这样的程序来展开文件，将其复原到原始大小。如果一切正常，展开的文件与压缩前的原始文件将完全相同。
乍一听好像很神秘：您是怎样减少比特和字节的数量并将它们原封不动地还原回去的呢？等一切水落石出之后，您会发现这个过程背后的基本理念其实非常简单明了。在本文中，我们将讨论这种通过简单压缩来明显减小文件的方法。
大多数计算机文件类型都包含相当多的冗余内容——它们会反复列出一些相同的信息。文件压缩程序就是要消除这种冗余现象。与反复列出某一块信息不同，文件压缩程序只列出该信息一次，然后当它在原始程序中出现时再重新引用它。
以我们熟悉的信息类型——单词——为例子。
肯尼迪（John F. Kennedy）在1961年的就职演说中曾说过下面这段着名的话：
Ask not what your country can do for you——ask what you can do for your country.（不要问国家能为你做些什么，而应该问自己能为国家做些什么。）
这段话有17个单词，包含61个字母、16个空格、1个破折号和1个句点。如果每个字母、空格或标点都占用1个内存单元，那么文件的总大小为79个单元。为了减小文件的大小，我们需要找出冗余的部分。
我们立刻发现：
如果忽略大小写字母间的区别，这个句子几乎有一半是冗余的。九个单词（ask、not、what、your、country、can、do、for、you）几乎提供了组成整句话所需的所有东西。为了构造出另一半句子，我们只需要拿出前半段句子中的单词，然后加上空格和标点就行了。
大多数压缩程序使用基于自适应字典的LZ算法来缩小文件。“LZ”指的是此算法的发明者Lempel和Ziv，“字典”指的是对数据块进行归类的方法。
排列字典的机制有很多种，它也可以像编号列表那样简单。在我们检查肯尼迪这句着名讲话时，可以挑出重复的单词，并将它们放到编号索引中。然后，我们直接写入编号而不是写入整个单词。
因此，如果我们的字典是：
ask
what
your
country
can
do
for
you
我们的句子现在就应该是这样的：
1 not 2 3 4 5 6 7 8-- 1 2 8 5 6 7 3 4
如果您了解这种机制，那么只需使用该字典和编号模式即可轻松重新构造出原始句子。这就是在展开某个下载文件时，计算机中的解压缩程序所做的工作。你可能还遇到过能够自行解压缩的压缩文件。若要创建这种文件，编程人员需要在被压缩的文件中设置一个简单的解压缩程序。在下载完毕后，它可以自动重新构造出原始文件。
但是使用这种机制究竟能够节省多少空间呢？“1 not 2 3 4 5 6 7 8——1 2 8 5 6 7 3 4”当然短于“Ask not what your country can do for you-- ask what you can do for your country.”，但应注意的是，我们需要随文件一起保存这个字典。
在实际压缩方案中，计算出各种文件需求是一个相当复杂的过程。让我们回过头考虑一下上面的例子。每个字符和空格都占用1个内存单元，整个原句要占用79个单元。压缩后的句子（包括空格）占用了37个单元，而字典（单词和编号）也占用了37个单元。也就是说，文件的大小为74个单元，因此我们并没有把文件大小减少很多。
但这只是一个句子的情况！可以想象的是，如果用该压缩程序处理完肯尼迪讲话的其余部分，我们会发现这些单词以及其他单词重复了更多次。而且，正如下一节所言，为了得到尽可能高的组织效率，可以对字典进行重写。
在上一个的例子中，我们挑出了所有重复的单词并将它们放在一个字典中。对于我们来说，这是最显而易见的字典编写方法。但是压缩程序却不这样认为：它对单词没有概念——它只会寻找各个模式。为了尽可能减小文件的大小，它会仔细挑选出最优模式。
如果从这个角度处理该句子，我们最终会得到一个完全不同的字典。
如果压缩程序扫描肯尼迪的这句话，它遇到的第一个冗余部分只有几个字母长。在ask not what your中，出现了一个重复的模式，即字母t后面跟一个空格——在not和what中。如果压缩程序将此模式写入字典，则每次出现“t”后面跟一个空格的情况时，它会写入一个“1”。但是在这个短句中，此模式的出现次数不够多，不足以将其保留为字典中的一个条目，因此程序最终会覆盖它。
程序接下来注意到的内容是ou，在your和country中都出现了它。如果这是一篇较长的文档，将此模式写入字典会节省大量空间——在英语中ou是一个十分常见的字母组合。但是在压缩程序看完整个句子后，它立即发现了一个更好的字典条目选择：不仅ou发生了重复，而且your和country整个单词都发生了重复，并且它们实际上是作为一个短语your country一起发生重复的。在本例中，程序会用your country条目覆盖掉字典中的ou条目。
短语can do for也发生了重复，一次后面跟着your，另一次跟着you，因此我们又发现can do for you也是一种重复模式。这样，我们可以用一个数字来代替15个字符（包含空格），而your country只允许我们用一个数字代替13个字符（包含空格），所以程序会用r country条目覆盖your country条目，然后再写入一个单独的can do for you条目。程序通过这种方式继续工作，挑出所有重复的信息，然后计算应该将哪一种模式写入字典。基于自适应字典的LZ算法中的“自适应”部分指的就是这种重写字典的能力。程序执行此工作的过程实际上非常复杂。
无论使用什么方法，这种深入搜索机制都能比仅仅挑出单词这种方法更有效率地对文件进行压缩。如果使用我们上面提取出的模式，然后用“__”代替空格，最终将得到下面这个更大的字典：
ask__
what__­
you
r__country
__can__do__for__you
而句子则较短：
“1not__2345__--__12354”
句子现在占用18个内存单元，字典占用41个单元。所以，我们将文件总大小从79个单元压缩到了59个单元！这仅仅是压缩句子的一种方法，而且不一定是最高效的方法。（看看您能找到更好的方法吗！）
那么这种机制到底有多好呢？文件压缩率取决于多种因素，包括文件类型、文件大小和压缩方案。
在世界上的大多数语言中，某些字母和单词经常以相同的模式一起出现。正是由于这种高冗余性，而导致文本文件的压缩率会很高。通常大小合适的文本文件的压缩率可以达到50%或更高。大多数编程语言的冗余度也很高，因为它们的命令相对较少，并且命令经常采用一种设定的模式。对于包含大量不重复信息的文件（例如图像或MP3文件），则不能使用这种机制来获得很高的压缩率，因为它们不包含重复多次的模式。
如果文件有大量重复模式，那么压缩率通常会随着文件大小的增加而增加。从我们的例子中就可以看出这一点——如果我们摘录的肯尼迪讲话再长一些，您会发现又多次出现了我们字典中的模式，因此能够通过每个字典条目节省更多的文件空间。此外，对于更大的文件，还可能出现具有更大普遍性的模式，从而能够创建出效率更高的字典。
此外，文件压缩效率还取决于压缩程序使用的具体算法。有些程序能够在某些类型的文件中更好地寻找到模式，因此能更有效地压缩这些类型的文件。其他一些压缩程序在字典中又使用了字典，这使它们在压缩大文件时表现很好，但是在压缩较小的文件时效率不高。尽管这一类的所有压缩程序都基于同一个基本理念，但是它们的执行方式却各不相同。程序开发人员始终在尝试建立更好的压缩机制。
有损压缩和无损压缩
我们在上文中讨论的压缩类型称为无损压缩，因为您重新创建的文件与原始文件完全相同。所有无损压缩都基于这样一种理念：将文件变为“较小”的形式以利于传输或存储，并在另一方收到它后复原以便重新使用它。
有损压缩则与此大不相同。这些程序直接去除“不必要”的信息，对文件进行剪裁以使它变得更小。这种类型的压缩大量应用于减小位图图像的文件大小，因为位图图像的体积通常非常庞大。为了了解有损压缩的工作原理，让我们看看你的计算机如何对一张扫描的照片进行压缩。
对于此类文件，无损压缩程序的压缩率通常不高。尽管图片的大部分看起来都是相同的——例如，整个天空都是蓝色的——但是大部分像素之间都存在微小的差异。为了使图片变得更小同时不降低其分辨率，您必须更改某些像素的颜色值。如果图片中包含大量的蓝色天空，程序会挑选一种能够用于所有像素的蓝色。然后，程序重写该文件，所有天空像素的值都使用此信息。如果压缩方案选择得当，您不会注意到任何变化，但是文件大小会显着减小。
当然，对于有损压缩，在文件压缩后您无法将其复原成原始文件的样子。您必须接受压缩程序对原始文件的重新解释。因此，如果需要完全重现原来的内容（例如软件应用程序、数据库和总统就职演说），则不应该使用这种压缩形式。

④ 压缩算法原理

哈夫曼
哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多为来表示。

哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。

2.1 原理
我不打算探究哈夫曼编码的所有实际的细节，但基本的原理是为每个符号找到新的二进制表示，从而通常符号使用很少的位，不常见的符号使用较多的位。

简短的说，这个问题的解决方案是为了查找每个符号的通用程度，我们建立一个未压缩数据的柱状图；通过递归拆分这个柱状图为两部分来创建一个二叉树，每个递归的一半应该和另一半具有同样的权（权是 ∑ N K =1 符号数 k , N 是分之中符号的数量，符号数 k 是符号 k出现的次数 ）

这棵树有两个目的：

1． 编码器使用这棵树来找到每个符号最优的表示方法

2． 解码器使用这棵树唯一的标识在压缩流中每个编码的开始和结束，其通过在读压缩数据位的时候自顶向底的遍历树，选择基于数据流中的每个独立位的分支，一旦一个到达叶子节点，解码器知道一个完整的编码已经读出来了。

压缩后的数据流是 24 位（三个字节），原来是 80 位（ 10 个字节）。当然，我应该存储哈夫曼树，这样解码器就能够解码出对应的压缩流了，这就使得该例子中的真正数据流比输入的流数据量大。这是相对较短的数据上的副作用。对于大数据量来说，上面的哈夫曼树就不占太多比例了。

解码的时候，从上到下遍历树，为压缩的流选择从左 / 右分支，每次碰到一个叶子节点的时候，就可以将对应的字节写到解压输出流中，然后再从根开始遍历。

2.2 实现
哈夫曼编码器可以在基本压缩库中找到，其是非常直接的实现。

这个实现的基本缺陷是：

1． 慢位流实现

2． 相当慢的解码（比编码慢）

3． 最大的树深度是 32 （编码器在任何超过 32 位大小的时候退出）。如果我不是搞错的话，这是不可能的，除非输出的数据大于 2 32字节。

另一方面，这个实现有几个优点：

1． 哈夫曼树以一个紧密的形式每个符号要求 12 位（对于 8 位的符号）的方式存储，这意味着最大的头为 384 。

2． 编码相当容易理解

哈夫曼编码在数据有噪音的情况（不是有规律的，例如 RLE ）下非常好，这中情况下大多数基于字典方式的编码器都有问题。

⑤ 利用哈夫曼编码进行压缩压缩率一般达到多少

哈夫曼编码进行压缩的压缩率是根据平均码长来计算的，压缩率比较低。

例如：用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：

4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61

2.61/3=0.87=87%

其平均码长是等长码的87%，所以平均压缩率为13%。

哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。

Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

压缩率，描述压缩文件的效果名，是文件压缩后的大小与压缩前的大小之比，例如：把100m的文件压缩后是90m，压缩率为90/100*100%=90%，压缩率一般是越小越好，但是压得越小，解压时间越长。

(5)哈夫曼无损压缩扩展阅读

哈夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。

每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的哈夫曼编码。

⑥ 如何写压缩软件，运用哈夫曼算法实现

到文件压缩大家很容易想到的就是rar,zip等我们常见的压缩格式。然而，还有一种就是大家在学习数据结构最常见到的哈夫曼树的数据结构，以前还不知道他又什么用，其实他最大的用途就是用来做压缩，也是一些rar,zip压缩的祖先，称为哈弗曼压缩（什么你不知道谁是哈弗曼，也不知道哈弗曼压缩，不急等下介绍）。

随着网络与多媒体技术的兴起，人们需要存储和传输的数据越来越多，数据量越来越大，以前带宽有限的传输网络和容量有限的存储介质难以满足用户的需求。

特别是声音、图像和视频等媒体在人们的日常生活和工作中的地位日益突出，这个问题越发显得严重和迫切。如今，数据压缩技术早已是多媒体领域中的关键技术之一。

一、什么是哈弗曼压缩

Huffman(哈夫曼)算法在上世纪五十年代初提出来了，它是一种无损压缩方法，在压缩过程中不会丢失信息熵，而且可以证明Huffman算法在无损压缩算法中是最优的。Huffman原理简单，实现起来也不困难，在现在的主流压缩软件得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合，Huffman算法是非常好的选择。

二、怎么实现哈弗曼压缩

哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。

故我们得了解几个概念：

1、二叉树：在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。2、哈夫曼编码(Huffman Coding)：是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。三、哈夫曼编码生成步骤：

①扫描要压缩的文件，对字符出现的频率进行计算。

②把字符按出现的频率进行排序，组成一个队列。

③把出现频率最低（权值）的两个字符作为叶子节点，它们的权值之和为根节点组成一棵树。

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

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

⑥把这棵树上的根节点定义为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三个二进制位。
效果显而易见。

⑦ 如何用哈夫曼编码实现英文文本的压缩和解压缩

哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。有人用C函数写了这个编码，见下面链接

http://ke..com/view/189694.htm