基于字典編碼的數(shù)據(jù)壓縮算法的設(shè)計(jì)與實(shí)現(xiàn)課件

1、2022/8/201數(shù)據(jù)壓縮的提出信息的時(shí)代解決方法提高硬件的制造工藝數(shù)據(jù)壓縮數(shù)據(jù)壓縮在一定的數(shù)據(jù)存儲(chǔ)空間要求下，將相對(duì)龐大的原始數(shù)據(jù)，重組為滿足前述空間要求的數(shù)據(jù)集合，使得從該數(shù)據(jù)集合中恢復(fù)出來的信息，能夠與原始數(shù)據(jù)相一致，或者能夠獲得與原始數(shù)據(jù)一樣的使用品質(zhì)。 2022/8/202數(shù)據(jù)壓縮理論基礎(chǔ)信息論熵的提出一條信息中真正需要編碼的信息量用 0 和 1 組成的二進(jìn)制數(shù)碼為含有 n 個(gè)符號(hào)的某條信息編碼，假設(shè)符號(hào) Fn 在整條信息中重復(fù)出現(xiàn)的概率為 Pn，則該符號(hào)的熵也即表示該符號(hào)所需的二進(jìn)制位數(shù)為：En = - log2( Pn )整條信息的熵也即表示整條信息所需的二進(jìn)制位數(shù)為：E =

2、knEn信息壓縮的極限2022/8/203數(shù)據(jù)壓縮基本原理信息存在冗余用較少的位數(shù)表示較頻繁出現(xiàn)的符號(hào)技術(shù)構(gòu)成模型得到字符或單詞在信息中出現(xiàn)的概率編碼精確地用模型計(jì)算出來的位數(shù)表示某個(gè)符號(hào) 壓縮 = 模型 + 編碼2022/8/204字典編碼基本思想數(shù)據(jù)本身包含有重復(fù)代碼 根據(jù)字典創(chuàng)建方式不同分為兩類：隱式字典查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串的“指針”顯式字典從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語字典”，編碼數(shù)據(jù)過程中當(dāng)遇到已經(jīng)在字典中出現(xiàn)的“短語”時(shí)，編碼器就輸出這個(gè)字典中的短語的“索引號(hào)” 2022/8/

3、205基于字典壓縮算法簡介隱式字典顯示字典2022/8/206算法實(shí)現(xiàn)與改進(jìn)借鑒LZW for GIF實(shí)現(xiàn)起來較容易實(shí)現(xiàn)方法的改進(jìn)使用面向?qū)ο缶幊碳夹g(shù)技術(shù)的“改進(jìn)”零搜索動(dòng)態(tài)編碼長度2022/8/207實(shí)現(xiàn)技術(shù)的選擇DelphiObject Pascal語言面向?qū)ο蟮拈_發(fā)工具，完全可視化方便快捷RAD工具2022/8/208實(shí)現(xiàn)簡介以類的形式實(shí)現(xiàn)編碼類解碼類使用生成對(duì)象主要流程GetBeginExecuteGetEnd2022/8/209類的定義TLZWEncode = class(TObject) private EncodeTable: array 0.LZWTABLESIZE - 1 o

4、f Word; / 編碼表 EncodePointer: array 0.LZWMAXCODES - 1 of LongWord; / 經(jīng)過編碼的緩存 ExportBlock: Pointer; / 存放編碼后的數(shù)據(jù)指針（輸出緩存塊指針） ExportBlockPtr: array of Byte; / 該指針指向 ExportBlock ，用于訪問數(shù)組 InitBits: Integer; / 壓縮數(shù)據(jù)的起始位數(shù) ClearCode: Integer; / 清除碼 EofCode: Integer; / 結(jié)束碼 PrefixCode: Integer; / 字頭碼 SuffixCode: I

5、nteger; / 字尾碼 Encode: Integer; / 壓縮編碼 RunBits: Integer; / 當(dāng)前處理位 MaxCodeSize: Integer; / 當(dāng)前處理最大編碼 FBegin: Boolean; / 開始處理標(biāo)志 FExportSize: Integer; / 輸出數(shù)據(jù)塊大小 FExportIndex: Integer; / 輸出數(shù)據(jù)塊索引 FExportTotalSize: Integer; / 記錄輸出緩存塊大小 ShiftBits: Integer; / 用于位處理，作臨時(shí)位 ShiftCode: Integer; / 用于位處理，作臨時(shí)代碼 protec

6、ted procedure ExportData(AData: Integer); virtual; / 輸出數(shù)據(jù)（虛方法） public function GetExportPointer: Pointer; / 返回輸出指針 function GetExportSize: Integer; / 返回輸出大小 procedure GetBegin; / 置開始編碼標(biāo)志 procedure GetEnd; / 置結(jié)束編碼標(biāo)志 procedure Execute(Data: array of Byte; DataSize: Integer); virtual; / 執(zhí)行編碼過程（虛方法） con

7、structor Create; destructor Destroy; override; end;2022/8/2010類的定義TLZWUnencode = class(TObject) private InitBits: Integer; / 壓縮數(shù)據(jù)的起始位數(shù) ClearCode: Integer; / 清除碼 EofCode: Integer; / 結(jié)束碼 PrefixCode: Integer; / 字頭碼 SuffixCode: Integer; / 字尾碼 Encode: Integer; / 壓縮編碼 RunBits: Integer; / 當(dāng)前處理位 MaxCodeSize

8、: Integer; / 當(dāng)前處理最大編碼 ExportBlock: Pointer; / 存放編碼后的數(shù)據(jù)指針（輸出緩存塊指針） ExportBlockPtr: array of Byte; / 該指針指向 ExportBlock ，用于訪問數(shù)組 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; / 輸出數(shù)據(jù)塊大小 FExportIndex: Integer; / 輸出數(shù)據(jù)塊索引 FExportTotalSize: Integer; / 記錄輸出緩存塊大小 ShiftBits: Integer; / 用于位處理，作臨時(shí)位 ShiftCode: Integer; / 用于位處理，作臨時(shí)代碼 protected procedure ExportData(AData: Integer); virtual; / 輸出數(shù)據(jù)（虛方法） public function GetExportPointer: Pointer; / 返回

10、輸出指針 function GetExportSize: Integer; / 返回輸出大小 procedure GetBegin; / 開始解碼（分配輸出內(nèi)存空間） procedure GetEnd; / 結(jié)束解碼（釋放輸出內(nèi)存空間） procedure Execute(Data: array of Byte; DataSize: Integer); virtual; / 執(zhí)行解碼過程（虛方法） constructor Create; destructor Destroy; override; end;2022/8/2011編碼流程變量初始化取出數(shù)據(jù)構(gòu)造地址輸出字頭取編碼值重置字典加入字典增加處理位編碼結(jié)束字對(duì)未編碼數(shù)據(jù)未處理完達(dá)到最大編碼值未達(dá)到最大編碼值達(dá)到最大處理編碼值數(shù)據(jù)未處理完數(shù)據(jù)處理完畢數(shù)