有多种方法可以进行霍夫曼编码吗？

Question

所以我做了一个应该进行霍夫曼编码的程序。将我的答案与正确答案进行比较时，并非我的所有答案都匹配。

我得到了

[("a","0"),("c","100"),("b","101"),("d","110"),("f","1110"),("e","1111")]

正确答案是

[('a',"0"),('b',"101"),('c',"100"),('d',"111"),('e',"1101"),('f',"1100")]

正确的树是

然而，我的方法给了我一点改变。在分支 30 上，我使用 0 而不是 1 到达 D。

所以这让我想知道，这两个答案都正确吗？毕竟它们都有相同的字符串长度。

如果我错了，有人可以解释为什么吗？

万一有人要，我的代码写在下面Haskell

mergHufffman::(String,Int) -> (String,Int) -> (String,Int)
mergHufffman x y =  (fst x ++ fst y, snd x + snd y)

data HTree a = Leaf a | Branch (HTree a) (HTree a) deriving Show

treeHuff::[(String,Int)] -> HTree (String,Int)
treeHuff (x:[]) = Leaf x
treeHuff (x:y:[])
        | snd x < snd y = Branch (Leaf x) (Leaf y)
        | snd x > snd y = Branch (Leaf y) (Leaf x)
treeHuff (x:y:z:list)
        | snd x > snd merged = Branch (Leaf x) (treeHuff $ sortFirst $ y:z:list)
        | otherwise = Branch (treeHuff $ y:z:[]) (treeHuff $ sortFirst $ x:list)
        where merged = mergHufffman y z 

sortFirst::[(String,Int)]->[(String,Int)]
sortFirst freq = reverse $ sortBy (comparing snd) freq

readHuffTree :: HTree (String,Int)-> String -> [(String, String)]
readHuffTree (Branch x y) code = f1 ++ f2
                          where 
                          f1 = readHuffTree x (code ++ "0")
                          f2 = readHuffTree y (code ++ "1")
readHuffTree (Leaf x) code = ((fst x, code):[])

Answer 1

是的，您可以随心所欲地将 0 和 1 分配给左右分支，并且您仍将拥有最佳霍夫曼编码。两个答案都是正确的，除非分配指定如何将位值分配给分支。事实上，有 32 个正确答案，因为有五个分支，每个分支有两个选择。

正如这些频率所发生的那样，那棵树是唯一可能的树。然而，有一些频率集可以给出具有不同拓扑结构的树。

一个简单的例子是频率1、1、2、2的集合。当你应用霍夫曼算法时，你会发现在第二步中选择两个最低频率时你可以任意选择。根据您做出的选择，您最终会得到一棵所有代码都具有相同长度 (2) 的树，或者您最终会得到长度为 1、2、3 和 3 的代码。这两个代码都是正确答案。哦，对于 1、2、3、3 树，您可以选择频率为 2 的符号位于顶部。所以实际上三棵不同的树是可能的。对于每棵树，您有八种分配 0 和 1 的方法。所以在这种情况下有 24 个正确答案。如果将代码长度乘以频率并将它们相加，您将看到两种树形拓扑结构均为 12，因此两者都是最优的。

有多种方法可以进行霍夫曼编码吗？

Are there multiple ways to do Huffman encoding?

haskell

huffman-code