如何使用这个霍夫曼编码实现？

Question

我发现 this Literate Haskell snippet 实现了霍夫曼编码，但我不明白如何使用它。有些函数对我来说很有意义——例如，我可以写：

a = freqList "lol" 
build list a

但是我怎样才能计算这个字符串的霍夫曼编码呢？ encode 和 encode' 函数似乎采用 Bits 参数。

这是霍夫曼编码实现的代码，减去 Literate Haskell 注释：

module Huffman where

import Control.Arrow
import Data.List
import qualified Data.Map as M
import Data.Function


class Eq a => Bits a where
    zer :: a
    one :: a

instance Bits Int where
    zer = 0
    one = 1

instance Bits Bool where
    zer = False
    one = True

type Codemap a = M.Map Char [a]

data HTree  = Leaf Char Int
            | Fork HTree HTree Int
            deriving (Show)

weight :: HTree -> Int
weight (Leaf _ w)    = w
weight (Fork _ _ w)  = w

merge t1 t2 = Fork t1 t2 (weight t1 + weight t2)

freqList :: String -> [(Char, Int)]
freqList = M.toList . M.fromListWith (+) . map (flip (,) 1)

buildTree :: [(Char, Int)] -> HTree
buildTree = bld . map (uncurry Leaf) . sortBy (compare `on` snd)
    where  bld (t:[])    = t
           bld (a:b:cs)  = bld $ insertBy (compare `on` weight) (merge a b) cs


buildCodemap :: Bits a => HTree -> Codemap a
buildCodemap = M.fromList . buildCodelist
    where  buildCodelist (Leaf c w)    = [(c, [])]
           buildCodelist (Fork l r w)  = map (addBit zer) (buildCodelist l) ++ map (addBit one) (buildCodelist r)
             where addBit b = second (b :)

stringTree :: String -> HTree
stringTree = buildTree . freqList

stringCodemap :: Bits a => String -> Codemap a
stringCodemap = buildCodemap . stringTree

encode :: Bits a => Codemap a -> String -> [a]
encode m = concat . map (m M.!)

encode' :: Bits a => HTree -> String -> [a]
encode' t = encode $ buildCodemap t

decode :: Bits a => HTree -> [a] -> String
decode tree = dcd tree
    where  dcd (Leaf c _) []        = [c]
           dcd (Leaf c _) bs        = c : dcd tree bs
           dcd (Fork l r _) (b:bs)  = dcd (if b == zer then l else r) bs

Answer 1

您要找的答案是

myString = "Ho-ho-ho"
result = encode (stringCodemap myString) myString

如何使用这个霍夫曼编码实现？

How to use this Huffman coding implementation?

haskell

huffman-code