手引きハフマン符号化と復号化--純javaコード実装

文書ディレクトリ

概要

実戦

シーン解析

概要
javaを始めたばかりの頃は についてよく知らなかったので、「xxxをマスターするにはこの一歩で手が引き裂かれる...」というブログを見ていたので、すごいと思いました
今私も手を引き裂いた道を歩いています. は実はトラだと気づきました.
実戦
具体的な流れは直接コードを见てください.疑问のあるところは私はすべて详しい注釈注を明记しました.もし疑问があれば、下のコメントを见てください.すぐに返事します.また、コードの直接コピーは使用できます.

ハフマン符号化

/**
	 *      
	 * 1.                   
	 * 2.      
	 * 3.        
	 * 4.           
	 * @param srcBytes
	 * @return
	 */
	public static byte[] haFuManEncode(byte[] srcBytes) {
		List<TreeNode> treeNodes = countBytes(srcBytes);
		TreeNode tree = createHaFuManTree(treeNodes);
		Map<Byte, String> encodeMap = createEncodeMap(tree);
		byte[] zipBytes = zip(srcBytes, encodeMap);
		return zipBytes;
	}
	
	
	
	private static byte[] zip(byte[] srcBytes, Map<Byte, String> encodeMap2) {
		StringBuilder sb = new StringBuilder();
		for (byte b : srcBytes) {
			sb.append(encodeMap2.get(b));
		}
		//System.out.println(sb.toString());
		//              
		int len = sb.length() / 8 == 0 ? sb.length()  / 8: sb.length() / 8 + 1;
		byte[] zipBytes = new byte[len];
		int t = 0;
		for (int i = 0; i < sb.length(); i += 8) {
			String binaryString;
			if (i + 8 > sb.length()) {
				binaryString = sb.substring(i);
			} else {
				binaryString = sb.substring(i, i+8);
			}
			int b = Integer.valueOf(binaryString, 2);
			zipBytes[t++] = (byte) b;
		}
 		return zipBytes;
	}

	//     
	static Map<Byte, String> encodeMap = new HashMap<Byte, String>();
	static StringBuilder lastBuilder = new StringBuilder();
	
	private static Map<Byte, String> createEncodeMap(TreeNode tree) {
		if (tree == null) return null;
		//     
		getRoute(tree.leftNode, "0", lastBuilder);
		//     
		getRoute(tree.rigNode, "1", lastBuilder);
		return encodeMap;
	}

	private static void getRoute(TreeNode node, String code, StringBuilder last) {
		//       
		StringBuilder sb = new StringBuilder(last);
		sb.append(code);
		
		if(node.data == null) {
			getRoute(node.leftNode, "0", sb);
			getRoute(node.rigNode, "1", sb);
		} else {
			encodeMap.put(node.data, sb.toString());
		}
		
	}

	private static TreeNode createHaFuManTree(List<TreeNode> treeNodes) {
		if(treeNodes == null) return null;
//		treeNodes.forEach(System.out::println);
		while(treeNodes.size() > 1) {
			Collections.sort(treeNodes);
			TreeNode left = treeNodes.get(0);
			TreeNode right = treeNodes.get(1);
			TreeNode newNode = new TreeNode(null, left.value + right.value);
			newNode.leftNode = left;
			newNode.rigNode = right;
			treeNodes.remove(left);
			treeNodes.remove(right);
			treeNodes.add(newNode);
		}
		return treeNodes.get(0);
	}

	private static List<TreeNode> countBytes(byte[] srcBytes) {
		Map<Byte, Integer> countMap = new HashMap<Byte, Integer>();
		for (byte b : srcBytes) {
			Integer value = countMap.get(b);
			countMap.put(b, value == null ? 1 : value + 1);
		}
		List<TreeNode> list = new ArrayList<TreeNode>();
		for (Map.Entry<Byte, Integer> entry : countMap.entrySet()) {
			list.add(new TreeNode(entry.getKey(), entry.getValue()));
		}
		return list;
	}

ハフマン復号

	/**
	 *      
	 * 1.      key-value       
	 * 2.                             
	 * 3.                    （         ）
	 * 4.                   （    ）
	 * @param zipBytes
	 * @param encodeMap
	 * @return
	 */
	public static byte[] haFuManDeCode(byte[] zipBytes, Map<Byte, String> encodeMap) {
		Map<String, Byte> decodeMap = new HashMap<String, Byte>();
		for (Map.Entry<Byte, String> entry : encodeMap.entrySet()) {
			decodeMap.put(entry.getValue(), entry.getKey());
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < zipBytes.length; i++) {
			byte b = zipBytes[i];
			boolean flag = (i == zipBytes.length -1);
			sb.append(convertToBianryBit(!flag, b));
		}
		//System.out.println(sb.toString());
		//              list
		List<Byte> list = new ArrayList<Byte>();
		for (int i = 0; i < sb.length();) {
			//    
			int step = 1;
			Byte value = null;
			while(true) {
				String binaryString;
				if (step + i > sb.length())
					binaryString = sb.substring(i);
				else
					binaryString = sb.substring(i, i + step);
				//        
				value = decodeMap.get(binaryString);
				if (step + i < sb.length() && value == null)
					step ++;
				else
					break;
			}
			if (i + step < sb.length()) {
				list.add(value);
			}
			//i     
			i += step;
		}
		
		byte[] unzipBytes= new byte[list.size()];
		for (int i = 0; i < list.size(); i++) {
			unzipBytes[i] = list.get(i);
		}
		
		return unzipBytes;
	}
	
	/**
	 *             
	 * @param b
	 * @param b2
	 */
	private static String convertToBianryBit(boolean flag, byte b2) {
		int temp = b2;
		if(flag)
			temp |= 256;
		String binaryString = Integer.toBinaryString(temp);
		if(flag)
			return binaryString.substring(binaryString.length() - 8);
		return binaryString;
	}

ハフマンツリーノード

package org.demo;

public class TreeNode implements Comparable<TreeNode>{
	Byte data;	//  
	int value;	//  
	TreeNode leftNode;
	TreeNode rigNode;
	
	public TreeNode(Byte data, int value) {
		this.data = data;
		this.value = value;
	}

	@Override
	public int compareTo(TreeNode o) {
		return this.value - o.value;
	}

	@Override
	public String toString() {
		return data + "-" + value;
	}
	
}

テスト

public static void main(String[] args) {
		String msg = "hello, hi hello";
		byte[] bytes = msg.getBytes();
		byte[] zip = haFuManEncode(bytes);
		byte[] unzip = haFuManDeCode(zip, encodeMap);
		System.out.println("       :" + bytes.length);
		System.out.println("       :" + zip.length);
		System.out.println("      : " + new String(unzip));
		
	}

テスト結果

       :15
       :6
      : hello, hi hello

シーン解析
ハフマンツリーが何であるかはよく知られていますが、データ圧縮というブロックの使用シーンには限界があり、構造 のときからハフマン符号化圧縮を使用するとデータ重複率が高いのが望ましいという特徴が感じられます.データ重複数が低いか、異なると、効率が低下します