如何实现SerDes接口？哈夫曼树的序列化与反序列化

Question

编写程序，实现SerDes接口。完成对HuffmanTree类的序列化与反序列化。

import java.io.Serializable;

/**
 * 序列化与反序列化方法接口，包含六个方法：
 * byte[] serBin(T t)    :将对象t序列化为字节数组
 * String serText(T t)    :将对象t序列化为一个字符串（可以先使用serBin序列化为字节数组，再用Base64编码为字符串）
 * T des(byte[] bin)        :将序列化后的字节数组反序列化为一个对象
 * T des(String text)    :将序列化后的字符串反序列化为一个对象
 * serToFile                :将对象序列化并写入磁盘文件
 * desFromFile            :将序列化后的对象从磁盘文件中读出
 * @author chenruoyu
 *
 */
public interface SerDes<T extends Serializable> {
    
    /**
     * 将对象t序列化为字节数组
     * @param t
     * @return 序列化后的字节数组
     */
    public byte[] serBin(T t);
    
    /**
     * 将对象t序列化为一个字符串。
     * 提示：可以先使用serBin方法将对象t序列化为字节数组，
     * 再将字节数组用Base64编码为字符串
     * @param t
     * @return
     */
    public String serTxt(T t);
    
    /**
     * 将序列化后的字节数组反序列化为一个对象
     * @param bin
     * @return
     */
    public T des(byte[] bin);
    
    /**
     * 将序列化后的字符串反序列化为一个对象，
     * 字符串应该是使用serText方法序列化得到的
     * @param text
     * @return
     */
    public T des(String text);
    
    /**
     * 将对象序列化并写入磁盘文件。
     * 提示：可以使用serBin将对象t序列化，
     * 然后将序列化后的字节数组写入文件
     * @param t
     * @param path
     * @param file
     * @return
     */
    public boolean serToFile(T t, String path, String file);

    /**
     * 将序列化后的对象从磁盘文件中读出。
     * 提示：可以首先从磁盘中读出字节数组，
     * 然后使用des方法将对象反序列化
     * @param path
     * @param file
     * @return
     */
    public T desFromFile(String path, String file);
    
}

``````java

public class HTNode implements Comparable<HTNode>{
    public enum Code{
        ZERO('0'), ONE('1');
        private char code;
        private Code(char c){
            this.code = c;
        }
        public char getCode(){
            return code;
        }
    }
    
    /**
     *  哈夫曼树的叶子结点数据
     */
    private char data = 0;
    /**
     * 结点的编码，只有0和1两种可能
     */
    private Code code = null;
    
    public static final char zero = '0';
    
    public static final char one = '1';
    
    private double weight = 0;
    private HTNode lchild = null;
    private HTNode rchild = null;
    private boolean isLeaf = false;
    public int tempDength;
    
    public HTNode() {
        super();
    }

    public HTNode(double weight, HTNode lchild, HTNode rchild,
            boolean isLeaf) {
        super();
        this.weight = weight;
        this.lchild = lchild;
        this.rchild = rchild;
        this.isLeaf = isLeaf;
    }
    
    public char getData() {
        return data;
    }
    public void setData(char data) {
        this.data = data;
    }
    public double getWeight() {
        return weight;
    }
    public void setWeight(double weight) {
        this.weight = weight;
    }
    public HTNode getLchild() {
        return lchild;
    }
    public void setLchild(HTNode lchild) {
        this.lchild = lchild;
    }
    public HTNode getRchild() {
        return rchild;
    }
    public void setRchild(HTNode rchild) {
        this.rchild = rchild;
    }
    public boolean isLeaf() {
        return isLeaf;
    }
    public void setLeaf(boolean isLeaf) {
        this.isLeaf = isLeaf;
    }
    public Code getCode() {
        return code;
    }
    public void setCode(Code code) {
        this.code = code;
    }
    @Override
    public int compareTo(HTNode o) {
        if(this.weight<o.weight){
            return -1;
        }else{
            return 1;
        }
    }
    
