java哈夫曼编码压缩

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

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

例如：用三位二进行数进行的等长编码平均长度为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%，压缩率一般是越小越好，但是压得越小，解压时间越长。

(1)java哈夫曼编码压缩扩展阅读

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

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

B. 哈夫曼编码与译码 java

class HaffmanNode //哈夫曼树的结点类
{
int weight; //权值
int parent,left,right; //父母结点和左右孩子下标

public HaffmanNode(int weight)
{
this.weight = weight;
this.parent=-1;
this.left=-1;
this.right=-1;
}
public HaffmanNode()
{
this(0);
}
public String toString()
{
return this.weight+", "+this.parent+", "+this.left+", "+this.right;
}
return code;
}

public static void main(String[] args)
{
int[] weight={5,29,7,8,14,23,3,11}; //指定权值集合
HaffmanTree htree = new HaffmanTree(weight);
System.out.println("哈夫曼树的结点数组:\n"+htree.toString());
String[] code = htree.haffmanCode();
System.out.println("哈夫曼编码:");
for (int i=0; i<code.length; i++)
System.out.println(code[i]);
}
}

C. 哈夫曼编码（理论）

哈夫曼编码是一种无损压缩文件一种方法，他的思路很简单，却又十分经典，他利用的是无重复前缀这种思想，就是每个字符的前缀是唯一的，若a的编码是001，那么就不会存在另一个以001开头的编码了，因为，哈夫曼编码是以二叉树为基础实现的，而二叉树到每一个叶子节点的路径是唯一的，那么也就是说每一个字符的编码也是唯一的。

哈夫曼编码是一种变长编码，比起定长编码的ascii码来说，哈夫曼编码能节省很多的空间，因为每一个字符出现的频率不是一致的，例如在英语中，‘e’出现的次数是最高的，那么如果我把‘e’的编码定义的短一点，那么是不是比起定长编码来说，空间就减少了？

基于这种思路，哈夫曼编码的具体实现过程如下：
（1）首先统计文本中各字符出现的频率（权重）。
（2）使用这些频率（权重），构建出哈夫曼树。
（3）规定从根节点开始，向叶子节点行走，经过左子树，编码为0，右子树，编码为1，这样就能得到每一个叶子节点字符的编码值了。

D. 为什么说哈夫曼编码是压缩率最高的编码

假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。

哈夫曼编码 根据上面可得编码表： a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000

用三位二进行数进行的等长编码平均长度为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%。

因为定长编码已经用相同的位数这个条件保证了任一个字符的编码都不会成为其它编码的前缀,所以这种情况只会出现在变长编码当中，要想避免这种情况，

就必须用一个条件来制约定长编码，这个条件就是要想成为压缩编码，变长编码就必须是前缀编码，所谓的前缀编码就是任何一个字符的编码都不能是另一个字符编码的前缀。

(4)java哈夫曼编码压缩扩展阅读：

实际应用中，除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，

例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。按照CCITT标准，需要统计2×1728种游程（长度），

这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。其中q称主码，r为基码。编码时，不小于64的游程长度由主码和基码组成。而当l为64的整数倍时，只用主码的代码，已不存在基码的代码。

E. 用java实现哈夫曼编码

只要自己再加个类Tree就可以了。
代码如下：

public class Tree {
double lChild, rChild, parent;
public Tree (double lChild, double rChild, double parent) {
this.lChild = lChild;
this.rChild = rChild;
this.parent = parent;
}
public double getLchild() {
return lChild;
}
public void setLchild(double lChild) {
this.lChild = lChild;
}
public double getRchild() {
return rChild;
}
public void setRchild(double rChild) {
this.rChild = rChild;
}
public double getParents() {
return parent;
}
public void setParents(double root) {
this.parent = root;
}

}

F. 哈夫曼编码的压缩实现

压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点：
CHuffmanNode nodes[511];
for(int nCount = 0; nCount < 256; nCount++)
nodes[nCount].byAscii = nCount;
其次，计算在输入缓冲区数据中，每个ASCII码出现的频率：
for(nCount = 0; nCount < nSrcLen; nCount++)
nodes[pSrc[nCount]].nFrequency++;
然后，根据频率进行排序：
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
哈夫曼树，获取每个ASCII码对应的位序列：
int nNodeCount = GetHuffmanTree(nodes); 构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。
// parent node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency; 有一个好的诀窍来避免使用任何队列组件。ASCII码只有256个，但实际分配了511个(CHuffmanNode nodes[511])，前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中：
int nDesIndex = 0;
// loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex>>3)) |=
nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
(nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面
(nDesIndex&7): &7 得到最高位.
此外，在压缩缓冲区中，必须保存哈夫曼树的节点以及位序列，这样才能在解压缩时重新构造哈夫曼树（只需保存ASCII值和对应的位序列）。 解压缩比构造哈夫曼树要简单的多，将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此，为了用ASCII值替换编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后将它的ASCII值添加到输出缓冲区中：
int nDesIndex = 0;
DWORD nCode;
while(nDesIndex < nDesLen)
{
nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
pNode = pRoot;
while(pNode->pLeft)
{
pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
nCode >>= 1;
nSrcIndex++;
}
pDes[nDesIndex++] = pNode->byAscii;
}