Расшифровка дерева Хаффмана - PullRequest
Новая
       27

Расшифровка дерева Хаффмана

0 голосов
/ 26 октября 2019

Учитывая дерево Хаффмана и поток битов, вернуть пару, содержащую (1) - строку символов, закодированных битами (согласно дереву Хаффмана), и - (2)Bool, указывающий, содержит ли выходной поток каждый бит из - input (то есть возвращает False, если остались какие-либо биты).

Вот код, он возвращает только первый символ в дереве,В чем проблема? 

data BTree a = Leaf a | Fork (BTree a) (BTree a) deriving (Show, Eq)

traT :: BTree a -> BTree a -> [Bool] -> [a] -> ([a], Bool)
traT (Leaf v) c bs res= (res++[v], True)
traT (Fork left right) c (b:bs) res
   | b         = traT right c bs res
   | otherwise = traT left c bs res
traT _ c [] res = (res, True)
traT _ c bs res = traT c c (bs) res
traT _ c bs res = (res, False)

decode :: BTree a -> [Bool] -> ([a], Bool)
decode (Fork x y) bs = traT (Fork x y) (Fork x y) bs []
decode (Leaf x) bs = traT(Leaf x) (Leaf x) bs []

1 Ответ

2 голосов
/ 28 октября 2019

Что ж, похоже, вы на правильном пути.

возвращает только первый символ в дереве.

Ваша главная проблема с этими двумя строками: 

traT (Leaf v) c bs res= (res++[v], True)
...
traT _ c bs res = traT c c (bs) res

Первый маскирует второй для всех конечных узлов. И второй - ваш единственный прямой рекурсивный вызов, который может работать на конечных узлах, следовательно, ваша единственная надежда - обработать любые последующие биты.

Пара замечаний:

  1. выражение res++[v] заставляет код повторно сканировать весь список символов при каждом новом символе.
  2. Вторая строка будет вызывать себя бесконечно (но она маскируется первой).

Другая (меньшая) проблема заключается в том, что возвращение только одного флага на наличие «лишних» битов в конце потока битов приводит к потере информации, поскольку мы хотели бы знать, что такое дополнительные биты. Это немного рискованно делать в вашей основной рекурсивной функции. Конечно, вполне нормально делать это в финальной внешней функции decode.

Вот почему в приведенном ниже примере кода я использовал дополнительный аргумент symBits, чтобы сохранить биты, которые былиобработано, но еще не приписано к символу. Я храню их в обратном порядке, потому что Haskell предпочитает добавлять элементы в список, а не помещать их в конец, повторно сканируя весь список, чтобы сделать это. Отсюда и вызов reverse на финальной стадии обработки. Это дешевый reverse вызов, так как он ограничен по длине до глубины нашего дерева Хаффмана.

Итак, вот несколько предложенных переработанных кодов, в которых я попытался выделить 4 случая: листовой узел илиУзел форка И в конце потока битов или нет. Я также позволил себе переименовать ваш c аргумент в htop. 

data BTree a = Leaf a | Fork (BTree a) (BTree a)  deriving (Show, Eq)

type Bit = Bool


--            hnode   htop     symBits    bs
travHT :: BTree a -> BTree a -> [Bit] -> [Bit] -> ([a], [Bit])

-- situations where at least one input bit remains:
travHT (Leaf v) htop symBits (b:rbs) =  -- CHANGE: forward recursive call
                     -- symbol completed, jump from leaf node to top of htree:
                     let  fwdRes      = travHT htop htop [] (b:rbs)
                          nextSyms    = fst fwdRes
                          lastSymBits = snd fwdRes
                     in   (v : nextSyms, lastSymBits)
travHT (Fork left right) htop symBits (b:rbs)
   | b          = travHT right htop  (b:symBits)  rbs
   | otherwise  = travHT left htop   (b:symBits)  rbs

-- situations where we have reached the end of the bit stream:
travHT (Leaf v)           htop  symBits [] = ([v],[])
--   no more bits and not at a leaf --> incomplete last symbol:
travHT (Fork left right)  htop  symBits [] = ([], reverse symBits)

-- homework-mandated interface:
decode :: BTree a -> [Bit] -> ([a], Bool)
decode htree bs =
   let pair = travHT htree htree [] bs
       (symbols, restOfBits) = pair
       weUsedAllBits = null restOfBits
   in  (symbols, weUsedAllBits)

Тестирование кода с помощью основной программы токена: 

xyz_code :: BTree Char
xyz_code = Fork (Leaf 'x') (Fork (Leaf 'y') (Leaf 'z'))

-- Bit streams for test purposes:
------      Y           Z          X       X       X      Y/Z??
bl0 = [True,False,  True,True  , False,  False,  False]
bl1 = [True,False,  True,True  , False,  False,  False,  True]


main = do
    let bitList = bl0
    let htree   = xyz_code
    let result = decode  htree  bitList
    putStrLn $ "result = " ++ show result

Вывод программы: 

result = ("yzxxx",True)

Надеюсь, это поможет. Я также попрошу у полномочий, которые будут , добавить тег [huffman-code] к вашему вопросу. Теги - это хороший способ помочь людям найти интересующие их вопросы. И у нас есть тег для кодов Хаффмана.

...