第九節 無損數據壓縮與LZSS演算法

第九節 無損數據壓縮與LZSS演算法

無損數據壓縮也稱為信息保持編碼、熵編碼、無失真編碼等，從壓縮模型上大體可以分為基於統計的壓縮演算法和基於字典的壓縮演算法兩大類，它是指使用壓縮後的數據進行解壓縮後的數據與原來的數據完全相同，也就是根據一定方法對大量數據進行編碼處理以達到信息壓縮存儲的過程。無損數據壓縮這類演算法壓縮率較低，一般為1/2～1/5。常用的無損壓縮演算法有霍夫曼演算法和LZW壓縮演算法，主要用於文本文件、語音資料庫、程序數據等方面的壓縮。

詞典編碼無損壓縮技術主要有LZ77、LZ78、LZSS、LZW等幾種基本演算法,比較而言LZSS演算法在單片機上實現起來較為理想,其壓縮率較高,編解碼演算法也較為簡單。LZSS壓縮演算法的字典模型使用了自適應的方式,也就是說,將已經編碼過的信息作為字典,如果要編碼的字元串曾經出現過,就輸出該字元串的出現位置及長度,否則輸出新的字元串。實際使用時,由於被壓縮的文件往往較大,一般使用「滑動窗口壓縮」方式,就是將一個虛擬的,可以跟隨壓縮進程滑動的窗口作為術語字典。LZSS演算法採用二分搜索樹，大大加快了壓縮速度，解碼時無鬚生成和維護樹因此更為迅速。該演算法的壓縮率較高，編譯演算法較簡單，但不足之處是每次壓縮都需要向前搜索到原文開頭，對於較長的原文（因建立的二叉樹過於龐大而降低了編碼的效率）需要的時間是不可忍受的，另外無論匹配長度為多少，都分配相同的代碼長度，這顯然存在一定的冗餘。

LZSS演算法仍有不少可改進之處。改進演算法的思路一是從過程出發，即提高編碼程序的效率，在壓縮率保持不變的前提下盡量減少演算法複雜度；二是從結果出發，分析壓縮代碼對，盡量精簡壓縮代碼對每個分量的表示方法，並盡量減少壓縮代碼所佔用的空間，以達到較好的壓縮效果。

:{"wid}5??k4d

推薦閱讀：