Generate a table of codes from Huffman's Tree

Question

Generate a table of codes from Huffman's Tree

Navigation

#1 by (0 votes)

0

given a tree of the type:

data THuffman = Hoja Char | Nodo THuffman THuffman

and with the data type

type TablaCodigo = [(Char,String)]

I must create a function

extraerCodigos :: THuffman -> TablaCodigo

That I generate a table of codes from a huffman tree. So far I have the recursive part of the function, but I can not figure out how to generate the string code.

The code would be: 1 if it is a node on the right and 0 if it is a node on the left. In the part of Char in the tuple, would go the data of the Leaf of the tree (that is a char)

Here goes what codee so far (the main function works the helper does not give desired result)

extraerCodigos (Hoja x) = [(x,"0")]
extraerCodigos (Nodo (Hoja x) (Hoja y)) = [(x,enumC "0"),(y,enumC "1")]
extraerCodigos (Nodo (Hoja x) y) = (x,enumC "0") : (extraerCodigos y)
extraerCodigos (Nodo x (Hoja y)) = (y, enumC "1") : (extraerCodigos x)
extraerCodigos (Nodo x y) = (extraerCodigos x) ++ (extraerCodigos y)


enumC bin = if (tail bin) == "0" then bin ++ "0"
            else bin ++ "1"

algoritmos haskell

asked by victor.ja 04.05.2017 в 04:06

source

1 answer

Why do not they upload the data from the BD with JSP? Error list in gridview with foreach [duplicate]

score 0 · Answer 1

You must use an additional argument to store the string until you reach a leaf node. Therefore, the extraerCodigos function simply calls the auxiliary function extraerCodigos' starting with an empty string:

extraerCodigos :: THuffman -> TablaCodigo
extraerCodigos = extraerCodigos' ""

The base case of extraerCodigos' is to reach a leaf node, where the character contained in the sheet is returned together with the accumulated code. If it is not a sheet, the function is recursively called with the left and right node, adding to the code a 0 and a 1 respectively, and concatenating the resulting lists.

extraerCodigos' :: String -> THuffman -> TablaCodigo
extraerCodigos' s (Hoja x) = [(x,s)]
extraerCodigos' s (Nodo l r) = extraerCodigos' (s++"0") l ++ extraerCodigos' (s++"1") r

More efficiently, you can add the new digits of the code as the head of the list, and at the end, invert it:

extraerCodigos' :: String -> THuffman -> TablaCodigo
extraerCodigos' s (Hoja x) = [(x,reverse s)]
extraerCodigos' s (Nodo l r) = extraerCodigos' ('0':s) l ++ extraerCodigos' ('1':s) r