tree - 方案 2 霍夫曼 BST 的最小值

Question

好吧，假设我得到了一个包含字母的对列表，以及它的频率 - 或它在文本中出现的次数。ex '((#\a . 4) (#\b . 2) (#\c . 9)) 我如何找到两个最低频率，以便将它们组合成一棵树？是否有某种功能可以帮助我找到这些？

Answer 1

看一下 SICP 书中的第 2.3.4 节，在那里你会找到关于如何从头开始实现 Huffman 编码树的完整解释。

关于这个问题，这是在具有指定格式的列表中找到两个最低频率的一种可能方法：

(define frequencies '((#\a . 4) (#\b . 2) (#\c . 9)))

(take
 (sort frequencies
       (lambda (x y)
         (< (cdr x) (cdr y))))
 2)

=> '((#\b . 2) (#\a . 4))

Answer 2

仅使用频率的未排序列表表示可能不是解决此问题的正确方法。原因如下：反复寻找最小值是计算霍夫曼编码树的主要操作。当您重复此最小查找操作时，您不想继续搜索整个列表。

作为对该问题的第一次攻击：考虑将排序作为一种方法，使找到最小值成为一种快速操作。

但是，对于这个特定问题，您可能应该考虑使用二进制堆，它是一种表示集合的数据结构。它有一个非常酷的特性，即从堆中取出最小元素非常便宜。在 Huffman 树的构建过程中，您最终会将新元素添加到您的收藏中。您不想一遍又一遍地使用列表。

Racket 在其标准库中的数据/堆集合中实现了二进制堆。将其应用于 Huffman 树构造相当简单。下面用堆实现了基本算法：

(require data/heap)

;; ...

;; make-huffman-tree: (listof leaf) -> node
(define (make-huffman-tree leaves)
  (define a-heap (make-heap node<=?))
  (heap-add-all! a-heap leaves)
  (for ([i (in-range (sub1 (length leaves)))])
    (define min-1 (heap-min a-heap))
    (heap-remove-min! a-heap)
    (define min-2 (heap-min a-heap))
    (heap-remove-min! a-heap)
    (heap-add! a-heap (merge (+ (frequency min-1) (frequency min-2))
                             min-1 min-2)))
  (heap-min a-heap))

其中自由变量node<=?旨在知道如何按频率进行比较，并merge旨在将两件事放在一起。

您可以在 中看到 Huffman 树构造的核心make-huffman-tree：使用堆提取两个最小元素，将它们合并在一起，然后将结果放回堆中。重复直到我们只剩下一棵树。