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