哈夫曼编码

哈夫曼编码是基于哈夫曼树实现的。而哈夫曼树又是基于完全二叉树实现的。那么什么是完全二叉树呢？

完全二叉树(Complete Binary Tree)

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。《来自百度百科》

（如果对二叉树不了解的可以去看我博客写的二叉树数据结构）

那么哈夫曼编码到底有什么作用呢？ 在远距离数据通信中，需要将文字转换成二进制的字符串，用0，1码的不同排列来表示字符串。例如需要传送报文“good good study”，用到了8个字符：g：2次；o：4次；d：3次；空格：2次；s，t，u，y各1次，现在要为这些字母设计编码，最简单的二进制编码是等长 编码，由于只用到8个字符，只要用3位二进制编码即可区别，共需要传输（2+4+3+4*1+2）*3=45个二进制位，然而问题是：在实际中，我们往往 更希望报文长度尽可能的短，那么是否有一种编码方式能够实现所得报文长度最短呢？当然有，即：哈夫曼编码。

哈夫曼编码是怎么实现的呢？看下面图，你大概会了解什么叫-----编码唯一、编码最短。

 

 哈夫曼编码的核心思想就是：使用频率高的字符编码最短，使用频率低的字符编码编码最长，这样就可以使得树的带权值路径长度最小，即用最短0、1 序列传输信息。

好了说了这么多，那么我们来分析下怎么去实现这样编码唯一，编码最短的哈夫曼编码呢？

首先我们要给每个字母根据频率建哈夫曼树。所有的节点Node{}里面有数据域权值(频率)（int weight）,左右孩子节点Node lchild,Node rchild,双亲节点Node parent，即用二叉链表的形式构建哈夫曼树，权值小的（使用频率低的）字符要在最长路径，所以我们采用逆向建树的过程。

怎么逆向建树呢？

我们需要辅助数组来帮助我们建树。申请一个长度为2*n-1的Node 型数组来存储所有将要创建的哈夫曼树的所有节点（想想为什么需要2*n-1长度，或者节点总数为什么是2*n-1？）首先把所有已知的叶节点存入数组，然后每次都去选取parent == null的权值最小的节点来创建一个子树，比如说上图中选取权值2、3的节点创建新的节点（5--<2,3>），它的lchild是权值为2的节点，rchild是权值为3的节点，并且将这个节点append到数组后面。（注意：创建新节点的过程要把权值为2和3的Node.parent = new Node(),并且new Node的权值应该为Node(2).weight+Node(3),weight）以此类推，数组最后一个空间！=null为止，即根节点的产生。

建完树之后怎么求编码？

举个例子比如说a这个字符怎么求它的哈夫曼编码呢？我们这里采用逆向寻找根节点,首先申请一个空字符串str,利用辅助数组，去寻找叶节点的root,然后每次寻找节点的parent的时候，判断该节点是该节点parent的lchild还是rchild，如果是lchild,str.append("0"),rchild，str.append("1")寻找到root之后str存储的字符串为a字符哈夫曼编码的逆序，聪明的你一定可以把它变成正序的（当然你可以选择二叉树的遍历，来寻找节点值为a的那个节点，首先定义一个空字符串str,然后每次选择llchild时候str.append("0"),rchild时候str.append("1")，这里str是a字符的哈夫曼编码正序）。

下面我来拓展介绍下哈夫曼编码的编码器和译码器：

编码器：其实在上面求每个字符哈夫曼编码的时候，我们可以把这些编码存到一个数据结构中，然后根据用户输入的字符串挨个解析字符输出每个字符对应的哈夫曼编码，将它们按照顺序输出就可以；

译码器：用户输入的是0、1序列，回顾下我们之前在求字符编码的时候0、1分别代表什么。0是代表lchild，1代表rchild，那么根据用户输入的0、1序列，从root节点，读到0就往左子树找，读到1就往右子树找，一直到node.lchild==null&&node.rchild==null，即叶节点为止，输出对应的字符；然后又从root节点找，直到读完所有0、1序列，那么你就成功译码了！！

 

说了这么多，代码已经迫不及待了！~

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

class HuffNode {
	char ch;
	int weight;
	HuffNode parent;
	HuffNode lchild, rchild;

	public HuffNode() {

	}

	public HuffNode(char ch, int weight, HuffNode parent, HuffNode lchild,
			HuffNode rchild) {
		this.ch = ch;
		this.lchild = lchild;
		this.rchild = rchild;
		this.weight = weight;
		this.parent = parent;
	}

}

