SICP-2.3.3节练习

SICP-2.3.4节练习

lispor posted @ May 03, 2011 03:31:49 AM in Scheme with tags SICP , 3827 阅读

练习 2.67 - 2.72

 
练习 2.67
Define an encoding tree and a sample message:
(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))
Use the decode procedure to decode the message, and give the result.
我的解答:
scheme@(guile-user)> (decode sample-message sample-tree)
(A D A B B C A)
 
练习 2.68
The encode procedure takes as arguments a message and a tree and produces the list of bits that
gives the encoded message.
(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))
Encode-symbol is a procedure, which you must write, that returns the list of bits that encodes a
given symbol according to a given tree. You should design encode-symbol so that it signals an error
if the symbol is not in the tree at all. Test your procedure by encoding the result you obtained in
Exercise 2-67 with the sample tree and seeing whether it is the same as the original sample message.
我的解答:
代码:
(define (make-leaf symbol weight)
  (list 'leaf symbol weight))

(define (leaf? x)
  (eq? 'leaf (car x)))

(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 (choose-branch bit branch)
  (cond ((= bit 0) (left-branch branch))
        ((= bit 1) (right-branch branch))
        (else (error "bad bit -- CHOOSE-BRANCH" bit))))

(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 (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)
                               (cadr pair))
                    (make-leaf-set (cdr pairs))))))

(define (encode-symbol symbol tree)
  (cond ((and (leaf? tree)
              (eq? symbol (symbol-leaf tree)))
         '())
        ((memq symbol (symbols (left-branch tree)))
         (cons 0 (encode-symbol symbol (left-branch tree))))
        ((memq symbol (symbols (right-branch tree)))
         (cons 1 (encode-symbol symbol (right-branch tree))))
        (else
         (error "bad symbol -- ENCODE-SYMBOL" symbol))))

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


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

运行结果:
scheme@(guile-user)> sample-message
(0 1 1 0 0 1 0 1 0 1 1 1 0)
scheme@(guile-user)> (define message (decode sample-message sample-tree))
scheme@(guile-user)> (encode message sample-tree)
(0 1 1 0 0 1 0 1 0 1 1 1 0)
 
练习 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.)
我的解答:
(define (successive-merge leaf-set)
  (if (= 1 (length leaf-set))
      (car leaf-set)
      (let* ((leaf-1 (car leaf-set))
             (leaf-2 (cadr leaf-set))
             (tree-12 (make-code-tree leaf-1 leaf-2)))
        (successive-merge  (adjoin-set tree-12
                                       (cddr leaf-set))))))

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))
 
练习 2.70
The following eight-symbol alphabet with associated relative frequencies was designed to efficiently
encode the lyrics of 1950s rock songs. (Note that the “symbols” of an “alphabet” need not be
individual letters.)

A     2 NA   16
BOOM  1 SHA  3
GET   2 YIP  9
JOB   2 WAH  1

Use generate-huffman-tree (Exercise 2-69) to generate a corresponding Huffman tree, and use encode
(Exercise 2-68) to encode the following message:

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

How many bits are required for the encoding? What is the smallest number of bits that would be
needed to encode this song if we used a fixed-length code for the eight-symbol alphabet?
我的解答:
huffman 编码需要84个二进制位,而定长编码最少需要108个二进制位:
scheme@(guile-user)> (define frequency-pairs '((a 2)
                                               (na 16)
                                               (boom 1)
                                               (sha 3)
                                               (get 2)
                                               (yip 9)
                                               (job 2)
                                               (wah 1)))
