素材网 素材网

java哈弗曼编码的实现

xw素材网
0

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;
	}
}


@ 2013 xwcms.net . All Rights Reserved. xw素材网 | 备案号:晋ICP备13005902号 联系管理员
×

邮箱订阅

什么是邮箱订阅?

邮箱订阅是xw素材网为jquery爱好者与web程序员提供一项以邮箱的方式发送最新jquery资源与素材资源的模式,用户只需在左侧填写正确的邮箱用户名与邮箱地址我们将每天推荐最新优质资源到用户邮箱。当然每份邮箱都会有一个取消订阅按钮,当用户点击取消按钮时我们将会停止对用户发送邮箱资源推送。再次感谢大家对xw素材网的支持与关注。