//Implementation class for haverman coding
public class HffmanCoding {
private int charsAndWeight[][];//[][0] is the character, [][1] is the weight of the character.
private int hfmcoding[][];//Store haverman trees
private int i = 0;//Loop variables
private String hcs[];
public HffmanCoding(int[][] chars) {
//The TODO constructor
charsAndWeight = new int[chars.length][2];
charsAndWeight = chars;
hfmcoding = new int[2 * chars.length - 1][4];//Allocate space for the haverman tree
}
//Implementation of the haverman tree
public void coding() {
int n = charsAndWeight.length;
if (n == 0)
return;
int m = 2 * n - 1;
//Initialize the haverman tree
for (i = 0; i < n; i++) {
hfmcoding[i][0] = charsAndWeight[i][1];//Initialize the haverman tree A weight
hfmcoding[i][1] = 0;//Initialize the haverman tree The root node
hfmcoding[i][2] = 0;//Initialize the haverman tree The left child
hfmcoding[i][3] = 0;//Initialize the haverman tree The right child
}
for (i = n; i < m; i++) {
hfmcoding[i][0] = 0;//Initialize the haverman tree A weight
hfmcoding[i][1] = 0;//Initialize the haverman tree The root node
hfmcoding[i][2] = 0;//Initialize the haverman tree The left child
hfmcoding[i][3] = 0;//Initialize the haverman tree The right child
}
//Construct a haverman tree
for (i = n; i < m; i++) {
int s1[] = select(i);//Find the smallest weight node with zero parents in the haverman tree
hfmcoding[s1[0]][1] = i;//Pay both parents for the haverman minimum
hfmcoding[s1[1]][1] = i;
hfmcoding[i][2] = s1[0];//Left child of the new node
hfmcoding[i][3] = s1[1];//The right child of the new node
hfmcoding[i][0] = hfmcoding[s1[0]][0] + hfmcoding[s1[1]][0];//The weight of the new node is the sum of the weights of the left and right children
}
}
//Find the node with the smallest weight with zero parents
private int[] select(int w) {
// TODO Auto-generated method stub
int s[] = { -1, -1 }, j = 0;//Sequence number of node with minimum weight s1 and zero parents, I is the loop variable
int min1 = 32767, min2 = 32767;
for (j = 0; j < w; j++) {
if (hfmcoding[j][1] == 0) {//Only look for nodes where a binary tree has not yet been constructed (nodes with zero parents)
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() {//Find the Huffman code according to the Huffman tree
int n = charsAndWeight.length;
int i, f, c;
String hcodeString = "";
hcs = new String[n];
for (i = 0; i < n; i++) {//Find the Huffman code according to the Huffman tree
c = i;
hcodeString = "";
f = hfmcoding[i][1]; //F the root node of the haverman tree
while (f != 0) {//Go down to the root
if (hfmcoding[f][2] == c) {//Handle the left child node
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) {//Encodes the string display
String textString = "";
char c[];
int k = -1;
c = new char[s.length()];
c = s.toCharArray();//Converts a string to an array of characters
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;
}
//Haverman code decompilation
public String reCoding(String s) {
String text = "";//Stores decompiled characters
int k = 0, m = hfmcoding.length - 1;//Start the query at the root node
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];//The value of k is the ordinal number of the left child of the root node
if (hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0)//Determine whether the leaf node, condition (left and right children are zero)
{
text += (char) charsAndWeight[k][0];
k = m;
}
}
if (c[i] == '1') {
k = hfmcoding[k][3];//The value of k is the ordinal number of the right child of the root node
if (hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0)//Determine whether the leaf node, condition (left and right children are zero)
{
text += (char) charsAndWeight[k][0];
k = m;
}
}
}
return text;
}
}