By jaresty


2011-04-23 14:18:05 8 Comments

From SICP:

Exercise 2.69. The following procedure takes as its argument a list of symbol-frequency pairs (where no symbol appears in more than one pair) and generates a Huffman encoding tree according to the Huffman algorithm.

(define (generate-huffman-tree pairs)
    (successive-merge (make-leaf-set pairs)))

Make-leaf-set is the procedure given above that transforms the list of pairs into an ordered set of leaves. Successive-merge is the procedure you must write, using make-code-tree to successively merge the smallest-weight elements of the set until there is only one element left, which is the desired Huffman tree. (This procedure is slightly tricky, but not really complicated. If you find yourself designing a complex procedure, then you are almost certainly doing something wrong. You can take significant advantage of the fact that we are using an ordered set representation.)

I wrote the following solution:

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

(define (successive-merge leaf-set)
  (define (iter result leaf-subset)
    (if (null? leaf-subset) 
        result 
        (let ((first-leaf (car leaf-subset)))
          (iter (make-code-tree first-leaf result) (cdr leaf-subset)))))
  (iter (make-code-tree (car leaf-set) (cadr leaf-set)) (cddr leaf-set)))

Is this a good answer? Can it be improved?

1 comments

@Rafe 2011-10-16 23:48:05

It's been a while since I've done any Lisp/Scheme, but I'll make one style point and one algorithmic point.

Style point: it's usually more readable if you define structure projection functions with meaningful names rather than using car, cdr, etc.

Algorithmic point: the simplest way of doing this is to include some priority queue structure from the standard library. Then you simply remove the two least items from the queue, create their combined Huffman tree, and reinsert them into the queue. You're done when the queue contains only one item.

@cmh 2012-04-14 09:58:33

I disagree with your style point. car and cdr are so fundamental to the language that they will be well understood by anyone reading your code. Redefining them will be more painful as you'll have to deal with each codebases particular convention.

@Rafe 2012-05-09 03:04:57

@cmh: the problem is not that the reader won't understand what car and cdr mean, rather that the reader has to keep in mind the structure of your type rather than its semantics.

Related Questions

Sponsored Content

0 Answered Questions

Huffman encoding in Rust

0 Answered Questions

Huffman encoding implementation -follow up

  • 2017-06-06 00:30:26
  • MAG
  • 94 View
  • 2 Score
  • 0 Answer
  • Tags:   rust compression

1 Answered Questions

[SOLVED] Huffman encoding implementation for Unicode

  • 2016-12-23 21:57:33
  • MAG
  • 190 View
  • 6 Score
  • 1 Answer
  • Tags:   rust compression

1 Answered Questions

1 Answered Questions

[SOLVED] C++11 implementation of Huffman-encoding

1 Answered Questions

[SOLVED] Order of evaluation of function arguments

  • 2011-05-19 03:28:53
  • jaresty
  • 316 View
  • 2 Score
  • 1 Answer
  • Tags:   lisp scheme sicp

0 Answered Questions

Coercion of arguments using successive raising

  • 2011-05-08 07:00:26
  • jaresty
  • 164 View
  • 1 Score
  • 0 Answer
  • Tags:   lisp scheme sicp

1 Answered Questions

[SOLVED] Writing a general purpose "split" function (for SICP's imaginary language)

  • 2011-04-15 02:37:44
  • jaresty
  • 205 View
  • 3 Score
  • 1 Answer
  • Tags:   lisp scheme sicp

1 Answered Questions

[SOLVED] Abstract tree-map function

1 Answered Questions

[SOLVED] Encode-symbol for Huffman tree

  • 2011-04-23 09:17:31
  • jaresty
  • 1473 View
  • 2 Score
  • 1 Answer
  • Tags:   lisp scheme sicp

Sponsored Content