LHARC中的動(dòng)態(tài)限長(zhǎng)編碼壓縮算法

湖北自考網(wǎng) 來(lái)源：時(shí)間：2005-11-09 00:00:00

摘要該文對(duì)DOS下常用的數(shù)據(jù)壓縮軟件LHARC的算法進(jìn)行了分析。該算法中采用了一種動(dòng)態(tài)限長(zhǎng)變化的不等長(zhǎng)編碼方法,使最短碼2位,而最長(zhǎng)碼不超過8位,達(dá)到了最佳壓縮效果。
一、前言
LHARC是DOS下的數(shù)據(jù)壓縮軟件之一,與同類軟件如ARJ、PKZIP、PKARC等相比,具有如下幾個(gè)特點(diǎn)。
1.壓縮比高
LHARC采用先進(jìn)的字符串自適應(yīng)壓縮與單個(gè)字符的限長(zhǎng)變化編碼壓縮相結(jié)合的方法,對(duì)文件進(jìn)行雙重壓縮,盡可能地減少了冗余,對(duì)各類文件的壓縮效果都很好。
2.保密性好
除應(yīng)具有保存文件、節(jié)約存儲(chǔ)空間的功能外,提高數(shù)據(jù)的保密性也是壓縮軟件的一個(gè)重要功能。LHARC由于采取了與眾不同的動(dòng)態(tài)限長(zhǎng)編碼壓縮技術(shù),使字符與其壓縮代碼之間無(wú)固定的對(duì)應(yīng)關(guān)系,壓縮后的數(shù)據(jù)更具保密性。
3.軟件短小精悍
LHARC整個(gè)軟件集壓縮、還原于一身,只有30余K,而其它同類軟件均有100余K。
LHARC的基本壓縮原理是,將待壓縮文件看作是字符流(字節(jié)流),將其中的冗余信息分成兩類:
(1) 同一字符的離散出現(xiàn)
如 abcda……
這里,字符a出現(xiàn)了兩次。
2.字符串的重復(fù)出現(xiàn)
如 abcdabcd……或abcd…abcd……
這里,字符串a(chǎn)bcd出現(xiàn)了兩次。值得說明的是,這里串的概念是LZW方法意義下的,即將字符流中每一字符均看作是一個(gè)串的起始字符。
壓縮時(shí),首先對(duì)字符流中的字符串進(jìn)行識(shí)別,將其中的重復(fù)串用壓縮格式記載,然后再將處理后的數(shù)據(jù)用不等長(zhǎng)編碼進(jìn)行代碼變換及壓縮。下面僅就其中的動(dòng)態(tài)限長(zhǎng)變化編碼方法進(jìn)行介紹。
二、動(dòng)態(tài)限長(zhǎng)編碼方法
1.基本原理
經(jīng)重復(fù)串壓縮后的數(shù)據(jù)中,重復(fù)串已大大減少,而同一字符的分布式冗余問題則比較突出。由于256個(gè)字符的使用概率一般不同,往往相差懸殊,若采用不等長(zhǎng)編碼,將高頻字符用較短代碼表示,低頻字符用較長(zhǎng)碼表示,則提高了整體的壓縮比。
Haffman編碼是最佳不等長(zhǎng)編碼,它根據(jù)文件中各字符的統(tǒng)計(jì)概率來(lái)分配代碼長(zhǎng)度。如設(shè)文件中不同字符數(shù)為n,第i個(gè)字符的概率為Pi,代碼長(zhǎng)度為li,則當(dāng)概率滿足P1≥P2≥…≥Pn時(shí),Haffman編碼的碼長(zhǎng)滿足l1≤l2≤…≤ln,此時(shí),代碼平均長(zhǎng)度的數(shù)學(xué)期望=∑ni=1Pi·li達(dá)到最小。
在一般的數(shù)據(jù)壓縮過程中,Haffman編碼的算法實(shí)現(xiàn)為:先統(tǒng)計(jì)出待壓文件中各字符的出現(xiàn)概率,據(jù)此動(dòng)態(tài)建立一棵Haffman樹,并以二分樹的序列形式存入壓縮數(shù)據(jù)文件首部以用于還原過程。在壓縮過程中,由Haffman樹實(shí)現(xiàn)字符的ASCII碼(等長(zhǎng)碼)與其壓縮代碼(Haffman不等長(zhǎng)碼)的轉(zhuǎn)換。這種處理方法需對(duì)待壓縮文件進(jìn)行兩遍掃描,且Haffman樹須保存于壓縮數(shù)據(jù)文件中而占用額外的存儲(chǔ)空間。
在LHARC的算法中,對(duì)Haffman編碼的實(shí)現(xiàn)采用了新的方法。其基本原理是:在壓縮前動(dòng)態(tài)建立一棵初始譯碼樹,在壓縮過程中不斷調(diào)整譯碼樹的結(jié)構(gòu),使各字符的壓縮代碼長(zhǎng)度隨字符出現(xiàn)的次數(shù)增加而逐步縮減。最短碼的長(zhǎng)度可達(dá)到2位,而最長(zhǎng)碼不超過8位(二進(jìn)制),從而獲得很高的壓縮比。該算法的其它優(yōu)點(diǎn)還有:(1)無(wú)須事先統(tǒng)計(jì)各字符的出現(xiàn)概率,一次掃描即可;(2)譯碼樹須保存在壓縮數(shù)據(jù)文件中,還原時(shí)同樣生成即可;(3)字符與其壓縮代碼之間無(wú)固定對(duì)應(yīng)關(guān)系,使壓縮后的數(shù)據(jù)具有一定的保密性。
2.壓縮的實(shí)現(xiàn)及碼樹的調(diào)整
壓縮前動(dòng)態(tài)建立一棵初始譯碼樹,每個(gè)葉結(jié)點(diǎn)對(duì)應(yīng)一個(gè)字符。由于壓縮前可以認(rèn)為各字符的出現(xiàn)概率相等,故初始碼樹應(yīng)為一有256片葉子的平衡二叉樹,如圖1所示。顯然每個(gè)字符的初始代碼長(zhǎng)度均為8位。
@@09A04900.GIF;圖1 初始譯碼樹@@
當(dāng)壓縮開始,第一個(gè)字符出現(xiàn)時(shí),將其對(duì)應(yīng)第一個(gè)葉結(jié)點(diǎn),沿碼樹向上的通路至根,所經(jīng)各邊標(biāo)號(hào)(左0右1)組成的0、1序列構(gòu)成該字符的初始代碼。輸出代碼后,調(diào)整碼樹,將該字符對(duì)應(yīng)的葉結(jié)點(diǎn)之值與上一層某一結(jié)點(diǎn)之值互換,當(dāng)該字符再次出現(xiàn)時(shí),其路徑長(zhǎng)度就會(huì)減少一結(jié)點(diǎn)。如字符原對(duì)應(yīng)8位長(zhǎng)代碼,則再次出現(xiàn)后就對(duì)應(yīng)7位代碼了。如該字符繼續(xù)不斷地出現(xiàn),其所對(duì)應(yīng)的葉結(jié)點(diǎn)將逐級(jí)上升到第6層、第5層、甚至第2層,而此字符的碼長(zhǎng)隨之減至6位、5位、直至2位。
代碼長(zhǎng)度縮減的規(guī)律是:設(shè)n為字符當(dāng)前所在層數(shù),則當(dāng)字符的重復(fù)出現(xiàn)次數(shù)為28-n時(shí),代碼長(zhǎng)度減少1位。
代碼長(zhǎng)度的縮減會(huì)帶來(lái)一個(gè)十分關(guān)鍵的問題:當(dāng)碼樹各結(jié)點(diǎn)值是靜態(tài)的時(shí)候,一字符對(duì)應(yīng)了某一高層結(jié)點(diǎn)后,此結(jié)點(diǎn)的所有下層枝葉將不能再對(duì)應(yīng)其它字符,否則

