第一次作业

答案：1.1：数据的压缩可分为：（1）有损数据压缩和（2）无损数据压缩两种。要压缩的是 ①物理空间:如存储器，磁盘，磁带，U盘等数据存储介质。②时间区间，如传输给定消息集合所需要的时间， ③电磁频段如传输给定消息集合所需要的频谱，带宽等。也就是指某个信号集合所占的空域，时域和频域空间

1.2：数据在计算机中的存储容量很大，如果直接存储数据会使得存储量很大，计算机运行缓慢，存取慢，效率低下，不方便。另外文本、声音、动画、图形、图像及视频等多种媒体信息。经过数字化处理后其数据量是非常大的，如果不进行数据压缩，计算机系统就无法对它进行存储、交换和传输。使用数据压缩是缩减数据量以减少存储空间，提高其传输、存储和处理效率的一种技术方法。我们对数据进行压缩是通过一些算法或者模型对数据的规律性或重复性进行重新组合，使得减少数据的冗余和存储的空间

1.6：一种分类方法是根据解码后数据是否能够完全无丢失地恢复原始数据，可分为：（1）无损压缩：也称可逆压缩、无失真编码、熵编码等。原理：去除或减少冗余值，但这些值可在解压缩时重新插入到数据中，恢复原始数据。（2）有损压缩：也称不可逆压缩和熵压缩等。此法在压缩时减少了的数据信息是不能恢复的。

第二种分类方法是按照压缩技术所采用的方法来分的：如静态图像编码，电视编码，熵编码等

参考书 1-4

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

通过压缩文件发现，虽然有的文件压缩后占用空间的大小不会变化太多，但大多数文件在压缩后占用的空间比原文件要小很多，在传输时方便了很多时间。还可以进行无损还原。

2、从一种通俗杂志中摘录几段文字，并删除所有不会影响理解的文字，实现压缩。例如，在“This is a 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/8 , P(a₄)=0.12

H=-Σ(a_i)logP(A_i)

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

=4*1/2

= 2

H=-Σ(a_i)logP(A_i)

= - 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/2+1/2+3/8+3/8

=1.75(bits)

H=-Σ(a_i)logP(A_i)

= - 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/8*log₂(1/8)-0.12*log₂0.12

=1.74

5、考虑以下序列：

ATGCTTAACGTGCTTAACCTGAAGCTTCCGCTGAAGAACCTG

CTGAACCCGCTTAAGCTTAAGCTGAACCTTCTGAACCTGCTT

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

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

（a）由题意得：

一阶为：

P(A)=21/84=1/4 、P(G)=16/84=4/21 、P(C)=24/84=2/7、P(T)=23/84

H=-ΣP(a_i)logP(A_i)

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

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

=1/2+ 0.52+0.46+0.52

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

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

#include "stdafx.h"
 
#include<cstdlib>
#include<ctime>
#include<iomanip>
#include<iostream>
using namespace std;
int main()
{
    int r,i,j;
    char a[100][100];
    srand(time(NULL));
    for(i=0;i<100;i++)
    {
        for(j=0;j<4;j++)
        {
            r=rand()%26;
            a[i][j]=r+'a';
        }
        a[i][4]='';
        cout<<i+1<<" "<<a[i]<<"		";
    }
return 0;
}