haskell - matematicas - introducción a la compresión huffman y entropía

Reconstruyendo el árbol de Huffman desde la cadena de bits(preorden) en Haskell

Question

Tengo el siguiente tipo de datos polimórficos Haskell:

data Tree a = Leaf Int a | Node Int (Tree a) (Tree a)

El árbol se comprimirá en una cadena de bits de 0 y 1. Un ''0'' significa un nodo y le sigue la codificación del subárbol izquierdo, luego la codificación del subárbol derecho. Un ''1'' significa una hoja y es seguido por 7 bits de información (por ejemplo, podría ser un char). Se supone que cada nodo / hoja también contiene la frecuencia de la información almacenada, pero esto no es importante para este problema (para que podamos poner cualquier cosa allí).

Por ejemplo, comenzando desde este árbol codificado

[0,0,0,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,1,1,1,1,0,0,0,1,1,1,
 1,0,0,1,1,1,1,1,1,1,0,0,1,0,0,1,1,1,1,0,1,1,1,1,1,1,0,0,0,0,1]

se supone que debe devolver algo como esto

Node 0 (Node 0 (Node 0 (Leaf 0 ''k'') (Leaf 0 ''t'')) 
       (Node 0 (Node 0 (Leaf 0 ''q'') (Leaf 0 ''g'')) (Leaf 0 ''r''))) 
(Node 0 (Leaf 0 ''w'') (Leaf 0 ''a''))

(el espaciado no es importante, pero no encaja en una línea).

Tengo poca experiencia trabajando con árboles, especialmente al implementar código. Tengo una vaga idea sobre cómo resolvería esto en papel (usando algo similar a una pila para tratar con la profundidad / niveles) pero aún estoy un poco perdido.

¡Cualquier ayuda o ideas son apreciadas!

Answer 1

Ok, aquí hay una manera simple (ad-hoc, pero más fácil de entender).

Necesitamos construir un parse función, con el siguiente tipo:

parse  :: [Int] -> Tree Char

El enfoque que mencionaste, con pilas, es el imperativo. Aquí simplemente ponemos en las llamadas recursivas. La compilación será compilada por el compilador y tendrá almacenadas en ella cada llamada recursiva (al menos puedes imaginarlo de esa manera, si quieres, o simplemente ignorar todo este párrafo).

Entonces, la idea es la siguiente: siempre que encuentre un 0 , necesita hacer dos llamadas recursivas al algoritmo. La primera llamada recursiva leerá una rama (la izquierda) del árbol. El segundo necesita ser llamado con el resto de la lista como argumento. El resto lo dejó la primera llamada recursiva. Entonces, necesitamos una función auxiliar parse'' con el siguiente tipo (ahora devolvemos un par, siendo el segundo valor el resto de la lista ):

parse'' :: [Int] -> (Tree Char, [Int])

A continuación, puede ver un fragmento de código donde el caso 0 es tal como se describió anteriormente.
Para el 1 caso, solo tenemos que tomar los siguientes 7 números y convertirlos en un char de alguna manera (dejo la definición de toChar por ti), luego, solo devuelvo un Leaf y el resto de la lista.