一些代碼將是另一些代碼的前綴,這將使還原過程無(wú)法進(jìn)行。因此代碼縮減將使編碼路徑數(shù)減少,一些后繼字符將無(wú)法由碼樹編碼。為此,該算法采取的策略是:按字符出現(xiàn)的次序?qū)⑺鼈兗信帕性诖a樹的一側(cè)葉子上,通過移動(dòng)和交換分枝點(diǎn)之值的方法,使各層結(jié)點(diǎn)之值重新組合,從而使被占用結(jié)點(diǎn)的下屬枝葉可“稼接”到未用的結(jié)點(diǎn)上。因此,當(dāng)高層結(jié)點(diǎn)被占用后,其下屬結(jié)點(diǎn)仍可使用,不會(huì)減少編碼路徑數(shù)。具體來(lái)說,當(dāng)一后繼字符出現(xiàn)并且其對(duì)應(yīng)葉子的父結(jié)點(diǎn)已被占用,它將改變?cè)械木幋a路徑,通過搜索找出一個(gè)未用的上層結(jié)點(diǎn)并由此得到其代碼。
同樣,當(dāng)一字符須上升一層時(shí),并不是升到其父結(jié)點(diǎn)中,而是升到上層中一個(gè)未用過的結(jié)點(diǎn)之中。當(dāng)該字符再度出現(xiàn)時(shí),它將沿新路徑得到其代碼,此代碼的長(zhǎng)度不僅為原代碼長(zhǎng)度減1,而且此代碼的各個(gè)位也與原代碼不同。下面以一具體例子加以說明。
設(shè)字符串為ababcabdabc……各字符的編碼路徑如圖2所示。其中的Xi表示X的第i次出現(xiàn)。
@@09A04901.GIF;圖2 字符編碼路徑示意圖@@
由此可看出,由該算法給出的編碼方法是逐步達(dá)到最佳碼長(zhǎng)的。一字符的壓縮代碼不僅與字符出現(xiàn)的次數(shù)有關(guān)(長(zhǎng)度不同),而且與字符在文件中的位置有關(guān)(編碼路徑不同)。
LHARC建立了兩個(gè)表專門用來(lái)記錄碼樹的占用情況及各字符出現(xiàn)的次數(shù),以便確定對(duì)碼樹的各種調(diào)整。當(dāng)壓縮后的數(shù)據(jù)達(dá)到32K時(shí),將對(duì)表及碼樹進(jìn)行“重組”,刪除表中部分累積的數(shù)據(jù)后再繼續(xù)進(jìn)行壓縮,以后將每隔16K“重組”一次。