    public boolean equals(HTNode node){
        if(this.weight != node.getWeight()){
            return false;
        }
        else{
            if(this.data != 0 && node.getData() != 0){
                if(this.data == node.getData())
                    return true;
                else
                    return false;
            }
            else if((this.data == 0 && node.getData() != 0) || (this.data != 0 && node.getData() == 0))
                return false;
            else{
                if(this.getCode().equals(node.getCode())){
                    if(this.isLeaf == node.isLeaf()){
                        if(this.getLchild() != null && this.getRchild() != null &&node.getLchild() != null &&node.getLchild() != null){
                            if(this.getLchild().equals(node.getLchild()) && this.getRchild().equals(node.getRchild()))
                                return true;
                            else
                                return false;
                        }
                        else if((this.getLchild() == null && this.getRchild() != null) || (this.getLchild() != null && this.getRchild() == null)
                                || (node.getLchild() == null &&node.getLchild() != null) || (node.getLchild() != null &&node.getLchild() == null))
                            return false;
                        else
                            return true;
                    }
                    else
                        return false;
                }
                else
                    return false;
            }
        }
    }
}

``````java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Stack;

import cn.edu.bistu.cs.HTNode.Code;

/**
 * 哈夫曼树实现
 * 
 *
 */
public class HuffmanTree {

    /**
     * 哈夫曼编码
     */
    private Map<Character, String> code = null;
    
    /**
     * 生成的huffman树根结点
     */
    private HTNode tree = null;
        
    /**
     * 根据初始的结点列表，建立哈夫曼树，
     * 并生成哈夫曼编码，保存在当前类的code对象中，
     * 生成的树根结点，被保存在当前类的tree对象中。
     * 可以反复生成哈夫曼树，每次重新构建树，将更新编码
     * @param nodes
     * @return
     */
    public HTNode buildTree(List<HTNode> nodes){
        ArrayList<HTNode> nList = this.sortList(nodes);
        while(nList.size() > 1){
            if(nList.size() != 2){
                HTNode p = nList.remove(0);
                p.setCode(Code.ONE);
                HTNode q = nList.remove(0);
                q.setCode(Code.ZERO);
                HTNode newNode = new HTNode(p.getWeight() + q.getWeight(), p, q, false);
                nList.add(newNode);
                nList = this.sortList(nList);
            }
            else{
                HTNode p = nList.remove(0);
                p.setCode(Code.ONE);
                HTNode q = nList.remove(0);
                q.setCode(Code.ZERO);
                this.tree = new HTNode(p.getWeight() + q.getWeight(), p, q, false);
            }
        }
        this.dength();
        this.getCode();
        return this.tree;
    }
    
    // 对结点列表排序
    public ArrayList<HTNode> sortList(List<HTNode> nodes){
        ArrayList<HTNode> nList = (ArrayList<HTNode>)nodes;
        for(int i = 0; i < nList.size(); i++){
            for(int j = i; j < nList.size(); j++){
                if(nList.get(i).compareTo(nList.get(j)) == 1){
                    HTNode temp = nList.get(i);
                    nList.set(i, nList.get(j));
                    nList.set(j, temp);
                }
            }
        }
        return nList;
    }
    
    // 更新树各结点的深度
    public void dength(){
        Queue<HTNode> que = new LinkedList<HTNode>();
        que.add(this.tree);
        this.tree.tempDength = 1;
        while(que.size() > 0){
            HTNode p = que.poll();
            if(p.getLchild() != null){
                p.getLchild().tempDength = p.tempDength + 1;
                que.add(p.getLchild());
            }
            if(p.getRchild() != null){
                p.getRchild().tempDength = p.tempDength + 1;
                que.add(p.getRchild());
            }
        }
    }
    
