Учитывая дерево Хаффмана, как вычислить код Хаффмана для каждого символа? - PullRequest
Новая
       79

Учитывая дерево Хаффмана, как вычислить код Хаффмана для каждого символа?

0 голосов
/ 18 июня 2020

Как указано в заголовке, я пишу функцию для вычисления кодов Хаффмана для символов в дереве, но чувствую себя совершенно потерянным.

Ветвь выглядит так: 

{:kind :branch, :frequency frequency, :left child0, :right child1}

Лист выглядит так: 

{:kind :leaf, :frequency frequency, :value symbol}

А сам код структурирован так: 

{:tree tree, :length length, :bits bits}

У меня уже есть основная функция (выглядит так): 

 (defn huffman-codes
    "Given a Huffman tree, compute the Huffman codes for each symbol in it. 
    Returns a map mapping each symbol to a sequence of bits (0 or 1)." 
   [T]

   (into {} (for [s (all-symbols T)] [s (find-in-tree s T '())])

 ) 
 )

all-symbols вернуть набор всех символов в дереве, и я должен написать вспомогательную функцию find-in-tree, которая находит битовую строку символа

EDIT: Я пробовал это сейчас, и это приближает меня к тому, что я хочу, но все еще не так (см. Сообщение об ошибке ниже) 

    (defn find-in-tree 
       [s T l]
    
       (if (isleaf? T)
           {(:value T) l}
           (merge (find-in-tree s (:left T) (concat l '(0)))
              (find-in-tree s (:right T) (concat l '(1)))
        )
       )
    
    )

ERROR -- got' {:c {:d (0 0 0), :c (0 0 1), :b (0 1), :a (1)}, :b {:d (0 0 0), :c (0 0 1), :b (0 1), :a (1)}, :d {:d (0 0 0), :c (0 0 1), :b (0 1), :a (1)}, :a {:d (0 0 0), :c (0 0 1), :b (0 1), :a (1)}} ', expected ' {:d (0 0 0), :c (0 0 1), :b (0 1), :a (1)} '

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

1 Ответ

1 голос
/ 19 июня 2020

Предполагается, что ваше дерево Хаффмана является действительным (это означает, что мы можем игнорировать :frequency), и что 0 означает «слева», а 1 означает «справа»: 

(defn code-map
  "Given a Huffman tree, returns a map expressing each symbol's code"
  [{:keys [kind left right value]} code]
  (if (= kind :leaf)
    {value code}
    (merge (code-map left (str code "0"))
           (code-map right (str code "1")))))

Демо: 

;; sample tree
(def root 
  {:kind :branch 
   :left {:kind :branch
          :left {:kind :leaf
                 :value "X"}
          :right {:kind :leaf
                  :value "Y"}}
   :right {:kind :leaf :value "Z"}})

;; make sure to pass it "" as second arg
(code-map root "")
;;=> {"X" "00", "Y" "01", "Z" "1"}

Чтобы очистить это, вы можете переместить "" arg во внутреннюю вспомогательную функцию, и рекурсию можно будет сделать с поддержкой TCO.

...