Решение упражнения 2.70 из SICP

18 February, 2008 (21:27) | Решения упражнений

Используя процедуру 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)

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

2701.png

Обозначив построенное дерево Хаффмана через 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 встречаются значительно чаще остальных.

Write a comment