Схема 2 минимальных значений для Хаффмана BST

Question

Хорошо, скажем, мне дали список пар, содержащих букву и ее частоту, или количество раз, которое оно было замечено в тексте. ex '((#\a . 4) (#\b . 2) (#\c . 9)) как мне найти 2 самые низкие частоты, чтобы я мог объединить их в дерево? Есть ли какая-то функция, которая поможет мне найти их?

Answer 1

Взгляните на раздел §2.3.4 в книге SICP, там вы найдете полное объяснение того, как реализовать дерево кодирования Хаффмана с нуля.

Что касается вопроса, вот один из возможных способов найти две самые низкие частоты в списке с указанным форматом:

(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

Только использование несортированного представления списка частот, вероятно, не является правильным подходом к этой проблеме. И вот почему: повторное нахождение минимума является основной операцией для вычисления дерева кодирования Хаффмана. Вы не хотите продолжать поиск по всему списку, когда повторяете эту операцию мини-поиска.

В качестве первой атаки на проблему: рассмотрите сортировку как способ сделать поиск минимума быстрой операцией.

Однако для этой конкретной проблемы вам, вероятно, следует рассмотреть возможность использования двоичной кучи, которая представляет собой структуру данных, представляющую коллекцию. У него есть действительно классное свойство: вытащить минимальный элемент из кучи очень дешево. В конечном итоге вы добавите новые элементы в свою коллекцию в процессе построения дерева Хаффмана. Вы не хотите продолжать прибегать к списку снова и снова.

Racket имеет реализацию двоичных куч в своей стандартной библиотеке, в коллекции data / heap. Применение этого к построению дерева Хаффмана довольно просто. Следующее реализует основной алгоритм с кучами:

(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 предназначен взять две вещи и соединить их.

Вы можете увидеть сердце дерева Хаффмана в make-huffman-tree: используйте кучу, чтобы вытащить два минимальных элемента, объединить их и поместить результат обратно в кучу. Повторяйте, пока мы не останемся с одним деревом.