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