哈夫曼树是数据结构的一种,用于实现无损压缩。压缩分为无损压缩和有损压缩,使用哈夫曼压缩的压缩比可达3:1到5:1,流行的有损压缩方法有lzw字典压缩等。
几个名词解释:
最优二叉树:树的加权路径总长度最短的二叉树。
权值:每个叶子节点带有一定的权值,在哈夫曼树中为该叶子节点代表的字符的出现频率。
树的加权路径总长度:各叶子节点到根节点的路径长度与该节点的权的乘积的总和。
加权路径长度:从根节点到该节点之间的路径长度与该节点的权的乘积。
路径长度(深度):当前节点到根节点所经历的层数。
叶子节点:没有子树的节点。
根节点:没有父节点的节点。
哈夫曼树属于二叉树的一种,是一种非线性的数据结构,其实现压缩的思想大致如下:
举个例子:英文中各个字母出现的频率是大不相同的,因此,对不同字母的编码长度若相同,就会浪费太多的空间,若给予出现频率较高的字符以较短的编码,而出现频率较少的字符以较长的编码。那么,总体的编码长度便会大大缩短,把该二进制编码存进文件中可实现压缩。术语志之曰:“最优编码方法”。哈夫曼树是一种最优二叉树,其自下向上的建树方法使得权值越大的节点越靠近根节点。
实现过程:
1.统计字符频率
建一个大小为256的byte数组,使用位映射,每读入一个字节,便在数组中该字节对应的ASCII码对应的位置加一,这样一来,文件读完的时候,字符频率也就统计完了。如:读入字符a,便使byte数组的下标为97的元素加一。
//统计字符频率 private byte[] bytecount = new byte[256]; public void countWeight() throws IOException { java.io.InputStream fins = new java.io.FileInputStream( "D:/JAVA/TestForIO(java)/testforIO.txt"); while (fins.available() > 0) { int i = fins.read();// 读入字节 bytecount[i]++;// 统计每个字节出现的次数(位图映射) } fins.close(); }
2.建树
i.使用队列,把字符及其频率存到一个队列中。
ii.对队列按频率大小进行排序,取频率最小的两个节点,生成一个父节点,权值为两个节点的频率之和,然后把这两个元素从队列中删掉,把父节点存到队列中。然后又排序,生成······如此往复,直到队列中只剩下一个节点,该节点就是根节点。
/* * 使用队列构建哈夫曼树 */ private static HuffNode root;// 声明根节点 public void creatHuffTree() { ArrayList<HuffNode> quene = new ArrayList<HuffNode>();// 创建队列,使用指定排序规则 // 把所有节点加入队列中 for (int i = 0; i < bytecount.length; i++) { if (bytecount[i] != 0) { // System.out.println(((char) i) + " " + bytecount[i]); HuffNode node = new HuffNode((char) i, bytecount[i]); quene.add(node);// 加入节点 } } // 构建哈夫曼树 while (quene.size() != 1) { sort(quene); HuffNode min1 = quene.get(0);// 获取队列头两个 quene.remove(0); HuffNode min2 = quene.get(0); quene.remove(0); HuffNode result = new HuffNode('-', min1.times + min2.times); result.leftchild = min1; result.rightchild = min2; quene.add(result); } // 得到根节点 root = quene.get(0); System.out.println("root=" + root.data + " " + root.times); }
3.编码
哈夫曼树建成后,对其进行编码,左边子树编码为0,右边为1。
// (前序遍历) private Code[] saveCode = new Code[256];// 创建一个code数组,储存每个字符对应的编码和编码长度 public void getMB(HuffNode root, String s) { if (root.leftchild == null && root.rightchild == null) { Code huffcode = new Code(); huffcode.length = s.length();// 把编码串的长度存到huffcode的length属性中 huffcode.code = s;// 把编码串存到huffcode的code属性中 saveCode[root.data] = huffcode;// 把huffcode对象存进saveCode对象数组中 System.out.println("节点" + root.data + "编码" + huffcode.code); System.out.println("节点" + root.data + "次数" + huffcode.length); } // 左0右1 if (root.leftchild != null) { getMB(root.leftchild, s + "0"); } if (root.rightchild != null) { getMB(root.rightchild, s + "1"); } }
为便于理解,建树及编码过程如图所示(图片来自维基百科):
各字符频率如下:
建树过程:
4.把编码转成二进制串,存入文件中,即可实现压缩。
相关推荐
该文件是关于用C语言构建哈夫曼树的代码,其中包括对字符的统计、对文档读取然后包括建树的过程,和对哈夫曼树解码的过程。
这是一个关于哈夫曼的建树,编码及解码的C#程序,使本人的原创作品,花费了本人的很多心血!
利用哈夫曼树的特性将一个文件压缩成自定义压缩包
1.掌握哈夫曼树的建树原理 2. 掌握哈夫曼树与哈夫曼码逻辑结构和存储结构。 3.掌握哈夫曼树与哈夫曼码的基本操作。 二、设计内容和要求 1.输入一个文本,统计各字符出现的频度,输出结果 2.使用二叉链表或三叉链表...
1.掌握哈夫曼树的建树原理 2. 掌握哈夫曼树与哈夫曼码逻辑结构和存储结构。 3.掌握哈夫曼树与哈夫曼码的基本操作。 二、设计内容和要求 1.输入一个文本,统计各字符出现的频度,输出结果 2.使用二叉链表或三叉链表...
这是一个用MFC写的哈夫曼树代码。可以实现建树、编码输出到文件夹和从文件读入编码并显示在界面上。还可以在界面上输出哈夫曼树的树形图。供借鉴...
在VC++6.0上完全能运行,构造简单 无误,1111111111111111111111111111111111111111
哈弗曼建树 编码 译码 绝对的好东西 ,才两个分 不拿可是会后悔的啊!! 总共有4个哈夫曼代码 总共打包给你才两分啊!!!
1) 对指定的文本文件进行各字符出现频度分析,并建立哈夫曼树与哈夫曼编码,将该文本文件编码成目标文件 也可另输入字符和对应频度建树 2) 对已编码的文件进行解码,还原成原来的文件
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)//W存放N个字符的权值,构造哈夫曼树HT,并求出N个字符的哈夫曼编码HC { int m,i,s1,s2,start; int c,f; HuffmanTree p; char *cd; if(n) ...
/****************初始化(建立哈夫曼树)函数********************/ void Initialization() //初始化 { int WeightNum; int i,j,pos1,pos2,max1,max2; // int choice; cout; cout***************** 建树方案...
本程序是用QT写的一个哈夫曼编码解码器,实现了中英文的编码解码问题。其中时间复杂度为O(N^2),使用...本程序界面简约,可以自己选择文件进行建树操作,并将树存为文件形式,以供下次编码解码。并且对输入进行了控制。
3、从终端读入字符集大小为n(即字符的个数),逐一输入n个字符和相应的n个权值(即字符出现的频度),建立哈夫曼树,进行编码并且输出。 注:可用C或C++编写。 4、用邻接矩阵或邻接图实现一个有向图的...