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

(0)

相关推荐

  • 基于Java实现的图的广度优先遍历算法

    本文以实例形式讲述了基于Java的图的广度优先遍历算法实现方法,具体方法如下: 用邻接矩阵存储图方法: 1.确定图的顶点个数和边的个数 2.输入顶点信息存储在一维数组vertex中 3.初始化邻接矩阵: 4.依次输入每条边存储在邻接矩阵arc中 输入边依附的两个顶点的序号i,j: 将邻接矩阵的第i行第j列的元素值置为1: 将邻接矩阵的第j行第i列的元素值置为1: 广度优先遍历实现: 1.初始化队列Q 2.访问顶点v:visited[v]=1;顶点v入队Q; 3.while(队列Q非空) v=队列

  • java实现MD5加密算法的实例代码

    复制代码 代码如下: package other; import java.security.MessageDigest;import java.security.NoSuchAlgorithmException;/* * MD5 算法*/public class MD5 { // 全局数组    private final static String[] strDigits = { "0", "1", "2", "3", &

  • 图解程序员必须掌握的Java常用8大排序算法

    这篇文章主要介绍了Java如何实现八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序,分享给大家一起学习. 分类 1)插入排序(直接插入排序.希尔排序) 2)交换排序(冒泡排序.快速排序) 3)选择排序(直接选择排序.堆排序) 4)归并排序 5)分配排序(基数排序) 所需辅助空间最多:归并排序 所需辅助空间最少:堆排序 平均速度最快:快速排序 不稳定:快速排序,希尔排序,堆排序. 先来看看8种排序之间的关系: 1.直接插入排序 (1)基本思想

  • java实现的海盗算法优化版

    本文实例讲述了java实现的海盗算法.分享给大家供大家参考,具体如下: 前面介绍了<C#实现的海盗分金算法>,这里再给出一个Java优化版的算法: package unit4; public class Pirate{ private String name; private int[] schemes; private int index; public Pirate(int t,int i) { name="unknow"; index=i; schemes=makeS

  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

    算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:

  • java字符串相似度算法

    本文实例讲述了java字符串相似度算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: public class Levenshtein {     private int compare(String str, String target) {         int d[][]; // 矩阵         int n = str.length();         int m = target.length();         int i; // 遍历str的      

  • JAVA简单分组的算法实现

    复制代码 代码如下: import java.util.ArrayList; import java.util.Collections; import java.util.List; /**  * Created with IntelliJ IDEA.  * User: dell  * Date: 13-3-5  * Time: 下午8:38  * To change this template use File | Settings | File Templates.  */ public c

  • JAVA实现简单抢红包算法(模拟真实抢红包)

    闲来无事,最近项目需求要写出用户登录首页来发现金红包,没有限额.我就自己稍微计算了一下如果有限额该怎么写.觉得这样与微信红包差不多.等项目需求完成以后.正好来博客贴一下我自己写的拆红包算法.个人觉得这个算法比较模拟现实抢红包规则.废话少说.先贴代码; import java.math.BigDecimal; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.ut

  • 史上最全的java随机数生成算法分享

    复制代码 代码如下: String password = RandomUtil.generateString(10); 源码如下: 复制代码 代码如下: package com.javaniu.core.util;import java.util.Random;public class RandomUtil { public static final String ALLCHAR = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRS

  • 使用java自带des加密算法实现文件加密和字符串加密

    复制代码 代码如下: import java.io.ByteArrayInputStream;import java.io.ByteArrayOutputStream;import java.io.File;import java.io.FileInputStream;import java.io.FileOutputStream;import java.io.InputStream;import java.io.OutputStream;import java.security.SecureR

随机推荐