huffman文件压缩

前言

用霍夫曼编码进行文件压缩，就是用更短的01串（bit）表示一个char型变量。很显然在java里面我们无法从最小单位bit入手改变，那么我们可以通过哈希表的映射来改变，只不过我们会出现一个问题，
如这个HashMap<Character,String> 很显然Character型的常量对应的是一个String型的01串，我们无法存储bit的数值类型。

这里我们也能想到的最关键的点是如何将String中的01串每次取8个char并让这8个char最终能代表一个byte。因为1个byte等于8个bit，这样一想我们String中每8个char不就等价于8个bit了吗？这样在某种程度上来说我们的确做到了用更短的bit来表示一个char型变量。

步骤

看到这我们就知道了我们要做些什么了：
第一，将文件读取出来并将其中的所有字母符号空格等用huffman进行编码
第二，将编码后的01串（String型）与char型数据一一对应放入HashMap中。
第三， 读取后的文件中的每一个char型数据运用操作二中得到的HashMap找到对应的01串，并写了一个缓冲字符串（用来将每8个01串转化为一个byte）中。
第四 ， 将缓冲字符串中的每8个01串转化为一个byte后，存入你所想放的文件中。压缩就完成了。

关键点

第一个是huffman编码，这次我改进了以下，比上次写的要看起来舒服写，实用度也高了些。

//将文件中出现的符号以及对应出现的次数储存起来
public static Map<Character,Integer> get(String words){
		char[] word = words.toCharArray();
		Map<Character,Integer> map = new TreeMap<>();
		for(int i = 0;i < word.length; i++) {
			if(!map.containsKey(word[i])) {
				map.put(word[i],1);
			}
			else {
				int count = map.get(word[i]);
				count++;
				map.put(word[i], count);
				}
			}
			
		
		return map;
	}
	//使用优先队列对存入了char型数据的HTreeNode类按照出现的频率进行自然排序（从小到大）
	public static Queue<HTreeNode> transfer(Map<Character, Integer> map) {
		Queue<HTreeNode> treenode = new PriorityQueue<>();
		for(char word : map.keySet()) {
			int count = map.get(word);
			HTreeNode node = new HTreeNode(count,word);
			treenode.add(node);
		}
		return treenode;
}
//排序后的优先队列，从第一个开始取出，每取出两个作为叶子节点，创造它的父节点，并放入该父节点，
//循环直至只剩一个父节点
	public static HTreeNode transferNode(Queue<HTreeNode> queue) {
		while(queue.size() > 1) {
			HTreeNode left = queue.poll();
			HTreeNode right = queue.poll();
			HTreeNode node = new HTreeNode(left.count + right.count);
			node.left = left;
			node.right = right;
			left.parent = node;
			right.parent = node;
			queue.add(node);
		}
		return queue.poll();	
	}
	//对最后剩下的父节点进行递归，赋予每个子节点一个huffman编码，并且用HashMap储存下来
	public static void toString(HTreeNode node,HashMap<Character, String> map) {	
		if(node.left != null) {
			node.left.code = node.code + "0";
			toString(node.left, map);
		}
		if(node.right != null) {
			node.right.code = node.code + "1";
			toString(node.right, map);
		}
		if(node.right == null && node.left == null) {
			System.out.println(node.chars + " = " + node.code);
			map.put(node.chars, node.code);
		}
	}

第二个关键点就是如何将每8个01串转化为一个byte。

public static byte stringToByte(String str) {
		byte b = 0;
		//位运算
		//位移：0000 0001<<1  = 0000 0010
		//位或: 0|0 = 0, 1|1 = 1|0 = 1
		//		0001 0000
		//		0000 0001 = 0001 0001
		//读取字符，位移为对应位的数字，和字节b进行位或运算
		for(int i=0 ;i<str.length(); i++) {
			//获取第i个字符
			char ch = str.charAt(i);
			//通过差值将本来是char型的‘1’转化为了int型的1，char型的‘0’同理
			int number = ch-'0';
			//将number向左移7-i位
			number = number<<7-i;
			//位或
			b = (byte)(b|number);
			/*比如输入的是“11111111”的字符串，
			首先取到的是i=0时候的1，这个时候是char型的‘1’，然后通过‘1’ - ‘0’
			变为int型的1，然后左移7-i即7位
			变为值为128的number（int型为32bit），此时它的**bit最后8位**表示为1000 0000 
			再将后8位的1000 0000 和 此时为 0000 0000 的byte类 b进行位或运算
			得到bit为 1000 0000 的byte数据b，再对该byte型的b进行下一次循环，最后变为1111 1111*/
			//输入11111111出来的是值为-1的byte，byte型是-128~127，采用补码表示法，
			//开头的01表示正负，
			//如果为负数就要将后面的01取反后加1，正数不用（正数的补码就是它本身）
		}
		return b;
	}

在知道这两个关键点后其他的就很简单了

步骤一和步骤二如下

public static void main(String[] args) throws IOException {
		DataInputStream in = new DataInputStream(
		new FileInputStream("C:/Users/lenovo/Desktop/ashdaskldnasd、.txt"));
		byte[] data = new byte[in.available()];
		in.read(data);
		String word_1 = new String(data);
		HashMap<Character, String> map = new HashMap<>();
		toString(transferNode(transfer(get(word_1))),map);

步骤三和步骤四

StringBuilder std = new StringBuilder();
DataOutputStream out = new DataOutputStream(new FileOutputStream("C:/Users/lenovo/Desktop/a.txt"));
		char[] words = word_1.toCharArray();
		for (char a : words) {
			
			String word_2 = map.get(a);
		
			std.append(word_2);	
		}
		int len = std.length()/8;
		
		for(int i = 0; i < len ; i++) {
			String code = std.substring(i, i+8);
			byte word_3 = stringToByte(code);
			out.write(word_3);
		}
		if(std.length() % 8 != 0) {//文件中的01串加起来可能不是8的整数
			String code_1 = std.substring(8*len, std.length());
			byte word_4 = stringToByte(code_1);
			out.write(word_4);
		}
		in.close();
		out.flush();
		out.close();
		
		
		
	}

}

这个String转byte我一开始是真的不知道怎么搞，没有老师告诉我真的根本没法搞出来。
还有如果你要解压的话最好在压缩的时候把HashMap的数据和你补充的0的个数一起放进去，不然没法解压的。我之后再看看怎么解压吧，（脑袋疼）

压缩前

压缩后