Построение дерева Хаффмана с использованием min-heap в Haskell

Question

У меня огромная проблема с этим.Я понятия не имею, как сделать дерево Хаффмана, так как оно строится снизу вверх (от рельефов до корня).

Я новичок в Haskell и функциональном программировании.Я видел другие посты, похожие на мои, но они мне не помогли.

Это мой код

    import Data.Map

type Value = Int
type Key = [Char]
type NodeValue = (Key,Value)

data Heap_ a = Empty
        | Node a (Heap_ a) (Heap_ a)
        deriving(Show, Eq)

type Heap a = Heap_ NodeValue

frequencyOfCharacters :: [Char] -> Map Key Value
frequencyOfCharacters [] = Data.Map.empty
frequencyOfCharacters (character:text) = insertWith (+) [character] 1 (frequencyOfCharacters text)

makeLeaf :: NodeValue -> Heap a
makeLeaf a = Node a Empty Empty

mergeHeaps :: Heap a -> Heap a -> Heap a
mergeHeaps Empty rightHeap = rightHeap
mergeHeaps leftHeap Empty = leftHeap
mergeHeaps leftHeap@(Node a lefta righta) rightHeap@(Node b leftb rightb)
    | snd a < snd b = Node a (mergeHeaps lefta rightHeap) righta
    | otherwise = Node b leftb (mergeHeaps leftHeap rightb)

addToHeap :: Heap a->NodeValue->Heap a
addToHeap Empty a =  makeLeaf a
addToHeap h a = mergeHeaps h (makeLeaf a)


takeHeadFromHeap :: Heap a -> (NodeValue,Heap a)
takeHeadFromHeap Empty = (("",-1), Empty)
takeHeadFromHeap (Node a leftBranch rightBranch) = (a, mergeHeaps leftBranch rightBranch)

makeHeap :: Map Key Value -> Heap a
makeHeap map_ = makeHeap_ $ toList map_

makeHeap_ :: [(Key,Value)] -> Heap a
makeHeap_ [] = Empty
makeHeap_ (x:xs) = addToHeap (makeHeap_ xs) x


huffmanEntry :: [Char]-> Heap a
huffmanEntry text = makeHeap $ frequencyOfCharacters text

Я думаю об этой структуре данных для дерева Хаффмана

data HuffmanTree h = Leaf [Char]
                   | NodeHuff [Char] (HuffmanTree h) (HuffmanTree h)
                   deriving(Show, Eq)

, но я не знаю, как сделать дерево Хаффмана из минимумакуча.

После этой строки кода в ghci min куча получается из входной строки

 *Main> huffmanEntry "Aasdqweqweasd"

Answer 1

Вам нужно создать Дерево Хаффмана с минимальной кучей, и вы сказали: «Я понятия не имею, как сделать Дерево Хаффмана из минимальной кучи».Давайте разберемся, что вам нужно сделать перед тем, как вы начнете кодировать, особенно на языке, с которым вы, возможно, не знакомы.

