The realization of Huffman tree

1. Coding idea

Huffman coding is a kind of coding scheme with variable length. The coding of characters varies according to the frequency of use. The coding of characters with high frequency is shorter, and the coding of characters with low frequency is longer, so that the total length of all codes is the shortest

1. Count the frequency of the new symbols in the original data, and the order of the safety rate
2. Add the lowest two frequencies as the parent node of the original two nodes, and the frequency of the secondary parent node is the sum of the child nodes
3. Repeat the above two parts until there is only one element left in the sum, then this element is the root

2. Decoding idea

A binary bit string s is known. Starting from the first bit of string s, match the 0 and 1 marked on the edge of binary tree bit by bit. Starting from the root node of Haffman tree, when encountering 0, left and right when encountering 1, several consecutive 0 and 1 determine a path from the root node to a leaf node. Once reaching a leaf node, a character is translated, Then start to search from the next bit of S

Decode as above

The coding implementation is as follows:

 1 package com.practice;
 2 
 3 /**
 4  * Static Trident list representation of binary tree
 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  * Huffman tree based on static linked list
 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         //Storage with complete binary tree,So need
13         //Application 2 * n - 1 Space
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         //New creation required n-1 individual(2 Degree node)
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) {          //Find the smallest two nodes among all the nodes without parents
26                                                         //Currently, all nodes have only n + i individual
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             //Construct parent node
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("The first" + i + "That's ok" + 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      * test
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("Array details:");
80         System.out.println(htree.toString()) ;
81 
82         String[] codes = htree.toCodes() ;
83         System.out.println("huffman Code: ") ;
84         for(int i = 0 ; i < codes.length ; ++i) {
85             System.out.println((char)('A' + i) + ": " + codes[i] + "   ");
86         }
87         
88     }
89 }