[移动开发]Huffman编码---java代码实现

import java.util.*;

public class HuffmanCodeing {
    private String code;
    private BinaryTree huffmanTree;
    private class BinaryTree{
        private Character character;
        private BinaryTree leftTree;
        private BinaryTree rightTree;
        private double percent;
        public BinaryTree() {
        }

        public double getPercent() {
            return percent;
        }

        public void setPercent(double percent) {
            this.percent = percent;
        }

        public Character getCharacter() {
            return character;
        }

        public void setCharacter(Character character) {
            this.character = character;
        }

        public BinaryTree getLeftTree() {
            return leftTree;
        }

        public void setLeftTree(BinaryTree leftTree) {
            this.leftTree = leftTree;
        }

        public BinaryTree getRightTree() {
            return rightTree;
        }

        public void setRightTree(BinaryTree rightTree) {
            this.rightTree = rightTree;
        }
    }
    public HuffmanCodeing(String code) {
        this.code = code;
    }

    public String getCode() {
        return code;
    }

    public void setCode(String code) {
        this.code = code;
    }

    private void calc(){
        Map<Character, Integer> map=new HashMap<>();
        PriorityQueue<BinaryTree> priorityQueue=new PriorityQueue<>(
                (o1, o2) -> (int)((o1.getPercent()-o2.getPercent())*1000000000));
        for(int i=0;i<this.code.length();i++){
            Character character=this.code.charAt(i);
            Integer integer=map.get(character);
            map.put(character,integer==null?1:integer+1);
        }
        for(Character character:map.keySet()){
            BinaryTree binaryTree=new BinaryTree();
            binaryTree.setCharacter(character);
            binaryTree.setPercent(map.get(character)*1.0/this.code.length());
            priorityQueue.add(binaryTree);
        }
//        while(!priorityQueue.isEmpty()){
//            Node node=priorityQueue.poll();
//            System.err.println(node.getData()+" "+node.percent);
//        }
        while(priorityQueue.size()!=1){
            BinaryTree rightNode=priorityQueue.poll();
            BinaryTree leftNode=priorityQueue.poll();
            BinaryTree node=new BinaryTree();
            node.setPercent(rightNode.getPercent()+leftNode.getPercent());
            BinaryTree treeNode=new BinaryTree();
            treeNode.setLeftTree(leftNode);
            treeNode.setRightTree(rightNode);
            priorityQueue.add(treeNode);
        }
        huffmanTree=priorityQueue.poll();
    }

    public void printHuffmanCoding(){
        if(huffmanTree==null)
            calc();
        BinaryTree binaryTree=huffmanTree;
        StringBuilder str=new StringBuilder();
        while(binaryTree!=null){
            if(binaryTree.getLeftTree()==null){
                System.err.println(binaryTree.getCharacter()+"   "+String.format("%.3f",binaryTree.getPercent()*100)+"%   "+str+"1");
                break;
            }
            System.err.println(binaryTree.getLeftTree().getCharacter()+"   "+String.format("%.3f",binaryTree.getLeftTree().getPercent()*100)+"%   "+str+"0");
            str.append('1');
            binaryTree=binaryTree.getRightTree();
        }
    }

    public static void main(String[] args) {
        HuffmanCodeing huffmanCodeing=new HuffmanCodeing("My school is very beautiful. I like my school very much." +
                "There is a big playground in my school and we often play sports on it ." +
                "My classroom is big and clean." +
                "There are many books in the library." +
                "I often read books here." +
                "There are some music rooms and art rooms in the teaching building, too." +
                "The teachers in my school are very kind ." +
                "The students are very polite and smart." +
                "I am happy in my school");
        huffmanCodeing.printHuffmanCoding();
    }
}

运行结果(第一行的字符为空白符)

    18.159%   0
e   8.440%   10
o   7.417%   110
a   5.882%   1110
r   5.882%   11110
s   5.627%   111110
i   5.115%   1111110
n   4.859%   11111110
h   4.348%   111111110
t   3.836%   1111111110
y   3.836%   11111111110
l   3.581%   111111111110
m   3.325%   1111111111110
c   2.813%   11111111111110
.   2.302%   111111111111110
d   2.302%   1111111111111110
u   1.790%   11111111111111110
b   1.790%   111111111111111110
p   1.535%   1111111111111111110
T   1.279%   11111111111111111110
g   1.279%   111111111111111111110
v   1.023%   1111111111111111111110
k   1.023%   11111111111111111111110
I   0.767%   111111111111111111111110
f   0.767%   1111111111111111111111110
M   0.512%   11111111111111111111111110
w   0.256%   111111111111111111111111110
,   0.256%   1111111111111111111111111111