Полагаю, нам следует проверить Интернет, чтобы найти способ создания дерева Хаффмана.Как насчет страницы Википедии по кодированию Хаффмана?(https://en.wikipedia.org/wiki/Huffman_coding)

В простейшем алгоритме построения используется очередь приоритетов , где узлу с наименьшей вероятностью присвоен самый высокий приоритет:

1. Создание листаузел для каждого символа и добавьте его в очередь с приоритетами.
2. Пока в очереди более одного узла:
   • Удалите два узла с наивысшим приоритетом (наименьшей вероятностью) из очереди
   • Создать новый внутренний узел с этими двумя узлами в качестве дочерних и с вероятностью, равной сумме вероятностей двух узлов.
   • Добавить новый узел в очередь.
3. Оставшийся узел является корневым узлом, и дерево завершено.

У вас уже есть код для определения частоты каждого символа в данной строке - этоваша frequencyOfCharacters функция.

Все, что вам сейчас нужно, это очередь с приоритетами! Вы определенно можете найти способ реализовать очередь с приоритетом, используя минимальную кучу.

Надеюсь, это поможет вам собратьлогический тогether.

Если вы хотите пошагово разобраться с проблемой, почему бы вам не начать с создания дерева Хаффмана с использованием работающей реализации очереди с приоритетами (http://hackage.haskell.org/package/PSQueue)?

Как только вы закончите с этим, вы можете попробовать заменить этот готовый модуль на собственный небольшой модуль очереди, используя рабочую реализацию минимальной кучи (http://hackage.haskell.org/package/heap).

Наконец, вы можете написатьмодуль минимальной кучи barebones самостоятельно (у вас уже много кода) и замените на него внешний модуль кучи.

Обновление: Еще несколько конкретных предложений о том, как построить дерево,Это требует небольшой настройки, поэтому, пожалуйста, потерпите меня.Предположим, у вас есть модуль Tree.hs, который позволяет вам работать с двоичными деревьями:

module Tree where

-- Binary Tree
data Tree k v =
    Empty
  | Node (k, v) (Tree k v) (Tree k v)
    deriving ( Show )

-- takes a (key, value) pair and returns a binary tree
-- containing one node with that pair
singleton :: (k, v) -> Tree k v
singleton = undefined

-- takes three things: a (key, value) pair, a binary tree t1
-- and another binary tree t2
-- then it constructs the tree
--    (key, val)
--   /         \
-- t1           t2
joinWith :: (k, v) -> Tree k v -> Tree k v -> Tree k v
joinWith = undefined

-- returns the value associated with the (key, value) pair
-- stored in the root node of the binary tree
value :: Tree k v -> v
value = undefined

, а также у вас есть модуль Queue.hs, который позволяет вам работать с приоритетными очередями (я предполагаю, что у вас естьрабочий модуль min-heap)

module Queue where

import Heap

-- a priority queue
type Queue k v = Heap k v

-- returns an empty queue
empty :: (Ord v)  => Queue k v
empty = undefined

-- adds a (key, value) pair to the queue and returns a
-- new copy of the queue containing the inserted pair
enqueue :: (Ord v) => (k, v) -> Queue k v -> Queue k v
enqueue = undefined

-- removes the lowest-value (key, value) pair from the queue
-- and returns a tuple consisting of the removed pair
-- and a copy of the queue with the pair removed
dequeue :: (Ord v) => Queue k v -> ((k, v), Queue k v)
dequeue = undefined

-- returns the number of elements in the queue
size :: (Ord v) => Queue k v -> Int
size = undefined

Тогда вот как вы можете попытаться создать модуль Huffman.hs, используя имеющиеся в вашем распоряжении инструменты.

module Huffman where

import Queue
import Tree

type HuffmanTree = Tree Char Int

-- takes a list of (character, frequency) pairs and turns them into
-- a Huffman Tree
makeHuffmanTree :: [(Char, Int)] -> HuffmanTree
makeHuffmanTree pairs = let
  nodeList = map (\pair -> (singleton pair, snd pair)) pairs
  nodeQueue = foldr enqueue empty nodeList
    in
  reduceNodes nodeQueue

-- takes pairs of nodes from the queue and combines them
-- till only one node containing the full Huffman Tree is
-- present in the queue
-- then this last node is dequeued and returned
reduceNodes :: Queue HuffmanTree Int -> HuffmanTree
reduceNodes q
  | size q == 0 = error "no nodes!" 
  | size q == 1 = fst (fst (dequeue q))
  | otherwise   = let
      ((tree1, freq1), q') = dequeue q
      ((tree2, freq2), q'') = dequeue q'
      freqSum = freq1 + freq2
      newTree = joinWith ('.', freqSum) tree1 tree2
        in
      reduceNodes (enqueue (newTree, freqSum) q'')

Поскольку типы провереныЯ успешно скомпилировал проект стека с этими модулями.Когда вы думаете, что у вас есть код построения дерева Хаффмана, который вы хотите, вы можете просто заполнить функции undefined тем, что они на самом деле должны делать, и у вас все хорошо!