当前位置:首页 >> 理学 >>

计算机科学导论原书第二版答案第十五章

CHAPTER 15

Data Compression
(Solutions to Practice Set)

Review Questions
1. The two categories of data compression methods are lossless and lossy. 2. Lossless compression preserves the integrity of the data; in lossy compression, some of the data is lost in the compression/decompression process. 3. Run length encoding is a lossless compression method in which repeated occurrences of a symbol are replaced by one occurrence of the symbol followed by the number of occurrences. 4. Lempel-Ziv (LZ) encoding is a type of dictionary-based, lossless compression method in which a dictionary is constructed during encoding. During decoding, the dictionary is reconstructed from the received data. During encoding or decoding, the already-encountered strings can be substituted by their index in the dictionary to reduce the amount of information transmitted. 5. Huffman coding uses the frequency of the characters in the file to construct a tree. The tree is then used to generate codes for each character with the more frequent characters having shorter codes than the less frequent characters. 6. The dictionary in LZ encoding consists of indexed entries that refer to substrings in the original file. These indices are used to refer to future occurrences of these substrings. 7. In Huffman coding, both the sender and receiver must have a copy of the same code in order for the decoded file to match the encoded file. In LZ encoding, the dictionary is generated from the data itself. 8. The three lossy compressions are JPEG, MPEG, and MP3. 9. JPEG is used to compress images while MPEG is used to compress video. 10. MPEG uses a method similar to JPEG to compress the individual frames of video. Whereas, JPEG uses only spatial compression, MPEG uses both spatial and temporal compression. 11. Blocking is the act of dividing the image into 8 × 8 blocks in order to reduce the number of calculations.
1

2

12. DCT changes the 64-pixel values in each block so that the relative relationships between pixels are kept but the redundancies are removed. 13. Quantization of the T table reduces the number of bits needed for encoding each value. 14. A motion picture is a rapid flow of a set of frames where each frame is a picture. 15. Spatial compression is the compression of each frame by using a modified version of JPEG; temporal compression is the removal of redundant frames in MPEG. 16. I-frames (intracoded frames) are complete, independent frames and are not related to any other frames. P-frames (predicted frames) contain only the changes from the preceding I-frame or P-frame. B-frames (bidirectional frames) are relative to the preceding and following I-frame or P-frame.

Multiple-Choice Questions
17. b 23. a 29. c 18. a 24. b 30. c 19. d 25. c 20. a 26. d 21. d 27. b 22. d 28. a

Exercises
31. 10010 00000 11111 11001 01111 00000 00000 32. 00000 01000 11111 01110 00000 00000 33. Different codes result from different ways of organizing the tree. One possible tree with the resulting code is shown Figure S15.33. Figure S15.33 Exercise 33
102

1
61

A: 000 E: 10 B: 1111 F: 110 C: 001 G: 1110 D: 01 0 A 12

0
41

1 0
30

0
21

1 D 20 E 31

0 F 14

1 0 G 8
16

1 C 9

1 B 8

34. Different codes result from different ways of constructing the tree. One possible tree with the resulting code is shown in Figure S15.34. 35. This can be a Huffman code. The shorter codes is not the prefix of any of the two longer codes. The tree is shown in Figure S15.35.

3

Figure S15.34 Exercise 34
10 A: 000 B: 001 C: 010 D: 011 E: 1000 F: 1001 G: 1010 H: 1011 I: 110 G: 111 0 0 0 0 A 1 2 1 B 1 4 0 C 1 1 2 1 D 1 0 E 1 0 2 1 F 1 4 1 0 G 1 2 1 H 1 0 I 1 2 1 J 1

1 6 1

Figure S15.35
A: 0 B: 10 C: 11 1 0 A 0 B 1 C

36. This cannot be a Huffman code. The longer codes all start with one of the shorter codes. For instance, if the receiver receives one 0, it cannot tell if this single zero is an A or the beginning of a C (00) or the beginning of a D (01). 37. 100 0101 0101 000 1100 38. ABBAAACCA 39. Encoding is shown in Figure 15.39a. Figure S15.39a Exercise 39 part a
Uncompressed B B B B, A B A AB B, A, 2B B A AB BB B, A, 2B, 1B B A AB BB BA B, A, 2B, 1B, 1A B A AB BB BA AC B, A, 2B, 2B, 1A, 2C B A AB BB BA AC AA AA AA B, A, 2B, 1B, 1A, 2C, 2A A A AB BB BA AC AABBBBAACAA ABBBBAACAA BBBAACAA BAACAA ACAA BAABBBBAACAA

B

BAABBBBAACAA

Compressed

B, A, 2B, 1B, 1A, 2C, 2A

Decoding is shown in Figure 15.39b.

4

Figure S15.39b

Exercise 39 part b
Compressed

B, A, 2B, 1B, 1A, 2C, 2A

B B B BA B A AB BAAB B A AB BB BAABBB B A AB BB BA BAABBBBA B A AB BB BA AC BAABBBBAAC B A AB BB BA AC AA BAABBBBAACAA A

B A 2B 1B 1A 2C 2A

B, A, 2B, 1B, 1A, 2C, 2A A, 2B, 1B, 1A, 2C, 2A 2B, 1B, 1A, 2C, 2A 1B, 1A, 2C, 2A

1A, 2C, 2A 2C, 2A 2A

Uncompressed

BAABBBBAACAA

