Кодировать-символ Хаффмана дерево


Из текста:

Упражнения 2.68. Кодирования процедуры принимает в качестве аргумента сообщение и дерево и производит список биты что дает закодированное сообщение.

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))

Кодирование-символ-это процедура, которая вы должны написать, что возвращает список битов, которая кодирует данный символ согласно данного дерева. Вы должны конструкция кодирования-символ сигнализирует об ошибке, если символ не в дереве вообще. Проверить свои процедура кодирования результат полученные в упражнении 2.67 с образец дерева и видеть, является ли это так же, как оригинальный образец сообщение.

Учебник содержит следующие определения:

(define (make-leaf symbol weight)
  (list 'leaf symbol weight))
(define (leaf? object)
  (eq? (car object) 'leaf))
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))

(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) (symbols right))
        (+ (weight left) (weight right))))

(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)
      (cadddr tree)))

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
        (let ((next-branch
               (choose-branch (car bits) current-branch)))
          (if (leaf? next-branch)
              (cons (symbol-leaf next-branch)
                    (decode-1 (cdr bits) tree))
              (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))
(define (choose-branch bit branch)
  (cond ((= bit 0) (left-branch branch))
        ((= bit 1) (right-branch branch))
        (else (error "bad bit -- CHOOSE-BRANCH" bit))))
(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((< (weight x) (weight (car set))) (cons x set))
        (else (cons (car set)
                    (adjoin-set x (cdr set))))))

(define (make-leaf-set pairs)
  (if (null? pairs)
      '()
      (let ((pair (car pairs)))
        (adjoin-set (make-leaf (car pair)    ; symbol
                               (cadr pair))  ; frequency
                    (make-leaf-set (cdr pairs))))))

(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                   (make-leaf 'B 2)
                   (make-code-tree (make-leaf 'D 1)
                                   (make-leaf 'C 1)))))

(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))

И я написал следующий ответ:

(define (member? x set)
  (not (equal? (member x set) false)))

(define (encode-branch symbol tree)
  (let ((left (left-branch tree))
        (right (right-branch tree)))
    (cond ((member? symbol (symbols left)) (list 0 left))
          ((member? symbol (symbols right)) (list 1 right))
          (else (error "Symbol is not a member of either left or right branches of the tree - can't encode" symbol tree)))))

(define (encode-symbol symbol tree)
  (if (leaf? tree) '()
      (let ((new-branch (encode-branch symbol tree)))
        (cons (car new-branch) (encode-symbol symbol (cadr new-branch))))))

Как я могу улучшить мое решение?



1510
2
задан 23 апреля 2011 в 09:04 Источник Поделиться
Комментарии
1 ответ

Не проще ли распаковать дерева в сопоставлении словарь каждого символа в соответствующую битовую строку? Затем вы можете просто искать каждый символ во входных данных для генерации соответствующих выходных битов.

Редактировать:
Как полагают syb0rg, вот реализация (С#, Я боюсь, что моя шепелявость слишком расти ... хотя это почти чистый). Части, относящейся к моему предложению выше живет в HuffmanCodes функции в конце.

void Main()
{
var corpus = @"Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat. Ut wisi enim ad minim veniam, quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut aliquip ex ea commodo consequat.";
var hcs = HuffmanCodes(corpus);
Console.WriteLine(hcs);
}

Dictionary<char, int> Histogram(string corpus) {
var hg = new Dictionary<char, int>();
foreach (var x in corpus) {
int f;
hg.TryGetValue(x, out f);
hg[x] = f + 1;
}
return hg;
}

class HuffTree {
internal char? Sym; // Non-null iff this is a leaf node with no children.
internal int Freq;
internal HuffTree L;
internal HuffTree R;
}

// Oh, for a priority queue. This is *really* inefficient!
HuffTree HuffmanTree(string corpus) {
var hg = Histogram(corpus);
var hts = hg.Keys.Select(x => new HuffTree { Sym = x, Freq = hg[x] }).OrderBy(t => t.Freq).ToList();
while (2 <= hts.Count) {
var leasts = hts.Take(2).ToList();
var l = leasts[0];
var r = leasts[1];
var newHt = new HuffTree { Freq = l.Freq + r.Freq, L = l, R = r };
hts = hts.Skip(2).Concat(new HuffTree[] { newHt }).OrderBy(t => t.Freq).ToList();
}
return hts.First();
}

Dictionary<char, string> HuffmanCodes(string corpus) {
var codes = new Dictionary<char, string>();
Action<HuffTree, string> a = null; // Sweet recursion.
a = (ht, code) => {
if (ht.Sym != null) {
codes[(char)ht.Sym] = code;
} else {
a(ht.L, code + "0");
a(ht.R, code + "1");
}
};
a(HuffmanTree(corpus), "");
return codes;
}

3
ответ дан 17 октября 2011 в 12:10 Источник Поделиться