简单哈弗曼树(Java)

2018-11-22 08:43:07来源：博客园阅读 ()

哈夫曼树的实现

　　1.编码思想

　　　　哈夫曼编码是一种变长的编码方案,字符的编码根据使用频率的的不同而长短不一, 使用频率高的字符其编码较短,使用频率低的字符编码较长,从而使所有的编码总长度为最短.

统计原始数据中个新号符号的频率,安频率高低的次序排列
将两个频率最小的相加,作为原本两个节点的父节点,次父节点的频率为子节点之和
重复上述两部,直到和为只剩下一个元素,那么这个元素就是根

2.解码思想

利用Haffman树进行解码,已知一个二进制位串S,从串S的第一位出发,逐位的去匹配二叉树边上标记的0和1,从haffman树的根节点出发,遇到0时,向左,遇到1时向右,若干连续的0和1确定一条从根节点到某个叶子节点的路径.一旦到达一个叶子节点,便译出一个字符,接着从S的下一个位开始继续寻找.

解码如上.

编码实现如下:

 1 package com.practice;
 2 
 3 /**
 4  * 二叉树的静态三叉链表表示法
 5  */
 6 public class TriElement {
 7     int data ;
 8     int parent, left, right ;
 9     public TriElement(int data, int parent, int left, int right) {
10         this.data = data ;
11         this.parent = parent ;
12         this.left = left ;
13         this.right = right ;
14     }
15     public TriElement(int data) {
16         this(data, -1, -1, -1) ;
17     }
18     public TriElement() {
19         this(0) ;
20     }
21 
22     @Override
23     public String toString() {
24         return "(" + this.data + "," + this.parent + "," + this.left + "," + this.right + ")" ;
25     }
26 }

 1 package com.practice;
 2 
 3 /**
 4  * 依靠静态链表实现的哈弗曼树
 5  */
 6 public class BuffmanTree {
 7     private int leafNum ;
 8     private TriElement[] hufftree ;
 9     public BuffmanTree(int[] weights) {
10         int n = weights.length ;
11         this.leafNum = n ;
12         //用完全二叉树存储,所以需要
13         //申请2 * n - 1个空间
14         this.hufftree = new TriElement[2 * n - 1] ;
15         for(int i = 0 ; i < n; ++i) {
16             this.hufftree[i] = new TriElement(weights[i]) ;
17         }
18 
19         //需要新创建n-1个(2度节点)
20         //(2 * n - 1) - n
21         for(int i = 0 ; i < n - 1; ++i) {
22             int min1 = Integer.MAX_VALUE ;
23             int min2 = min1 ;
24             int p1 = -1, p2 = -1 ;
25             for(int j = 0 ; j < n + i ; ++j) {          //在所有的无父母的节点中查找最小的两个节点
26                                                         //当前所有节点只有 n + i 个
27                 if(hufftree[j].data < min1 && hufftree[j].parent == -1) {
28                     min2 = min1 ;
29                     p2 = p1 ;
30                     min1 = hufftree[j].data ;
31                     p1 = j ;
32                 } else if(hufftree[j].data < min2 && hufftree[j].parent == -1) {
33                     min2 = hufftree[j].data ;
34                     p2 = j ;
35                 }
36             }
37             //构造父母节点
38             hufftree[p1].parent = n + i ;
39             hufftree[p2].parent = n + i ;
40             this.hufftree[n + i] = new TriElement(min1 + min2, -1, p1, p2) ;
41         }
42     }
43 
44     @Override
45     public String toString() {
46         StringBuilder stringBuilder = new StringBuilder() ;
47         for(int i = 0 ; i < this.hufftree.length && hufftree[i] != null ; ++i) {
48             stringBuilder.append("第" + i + "行" + this.hufftree[i].toString() + "\n") ;
49         }
50         return stringBuilder.toString() ;
51     }
52 
53     public String[] toCodes() {
54         String[] huffcodes = new String[this.leafNum] ;
55 
56         for(int i = 0 ; i < this.leafNum ; ++i) {
57             huffcodes[i] = "" ;
58             int child = i ;
59             int parent = hufftree[child].parent ;
60             while(parent != -1) {
61                 if(hufftree[parent].left == child) {
62                     huffcodes[i] = "0" + huffcodes[i] ;
63                 } else {
64                     huffcodes[i] = "1" + huffcodes[i] ;
65                 }
66                 child = parent ;
67                 parent = hufftree[child].parent ;
68             }
69         }
70         return huffcodes ;
71     }
72 
73     /**
74      * 测试
75      */
76     public static void main(String[] args) {
77         int[] weights = {1,3,5,8,32,12} ;
78         BuffmanTree htree = new BuffmanTree(weights) ;
79         System.out.println("数组细节:");
80         System.out.println(htree.toString()) ;
81 
82         String[] codes = htree.toCodes() ;
83         System.out.println("huffman编码: ") ;
84         for(int i = 0 ; i < codes.length ; ++i) {
85             System.out.println((char)('A' + i) + ": " + codes[i] + "   ");
86         }
87         
88     }
89 }