parse'' (0:xs) = let (l, xs'')    = parse'' xs
                    (r, xs'''')   = parse'' xs'' in (Node 0 l r, xs'''') --xs'''' should be []
parse'' (1:xs) = let w = toChar (take 7 xs) in (Leaf 0 w , drop 7 xs)

Finalmente, nuestra función de análisis llama al análisis auxiliar uno y devuelve el primer elemento del par.

parse xs = fst $ parse'' xs

Answer 2

hacer un doblez correcto:

import Data.Char (chr)

data Tree a = Leaf a | Node (Tree a) (Tree a)
  deriving Show

build :: [Int] -> [Tree Char]
build xs = foldr go (/_ _ -> []) xs 0 0
  where
  nil = Leaf ''?''
  go 0 run 0 0 = case run 0 0 of
    []     -> Node nil nil:[]
    x:[]   -> Node x   nil:[]
    x:y:zs -> Node x   y  :zs

  go 1 run 0 0 = run 0 1
  go _ _   _ 0 = error "this should not happen!"
  go x run v 7 = (Leaf $ chr (v * 2 + x)): run 0 0
  go x run v k = run (v * 2 + x) (k + 1)

entonces:

/> head $ build [0,0,0,1,1,1,0, ...] -- the list of 01s as in the question
Node (Node (Node (Leaf ''k'') (Leaf ''t''))
      (Node (Node (Leaf ''q'') (Leaf ''g'')) (Leaf ''r'')))
 (Node (Leaf ''w'') (Leaf ''a''))

Answer 3

Bueno, estás tratando de analizar un árbol de bytes de un bit-stream. El análisis es uno de esos casos en los que vale la pena establecer una estructura: vamos a escribir una biblioteca combinadora de analizador en miniatura al estilo de Cómo reemplazar falla por una lista de éxitos , lo que nos permitirá escribir nuestro código de forma idiomática. estilo funcional y delegar una gran parte del trabajo a la máquina.

Traduciendo la vieja rima al lenguaje de los transformadores de mónada, y leyendo "cadena" como "cuerda de bit", tenemos

newtype Parser a = Parser (StateT [Bool] [] a)
    deriving (Functor, Applicative, Monad, Alternative)

runParser :: Parser a -> [Bool] -> [(a, [Bool])]
runParser (Parser m) = runStateT m

Un analizador sintáctico es un cálculo monádico que opera de manera estable en una secuencia de booleanos, produciendo una colección de a s analizados con éxito. Las superpotencias GeneralizedNewtypeDeriving de GHC me permiten eludir las instancias repetitivas de Monad et al.

El objetivo, entonces, es escribir un Parser (Tree SevenBits) - un analizador que devuelve un árbol de septuples de Booleanos. (Puede convertir los 7 bits en Word8 en su tiempo libre derivando una instancia de Functor para Tree y usando fmap ). Voy a usar la siguiente definición de Tree porque es más simple: estoy seguro de que puede averiguar cómo adapta este código a tus propios fines.

data Tree a = Leaf a | Node (Tree a) (Tree a) deriving Show

type SevenBits = (Bool, Bool, Bool, Bool, Bool, Bool, Bool)

Aquí hay un analizador que intenta consumir un solo bit de la secuencia de entrada, fallando si está vacío:

one :: Parser Bool
one = Parser $ do
    stream <- get
    case stream of
        [] -> empty
        (x:xs) -> put xs *> return x

Aquí hay uno que intenta consumir un bit particular de la corriente de entrada, fallando si no coincide:

bit :: Bool -> Parser ()
bit b = do
    i <- one
    guard (i == b)

Aquí estoy sacando una secuencia de siete booleanos del flujo de entrada utilizando replicateM y empaquetándolos en una tupla. Lo usaremos para llenar los contenidos de los nodos de Leaf .

sevenBits :: Parser SevenBits
sevenBits = pack7 <$> replicateM 7 one
    where pack7 [a,b,c,d,e,f,g] = (a, b, c, d, e, f, g)

Ahora podemos finalmente escribir el código que analiza la estructura del árbol en sí. Elegiremos entre las alternativas de Node y Leaf usando <|> .

tree :: Parser (Tree SevenBits)
tree = node <|> leaf
    where node = bit False *> liftA2 Node tree tree
          leaf = bit True *> fmap Leaf sevenBits

Si el node tiene éxito al analizar un bit bajo desde el encabezado de la secuencia, continúa analizando recursivamente la codificación del subárbol izquierdo seguido del subárbol derecho, secuenciando las acciones aplicativas con liftA2 . El truco es que el node falla si no encuentra un bit bajo en la cabecera de la secuencia de entrada, lo que le dice a <|> que abandone el node e intente con la leaf lugar.

Tenga en cuenta cómo la estructura del tree refleja la estructura del tipo de Tree sí. Esto es un análisis aplicativo en el trabajo. Podríamos haber estructurado alternativamente este analizador monádicamente, primero usando one para analizar un bit arbitrario y luego usando un análisis de case en el bit para determinar si debemos continuar analizando un par de árboles o una hoja. En mi opinión, esta versión es más simple, más declarativa y menos detallada.

También compare la claridad de este código con el estilo de bajo nivel de la solución basada en foldr de @ behzad.nouri. En lugar de construir una máquina explícita de estado finito que cambie entre analizar nodos y hojas, una idea de imperativo imperativo, mi diseño le permite describir declarativamente la gramática de la máquina utilizando funciones estándar como liftA2 y <|> y confiar en que las abstracciones hacer lo correcto.

De todos modos, aquí estoy analizando un árbol simple que consiste en un par de Leaf contienen los números ( 0 y 1 codificados en binario). Como puede ver, devuelve el único análisis exitoso y una secuencia vacía de bits restantes.

ghci> runParser tree $ map (>0) [0, 1, 0,0,0,0,0,0,0, 1, 0,0,0,0,0,0,1]
[(Node (Leaf (False, False, False, False, False, False, False)) (Leaf (False, False, False, False, False, False, True)),[])]