算法 – 霍夫曼解码(在Scala中)

发布时间：2020-12-16 18:14:32 所属栏目：安全来源：网络整理

导读：我正在尝试编写一种算法来执行霍夫曼解码.我在 Scala中这样做 – 这是Coursera课程的作业,我不想违反荣誉代码,所以下面是伪代码而不是Scala. 我编写的算法采用树形树和位位列表,并且应该返回消息.但是,当我在提供的树上尝试它时,我得到一个NoSuchElementExce

我正在尝试编写一种算法来执行霍夫曼解码.我在 Scala中这样做 – 这是Coursera课程的作业,我不想违反荣誉代码,所以下面是伪代码而不是Scala.

我编写的算法采用树形树和位位列表,并且应该返回消息.但是,当我在提供的树上尝试它时,我得到一个NoSuchElementException(空列表的头部).我不明白为什么.

我知道我的代码可以整理一下 – 我对函数式编程仍然很陌生,所以我用一种对我有意义的方式编写它,而不是以最紧凑的方式编写.

def decode(tree,bits) [returns a list of chars]: {

    def dc(aTree,someBits,charList) [returns a list of chars]: {

        if aTree is a leaf: 

            if someBits is empty: return char(leaf) + charList
            else: dc(aTree,char(leaf) + charList)

        else aTree is a fork:

            if someBits.head is 0: dc(leftFork,someBits.tail,charList)
            else someBits is 1:  dc(rightFork,charList)
        }

     dc(tree,bits,[empty list])

     }

在此先感谢您的帮助.这是我第一次使用StackOverflow,所以我可能有一些学习如何最好地使用该网站.

解决方法

如果我理解正确,你想要通过分叉(从位的方向),直到你找到一片叶子.然后,您将叶值添加到您的char列表,??从这一点开始,您需要重复步骤.
如果我是对的,那么你应该将原始树传递给你的助手方法,而不是现在是叶子的leftFork或rightFork.
所以它会是这样的：

if aTree is a leaf: 
    if someBits is empty: return char(leaf) + charList
    else: dc(tree,char(leaf) + charList)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!