Java学习第30天:Huffman 编码 (编码与解码)

本文主要是介绍Java学习第30天:Huffman 编码 (编码与解码)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

主要任务：今天主要是根据前两天构建的Huffman树来获得Huffman编码。

继续在昨天代码继续添加以下代码：

	/**
	 *********************
	 * 前序遍历.
	 *********************
	 */
	public void preOrderVisit(HuffmanNode paraNode) {
		System.out.print("(" + paraNode.character + ", " + paraNode.weight + ") ");

		if (paraNode.leftChild != null) {
			preOrderVisit(paraNode.leftChild);
		} // Of if

		if (paraNode.rightChild != null) {
			preOrderVisit(paraNode.rightChild);
		} // Of if
	}// Of preOrderVisit

	/**
	 *********************
	 * 为每一个字符创建编码.
	 *********************
	 */
	public void generateCodes() {
		huffmanCodes = new String[alphabetLength];
		HuffmanNode tempNode;
		for (int i = 0; i < alphabetLength; i++) {
			tempNode = nodes[i];
			// Use tempCharCode instead of tempCode such that it is unlike
			// tempNode.
			// This is an advantage of long names.
			String tempCharCode = "";
			while (tempNode.parent != null) {
				if (tempNode == tempNode.parent.leftChild) {
					tempCharCode = "0" + tempCharCode;
				} else {
					tempCharCode = "1" + tempCharCode;
				} // Of if

				tempNode = tempNode.parent;
			} // Of while

			huffmanCodes[i] = tempCharCode;
			System.out.println("The code of " + alphabet[i] + " is " + tempCharCode);
		} // Of for i
	}// Of generateCodes

	/**
	 *********************
	 * 编码.
	 * 
	 * @param paraString
	 *            The String.
	 *********************
	 */
	public String coding(String paraString) {
		String resultCodeString = "";

		int tempIndex;
		for (int i = 0; i < paraString.length(); i++) {
			// From the original char to the location in the alphabet.
			tempIndex = charMapping[(int) paraString.charAt(i)];

			// From the location in the alphabet to the code.
			resultCodeString += huffmanCodes[tempIndex];
		} // Of for i
		return resultCodeString;
	}// Of coding

	/**
	 *********************
	 * 解码.
	 * 
	 * @param paraString
	 *            The given string.
	 *********************
	 */
	public String decoding(String paraString) {
		String resultCodeString = "";

		HuffmanNode tempNode = getRoot();

		for (int i = 0; i < paraString.length(); i++) {
			if (paraString.charAt(i) == '0') {
				tempNode = tempNode.leftChild;
				System.out.println(tempNode);
			} else {
				tempNode = tempNode.rightChild;
				System.out.println(tempNode);
			} // Of if

			if (tempNode.leftChild == null) {
				System.out.println("Decode one:" + tempNode);
				// Decode one char.
				resultCodeString += tempNode.character;

				// Return to the root.
				tempNode = getRoot();
			} // Of if
		} // Of for i

		return resultCodeString;
	}// Of decoding

	/**
	 *********************
	 * 主程序.
	 * 
	 * @param args
	 *            Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		Huffman tempHuffman = new Huffman("D:\\Java-eclipse\\eclipse/lalala.txt");
		tempHuffman.constructAlphabet();

		tempHuffman.constructTree();

		HuffmanNode tempRoot = tempHuffman.getRoot();
		System.out.println("The root is: " + tempRoot);
		System.out.println("Preorder visit:");
		tempHuffman.preOrderVisit(tempHuffman.getRoot());

		tempHuffman.generateCodes();

		String tempCoded = tempHuffman.coding("abcdb");
		System.out.println("Coded: " + tempCoded);
		String tempDecoded = tempHuffman.decoding(tempCoded);
		System.out.println("Decoded: " + tempDecoded);
	}// Of main

}// Of class Huffman

运行结果： 

The text is:
abcdefg
97 98 99 100 101 102 103 The alphabet is: [a, b, c, d, e, f, g]
Their counts are: [1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
The char mappings are: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 4, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
Selecting 0 and 1
The children of 7 are 0 and 1
Selecting 2 and 3
The children of 8 are 2 and 3
Selecting 4 and 5
The children of 9 are 4 and 5
Selecting 6 and 7
The children of 10 are 6 and 7
Selecting 8 and 9
The children of 11 are 8 and 9
Selecting 10 and 11
The children of 12 are 10 and 11
The root is: (*, 7)
Preorder visit:
(*, 7) (*, 3) (g, 1) (*, 2) (a, 1) (b, 1) (*, 4) (*, 2) (c, 1) (d, 1) (*, 2) (e, 1) (f, 1) The code of a is 010
The code of b is 011
The code of c is 100
The code of d is 101
The code of e is 110
The code of f is 111
The code of g is 00
Coded: 010011100101011
(*, 3)
(*, 2)
(a, 1)
Decode one:(a, 1)
(*, 3)
(*, 2)
(b, 1)
Decode one:(b, 1)
(*, 4)
(*, 2)
(c, 1)
Decode one:(c, 1)
(*, 4)
(*, 2)
(d, 1)
Decode one:(d, 1)
(*, 3)
(*, 2)
(b, 1)
Decode one:(b, 1)
Decoded: abcdb

注：从根节点到目标叶节点的路径，路径中沿左孩子为0，沿右孩子为1，即到达叶节点这个过程所产生的一串编码即为Huffman编码。同理解码就根据Huffman编码从根节点依次往下遍历到叶节点便会自动停止，然后又从根节点开始往下遍历，直到遍历完所有编码，最终即可得到解码。

这篇关于Java学习第30天:Huffman 编码 (编码与解码)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！