Java 哈夫曼編碼反編碼的實現

Java 哈夫曼編碼反編碼的實現：

1. //哈弗曼編碼的實現類
2. public class HffmanCoding {
3. private int charsAndWeight[][];// [][0]是 字符，[][1]存放的是字符的權值（次數）
4. private int hfmcoding[][];// 存放哈弗曼樹
5. private int i = 0;// 循環變量
6. private String hcs[];
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. }
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. }
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. }
45. }
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;
60. } else if (hfmcoding[j][0] < min2) {
61. min2 = hfmcoding[j][0];
62. s[1] = j;
63. }
64. }
65. }
67. return s;
68. }
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. }
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;
107. }
109. // 哈弗曼編碼反編譯
110. public String reCoding(String s) {
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. }
135. }
136. }
137. return text;
138. }
139. }
141. 調用的時候直接調用該類就行了
143. eg ：
145. int chars[][] ；
147. String s =“101010110”；
149. HffmanCoding hfc = new HffmanCoding(chars);
151. hfc.coding();//哈弗曼樹
152. String s[] = hfc.CreateHCode();//哈弗曼編碼
154. s=hfc.show(s)；