Java 实现Huffman 编码算法详解编程语言

  
static class Tree { 
                private Node root; 
   
                public Node getRoot() { 
                        return root; 
                } 
   
                public void setRoot(Node root) { 
                        this.root = root; 
                } 
        } 
   
        static class Node implements Comparable { 
                private String chars = ""; 
                private int frequence = 0; 
                private Node parent; 
                private Node leftNode; 
                private Node rightNode; 
   
                @Override 
                public int compareTo(Node n) { 
                        return frequence - n.frequence; 
                } 
   
                public boolean isLeaf() { 
                        return chars.length() == 1; 
                } 
   
                public boolean isRoot() { 
                        return parent == null; 
                } 
   
                public boolean isLeftChild() { 
                        return parent != null && this == parent.leftNode; 
                } 
   
                public int getFrequence() { 
                        return frequence; 
                } 
   
                public void setFrequence(int frequence) { 
                        this.frequence = frequence; 
                } 
   
                public String getChars() { 
                        return chars; 
                } 
   
                public void setChars(String chars) { 
                        this.chars = chars; 
                } 
   
                public Node getParent() { 
                        return parent; 
                } 
   
                public void setParent(Node parent) { 
                        this.parent = parent; 
                } 
   
                public Node getLeftNode() { 
                        return leftNode; 
                } 
   
                public void setLeftNode(Node leftNode) { 
                        this.leftNode = leftNode; 
                } 
   
                public Node getRightNode() { 
                        return rightNode; 
                } 
   
                public void setRightNode(Node rightNode) { 
                        this.rightNode = rightNode; 
                } 
        } 
   
   
统计方法实现如下： 
public static Map<Character, Integer> statistics(char[] charArray) { 
                Map<Character, Integer> map = new HashMap<Character, Integer>(); 
                for (char c : charArray) { 
                        Character character = new Character(c); 
                        if (map.containsKey(character)) { 
                                map.put(character, map.get(character) + 1); 
                        } else { 
                                map.put(character, 1); 
                        } 
                } 
   
                return map; 
        } 
   
   
构建树 
private static Tree buildTree(Map<Character, Integer> statistics, 
                        List leafs) { 
                Character[] keys = statistics.keySet().toArray(new Character[0]); 
   
                PriorityQueue priorityQueue = new PriorityQueue(); 
                for (Character character : keys) { 
                        Node node = new Node(); 
                        node.chars = character.toString(); 
                        node.frequence = statistics.get(character); 
                        priorityQueue.add(node); 
                        leafs.add(node); 
                } 
   
                int size = priorityQueue.size(); 
                for (int i = 1; i <= size - 1; i++) { 
                        Node node1 = priorityQueue.poll(); 
                        Node node2 = priorityQueue.poll(); 
   
                        Node sumNode = new Node(); 
                        sumNode.chars = node1.chars + node2.chars; 
                        sumNode.frequence = node1.frequence + node2.frequence; 
   
                        sumNode.leftNode = node1; 
                        sumNode.rightNode = node2; 
   
                        node1.parent = sumNode; 
                        node2.parent = sumNode; 
   
                        priorityQueue.add(sumNode); 
                } 
   
                Tree tree = new Tree(); 
                tree.root = priorityQueue.poll(); 
                return tree; 
        } 
   
   
   
编码 
public static String encode(String originalStr, 
                        Map<Character, Integer> statistics) { 
                if (originalStr == null || originalStr.equals("")) { 
                        return ""; 
                } 
   
                char[] charArray = originalStr.toCharArray(); 
                List leafNodes = new ArrayList(); 
                buildTree(statistics, leafNodes); 
                Map<Character, String> encodInfo = buildEncodingInfo(leafNodes); 
   
                StringBuffer buffer = new StringBuffer(); 
                for (char c : charArray) { 
                        Character character = new Character(c); 
                        buffer.append(encodInfo.get(character)); 
                } 
   
                return buffer.toString(); 
        } 
   
private static Map<Character, String> buildEncodingInfo(List leafNodes) { 
                Map<Character, String> codewords = new HashMap<Character, String>(); 
                for (Node leafNode : leafNodes) { 
                        Character character = new Character(leafNode.getChars().charAt(0)); 
                        String codeword = ""; 
                        Node currentNode = leafNode; 
   
                        do { 
                                if (currentNode.isLeftChild()) { 
                                        codeword = "0" + codeword; 
                                } else { 
                                        codeword = "1" + codeword; 
                                } 
   
                                currentNode = currentNode.parent; 
                        } while (currentNode.parent != null); 
   
                        codewords.put(character, codeword); 
                } 
   
                return codewords; 
        } 
   
解码 
public static String decode(String binaryStr, 
                        Map<Character, Integer> statistics) { 
                if (binaryStr == null || binaryStr.equals("")) { 
                        return ""; 
                } 
   
                char[] binaryCharArray = binaryStr.toCharArray(); 
                LinkedList binaryList = new LinkedList(); 
                int size = binaryCharArray.length; 
                for (int i = 0; i < size; i++) { 
                        binaryList.addLast(new Character(binaryCharArray[i])); 
                } 
   
                List leafNodes = new ArrayList(); 
                Tree tree = buildTree(statistics, leafNodes); 
   
                StringBuffer buffer = new StringBuffer(); 
   
                while (binaryList.size() > 0) { 
                        Node node = tree.root; 
   
                        do { 
                                Character c = binaryList.removeFirst(); 
                                if (c.charValue() == '0') { 
                                        node = node.leftNode; 
                                } else { 
                                        node = node.rightNode; 
                                } 
                        } while (!node.isLeaf()); 
   
                        buffer.append(node.chars); 
                } 
   
                return buffer.toString(); 
        } 
   
   
测试以及比较 
   
public static void main(String[] args) { 
                String oriStr = "Huffman codes compress data very effectively: savings of 20% to 90% are typical, " 
                                + "depending on the characteristics of the data being compressed. 中华崛起"; 
                Map<Character, Integer> statistics = statistics(oriStr.toCharArray()); 
                String encodedBinariStr = encode(oriStr, statistics); 
                String decodedStr = decode(encodedBinariStr, statistics); 
   
                System.out.println("Original sstring: " + oriStr); 
                System.out.println("Huffman encoed binary string: " + encodedBinariStr); 
                System.out.println("decoded string from binariy string: " + decodedStr); 
   
                System.out.println("binary string of UTF-8: " 
                                + getStringOfByte(oriStr, Charset.forName("UTF-8"))); 
                System.out.println("binary string of UTF-16: " 
                                + getStringOfByte(oriStr, Charset.forName("UTF-16"))); 
                System.out.println("binary string of US-ASCII: " 
                                + getStringOfByte(oriStr, Charset.forName("US-ASCII"))); 
                System.out.println("binary string of GB2312: " 
                                + getStringOfByte(oriStr, Charset.forName("GB2312"))); 
        } 
   
        public static String getStringOfByte(String str, Charset charset) { 
                if (str == null || str.equals("")) { 
                        return ""; 
                } 
   
                byte[] byteArray = str.getBytes(charset); 
                int size = byteArray.length; 
                StringBuffer buffer = new StringBuffer(); 
                for (int i = 0; i < size; i++) {                        byte temp = byteArray[i];                       buffer.append(getStringOfByte(temp));           }               return buffer.toString();       }       public static String getStringOfByte(byte b) {          StringBuffer buffer = new StringBuffer();               for (int i = 7; i >= 0; i--) { 
                        byte temp = (byte) ((b >> i) & 0x1); 
                        buffer.append(String.valueOf(temp)); 
                } 
   
                return buffer.toString(); 
        }