huffman.java

问题描述] 利用哈夫曼编码进行信息通信可以大大提高信道利用率

package hartech.kids.huffman;

/**
 * <p>Title: 哈夫曼编/译码器</p>
 *
 * <p>Description:
 * 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
 * 但是，这要求在发送端通过一个编码系统对待传数据预先编码，
 * 在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），
 * 每端都需要一个完整的编／译码系统。试为这样的信息收发站写一个哈夫曼码的编／译码系统。
 * </p>
 *
 * <p>Website: www.hartech.cn </p>
 * <p>Page: http://www.hartech.cn/blog/blogview.asp?logID=87 </p>
 * <p>Date: 2006-09-05 </p>
 */
public class Huffman {

  class Elem {
    char chara;
    int weight;
    int parent;
    int lchild;
    int rchild;
    public Elem(char c, int w, int p, int l, int r) {
      chara = c;
      weight = w;
      parent = p;
      lchild = l;
      rchild = r;
    }
  }

  // 哈夫曼树
  private Elem[] huffmanTree;
  // 哈夫曼编码表
  private String[] huffmanCode;
  // 字符个数
  int charNum;

  // 给出 in 构造哈夫曼树 huffmanTree、哈夫曼编码表huffmanCode
  // in 格式为{'字符1',对应权值,'字符2',对应权值,  ...}
  public Huffman(char[] in) {
    if (in == null || in.length == 0 || in.length % 2 != 0) {
      System.err.println("dd");
      return;
    }
    charNum = in.length / 2;
    // 0 单元不用，要用到 0 来标记是否有孩子、父亲
    huffmanTree = new Elem[charNum * 2];
// 初始化
    for (int i = 1; i < charNum + 1; i++) {
      huffmanTree[i] = new Elem(in[ (i - 1) * 2], in[i * 2 - 1], 0, 0, 0);
    }
    for (int i = charNum + 1; i < charNum * 2; i++) {
      huffmanTree[i] = new Elem( (char) 0, 0, 0, 0, 0);
    }

// 构造哈夫曼树
    huffmanTree[0] = new Elem( (char) 0, Integer.MAX_VALUE, 0, 0, 0);
    int minNo1, minNo2;
    for (int i = charNum + 1; i < charNum * 2; i++) {
      // 找出weight最小且无父节点的两个
      minNo1 = 0;
      minNo2 = 0;
      for (int j = 1; j < i; j++) {
        if (huffmanTree[j].parent == 0) {
          if (huffmanTree[j].weight < huffmanTree[minNo1].weight ||
              huffmanTree[j].weight < huffmanTree[minNo2].weight) {
            if (huffmanTree[minNo1].weight < huffmanTree[minNo2].weight) {
              minNo2 = j;
            }
            else {
              minNo1 = j;
            }
          }
        }
      }

      huffmanTree[minNo1].parent = i;
      huffmanTree[minNo2].parent = i;
      // 保持叶子节点为父节点的左孩，如书上图6.26
      if (minNo1 <= charNum) {
        huffmanTree[i].lchild = minNo1;
        huffmanTree[i].rchild = minNo2;
      }
      else {
        huffmanTree[i].lchild = minNo2;
        huffmanTree[i].rchild = minNo1;
      }
      huffmanTree[i].weight = huffmanTree[minNo1].weight +
          huffmanTree[minNo2].weight;
    }

// 求出每个字符编码，从叶子到根，保存至 huffmanCode
    huffmanCode = new String[charNum + 1];
    char[] temp = new char[charNum + 1];
    int start, pa, ch;
    for (int i = 1; i <= charNum; i++) {
      start = charNum;
      ch = i;
      pa = huffmanTree[i].parent;
      while (pa != 0) {
        if (huffmanTree[pa].lchild == ch) {
          temp[start] = '0';
        }
        else {
          temp[start] = '1';
        }
        start--;
        ch = pa;
        pa = huffmanTree[pa].parent;
      }
      huffmanCode[i] = String.valueOf(temp, start + 1, charNum - start);
    }
  }

  // 返回给定字符串的哈夫曼代码，对于本树中无记录的字符则直接插入到原对应位置
  String toCodes(String in) {
    StringBuffer out = new StringBuffer();
    char c;
    int j;
    for (int i = 0; i < in.length(); i++) {
      c = in.charAt(i);
      j = 1;
      while (huffmanTree[j].chara != c && j <= charNum) {
        j++;
      }
      if (j <= charNum) {
        out.append(huffmanCode[j]);
      }
      else {
        out.append(c);
      }
    }
    return out.toString();
  }

  // 对给定哈夫曼码译码，对于非 1、0 的字符直接插入到原对应位置
  String toChars(String in) {
    StringBuffer out = new StringBuffer();
    // 指向树根
    int point = charNum * 2 - 1;
    char c;
    for (int i = 0; i < in.length(); i++) {
      c = in.charAt(i);
      if (c == '0') {
        point = huffmanTree[point].lchild;
      }
      else if (c == '1') {
        point = huffmanTree[point].rchild;
      }
      else {
        out.append(c);
        continue;
      }
      // 为叶子
      if (point <= charNum) {
        out.append(huffmanTree[point].chara);
        point = charNum * 2 - 1;
      }
    }
    return out.toString();
  }

  // 打印哈夫曼树
  public String printTree() {
    StringBuffer out = new StringBuffer();
    out.append("No.\t" + "Char\t" + "Weight\t" + "Parent\t" + "Lchild\t" +
               "Rchild" + "\r\n\r\n");
    for (int i = 1; i < charNum * 2; i++) {
      out.append("[" + i + "]\t" + huffmanTree[i].chara + "\t" +
                 huffmanTree[i].weight + "\t" +
                 huffmanTree[i].parent + "\t" + huffmanTree[i].lchild + "\t" +
                 huffmanTree[i].rchild + "\r\n");
    }
    return out.toString();
  }

  // 打印出所有编码
  public String printCodes() {
    StringBuffer out = new StringBuffer();
    int value = 0;
    out.append("No.\t" + "Char\t" + "Code" + "\r\n\r\n");
    for (int i = 1; i < charNum + 1; i++) {
      out.append("[" + i + "]\t" + huffmanTree[i].chara + "\t" + huffmanCode[i] +
                 "\r\n");
      value += huffmanCode[i].length() * huffmanTree[i].weight;
    }
    out.append("\r\n总带权路径长度为：\t" + value + "\r\n");
    return out.toString();
  }

  public static void main(String[] args) {
    // test：

    // 词频表
    char[] in = {
        ' ', 186, 'a', 64, 'b', 13, 'c', 22, 'd', 32, 'e', 103, 'f', 21, 'g',
        15, 'h', 47, 'i', 57, 'j', 1, 'k', 5, 'l', 32, 'm', 20, 'n', 57, 'o',
        63, 'p', 15, 'q', 1, 'r', 48, 's', 51, 't', 80, 'u', 23, 'v', 8, 'w',
        18, 'x', 1, 'y', 16, 'z', 1};

    Huffman huffman = new Huffman(in);
    huffman.printTree();
    huffman.printCodes();

    // 编码：
    // 输出：0010111010101101000010101110001000101111100011000111000010101101
    //      000001110010100000001111011000110100100110010100010100
    String code = huffman.toCodes("this program is my favorite");

    // 译码：
    // 输出：this program is my favorite
    huffman.toChars(code);
  }
}