    /**
     * 根据已建立的哈夫曼树根结点，生成对应的字符编码，
     * 字符编码应为0，1字符串
     * @param tree
     * @return
     */
    public static Map<Character, String> getCode(HTNode tree){
        //TODO
        Stack<HTNode> sList = new Stack<HTNode>();
        Map<Character, String> codeList = new HashMap<Character, String>();
        int temp = 1;
        String codes = "";
        sList.push(tree);
        while(!sList.isEmpty()){
            HTNode p = sList.pop();
            if(temp > p.tempDength){
                codes = codes.substring(0, codes.length() - (temp - p.tempDength));
            }
            temp = p.tempDength;
            if(p.getRchild() != null)
                sList.push(p.getRchild());
            if(p.getLchild() != null)
                sList.push(p.getLchild());
            if(p.getCode() != null){
                if(p.isLeaf()){
                    codeList.put(p.getData(), codes + p.getCode().getCode());
                }
                else
                    codes += p.getCode().getCode();
            }
        }
        return codeList;
    }
    
    /**
     * 获取已建立的哈夫曼树生成的字符编码，
     * 字符编码应为0，1字符串
     * @return
     */
    public Map<Character, String> getCode(){
        this.code = HuffmanTree.getCode(this.tree);
        return this.code;
    }
    
    
    /**
     * 统计字符串中字符出现的频率
     * @param text
     * @return
     */
    public static Map<Character,Integer> computeCharCount(String text){
        //TODO
        Map<Character, Integer> hMap = new HashMap<Character, Integer>();
        for(int i = 0; i < text.length(); i++){
            char temp = text.charAt(i);
            if(hMap.containsKey(temp)){
                hMap.replace(temp, hMap.get(temp) + 1);
            }
            else{
                hMap.put(temp, 1);
            }
            
        }
        return hMap;
    }
    
    /**
     * 使用当前类训练好的huffman编码来对文本进行编码
     * @return
     */
    public String encode(String text){
        //TODO
        return encode(text, this.code);
    }
    
    /**
     * 使用指定的huffman编码来对文本进行编码
     * @return
     */
    public static String encode(String text, Map<Character, String> code){
        //TODO
        Map<Character, String> hMap = (HashMap<Character, String>)code;
        if(code == null)
            return null;
        String result = "";
        for(int i = 0; i < text.length(); i++){
            char p = text.charAt(i);
            result += hMap.get(p);
        }
        
        return result;
    }

    // 通过编码表得到解码表
    public static Map<String, Character> disencode(Map<Character, String> code){
        Map<String, Character> discode = new HashMap<String, Character>();
        HashMap<Character, String> Hcode = (HashMap<Character, String>) code;
        for(Entry<Character, String> en : Hcode.entrySet()){
            discode.put(en.getValue(), en.getKey());
        }
        return discode;
    }
    
    /**
     * 使用当前类中训练好的huffman编码，
     * 对编码后的文本进行解码
     * @param text
     * @return
     */
    public String decode(String text){
        //TODO
        return decode(text, this.tree);
    }
    
    public HTNode getTree() {
        return tree;
    }

    /**
     * 使用预先建立好的huffman树，
     * 对编码后的文本进行解码
     * @param text
     * @return
     */
    public String decode(String text, HTNode tree){
        //TODO
        if(tree == null || text == null)
            return null;
        HashMap<Character, String> code = (HashMap<Character, String>)getCode(tree);
        HashMap<String, Character> discode = (HashMap<String, Character>)disencode(code);
        String result = "";
        String temp = "";
        for(int i = 0; i < text.length(); i++){
            temp += text.charAt(i);
            if(discode.containsKey(temp)){
                result += discode.get(temp);
                temp = "";
            }
        }
        return result;
    }
    public static void main(String[] args){
        HuffmanTree htree = new HuffmanTree();
        //首先对字符串中的字符出现次数进行统计
        String data = "In computer science and information theory, "
                + "a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. "
                + "The process of finding and/or using such a code proceeds by means of Huffman coding, "
                + "an algorithm developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper "
                + "\"A Method for the Construction of Minimum-Redundancy Codes\".[1] "
                + "The output from Huffman's algorithm can be viewed as a variable-length code table for encoding a source symbol "
                + "(such as a character in a file). The algorithm derives this table from the estimated probability or frequency of occurrence"
                + " (weight) for each possible value of the source symbol. As in other entropy encoding methods, more common symbols are generally "
                + "represented using fewer bits than less common symbols. Huffman's method can be efficiently implemented, "
                + "finding a code in linear time to the number of input weights if these weights are sorted.[2] However, "
                + "although optimal among methods encoding symbols separately, Huffman coding is not always optimal among all compression methods.";
        Map<Character, Integer> chars = HuffmanTree.computeCharCount(data);
        ArrayList<HTNode> nodes = new ArrayList<>();
        for(Character c : chars.keySet()){
            HTNode node = new HTNode();
            node.setData(c);
            node.setWeight(chars.get(c));
            node.setLchild(null);
            node.setRchild(null);
            node.setLeaf(true);
            nodes.add(node);
        }
        ArrayList<HTNode> nodeList = htree.sortList(nodes);
        for(int i = 0; i < nodeList.size(); i++){
            System.out.println(nodeList.get(i).getData()+ "" + nodeList.get(i).getWeight());
        }
        HTNode tree = htree.buildTree(nodes);
        Map<Character, String> code = HuffmanTree.getCode(tree);
        for(Character c : code.keySet()){
            System.out.println("字符'"+c+"'的哈夫曼编码："+code.get(c));
        }
        String text = "In computer science and information theory";
        String coded = htree.encode(text);
        System.out.println("字符串：In computer science and information theory");
        System.out.println("被编码为："+coded);
        String oriText = htree.decode(coded);
        System.out.println("编码："+coded);
        System.out.println("被解码为："+oriText);
        System.out.println(oriText.equals(text));
    }
    
    
    
}

