2.3.5 · Деревья кодов Хаффмана

Дерево Хаффмана и короткие коды частых символов

Взвешенные листья образуют дерево двоичного кода, где частые символы получают короткие пути, а одно представление служит кодированию и декодированию.

Вопрос для размышления

Как одно взвешенное дерево может определять как записываемые биты, так и восстанавливаемые символы?

Представление каждого листа одним символом и его весом частоты
Построение дерева кода путем многократного объединения двух самых легких узлов
Кодирование символа путем отслеживания принадлежности ветви от корня
Декодирование битов путем перехода к листу и перезапуска от корня

make-leaf-set упорядочивает конечное число взвешенных символов от самых легких к самым тяжелым. successive-merge извлекает два самых легких узла, объединяет их множества символов и веса, а затем вставляет новый узел обратно в этот порядок, пока не останется одно дерево. При предоставленных весах A получает путь длиною в один бит, тогда как B, C и D получают все более глубокие пути.

Кодирование проверяет, принадлежит ли следующий символ левой или правой ветви, и записывает 0 или 1 перед продолжением пути под этой ветвью. Декодирование обрабатывает те же решения в обратном направлении. Достижение листа выдает его символ и возвращает к корню для следующего кодового слова. Одинаковые веса могут допускать другое корректное дерево, но явное правило вставки фиксирует дерево, используемое в этих запусках.

Код SICP2,224 из 1,048,576 байт UTF-8

(begin
  (define (append-symbols left right)
    (if (null? left)
        right
        (cons (car left) (append-symbols (cdr left) right))))
  (define (make-leaf symbol weight)
    (list 'leaf symbol weight))
  (define (leaf? object) (eq? (car object) 'leaf))
  (define (symbol-leaf leaf) (cadr leaf))
  (define (weight-leaf leaf) (caddr leaf))
  (define (left-branch tree) (car tree))
  (define (right-branch tree) (cadr tree))
  (define (symbols tree)
    (if (leaf? tree)
        (list (symbol-leaf tree))
        (caddr tree)))
  (define (weight tree)
    (if (leaf? tree)
        (weight-leaf tree)
        (car (cdr (cdr (cdr tree))))))
  (define (make-code-tree left right)
    (list left
          right
          (append-symbols (symbols left) (symbols right))
          (+ (weight left) (weight right))))
  (define (adjoin-weighted node nodes)
    (cond ((null? nodes) (list node))
          ((< (weight node) (weight (car nodes)))
           (cons node nodes))
          (else
           (cons (car nodes)
                 (adjoin-weighted node (cdr nodes))))))
  (define (make-leaf-set pairs)
    (if (null? pairs)
        '()
        (let ((entry (car pairs)))
          (adjoin-weighted
            (make-leaf (car entry) (cadr entry))
            (make-leaf-set (cdr pairs))))))
  (define (successive-merge nodes)
    (if (null? (cdr nodes))
        (car nodes)
        (successive-merge
          (adjoin-weighted
            (make-code-tree (car nodes) (cadr nodes))
            (cdr (cdr nodes))))))
  (define (symbol-in? symbol items)
    (cond ((null? items) #f)
          ((eq? symbol (car items)) #t)
          (else (symbol-in? symbol (cdr items)))))
  (define (encode-symbol symbol tree)
    (if (leaf? tree)
        '()
        (if (symbol-in? symbol (symbols (left-branch tree)))
            (cons 0 (encode-symbol symbol (left-branch tree)))
            (cons 1 (encode-symbol symbol (right-branch tree))))))
  (define tree
    (successive-merge
      (make-leaf-set '((A 4) (B 2) (D 1) (C 1)))))
  (list (weight tree)
        (symbols tree)
        (list (encode-symbol 'A tree)
              (encode-symbol 'B tree)
              (encode-symbol 'C tree)
              (encode-symbol 'D tree))))

(begin
  (define (append-symbols left right)
    (if (null? left)
        right
        (cons (car left) (append-symbols (cdr left) right))))
  (define (make-leaf symbol weight)
    (list 'leaf symbol weight))
  (define (leaf? object) (eq? (car object) 'leaf))
  (define (symbol-leaf leaf) (cadr leaf))
  (define (weight-leaf leaf) (caddr leaf))
  (define (left-branch tree) (car tree))
  (define (right-branch tree) (cadr tree))
  (define (symbols tree)
    (if (leaf? tree)
        (list (symbol-leaf tree))
        (caddr tree)))
  (define (weight tree)
    (if (leaf? tree)
        (weight-leaf tree)
        (car (cdr (cdr (cdr tree))))))
  (define (make-code-tree left right)
    (list left
          right
          (append-symbols (symbols left) (symbols right))
          (+ (weight left) (weight right))))
  (define (adjoin-weighted node nodes)
    (cond ((null? nodes) (list node))
          ((< (weight node) (weight (car nodes)))
           (cons node nodes))
          (else
           (cons (car nodes)
                 (adjoin-weighted node (cdr nodes))))))
  (define (make-leaf-set pairs)
    (if (null? pairs)
        '()
        (let ((entry (car pairs)))
          (adjoin-weighted
            (make-leaf (car entry) (cadr entry))
            (make-leaf-set (cdr pairs))))))
  (define (successive-merge nodes)
    (if (null? (cdr nodes))
        (car nodes)
        (successive-merge
          (adjoin-weighted
            (make-code-tree (car nodes) (cadr nodes))
            (cdr (cdr nodes))))))
  (define (symbol-in? symbol items)
    (cond ((null? items) #f)
          ((eq? symbol (car items)) #t)
          (else (symbol-in? symbol (cdr items)))))
  (define (encode-symbol symbol tree)
    (if (leaf? tree)
        '()
        (if (symbol-in? symbol (symbols (left-branch tree)))
            (cons 0 (encode-symbol symbol (left-branch tree)))
            (cons 1 (encode-symbol symbol (right-branch tree))))))
  (define tree
    (successive-merge
      (make-leaf-set '((A 4) (B 2) (D 1) (C 1)))))
  (list (weight tree)
        (symbols tree)
        (list (encode-symbol 'A tree)
              (encode-symbol 'B tree)
              (encode-symbol 'C tree)
              (encode-symbol 'D tree))))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Первая программа возвращает (8 (A B C D) ((0) (1 0) (1 1 0) (1 1 1))). Вторая программа возвращает ((0 1 1 1 1 0) (A D B)).

На что обратить внимание в трассе

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

Попробуйте сами

Измените программу и сравните результат.

Закодируйте (A B C D A) с помощью предоставленного дерева. Перед запуском определите общее количество битов и объясните, почему A требует меньше битов, чем C или D.

Показать подсказку

Считайте каждый код из первого примера, соедините пять путей и подсчитайте решения на ветвях.

Завершить этот урок

В этой главе пройдено 0 из 20 уроков0%