java完成哈弗曼編碼與反編碼實例分享(哈弗曼算法)。本站提示廣大學習愛好者:(java完成哈弗曼編碼與反編碼實例分享(哈弗曼算法))文章只能為提供參考,不一定能成為您想要的結果。以下是java完成哈弗曼編碼與反編碼實例分享(哈弗曼算法)正文
//哈弗曼編碼的完成類
public class HffmanCoding {
private int charsAndWeight[][];// [][0]是 字符,[][1]寄存的是字符的權值(次數)
private int hfmcoding[][];// 寄存哈弗曼樹
private int i = 0;// 輪回變量
private String hcs[];
public HffmanCoding(int[][] chars) {
// TODO 結構辦法
charsAndWeight = new int[chars.length][2];
charsAndWeight = chars;
hfmcoding = new int[2 * chars.length - 1][4];// 為哈弗曼樹分派空間
}
// 哈弗曼樹的完成
public void coding() {
int n = charsAndWeight.length;
if (n == 0)
return;
int m = 2 * n - 1;
// 初始化哈弗曼樹
for (i = 0; i < n; i++) {
hfmcoding[i][0] = charsAndWeight[i][1];// 初始化哈弗曼樹的權值
hfmcoding[i][1] = 0;// 初始化哈弗曼樹的根節點
hfmcoding[i][2] = 0;// 初始化哈弗曼樹的左孩子
hfmcoding[i][3] = 0;// 初始化哈弗曼樹的右孩子
}
for (i = n; i < m; i++) {
hfmcoding[i][0] = 0;// 初始化哈弗曼樹的權值
hfmcoding[i][1] = 0;// 初始化哈弗曼樹的根節點
hfmcoding[i][2] = 0;// 初始化哈弗曼樹的左孩子
hfmcoding[i][3] = 0;// 初始化哈弗曼樹的右孩子
}
// 構建哈弗曼樹
for (i = n; i < m; i++) {
int s1[] = select(i);// 在哈弗曼樹中查找雙親為零的 weight最小的節點
hfmcoding[s1[0]][1] = i;// 為哈弗曼樹最小值付雙親
hfmcoding[s1[1]][1] = i;
hfmcoding[i][2] = s1[0];// 新節點的左孩子
hfmcoding[i][3] = s1[1];// 新節點的右孩子
hfmcoding[i][0] = hfmcoding[s1[0]][0] + hfmcoding[s1[1]][0];// 新節點的權值是閣下孩子的權值之和
}
}
// 查找雙親為零的 weight最小的節點
private int[] select(int w) {
// TODO Auto-generated method stub
int s[] = { -1, -1 }, j = 0;// s1 最小權值且雙親為零的節點的序號 , i 是輪回變量
int min1 = 32767, min2 = 32767;
for (j = 0; j < w; j++) {
if (hfmcoding[j][1] == 0) {// 只在還沒有結構二叉樹的結點中查找(雙親為零的節點)
if (hfmcoding[j][0] < min1) {
min2 = min1;
s[1] = s[0];
min1 = hfmcoding[j][0];
s[0] = j;
} else if (hfmcoding[j][0] < min2) {
min2 = hfmcoding[j][0];
s[1] = j;
}
}
}
return s;
}
public String[] CreateHCode() {// 依據哈夫曼樹求哈夫曼編碼
int n = charsAndWeight.length;
int i, f, c;
String hcodeString = "";
hcs = new String[n];
for (i = 0; i < n; i++) {// 依據哈夫曼樹求哈夫曼編碼
c = i;
hcodeString = "";
f = hfmcoding[i][1]; // f 哈弗曼樹的根節點
while (f != 0) {// 循序直到樹根結點
if (hfmcoding[f][2] == c) {// 處置左孩子結點
hcodeString += "0";
} else {
hcodeString += "1";
}
c = f;
f = hfmcoding[f][1];
}
hcs[i] = new String(new StringBuffer(hcodeString).reverse());
}
return hcs;
}
public String show(String s) {// 對字符串顯示編碼
String textString = "";
char c[];
int k = -1;
c = new char[s.length()];
c = s.toCharArray();// 將字符串轉化為字符數組
for (int i = 0; i < c.length; i++) {
k = c[i];
for (int j = 0; j < charsAndWeight.length; j++)
if (k == charsAndWeight[j][0])
textString += hcs[j];
}
return textString;
}
// 哈弗曼編碼反編譯
public String reCoding(String s) {
String text = "";// 寄存反編譯後的字符
int k = 0, m = hfmcoding.length - 1;// 從根節點開端查詢
char c[];
c = new char[s.length()];
c = s.toCharArray();
k = m;
for (int i = 0; i < c.length; i++) {
if (c[i] == '0') {
k = hfmcoding[k][2];// k的值為根節點左孩子的序號
if (hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0)// 斷定是否是葉子節點,前提(閣下孩子都為零)
{
text += (char) charsAndWeight[k][0];
k = m;
}
}
if (c[i] == '1') {
k = hfmcoding[k][3];// k的值為根節點右孩子的序號
if (hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0)// 斷定是否是葉子節點,前提(閣下孩子都為零)
{
text += (char) charsAndWeight[k][0];
k = m;
}
}
}
return text;
}
}