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[];  
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.   
143. eg ：  
144.   
145. int chars[][] ；  
146.   
147. String s =“101010110”；  
148.   
149. HffmanCoding hfc = new HffmanCoding(chars);  
150.   
151. hfc.coding();//哈弗曼樹   
152. String s[] = hfc.CreateHCode();//哈弗曼編碼   
153.   
154. s=hfc.show(s)；