java 哈夫曼编码反编码的实现

1//哈弗曼编码的实现类
2public class HffmanCoding {
3	private int charsAndWeight[][];// [][0]是 字符，[][1]存放的是字符的权值（次数）
4	private int hfmcoding[][];// 存放哈弗曼树
5	private int i = 0;// 循环变量
6	private String hcs[];
7
8	public HffmanCoding(int[][] chars) {
9		// TODO 构造方法
10		charsAndWeight = new int[chars.length][2];
11		charsAndWeight = chars;
12		hfmcoding = new int[2 * chars.length - 1][4];// 为哈弗曼树分配空间
13	}
14
15	// 哈弗曼树的实现
16	public void coding() {
17		int n = charsAndWeight.length;
18		if (n == 0)
19			return;
20		int m = 2 * n - 1;
21		// 初始化哈弗曼树
22		for (i = 0; i < n; i++) {
23			hfmcoding[i][0] = charsAndWeight[i][1];// 初始化哈弗曼树的权值
24			hfmcoding[i][1] = 0;// 初始化哈弗曼树的根节点
25			hfmcoding[i][2] = 0;// 初始化哈弗曼树的左孩子
26			hfmcoding[i][3] = 0;// 初始化哈弗曼树的右孩子
27		}
28		for (i = n; i < m; i++) {
29			hfmcoding[i][0] = 0;// 初始化哈弗曼树的权值
30			hfmcoding[i][1] = 0;// 初始化哈弗曼树的根节点
31			hfmcoding[i][2] = 0;// 初始化哈弗曼树的左孩子
32			hfmcoding[i][3] = 0;// 初始化哈弗曼树的右孩子
33		}
34
35		// 构建哈弗曼树
36		for (i = n; i < m; i++) {
37			int s1[] = select(i);// 在哈弗曼树中查找双亲为零的 weight最小的节点
38			hfmcoding[s1[0]][1] = i;// 为哈弗曼树最小值付双亲
39			hfmcoding[s1[1]][1] = i;
40			hfmcoding[i][2] = s1[0];// 新节点的左孩子
41			hfmcoding[i][3] = s1[1];// 新节点的右孩子
42			hfmcoding[i][0] = hfmcoding[s1[0]][0] + hfmcoding[s1[1]][0];// 新节点的权值是左右孩子的权值之和
43		}
44
45	}
46
47	// 查找双亲为零的 weight最小的节点
48	private int[] select(int w) {
49		// TODO Auto-generated method stub
50		int s[] = { -1, -1 }, j = 0;// s1 最小权值且双亲为零的节点的序号 ， i 是循环变量
51		int min1 = 32767, min2 = 32767;
52		for (j = 0; j < w; j++) {
53			if (hfmcoding[j][1] == 0) {// 只在尚未构造二叉树的结点中查找（双亲为零的节点）
54				if (hfmcoding[j][0] < min1) {
55					min2 = min1;
56					s[1] = s[0];
57					min1 = hfmcoding[j][0];
58					s[0] = j;
59
60				} else if (hfmcoding[j][0] < min2) {
61					min2 = hfmcoding[j][0];
62					s[1] = j;
63				}
64			}
65		}
66
67		return s;
68	}
69
70	public String[] CreateHCode() {// 根据哈夫曼树求哈夫曼编码
71		int n = charsAndWeight.length;
72		int i, f, c;
73		String hcodeString = "";
74		hcs = new String[n];
75		for (i = 0; i < n; i++) {// 根据哈夫曼树求哈夫曼编码
76			c = i;
77			hcodeString = "";
78			f = hfmcoding[i][1]; // f 哈弗曼树的根节点
79			while (f != 0) {// 循序直到树根结点
80				if (hfmcoding[f][2] == c) {// 处理左孩子结点
81					hcodeString += "0";
82				} else {
83					hcodeString += "1";
84				}
85				c = f;
86				f = hfmcoding[f][1];
87			}
88			hcs[i] = new String(new StringBuffer(hcodeString).reverse());
89		}
90		return hcs;
91	}
92
93	public String show(String s) {// 对字符串显示编码
94		String textString = "";
95		char c[];
96		int k = -1;
97		c = new char[s.length()];
98		c = s.toCharArray();// 将字符串转化为字符数组
99		for (int i = 0; i < c.length; i++) {
100			k = c[i];
101			for (int j = 0; j < charsAndWeight.length; j++)
102				if (k == charsAndWeight[j][0])
103					textString += hcs[j];
104		}
105		return textString;
106
107	}
108
109	// 哈弗曼编码反编译
110	public String reCoding(String s) {
111
112		String text = "";// 存放反编译后的字符
113		int k = 0, m = hfmcoding.length - 1;// 从根节点开始查询
114		char c[];
115		c = new char[s.length()];
116		c = s.toCharArray();
117		k = m;
118		for (int i = 0; i < c.length; i++) {
119			if (c[i] == '0') {
120				k = hfmcoding[k][2];// k的值为根节点左孩子的序号
121				if (hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0)// 判断是不是叶子节点，条件（左右孩子都为零）
122				{
123					text += (char) charsAndWeight[k][0];
124					k = m;
125				}
126			}
127			if (c[i] == '1') {
128				k = hfmcoding[k][3];// k的值为根节点右孩子的序号
129				if (hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0)// 判断是不是叶子节点，条件（左右孩子都为零）
130				{
131					text += (char) charsAndWeight[k][0];
132					k = m;
133				}
134
135			}
136		}
137		return text;
138	}
139}
140
141调用的时候直接调用该类就行了
142
143eg ：
144
145int chars[][] ；
146
147String s =“101010110”；
148
149HffmanCoding hfc = new HffmanCoding(chars);
150
151hfc.coding();//哈弗曼树
152String s[] = hfc.CreateHCode();//哈弗曼编码
153
154s=hfc.show(s)；