|
编码方案 编码和解码 数据压缩过程称为编码即将文件中的每个字符均转换为一个惟一的二进制位串 数据解压过程称为解码即将二进制位串转换为对应的字符 等长编码方案和变长编码方案 给定的字符集C可能存在多种编码方案 () 等长编码方案 等长编码方案将给定字符集C中每个字符的码长定为[lg|C|]|C|表示字符集的大小 【例】设待压缩的数据文件共有个字符这些字符均取自字符集C={abcdef}等长编码需要三位二进制数字来表 示六个字符因此整个文件的编码长度为位 ()变长编码方案 变长编码方案将频度高的字符编码设置短将频度低的字符编码设置较长 【例】设待压缩的数据文件共有个字符这些字符均取自字符集C={abcdef}其中每个字符在文件中出现的次数 (简称频度)见表 表 字符编码问题
字符 a b c d e f 频度(单位千次) 定长编码 变长编码
根据计算公式 (*+*+*+*+*+)*= 整个文件被编码为位比定长编码方式节约了约%的存储空间 注意 变长编码可能使解码产生二义性产生该问题的原因是某些字符的编码可能与其他字符的编码开始部分(称为前缀)相同 【例】设ETW分别编码为则解码时无法确定信息串是ET还是W 前缀码方案 对字符集进行编码时要求字符集中任一字符的编码都不是其它字符的编码的前缀这种编码称为前缀(编)码 注意 等长编码是前缀码 最优前缀码 平均码长或文件总长最小的前缀编码称为最优的前缀码最优的前缀码对文件的压缩效果亦最佳 其中 p i 为第i个字符得概率 l i 为码长 【例】若将表所示的文件作为统计的样本则a至f六个字符的概率分别为对变长编码 求得的平均码长为优于定长编码(平均码长为) |