Answer 1

一个 HuffmanNode 类

表示哈夫曼树的节点，包含两个属性：权值和左右子节点。节点类可以实现 Serializable 接口，表示该类可以序列化和反序列化。

import java.io.Serializable;

public class HuffmanNode implements Serializable {
    private int weight;
    private HuffmanNode leftChild;
    private HuffmanNode rightChild;

    public HuffmanNode(int weight) {
        this.weight = weight;
    }

    public void setLeftChild(HuffmanNode leftChild) {
        this.leftChild = leftChild;
    }

    public void setRightChild(HuffmanNode rightChild) {
        this.rightChild = rightChild;
    }

    // getter and setter methods omitted for brevity
}

定义一个 HuffmanTree 类

表示哈夫曼树，包含一个根节点属性。HuffmanTree 类同样可以实现 Serializable 接口。

public class HuffmanTree implements Serializable {
    private HuffmanNode root;

    public void setRoot(HuffmanNode root) {
        this.root = root;
    }

    // getter and setter methods omitted for brevity
}

序列化和反序列化的实现：

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;

public class HuffmanSerDes {
    public static byte[] serialize(HuffmanTree tree) throws IOException {
        ByteArrayOutputStream bos = new ByteArrayOutputStream();
        ObjectOutputStream oos = new ObjectOutputStream(bos);
        oos.writeObject(tree);
        oos.flush();
        byte[] bytes = bos.toByteArray();
        oos.close();
        bos.close();
        return bytes;
    }

    public static HuffmanTree deserialize(byte[] bytes) throws IOException, ClassNotFoundException {
        ByteArrayInputStream bis = new ByteArrayInputStream(bytes);
        ObjectInputStream ois = new ObjectInputStream(bis);
        HuffmanTree tree = (HuffmanTree) ois.readObject();
        ois.close();
        bis.close();
        return tree;
    }
}

调用示例

public class Main {
    public static void main(String[] args) throws IOException, ClassNotFoundException {
        // 构建哈夫曼树
        HuffmanNode node1 = new HuffmanNode(1);
        HuffmanNode node2 = new HuffmanNode(2);
        HuffmanNode node3 = new HuffmanNode(3);
        HuffmanNode node4 = new HuffmanNode(4);
        node1.setLeftChild(node2);
        node1.setRightChild(node3);
        node3.setRightChild(node4);
        HuffmanTree tree = new HuffmanTree();
        tree.setRoot(node1);

        // 序列化
        byte[] bytes = HuffmanSerDes.serialize(tree);

        // 反序列化
        HuffmanTree tree2 = HuffmanSerDes.deserialize(bytes);
        System.out.println(tree2.getRoot().getRightChild().getRightChild().getWeight()); // 输出 4
    }
}