I' am m trying to implement the Huffman tree for decode/encoding messages as part of an assignment. I seem to go wrong somewhere in the code as I get correct length and I can confirm by doing a level order.
Where am I doing wrong? Would love some hints or guidance
I have been trying a lot of different implementations of minHeap/priority queue but the current state of the code is the one that is closest to achieving the result.
package main
import (
"fmt"
"sort"
)
const nullchar = '\x00'
type treeNode struct {
left, right *treeNode
letter rune
frequency int
}
type tree struct {
root *treeNode
}
func makeNode(letter rune) *treeNode {
return &treeNode{
letter: letter,
frequency: 1,
}
}
func makePriorityQueue(letters []*treeNode, byAlpha bool) {
// sort queue into priotiry queue after frequency
sort.Slice(letters, func(i, j int) bool {
if byAlpha {
return letters[i].letter < letters[j].letter
}
return letters[i].frequency < letters[j].frequency
})
}
func mapRunesToNodes(message string) []*treeNode {
letters := make([]*treeNode, 0)
for _, letter := range message {
containsLetter := false
for _, node := range letters {
if node != nil && node.letter == letter {
node.frequency++
containsLetter = true
break
}
}
if !containsLetter {
letters = append(letters, makeNode(letter))
}
}
return letters
}
func printPriorityQueue(letters []*treeNode) {
for _, node := range letters {
if node != nil {
fmt.Println(node)
}
}
}
func makeHuffmanTree(letters []*treeNode) *tree {
tree := new(tree)
if len(letters) == 1 {
tree.root = letters[0]
return tree
}
for len(letters) > 1 {
root := &treeNode{
letter: nullchar,
left: letters[0],
right: letters[1],
frequency: letters[0].frequency + letters[1].frequency,
}
letters = append(letters, root)
letters = append(letters[:0], letters[2:]...)
makePriorityQueue(letters, false)
}
tree.root = letters[0]
return tree
}
func levelOrder(root *treeNode) [][]int {
res := [][]int{}
var dfs func(*treeNode, int)
dfs = func(root *treeNode, level int) {
if root == nil {
return
}
if level >= len(res) {
res = append(res, []int{})
}
res[level] = append(res[level], root.frequency)
dfs(root.left, level+1)
dfs(root.right, level+1)
}
dfs(root, 0)
return res
}
func (root *treeNode) isLeaf() bool {
return root.left == nil && root.right == nil
}
// visit current subtree
func (root *treeNode) traverse(encodeMap *map[rune]string, code string) *map[rune]string {
if root == nil {
return encodeMap
}
if root.isLeaf() {
(*encodeMap)[root.letter] = code
}
root.left.traverse(encodeMap, code+"0")
root.right.traverse(encodeMap, code+"1")
return encodeMap
}
func encode(root *treeNode) map[rune]string {
encodedMap := make(map[rune]string)
root.traverse(&encodedMap, "")
fmt.Println(encodedMap)
return encodedMap
}
func main() {
toEncode := "i love computer science"
toDecode := "110010111010000110111111011000000111000110010011111110100101010110011001110110100111"
queue := mapRunesToNodes(toEncode)
makePriorityQueue(queue, true)
//printPriorityQueue(queue)
huffmanTree := makeHuffmanTree(queue)
/*level := levelOrder(huffmanTree.root)
num := 0
for i, l := range level {
fmt.Printf("LEVEL %d: %v
", i+1, l)
num += len(l)
}
fmt.Printf("NUM NODES: %d
", num)*/
encodedMap := encode(huffmanTree.root)
output := ""
for _, v := range toEncode {
output += encodedMap[v]
}
fmt.Printf("
MATCHING: %v
ENCODED: %s
TARGET: %s
", output == toDecode, output, toDecode)
/*for k, v := range encodedMap {
fmt.Printf("%s %s
", string(k), v)
}*/
}
I expect the result of the variable "toEncode" to be equal to the variable "toDecode" after running the encoding on the string.
Note from teacher that might help debug: "When initially adding characters into your priority queue, insert the characters in alphabetical order. For example, if your frequency map is: b:2, c:1, x:1, a:4, [space]:3 then you would add them into the priority queue in this order: [space],a, b, c, x."
