HuffEncoding recursively traverses the Huffman tree pointed by node to obtain the map codes, that associates a rune with a slice of booleans. Each code is prefixed by prefix and left and right children are labelled with the booleans false and true, respectively.
(node *Node, prefix []bool, codes map[rune][]bool)
| 76 | // Each code is prefixed by prefix and left and right children are labelled with |
| 77 | // the booleans false and true, respectively. |
| 78 | func HuffEncoding(node *Node, prefix []bool, codes map[rune][]bool) { |
| 79 | if node.symbol != -1 { //base case |
| 80 | codes[node.symbol] = prefix |
| 81 | return |
| 82 | } |
| 83 | // inductive step |
| 84 | prefixLeft := make([]bool, len(prefix)) |
| 85 | copy(prefixLeft, prefix) |
| 86 | prefixLeft = append(prefixLeft, false) |
| 87 | HuffEncoding(node.left, prefixLeft, codes) |
| 88 | prefixRight := make([]bool, len(prefix)) |
| 89 | copy(prefixRight, prefix) |
| 90 | prefixRight = append(prefixRight, true) |
| 91 | HuffEncoding(node.right, prefixRight, codes) |
| 92 | } |
| 93 | |
| 94 | // HuffEncode encodes the string in by applying the mapping defined by codes. |
| 95 | func HuffEncode(codes map[rune][]bool, in string) []bool { |