scheme@(guile-user)> (define message '(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))
scheme@(guile-user)> (define tree (generate-huffman-tree frequency-pairs))
scheme@(guile-user)> (length (encode message tree))
84
scheme@(guile-user)> (* 3 (length message))
108
 
练习 2.71
Suppose we have a Huffman tree for an alphabet of n symbols, and that the relative frequencies of
the symbols are 1, 2, 4, ..., 2^(n-1). Sketch the tree for n=5; for n=10. In such a tree (for
general n) how may bits are required to encode the most frequent symbol? the least frequent symbol?
我的解答:
n=5时:

                     {a b c d e} 31
                     /           \
                {a b c d} 15      e 16
                 /     \
           {a b c} 7    d 8
             /    \
        {a b} 3    c 4
         /   \
      a 1    b 2
n=10时,与n=5时类似。
编码最频繁的符号只用1位二进制位
而最不频繁的符号用了n-1位。
 
练习 2.72
Consider the encoding procedure that you designed in Exercise 2-68. What is the order of growth in
the number of steps needed to encode a symbol? Be sure to include the number of steps needed to
search the symbol list at each node encountered. To answer this question in general is
difficult. Consider the special case where the relative frequencies of the n symbols are as
described in Exercise 2-71, and give the order of growth (as a function of n) of the number of steps
needed to encode the most frequent and least frequent symbols in the alphabet.
我的解答:
最频繁的符号 O(n)
最不频繁的符号 O(n^2)
 
good information 说:
Nov 04, 2024 07:03:57 PM

All the best blogs that is very useful for keeping me share the ideas of the future as well this is really what I was looking for, and I am very happy to come here. Thank you very much Feel free to visit my website

Learn more 说:
Nov 04, 2024 07:05:53 PM

I know that you explain it very well. And I hope that other readers will also experience how I feel after reading your article. I really enjoy simply reading all of your weblogs. Simply wanted to inform you that you have people like me who appreciate your work. Definitely a great post. Hats off to you! The information that you have provided is very helpful. 

information 说:
Nov 04, 2024 07:07:13 PM

Hello, I'm happy to see some great articles on your site. Would you like to come to my site later? My site also has posts, comments and communities similar to yours. Please visit and take a look

eci-glasgow2012 说:
Nov 04, 2024 07:08:23 PM

Hello, I'm happy to see some great articles on your site. Would you like to come to my site later? My site also has posts, comments and communities similar to yours. Please visit and take a look

토토뱃지 说:
Nov 04, 2024 07:09:51 PM

your mental health is often the most efficient. Because no two weight-loss journeys are alike, we asked a bunch of women who’ve accomplished a major weight loss exactly how they did it

check here 说:
Nov 04, 2024 07:11:17 PM

It's amazing. I want to learn your writing skills. In fact, I also have a website. If you are okay, please visit once and leave your opinion. First of all let me tell you, you have got a great blog .I am interested in looking for more of such topics and would like to have further information Thank you.

here 说:
Nov 04, 2024 07:12:39 PM

Positive site, where did u come up with the information on this posting?I have read a few of the articles on your website now, and I really like your style. Thanks a million and please keep up the effective work. Feel free to visit my website

카지노헌터 说:
Nov 04, 2024 07:14:00 PM

Thanks for all the tips mentioned in this article! it’s always good to read things you have heard before and are implementing, but from a different perspective, always pick up some extra bits of information.

contents 说:
Nov 04, 2024 07:15:24 PM

I think commenting is the best part of my blogging – especially here at Pro Blogger. You see I’m not that profound or wise, but many of my readers are. Comments add value to my blog. They take my posts to the next level and often take my ideas in rewarding new directions.”

more info 说:
Nov 04, 2024 07:15:49 PM

Youre so right. Im there with you. Your weblog is definitely worth a read if anyone comes throughout it. Im lucky I did because now Ive received a whole new view of this.

토토디펜드 说:
Nov 04, 2024 07:17:44 PM

your mental health is often the most efficient. Because no two weight-loss journeys are alike, we asked a bunch of women who’ve accomplished a major weight loss exactly how they did it

good contents 说:
Nov 04, 2024 07:18:48 PM

Pretty useful article. I merely stumbled upon your internet site and wanted to say that I’ve very favored learning your weblog posts. Any signifies I’ll be subscribing with your feed and I hope you publish once additional soon.

read more 说:
Nov 04, 2024 08:07:19 PM

Our the purpose is to share the reviews about the latest Jackets,Coats and Vests also share the related Movies,Gaming, Casual,Faux Leather and Leather materials available

토토서치 说:
Nov 04, 2024 08:09:05 PM

 is everything that deals with clothes, accessories, footwear, jewelry, hairstyle and etc. It is a habitual trend in which a person dresses up in her best, does her make up, wears her accessories and shoes. Looking good is the main aim of fashion

토디야 说:
Nov 04, 2024 08:30:17 PM

’ve read some good stuff here. Definitely worth bookmarking for revisiting. I surprise how much effort you put to create such a great informative website I bookmark this site and will track down your posts often from now on. Much obliged once more

먹튀코비드 说:
Nov 04, 2024 08:40:32 PM

While looking for articles on these topics, I came across this article on the site here. As I read your article, I felt like an expert in this field. I have several articles on these topics posted on my site

Learn more 说:
Nov 04, 2024 09:53:11 PM

While looking for articles on these topics, I came across this article on the site here. As I read your article, I felt like an expert in this field. I have several articles on these topics posted on my site

스포셀 说:
Nov 04, 2024 10:08:00 PM

it's really nice and meanful. it's really cool blog. Linking is very useful thing.you have really helped lots of people who visit blog and provide them usefull iinformation I bookmark this site and will track down your posts often from now on. Much obliged once more

토토장터 说:
Nov 04, 2024 10:22:59 PM

It has fully emerged to crown Singapore's southern shores and undoubtedly placed her on the global map of residential landmarks. I still scored the more points than I ever have in a season for GS. I think you would be hard pressed to find somebody with the same consistency

get more info 说:
Nov 04, 2024 10:39:03 PM

I found this is an informative and interesting post so i think so it is very useful and knowledgeable. I would like to thank you for the efforts you have made in writing this article.

check here 说:
Nov 04, 2024 10:42:03 PM

 really like this post,and i parent that they havihing this type of useful internet website online. Your internet log isn’t only useful but it's miles moreover clearly creative too "`i like viewing net web sites which recognise the price of handing over the incredible beneficial useful resource freed from rate. I honestly cherished studying your posting. Thanks! 

information 说:
Nov 04, 2024 10:46:28 PM

 is everything that deals with clothes, accessories, footwear, jewelry, hairstyle and etc. It is a habitual trend in which a person dresses up in her best, does her make up, wears her accessories and shoes. Looking good is the main aim of fashion

카디즈 说:
Nov 04, 2024 10:48:18 PM

’d really love to be a part of online community where I can get responses from other knowledgeable individuals that share the same interest. If you have any recommendations, please let me know. Appreciate it! Feel free to visit my website;

먹튀검증사이트 说:
Nov 04, 2024 11:01:39 PM

The article is about how one can go about buying fine jewellery. It details the several aspects that a person should look for when identifying finely crafted jewellery. The cost aspect of such a purchase is also given attention and one is guided about how to buy fine jewellery without paying too much


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter