当前位置:首页软件开发Java → 哈夫曼压缩

哈夫曼压缩

时间:2020-12-10 00:36:35来源:互联网我要评论(0)

   此文主要分析的是哈夫曼压缩的重点包括统计字符频率,建哈夫曼树,生成码表。哈夫曼压缩是最常用的一种静态无痕压缩。
   以前也学习过哈夫曼的算法结构,但是没有自己去写代码实现,这次再学习了一遍,更加深刻理解哈夫曼压缩的原理,如何真正实现文件的压缩节省内存资源。下面梳理下我的代码和分析逻辑。
   第一步是打开文件,读取文件流,统计文字频率。
   方法是读取文件内容,根据每个字符有唯一的字节,存储在长度为256的数组中。可将字符和频率绑定为一个节点类Node,所有节点类的对象存储在队列中。

/*
	 * 统计频率
	 */
	private static Mylist<Node> countFre(String path) throws IOException {
		// 创建一个文件输入流对象  
	    java.io.FileInputStream fis = new java.io.FileInputStream(path);  
	    java.io.BufferedInputStream bis = new java.io.BufferedInputStream(fis);  
		int[] byteArray = new int[256];
		 while (bis.available() > 0) {  
		     int i = bis.read();
		     // 统计字符的频率  
	         byteArray[i]++; 
	    }  
		// 关闭文件输入流  
		fis.close();  
		     
		Mylist<Node> l = new Mylist<Node>();
		// 遍历数组,打印并保存
		for (int i = 0; i < byteArray.length; i++) {
			if (byteArray[i] != 0) {
				char c = (char) i;
				int count = byteArray[i];
				// System.out.println("字符:"+c+"   "+"频率:"+count);
				// 添加到队列
				l.add(new Node(c, count));
			}
		}
		return l;
	}


  第二步是排序。
   根据字符所对应的频率由小到大进行排序,可用选择排序算法。

/*
	 * 排序
	 */
	private static void sort(Mylist<Node> list) {
		for (int i = 0; i < list.size() - 1; i++) {
			int min = i;
			for (int j = i + 1; j < list.size(); j++) {
				// 如果j返回的节点中的频率大于i
				if (list.get(j).getFrequency() < list.get(min).getFrequency())
					min = j;
			}
			// 交换
			if (i != min) {
				Node n = list.get(min);
				list.set(list.get(i), min);
				list.set(n, i);
			}
		}

	}


第三步是构建哈夫曼二叉树。
   依次取出排好序的节点,每次取出前两个生成一个父节点,再将父节点添加到队列中,这里我将生成父节点的过程写在另一个函数creatHFM里,方便理解逻辑。

	/*
	 * 构建哈夫曼二叉树
	 */
	private static Node creat(Mylist<Node> list){
		while (list.size() > 1) {
			Node l = list.remove(0);
			Node r = list.remove(0);
			Node n = creatHFM(l, r);
			// 把新的节点添加到队列中
			list.add(n);
			// 排序
			sort(list);
		}
		//根节点
		Node root = list.get(0);
		return root;
	}
	private static Node creatHFM(Node left, Node right) {
		int fc = left.getFrequency() + right.getFrequency();
		Node root = new Node(' ', fc);
		root.setLeft(left);
		root.setRight(right);
		return root;
	}


   第四步是给每个字符编码,生成码表。
  用递归遍历的方法生成每一个字符的编码,左0右1,并绑定字符保存,即新建一个类,依次保存到队列中。

	/*
	 * 计算编码
	 */
	private static void creatCode(Node root, String str) {
		// 若不是叶节点,递归遍历
		if (root.getLeft() != null) {
			creatCode(root.getLeft(), str + "0");
			creatCode(root.getRight(), str + "1");
		} else {// 否则输出,编码,并保存
			count += root.getFrequency() * str.length();
			System.out.println(root.getC() + " = " + str);
			// 保存每一个字符及其编码,存入队列
			Character chact = new Character(root.getC(), str);
			codelist.add(chact);
		}

	}



   在以上代码中所有的方法的参数输入由上一个方法的返回决定,更加方便梳理逻辑,查错。
  
   构造方法及主函数,其中主函数中测试文件中的内容为string

public HFMtree(String path) throws IOException {
		// 统计每个字符的频率
		list = countFre(path);
		
		// 根据每个字符的频率排序
		sort(list);
		// 构建哈夫曼二叉树,返回根节点
		Node root = creat(list);
		// 生成每一个字符的编码及带权路径。并保存编码
		creatCode(root, "");
	}

	/*
	 * 主函数
	 */
	public static void main(String[] args) throws IOException {
//		文件路径
		String str = "F:/text.txt";
//		文件的内容
//		String string = "jfsjflvyavllcyqlcjhqvYV";
		HFMtree hfm=new HFMtree(str);
		System.out.print("带权路径=" + count);

	
	}


测试结果

相关文章

网友评论

热门评论

最新评论

发表评论 查看所有评论()

昵称:
表情: 高兴 可 汗 我不要 害羞 好 下下下 送花 屎 亲亲
字数: 0/500 (您的评论需要经过审核才能显示)

关于万荚 | 联系方式 | 发展历程 | 版权声明 | 帮助(?) | 网站地图 | 友情链接

Copyright 2005-2020 16WJ.COM 〖万荚网〗 版权所有 桂ICP备18000060号 |

声明: 本站所有文章来自互联网 如有异议 请与本站联系