第十章 数据压缩算法 2021/2/21 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 1 第十章 数据压缩算法
数据压缩 ■将信源所发出的信号用较少的数码表示,减少 容纳给定数据集合的信号空间 所谓信号空间亦即被压缩的对象是指: ■①物理空间,即数据存储介质的尺寸。 ■②时间区间,传输消息集合所需要的时间 ■③电磁频谱区域,如为传输消息的带宽等。 ■信号空间的各种形式相互关联。减少存储空间 就能提高传输效率和节省带宽的占用。 2021/221 计算机算法设计与分析 2
2021/2/21 计算机算法设计与分析 2 数据压缩 ◼ 将信源所发出的信号用较少的数码表示，减少 容纳给定数据集合的信号空间。 ◼ 所谓信号空间亦即被压缩的对象是指： ◼ ①物理空间，即数据存储介质的尺寸。 ◼ ②时间区间，传输消息集合所需要的时间。 ◼ ③电磁频谱区域，如为传输消息的带宽等。 ◼ 信号空间的各种形式相互关联。减少存储空间 就能提高传输效率和节省带宽的占用
可逆压缩和不可逆压缩 ■可逆压缩叫做无失真、无差错编码。压缩后的 数据可以精确地恢复为原来的数据。如ZIP RAR、ARJ、CAB等文件,都是可逆压缩。 ■不可逆压缩叫做失真编码。压缩后的数据不可 能精确地恢复成原始数据。如在计算机中存储 的图片、声音、视频等文件。 ■人的感觉器官本身对于图片、声音、视频中的 某些信息的丢失,是难以察觉的。 ■不可逆压缩技术的标准有:JPEG、MPEG-1 MPEG-2、MPEG-4等,均达到了很高的压缩比。 2021/22 计算机算法设计与分析 3
2021/2/21 计算机算法设计与分析 3 可逆压缩和不可逆压缩 ◼ 可逆压缩叫做无失真、无差错编码。压缩后的 数据可以精确地恢复为原来的数据。如ZIP、 RAR、ARJ、CAB等文件，都是可逆压缩。 ◼ 不可逆压缩叫做失真编码。压缩后的数据不可 能精确地恢复成原始数据。如在计算机中存储 的图片、声音、视频等文件。 ◼ 人的感觉器官本身对于图片、声音、视频中的 某些信息的丢失，是难以察觉的。 ◼ 不可逆压缩技术的标准有：JPEG、MPEG-1、 MPEG-2、MPEG-4等，均达到了很高的压缩比
ASCI码压缩算法 ■数采用不同的基数来表示,长度不同。 般来说,基数较大,长度较短 例娜采厭诎摟是驷轄儒数 钥节衿储,节腚进黻颧裁颈 鯽娃数姬众籌蘧壯进数字 郎迹独,剁懦饗瀜置,此还可以压缩 ■把第八个数的依次放到前7个字节的最高 位上。这样可以压缩62.5%。 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 4 ASCII码压缩算法 ◼ 数采用不同的基数来表示，长度不同。 一般来说，基数较大，长度较短。 例如，十进制的1234是四位，需要四个 字节存储，用16进制数表示为三位， 4D2，只需要两个字节。 ◼ 如果采用100为基数，即每两位十进制数 用一个字节存放，就可以压缩50%。 例如，十进制的1234表示为百进制数， 即12 34，只需要两个字节。 ◼ 但是数字00~99只需要7个比特，每个字 节还有一个比特闲置，因此还可以压缩。 ◼ 把第八个数的依次放到前7个字节的最高 位上。 这样可以压缩62.5%
ASCI码压缩算法 ■1、将原数据的每两位数字作为一组,其 值在00~99之间;然后将它们转化为16进 制,即00~99分别对应于00H-~63H ■2、从第一个16进制数开始, ■3、每8个16进制数为一组,将第8个数字 拆成7个比特,把它们依次放到前面7个 16进制数的最高位上。 ■4、重复第3步,直至完成全部数据为止。 2021/22 计算机算法设计与分析 5
2021/2/21 计算机算法设计与分析 5 ASCII码压缩算法 ◼ 1、将原数据的每两位数字作为一组，其 值在00~99之间；然后将它们转化为16进 制，即00~99分别对应于00H~63H。 ◼ 2、从第一个16进制数开始， ◼ 3、每8个16进制数为一组，将第8个数字 拆成7个比特，把它们依次放到前面7个 16进制数的最高位上。 ◼ 4、重复第3步，直至完成全部数据为止