第一次作业

《数据压缩（第3版）》

1-1 数据压缩的一个基本问题是”我们要压缩什么“，对此你是怎么理解的？

压缩信号空间，即压缩物理空间，如存储器、磁盘、磁带等，压缩时间区段，如传输给定消息集合所需时间；压缩电磁频段，如传输给定消息集合所要求的频谱和带宽。

要压缩信息，由于人类社会进入信息时代，所以会产生越来越多的信息，信息量的增加使得信息的传递和信息的存储量都变的很大，所以我们需要压缩这些信息。方便我们对信息的传递和存储。

1-2 数据压缩的另一个基本问题是”为什么要进行压缩“，对此你又是怎么理解的？

由于信息时代的到来，数据压缩的好处带社会效益和经济效益的提高，如较快的传输各种信源，在现有的通信干线上开通更多的并行业务，降低发射功率，紧缩数据存储容量等。同时因为处在信息发展的高速时代，信息量的增加，导致数据的过大，存储空间的需求过大，然而大量的数据中存在冗余，数据压缩能减少存储空间的消耗，提高存储器的利用率。

1-6 数据压缩技术室如何分类的？

数据压缩的方法根据不同的依据可产生不同的分类。

　　第一种，常用的压缩编码方法可根据质量是否有损失可以分为两大类，一类是无损压缩法（冗余压缩法、可逆压缩）、一类是有损压缩法（熵压缩法、不可逆压缩）、有失真压缩法。

　　第二种，按照其作用域在空间域或频率域上分为：空间方法、变换方法和混合方法。

　　第三种，根据是否自适应分为自适应性编码和非自适应性编码。

　　第四种，根据编码后产生的码词长度是否相等，数据编码又可分为定长码和变长码两类。

参考书《数据压缩导论（第4版）》Page 8（1.4）

1. 用你的计算机上的压缩工具来压缩不同文件。研究原文件的大小和类型对于压缩文件与原文件的大小之比的影响。

一般字符文件的压缩比较高。可以达到50%左右。
视频，音频，图像文件，压缩比一般80%左右。

2.从一本通俗杂志中摘录几段文字，并删除所有不会影响理解的文字，实现压缩。例如，在“This is the dog that belongs to my friend”中，删除is、the、that和to之后，仍然能传递相同的意思。用被删除的单词数与原文本的总单词数之比来衡量文本中的冗余度。用一本技术期刊中的文字来重复这一试验。对于摘自不同来源的文字，我们能否就其冗余度做出定量论述？

不能，因为不同文本的想表达的意思不同，用词的冗余不同，安同等的冗余度压缩，就会损失原文本的意思。

参考书《数据压缩导论（第4版）》Page 30 （3，5，7(a)）

3、给定符号集A={a₁,a₂,a₃,a₄},求一下条件下的一阶熵：

（a）P(a₁)=P(a₂)=P(a₃)=P(a₄)=1/4

（b）P(a₁)=1/2 , P(a₂)=1/4 , P(a₃)=P(a₄)=1/8

（c）P(a₁)=0.505 , P(a₂)=1/4 , P(a₃)=1/4 , P(a₄)=0.12

H（a）=-∑P(x)logP(x)

=-P(a₁)log₂P(a₁)-P(a₂)log₂P(a₂)-P(a₃)log₂P(a₃)-P(a₄)log₂P(a₄)

=-(1/4)log₂(1/4)-(1/4)log₂(1/4)-(1/4)log₂(1/4)-(1/4)log₂(1/4)

=2bits

H（b）=-∑P(x)logP(x)

=-P(a₁)log₂P(a₁)-P(a₂)log₂P(a₂)-P(a₃)log₂P(a₃)-P(a₄)log₂P(a₄)

=-(1/2)log₂(1/2)-(1/4)log₂(1/4)-(1/8)log₂(1/8)-(1/8)log₂(1/8)

=1.75bits

H（a）=-∑P(x)logP(x)

=-P(a₁)log₂P(a₁)-P(a₂)log₂P(a₂)-P(a₃)log₂P(a₃)-P(a₄)log₂P(a₄)

=-(0.505)log₂(0.505)-(1/4)log₂(1/4)-(1/4)log₂(1/4)-(0.12)log₂(0.12)

≈1.875bits

5、考虑以下序列：

ATGCTTAACGTGCTTAACCTGAAGCTTCCGCTGAAGAACCTG

CTGAACCCGCTTAAGCTTAAGCTGAACCTTCTGAACCTGCTT

（a）根据此序列估计个概率值，并计算这一序列的一阶、二阶、三阶和四阶熵。

（b）根据这些熵，能否推断此序列具有什么样的结构？

一阶（a）P(A)=21/84=1/4

P(T)=23/84

P(G)=16/84=4/21

P(C)=24/84=2/7

H（a）=-∑P(x)logP(x)

=-P(A)log₂P(A)-P(T)log₂P(T)-P(G)log₂P(G)-P(C)log₂P(C)

=-(1/4)log₂(1/4)-(23/84)log₂(23/84)-(4/21)log₂(4/21)-(2/7)log₂(2/7)

≈1.9bits

7、做一个实验，看看一个模型能够多么准确地描述一个信源。

(a)编写一段程序，从包括26个字母的符号集{a,b,...,z}中随机选择字母，组成100个四字母单词，这些单词中有多少是有意义的？

#include<iostream>
using namespace std;
#include<cstdlib>
#include<iomanip>
#include<ctime>
int main()
{
	int p,i,j;
	char m[100][100];
	srand(time(NULL));
	cout<<setfill('0');
	for(i=0;i<100;i++)
	{
		for(j=0;j<4;j++)
		{
			p=rand()%26;
			m[i][j]=p+'a';
		}
		m[i][4]='\0';
		cout<<setw(3)<<i+1
			<<" "<<m[i]<<"\t";
	}
	return 0;
}

　　、

只有一个单词。

第一次作业

推荐阅读