SICP по-русски

Используя процедуру generate-huffman-tree, построим следующее дерево для заданного “рок-алфавита”:

> (generate-huffman-tree '((A 2) (BOOM 1) (GET 2) (JOB 2)
                           (NA 16) (SHA 3) (YIP 9) (WAH 1)))
((leaf NA 16)
 ((leaf YIP 9)
  (((leaf A 2)
    ((leaf WAH 1)
     (leaf BOOM 1)
     (WAH BOOM)
     2)
    (A WAH BOOM)
    4)
   ((leaf SHA 3)
    ((leaf JOB 2)
     (leaf GET 2)
     (JOB GET)
     4)
    (SHA JOB GET)
    7)
   (A WAH BOOM SHA JOB GET)
   11)
  (YIP A WAH BOOM SHA JOB GET)
  20)
 (NA YIP A WAH BOOM SHA JOB GET)
 36)

Оно может быть схематически изображено так (я оставил только листья и веса поддеревьев):

Обозначив построенное дерево Хаффмана через ht, закодируем текст песни:

> (encode '(GET A JOB
          SHA NA NA NA NA NA NA NA NA
          GET A JOB
          SHA NA NA NA NA NA NA NA NA
          WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP
          SHA BOOM)
        ht)

(1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1
 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1)

Получили код из 84 битов.

Для кодирования этой же песни кодом фиксированной длины для алфавита из 8 символов нам пришлось бы выделить минимум 3 бита на кодирование одного символа (так как 8 - это 2 в третьей степени). Всего символов в песне 36. Таким образом нам бы потребовалось 36*3 = 108 битов, что больше, чем в случае использования кодирования по Хаффману.

Выигрыш мы получаем за счет того, что слова-символы NA и YIP встречаются значительно чаще остальных.