exercise-71.scm (3044B)
1 (import (only (srfi :1) zip)) 2 (import (srfi :26)) 3 (import (srfi :42)) 4 (import (srfi :64)) 5 (import (only (sicp solutions huffman-codes-stuff) 6 generate-huffman-tree 7 make-code-tree 8 make-leaf)) 9 10 ;; For n = 5 11 12 ;; 1 2 3 4 5 13 ;; 0 1 2 3 4 14 ;; 1 2 4 8 16 (sum = 31) 15 ;; A B C D E 16 17 ;; (A B C D E) 31 18 ;; / \ 19 ;; E 16 \ 20 ;; (A B C D) 15 21 ;; / \ 22 ;; D 8 \ 23 ;; (A B C) 7 24 ;; / \ 25 ;; C 4 \ 26 ;; (A B) 3 27 ;; / \ 28 ;; B 2 A 1 29 30 31 ;; For n = 10 32 33 ;; 1 2 3 4 5 6 7 8 9 10 34 ;; 0 1 2 3 4 5 6 7 8 9 35 ;; 1 2 4 8 16 32 64 128 256 512 (sum = 1023) 36 ;; A B C D E F G H I J 37 38 ;; ({A 1} {B 2} {C 4} {D 8} {E 16} {F 32} {G 64} {H 128} {I 256} {J 512}) 39 ;; ({A B 3} {C 4} {D 8} {E 16} {F 32} {G 64} {H 128} {I 256} {J 512}) 40 ;; ({A B C 7} {D 8} {E 16} {F 32} {G 64} {H 128} {I 256} {J 512}) 41 ;; ({A B C D 15} {E 16} {F 32} {G 64} {H 128} {I 256} {J 512}) 42 ;; ({A B C D E 31} {F 32} {G 64} {H 128} {I 256} {J 512}) 43 ;; ({A B C D E F 63} {G 64} {H 128} {I 256} {J 512}) 44 ;; ({A B C D E F G 127} {H 128} {I 256} {J 512}) 45 ;; ({A B C D E F G H 255} {I 256} {J 512}) 46 ;; ({A B C D E F G H I 511} {J 512}) 47 ;; ({A B C D E F G H I J 1023}) 48 49 ;; (A B C D E F G H I J) 1023 50 ;; / \ 51 ;; J 512 \ 52 ;; \ 53 ;; (A B C D E F G H I) 511 54 ;; / \ 55 ;; I 256 \ 56 ;; \ 57 ;; (A B C D E F G H) 255 58 ;; / \ 59 ;; H 128 \ 60 ;; \ 61 ;; (A B C D E F G) 127 62 ;; / \ 63 ;; G 64 \ 64 ;; \ 65 ;; (A B C D E F) 63 66 ;; / \ 67 ;; F 32 \ 68 ;; \ 69 ;; (A B C D E) 31 70 ;; / \ 71 ;; E 16 \ 72 ;; (A B C D) 15 73 ;; / \ 74 ;; D 8 \ 75 ;; (A B C) 7 76 ;; / \ 77 ;; C 4 \ 78 ;; (A B) 3 79 ;; / \ 80 ;; B 2 A 1 81 82 (test-begin "chapter-2-exercise-71") 83 (test-equal 84 (make-code-tree 85 (make-leaf 'E 16) 86 (make-code-tree 87 (make-leaf 'D 8) 88 (make-code-tree 89 (make-leaf 'C 4) 90 (make-code-tree 91 (make-leaf 'B 2) 92 (make-leaf 'A 1))))) 93 (generate-huffman-tree (zip '(A B C D E) 94 (map (cut expt 2 <>) 95 (iota 5 0))))) 96 (test-equal 97 (make-code-tree 98 (make-leaf 'J 512) 99 (make-code-tree 100 (make-leaf 'I 256) 101 (make-code-tree 102 (make-leaf 'H 128) 103 (make-code-tree 104 (make-leaf 'G 64) 105 (make-code-tree 106 (make-leaf 'F 32) 107 (make-code-tree 108 (make-leaf 'E 16) 109 (make-code-tree 110 (make-leaf 'D 8) 111 (make-code-tree 112 (make-leaf 'C 4) 113 (make-code-tree 114 (make-leaf 'B 2) 115 (make-leaf 'A 1)))))))))) 116 (generate-huffman-tree (zip '(A B C D E F G H I J) 117 (map (cut expt 2 <>) 118 (iota 10 0))))) 119 (test-end "chapter-2-exercise-71") 120 121 ;; For n encoded symbols, the most frequent symbol would need 1 bit and the 122 ;; least frequent symbol would need (n - 1) bits.