Блог

Я пытаюсь реализовать дерево Хаффмана для декодирования / кодирования сообщений как часть назначения. Кажется, я где-то ошибаюсь в коде, поскольку получаю правильную длину, и я могу подтвердить, выполнив порядок уровней.

Где я делаю неправильно? Хотелось бы получить несколько советов или указаний

Я перепробовал множество различных реализаций MinHeap / приоритетной очереди, но текущее состояние кода является наиболее близким к достижению результата.

 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 amp;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 amp;amp; 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 := amp;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 amp;amp; 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(amp;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: %vn", i 1, l)
        num  = len(l)
    }

    fmt.Printf("NUM NODES: %dn", num)*/

    encodedMap := encode(huffmanTree.root)

    output := ""
    for _, v := range toEncode {
        output  = encodedMap[v]
    }

    fmt.Printf("nnMATCHING: %vnENCODED: %snTARGET:  %sn", output == toDecode, output, toDecode)

    /*for k, v := range encodedMap {
        fmt.Printf("%s %sn", string(k), v)
    }*/
}


  

Я ожидаю, что результат переменной «toEncode» будет равен переменной «toDecode» после выполнения кодирования в строке.

Примечание от преподавателя, которое может помочь в отладке: «При первоначальном добавлении символов в очередь приоритетов вставляйте символы в алфавитном порядке. Например, если ваша частотная карта: b: 2, c: 1, x: 1, a: 4, [пробел]: 3, тогда вы должны добавить их в очередь приоритетов в таком порядке: [пробел], a, b, c, x «.