40. Figure S15.40 shows the dictionary. Figure S15.40 Exercise 40
Uncompressed
A B AB ABB AA ... 1A A B AB ABB AA AAB ... 1A, 5B A B AB ABB AA AAB BC .... 1A, 5B, 2C A B AB ABB AA AAB BC ... 1A, 5B, 2C, C A B AB ABB AA AAB BC ... 1A, 5B, 2C, C, 8B A B AB ABB AA AAB BC ... 1A, 5B, 2C, C, 8B, 2B C

... AAAABBCCCBBB ...

AA AAB

AAAABBCCCBBB ... AABBCCCBBB ... BCCCBBB ... CCBBB ... CBBB ... BB ...

BC C
C CB

CB
C CB BB

BB

Compressed

...1A, 5B, 2C, C, 8B, 2B ...

Note that if the dictionary contains ABB, it must also have A, B, AB.

5

41. Calculations are
T(0, 0) T(0, 1) T(1, 0) T(1, 1)

= = = =

1/16 [16 + 32 + 128 + 48] 1/16 [0.94 (64) + 0.90 (32) + 0.85 (128) + 0.80 (48)] 1/16 [0.90 (64) + 0.85 (32) + 0.80 (128) + 0.75 (48)] 1/16 [0.85 (64) + 0.80 (32) + 0.75 (128) + 0.70 (48)]

= = = =

17.00 14.08 13.59 13.10


相关文章:
计算机科学导论原书第二版答案第十四章.pdf
计算机科学导论原书第二版答案第十四章 - CHAPTER 14 Database
计算机科学导论原书第二版答案第二章.pdf
计算机科学导论原书第二版答案第 - CHAPTER 2 Number Sys
计算机科学导论原书第二版答案第十一章.pdf
计算机科学导论原书第二版答案第十一章 - CHAPTER 11 Data Str
计算机科学导论第2版答案.doc
第1章 概述习题(答案) 一.选择题 1. D 6. A 2. B 7. B 3. CD 8...计算机科学导论原书第二... 7页 1下载券 计算机科学导论第13章参... ...
计算机科学导论第二版答案.doc
计算机科学导论第二版答案 - 计算机科学导论第二版答案 【篇一:计算机科学导论习题答案】 题(答案) 一.选择题 1. d2. b3. cd 4. c5. abc 6. a7. b8...
计算机科学导论习题答案.doc
计算机科学导论习题答案 - 第1章 概述 习题(答案) 一.选择题 1. D 2. B 3. CD 6. A 7. B 8. B 4. C 5. ABC 9. ABCD 10. ABCDE ...
2016下《计算机科学导论》第2次作业答案.doc
2016下《计算机科学导论第2次作业答案 - 《计算机科学导论第 2 次作业答案 (第 8 章第 15 章) 一、选择题 1.与批处理系统相比较,分时系统的最大...
计算机科学导论答案.doc
计算机科学导论答案_哲学_高等教育_教育专区。计算机科学导论答案 2011 年计算机导论修订第二版课后练习答案 第一章 一、简答题 1、什么是计算机? 计算机系统是一种...
计算机科学导论第2次作业答案[1].doc
计算机科学导论第2次作业答案[1] - 《计算机科学导论第 2 次作业答案 (第 8 章第 15 章) 一、选择题 1.与批处理系统相比较,分时系统的最大优点在于(...
计算机科学导论习题集.pdf
计算机科学导论习题集_电脑基础知识_IT/计算机_专业资料。1 2011年计算机导论修订第二版课后练习答案 第一章 一、简答题 1、什么是计算机? 计算机系统是一种能够...
计算机科学导论第三版答案.doc
计算机科学导论第版答案_电脑基础知识_IT/计算机_专业资料。第1章 概述 习题...B 15. ABCD 二.简答题 1.简述计算机的发展阶段 计算机的出现是 20 世纪最...
计算机科学导论第12章参考答案.pdf
计算机科学导论| 计算机科学导论第12章参考答案_工学_高等教育_教育专区。计算机科学导论第12章(抽象数据类型)课后习题参考答案英文版 CHAPTER...
计算机科学导论第三版答案Ch-18.pdf
Figure P18-15 The initial and goal state of a puzzle Initial State 4 1...计算机科学导论答案第一... 2页 1下载券 计算机科学导论原书第二... ...
《计算机科学导论》课后练习(翻译).doc
计算机科学导论》课后练习(翻译)_理学_高等教育_...也就是在第二代计算机末期和第三代 计算机初期出现...A.位图 B.矢量图 C.余码系统 D.答案 A 或 B...
计算机科学导论 第二次作业-答案.doc
计算机科学导论 第二次作业-答案 - 1 计算机内存容量为 512MB,它一共有
计算机科学导论模拟题2.doc
计算机科学导论第三版,计算机科学导论第三版答案,计算机科学导论第五版答案,计算机科学导论pdf,计算机科学导论有用吗,计算机科学导论讲什么,计算机科学导论第二版答案 ...
计算机科学导论习题.doc
计算机科学导论》习题一、选择题 1. 电子计算机从诞生之日起,经历了 4 个发
计算机科学导论习题答案.pdf
计算机科学导论习题答案_IT/计算机_专业资料。计算机科学导论习题答案 原书第二版 英文 CHAPTER 1 Introduction (Solutions to Practice Set) Review Questions 1. ...
计算机科学导论习题答案.txt
计算机科学导论习题答案 - 计算机科学导论习题答案 第一章 一.选择题 1-5 A D B D D 二.填空题 【1】 处理信息快、存储容量大、可靠性高、准确性高 【2...
计算机科学导论 练习题 汇总.doc
计算机科学导论 练习题 汇总_理学_高等教育_教育专区。计算机科学导论试题 双击自动滚屏 发布者:admin 发布时间:2011-12-13 计算机科学导论试题 1. ...