結(jié)束

本文標(biāo)簽

特別聲明：1.凡本網(wǎng)注明稿件來(lái)源為“湖北自考網(wǎng)”的，轉(zhuǎn)載必須注明“稿件來(lái)源：湖北自考網(wǎng)（m.heywebguys.com）”,違者將依法追究責(zé)任；
2.部分稿件來(lái)源于網(wǎng)絡(luò)，如有不實(shí)或侵權(quán)，請(qǐng)聯(lián)系我們溝通解決。最新官方信息請(qǐng)以湖北省教育考試院及各教育官網(wǎng)為準(zhǔn)！

上一篇：自考“中國(guó)近現(xiàn)代史綱要”復(fù)習(xí)資料第一章下一篇：可移植的256色圖形用戶界面的設(shè)計(jì)

"LHARC中的動(dòng)態(tài)限長(zhǎng)編碼壓縮算法" 相關(guān)文章推薦

限時(shí)，免費(fèi)獲取學(xué)歷提升方案

已幫助10w萬(wàn)+意向?qū)W歷提升用戶成功上岸

武漢自考工具箱

自考流程報(bào)名時(shí)間考試時(shí)間考場(chǎng)查詢成績(jī)查詢成績(jī)復(fù)查自考違規(guī) 免考辦理轉(zhuǎn)考辦理實(shí)踐考核畢業(yè)申請(qǐng) 學(xué)位申請(qǐng) 學(xué)位外語(yǔ) 自考助學(xué) 成人高考

推薦信息

2024自考助學(xué)班

武漢自考專題推薦

自考視頻課程自考模擬真題

毛澤東思想概論
培訓(xùn)優(yōu)勢(shì)：課時(shí)考點(diǎn)精講+刷題+沖刺，熟練應(yīng)對(duì)考試題型。全程督促學(xué)習(xí)，安排好學(xué)習(xí)計(jì)劃。毛澤東思想概論...自考培訓(xùn)
英語(yǔ)二
本課程既是一門語(yǔ)言實(shí)踐課程,也是拓寬知識(shí)、了解世界文化的重要素質(zhì)課程,它以培養(yǎng)學(xué)習(xí)者的綜合語(yǔ)言應(yīng)用能力為目標(biāo)，使他們?cè)趯W(xué)習(xí)、工作和社會(huì)交往中能夠使用英語(yǔ)進(jìn)行有效的交流。英語(yǔ)二...自考培訓(xùn)
馬克思主義基本原理概論
本書包括兩個(gè)部分：自學(xué)考試大綱和基本原理。主要內(nèi)容有，馬克思主義是關(guān)于工人階級(jí)和人類解放的科學(xué)，物質(zhì)世界及其發(fā)展規(guī)律，認(rèn)識(shí)的本質(zhì)及其規(guī)律，人類社會(huì)及其發(fā)展規(guī)律，資本主義的形成及其發(fā)展，資本主義發(fā)展的歷史進(jìn)程，社會(huì)主義社會(huì)及其進(jìn)程，共產(chǎn)主義社會(huì)及其進(jìn)程等。馬克思主義基本原理概論...自考培訓(xùn)
思想道德修養(yǎng)與法律基礎(chǔ)
《思想道德修養(yǎng)與法律基礎(chǔ)》課具有鮮明的政治性、思想性、理論性、針對(duì)性、科學(xué)性、知識(shí)性以及實(shí)踐性和修養(yǎng)性。它包羅政治、思想、道德、心理本質(zhì)、學(xué)習(xí)成才和法律本質(zhì)等內(nèi)容，指導(dǎo)和回答大學(xué)生在人生、抱負(fù)、信念等方面遍及關(guān)心和迫切需要解決的問題。思想道德修養(yǎng)與法律基礎(chǔ)...自考培訓(xùn)
中國(guó)近代史綱要
“中國(guó)近現(xiàn)代史綱要”全國(guó)高等教育自學(xué)考試指定教材，依據(jù)中央審定的普通高等學(xué)?！爸袊?guó)近現(xiàn)代史綱要”編寫大綱以及馬克思主義理論研究和建設(shè)工程重點(diǎn)教材《中國(guó)近現(xiàn)代史綱要》，結(jié)合自學(xué)考試的特點(diǎn)設(shè)計(jì)了十章，集中講述1840年鴉片戰(zhàn)爭(zhēng)爆發(fā)一直到2007年中國(guó)共產(chǎn)黨第十七次全國(guó)代表大會(huì)召開的160多年的中國(guó)近現(xiàn)代歷史。中國(guó)近代史綱要...自考培訓(xùn)