详解Huffman编码 – Java实现JunyuLee的博客-

关于Huffman编码的具体定义可参考《算法导论》P245

Huffman Tree节点定义:

abstract class AbstractNode { protected int weight; protected abstract AbstractNode setWeight(int weight); protected abstract int getWeight(); protected AbstractNode(int weight) { this.weight = weight; } } class IntlNode extends AbstractNode { private AbstractNode leftNode; private AbstractNode rightNode; public IntlNode(int weight) { super(weight); } public IntlNode(AbstractNode leftNode, AbstractNode rightNode) { super(leftNode.getWeight() + rightNode.getWeight()); this.leftNode = leftNode; this.rightNode = rightNode; } public IntlNode setLeftNode(AbstractNode leftNode) { this.leftNode = leftNode; return this; } public IntlNode setRightNode(AbstractNode rightNode) { this.rightNode = rightNode; return this; } public AbstractNode getLeftNode() { return leftNode; } public AbstractNode getRightNode() { return rightNode; } @Override public IntlNode setWeight(int weight) { throw new RuntimeException("Illegal modification"); } @Override public int getWeight() { return super.weight; } @Override public String toString() { return "IntlNode{" + "weight=" + super.weight + ", leftNode=" + leftNode + ", rightNode=" + rightNode + '}'; } } class LeafNode extends AbstractNode { private char nodeChar; public LeafNode(int weight, char nodeChar){ super(weight); this.nodeChar = nodeChar; } public char getNodeChar() { return nodeChar; } public LeafNode setNodeChar(char nodeChar) { this.nodeChar = nodeChar; return this; } @Override public LeafNode setWeight(int weight) { super.weight = weight; return this; } @Override public int getWeight() { return super.weight; } @Override public String toString() { return "LeafNode{" + "weight=" + super.weight + ", nodeChar=" + nodeChar + '}'; } } 

获取根节点下某个字符的huffman编码：

 /**      * @param root huffman树root      * @param c 字符      * @return  c 在 root下 的huffmanCode      */ private static String getPath(AbstractNode root, char c) { return getPath0(root, c, new StringBuilder()); } private static String getPath0(AbstractNode root, char c, StringBuilder builder) { if (root instanceof LeafNode) { //simple case, root is leaf             LeafNode leaf = (LeafNode) root; if (leaf.getNodeChar() == c) { return ""; } }else { //root is intlNode             IntlNode intl = (IntlNode) root; //check left             String left = getPath(intl.getLeftNode(), c); if (left != null) { return builder.append(LEFT).append(left).toString(); } //check right             String right = getPath(intl.getRightNode(), c); if (right != null) { return builder.append(RIGHT).append(right).toString(); } } return null; } 

获取根节点下的某个huffman编码对应的字符:

 /**      * @param root huffman root      * @param charArray  字符编码数组      * @return  字符编码对应的字符      */ private static char getChar(AbstractNode root, char[] charArray) { return getChar0(root, charArray, 0); } private static char getChar0(AbstractNode root, char[] charArray, int index) { if (index == charArray.length) { if (root instanceof LeafNode) { return ((LeafNode) root).getNodeChar(); } }else { if(root instanceof IntlNode) {                 IntlNode intlNode = (IntlNode) root; if (charArray[index] == '0') { return getChar0(intlNode.getLeftNode(), charArray, index + 1); } else { return getChar0(intlNode.getRightNode(), charArray, index + 1); } } } throw new RuntimeException("Invalid char array"); } 

建立Huffman树 & 测试：

 public static void main(String[] args) {         List<LeafNode> leafNodeList = new ArrayList<>();         leafNodeList.add(makeLeaf(5, 'f'));         leafNodeList.add(makeLeaf(9, 'e'));         leafNodeList.add(makeLeaf(12, 'c'));         leafNodeList.add(makeLeaf(13, 'b'));         leafNodeList.add(makeLeaf(16, 'd'));         leafNodeList.add(makeLeaf(28, 't'));         leafNodeList.add(makeLeaf(45, 'a'));         leafNodeList.add(makeLeaf(14, 'p')); //使用weight作为优先队列的比较器         Queue<AbstractNode> nodeQueue = new PriorityQueue<>(leafNodeList.size(),                 Comparator.comparingInt(AbstractNode::getWeight));         nodeQueue.addAll(leafNodeList); for (int i = 0, initSize = nodeQueue.size(); i < initSize - 1; i++) {             AbstractNode left = nodeQueue.poll();             AbstractNode right = nodeQueue.poll();             IntlNode combined = new IntlNode(left, right);             nodeQueue.add(combined); } //字符'p'对应010         System.out.println(getPath(nodeQueue.peek(), 'p'));         System.out.println(getChar(nodeQueue.peek(), "010".toCharArray())); } private static LeafNode makeLeaf(int weight, char nodeChar) { return new LeafNode(weight, nodeChar); }