给定一个霍夫曼树，如何计算每个符号的霍夫曼码？

Question

如标题所述，我正在编写一个函数来计算树中符号的哈夫曼编码，但我感到完全迷失了。

分支看起来像这样：

{: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 return 树中所有符号的集合，我将编写一个辅助函数 find-in-tree 来查找符号的位串

编辑： 我现在已经试过了，它让我更接近我想要的，但仍然不对（见下面的错误信息）

    (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)} '

它获得了所有正确的位串，但将整个映射分配给每个值，我不知道出了什么问题。

Answer 1

假设你的霍夫曼树是有效的（意味着我们可以忽略 :frequency），并且 0 意味着 'left' 而 1 意味着 'right'：

(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-able。

给定一个霍夫曼树，如何计算每个符号的霍夫曼码？

Given a Huffman tree, how to compute Huffman code for each symbol?

lisp

math

clojure