常用數據無損壓縮算法分析
加入技術交流群
(2)字典維護與更新 字典指針由哈希函數生成。正確選擇哈希函數非常重要，這將影響執行效率。正確的哈希函數所產生的重復值極少，這樣檢索字符串所需比較次數也較少，從而可有效提高代碼的執行效率。
當字典滿時，字典的維護和更新對壓縮率也是至關重要的。可重新從初始狀態建立字典；也可監測壓縮率，當壓縮率變壞時全部或部分清除字典。
(3)壓縮數據代碼長度 壓縮時，輸入數據一般是8位。但壓縮后的輸出是轉化的字符串代碼，其中0～255為8位碼，256為9位碼，25l～512為10位碼，l 024為11位碼。解壓則相反，需要位操作。因此，輸出可以從9位碼開始，隨著字典內容的增加，碼字也逐漸增加。這樣可提高執行效率，但在譯碼時需考慮不等長碼的識別，可通過設置標志位來解決。
3．3 基于哈夫曼編碼原理的壓縮算法
哈夫曼算法的過程為：統計原始數據中各字符出現的頻率；所有字符按頻率降序排列；建立哈夫曼樹：將哈夫曼樹存入結果數據；重新編碼原始數據到結果數據。哈夫曼算法實現流程如圖3所示。本文引用地址：http://www.j9360.com/article/188663.htm
哈夫曼算法的實質是針對統計結果對字符本身重新編碼，而不是對重復字符或重復子串編碼。實用中．符號的出現頻率不能預知，需要統計和編碼兩次處理，所以速度較慢，無法實用。而自適應(或動態)哈夫曼算法取消了統計，可在壓縮數據時動態調整哈夫曼樹，這樣可提高速度。因此，哈夫曼編碼效率高，運算速度快，實現方式靈活。
采用哈夫曼編碼時需注意的問題：
(1)哈夫曼碼無錯誤保護功能，譯碼時，碼串若無錯就能正確譯碼；若碼串有錯應考慮增加編碼，提高可靠性。
(2)哈夫曼碼是可變長度碼，因此很難隨意查找或調用壓縮文件中間的內容，然后再譯碼，這就需要在存儲代碼之前加以考慮。
(3)哈夫曼樹的實現和更新方法對設計非常關鍵。
3．4 基于算術編碼的壓縮算法
算術編碼壓縮也是一種根據字符出現概率重新編碼的壓縮方案。該思想和哈夫曼編碼有些相似，但哈夫曼編碼的每個字符需用整數個位表示。而算術編碼方法則無這一限制，它是將輸入流視為整體進行編碼。雖然算術編碼壓縮率高．但運算復雜，速度慢。
4 結語
游程編碼和LZW編碼屬于基于字典模型的壓縮算法，而哈夫曼編碼和算術編碼屬于基于統計模型的壓縮算法，前者與原始數據的排列次序有關而與其出現頻率無關，后者則正好相反。這兩類壓縮方法算法思想各有所長，相互補充。許多壓縮軟件結合了這兩類算法。例如WINRAR就采用了字典編碼和哈夫曼編碼算法。這幾種數據無損壓縮算法應用廣泛，設計人員可以根據具體應用中的數據流特點來改進算法從而開發適用的軟硬件壓縮器。
評論