基于字典编码的数据压缩算法的设计与实现课件

1、2022/8/201数据压缩的提出信息的时代解决方法提高硬件的制造工艺数据压缩数据压缩在一定的数据存储空间要求下，将相对庞大的原始数据，重组为满足前述空间要求的数据集合，使得从该数据集合中恢复出来的信息，能够与原始数据相一致，或者能够获得与原始数据一样的使用品质。 2022/8/202数据压缩理论基础信息论熵的提出一条信息中真正需要编码的信息量用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码，假设符号 Fn 在整条信息中重复出现的概率为 Pn，则该符号的熵也即表示该符号所需的二进制位数为：En = - log2( Pn )整条信息的熵也即表示整条信息所需的二进制位数为：E =

2、knEn信息压缩的极限2022/8/203数据压缩基本原理信息存在冗余用较少的位数表示较频繁出现的符号技术构成模型得到字符或单词在信息中出现的概率编码精确地用模型计算出来的位数表示某个符号 压缩 = 模型 + 编码2022/8/204字典编码基本思想数据本身包含有重复代码 根据字典创建方式不同分为两类：隐式字典查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”显式字典从输入的数据中创建一个“短语字典”，编码数据过程中当遇到已经在字典中出现的“短语”时，编码器就输出这个字典中的短语的“索引号” 2022/8/

3、205基于字典压缩算法简介隐式字典显示字典2022/8/206算法实现与改进借鉴LZW for GIF实现起来较容易实现方法的改进使用面向对象编程技术技术的“改进”零搜索动态编码长度2022/8/207实现技术的选择DelphiObject Pascal语言面向对象的开发工具，完全可视化方便快捷RAD工具2022/8/208实现简介以类的形式实现编码类解码类使用生成对象主要流程GetBeginExecuteGetEnd2022/8/209类的定义TLZWEncode = class(TObject) private EncodeTable: array 0.LZWTABLESIZE - 1 o

4、f Word; / 编码表 EncodePointer: array 0.LZWMAXCODES - 1 of LongWord; / 经过编码的缓存 ExportBlock: Pointer; / 存放编码后的数据指针（输出缓存块指针） ExportBlockPtr: array of Byte; / 该指针指向 ExportBlock ，用于访问数组 InitBits: Integer; / 压缩数据的起始位数 ClearCode: Integer; / 清除码 EofCode: Integer; / 结束码 PrefixCode: Integer; / 字头码 SuffixCode: I

5、nteger; / 字尾码 Encode: Integer; / 压缩编码 RunBits: Integer; / 当前处理位 MaxCodeSize: Integer; / 当前处理最大编码 FBegin: Boolean; / 开始处理标志 FExportSize: Integer; / 输出数据块大小 FExportIndex: Integer; / 输出数据块索引 FExportTotalSize: Integer; / 记录输出缓存块大小 ShiftBits: Integer; / 用于位处理，作临时位 ShiftCode: Integer; / 用于位处理，作临时代码 protec

6、ted procedure ExportData(AData: Integer); virtual; / 输出数据（虚方法） public function GetExportPointer: Pointer; / 返回输出指针 function GetExportSize: Integer; / 返回输出大小 procedure GetBegin; / 置开始编码标志 procedure GetEnd; / 置结束编码标志 procedure Execute(Data: array of Byte; DataSize: Integer); virtual; / 执行编码过程（虚方法） con

7、structor Create; destructor Destroy; override; end;2022/8/2010类的定义TLZWUnencode = class(TObject) private InitBits: Integer; / 压缩数据的起始位数 ClearCode: Integer; / 清除码 EofCode: Integer; / 结束码 PrefixCode: Integer; / 字头码 SuffixCode: Integer; / 字尾码 Encode: Integer; / 压缩编码 RunBits: Integer; / 当前处理位 MaxCodeSize

8、: Integer; / 当前处理最大编码 ExportBlock: Pointer; / 存放编码后的数据指针（输出缓存块指针） ExportBlockPtr: array of Byte; / 该指针指向 ExportBlock ，用于访问数组 StackIndex: Integer; / 栈索引 StackTable: array 0.LZWSTACKBUFFERSIZE - 1 of Byte; / 栈表 PrefixTable: array 0.LZWMAXCODES - 1 of Word; / 字头表 SuffixTable: array 0.LZWMAXCODES - 1 of

9、 Byte; / 字尾表 FExportSize: Integer; / 输出数据块大小 FExportIndex: Integer; / 输出数据块索引 FExportTotalSize: Integer; / 记录输出缓存块大小 ShiftBits: Integer; / 用于位处理，作临时位 ShiftCode: Integer; / 用于位处理，作临时代码 protected procedure ExportData(AData: Integer); virtual; / 输出数据（虚方法） public function GetExportPointer: Pointer; / 返回

10、输出指针 function GetExportSize: Integer; / 返回输出大小 procedure GetBegin; / 开始解码（分配输出内存空间） procedure GetEnd; / 结束解码（释放输出内存空间） procedure Execute(Data: array of Byte; DataSize: Integer); virtual; / 执行解码过程（虚方法） constructor Create; destructor Destroy; override; end;2022/8/2011编码流程变量初始化取出数据构造地址输出字头取编码值重置字典加入字典增加处理位编码结束字对未编码数据未处理完达到最大编码值未达到最大编码值达到最大处理编码值数据未处理完数据处理完毕数