public class HuffCode {
	public static void main(String[] args) throws FileNotFoundException {
		char letter = 'a';
		// 为26字母个以及空格符创建Huffman树申请空间 O = 27*2-1
		HuffNode[] hfArr = new HuffNode[53];
		// 第一个为空格字符
		hfArr[0] = new HuffNode(' ', 184, null, null, null);
		// 用文本io方式读取剩下字符和权值
		File wgTable = new File("DataTable\\charTable.txt");
		Scanner read = new Scanner(wgTable);
		for (int i = 1; i <= 26; i++) {
			hfArr[i] = new HuffNode((char) (i + 96), read.nextInt(), null,
					null, null);
		}
		// 初始化剩下的空间
		for (int i = 27; i <= 52; i++) {
			hfArr[i] = new HuffNode();
		}
		// 构建Huffman树
		int size = 26;
		int minWeight;
		int minIndex = -1;
		int sminWeight;
		int sminIndex = -1;
		while (hfArr[52].lchild == null) {
			minWeight = 10000;
			sminWeight = 10000;

			// 寻找没有双亲节点的权值最小的节点
			for (int i = 0; i <= size; i++) {
				if (minWeight > hfArr[i].weight && hfArr[i].parent == null) {
					minWeight = hfArr[i].weight;
					minIndex = i;
				}
			}
			// System.out.println("找到最小值 " + minWeight + "字母为 "
			// + hfArr[minIndex].ch);
			// 寻找没有双亲节点的权值次小的节点
			for (int i = 0; i <= size; i++) {
				if (sminWeight > hfArr[i].weight && hfArr[i].parent == null
						&& i != minIndex) {
					sminWeight = hfArr[i].weight;
					sminIndex = i;
				}
			}
			// System.out.println("找次=最小值 " + sminWeight + "字母为 "
			// + hfArr[sminIndex].ch);
			// 两个权值最小的节点创建新节点
			int weight = hfArr[minIndex].weight + hfArr[sminIndex].weight;
			hfArr[++size] = new HuffNode('\0', weight, null, hfArr[minIndex],
					hfArr[sminIndex]);
			hfArr[minIndex].parent = hfArr[size];
			hfArr[sminIndex].parent = hfArr[size];
		}
		// System.out.println(hfArr[52].parent);
		// 求各个字符Huffman编码
		HuffNode curhfNode;
		String[] hfcode = new String[27]; // 申请27空间存储Huffman逆向编码（！！不是正向编码）
		// 初始化每个字符串编码
		for (int i = 0; i < hfcode.length; i++) {
			hfcode[i] = "";
		}
		// 从子叶到根节点逆向求每个字符编码
		for (int i = 0; i < hfcode.length; i++) {
			// 当前叶节点
			curhfNode = hfArr[i];
			// 一直寻找，直到寻找到根节点
			while (curhfNode.parent != null) {
				// 假如是左孩子，则编码追加字符0，右孩子则追加字符1；
				if (curhfNode.parent.lchild == curhfNode) {
					hfcode[i] += "0";
				} else {
					hfcode[i] += "1";
				}
				curhfNode = curhfNode.parent;
			}

		}
		// System.out.println("a = " + hfcode[1]);
		// 对每个字符的Huffman逆向编码倒转成正向编码
		String tempStr;
		for (int i = 0; i < hfcode.length; i++) {
			tempStr = "";
			for (int j = hfcode[i].length() - 1; j >= 0; j--) {
				tempStr += hfcode[i].charAt(j);
			}
			hfcode[i] = tempStr;
		}
		char op;
		System.out.println("Which do you want to do? Encoding or Decoding? The former choose \"A\" and the latter choose \"B\"");
		Scanner choose = new Scanner(System.in);
		op = choose.next().charAt(0);
		if(op == 'A'){
			encode(hfcode);
		}else{
			decode(hfArr[52]);
		}
		
	}
	/**
	 * 编码器原理：读取每一个字符，通过寻找该字符在Huffman编码表中所对应哈夫曼编码，来依次append编码就可以
	 * @param hfcode
	 */
	public static void encode(String[] hfcode){
		System.out.println("Please enter your Plain Text: ");
		Scanner cin = new Scanner(System.in);
		String code = cin.nextLine();
		String otCode = "";
		for(int i =0;i<code.length();i++){
			if(code.charAt(i)==' '){
				otCode+=hfcode[0];
			}else{
				otCode+=hfcode[code.charAt(i)-96];
			}
		}
		System.out.println("After encoding: "+otCode);
	}
	/**
	 * 译码器原理：主要是通过读取0,1序列（0代表左孩子，1表示右孩子）从根节点开始寻找对应的叶节点，每次寻找到叶节点（即字符）就又从根节点开始寻找
	 * @param rootHf
	 */
	public static void decode(HuffNode rootHf){
		HuffNode tempHuf = rootHf;
		System.out.println("Please enter your Cipher Text: ");
		Scanner cin = new Scanner(System.in);
		String code = cin.nextLine();
		String otText = "";
		for(int i=0;i<code.length();i++){
			//读到1.就寻找右孩子
			if(code.charAt(i)=='1'){
				tempHuf = tempHuf.rchild;
				//寻找到对应的字符就重新从根节点开始
				if(tempHuf.ch>='a'&&tempHuf.ch<='z'||tempHuf.ch==' '){
					otText+=tempHuf.ch;
					tempHuf = rootHf;
				}
				//读到0，寻找左孩子
			}else{
				tempHuf = tempHuf.lchild;
				//寻找到对应的字符就重新从根节点开始
				if(tempHuf.ch>='a'&&tempHuf.ch<='z'||tempHuf.ch==' '){
					otText+=tempHuf.ch;
					tempHuf = rootHf;
				}
			}
		}
		System.out.println("After decoding: "+otText);
	}

}