醫(yī)軟11大三第一學(xué)期第一章參考格式

1、實(shí)踐與經(jīng)驗(yàn)樹的實(shí)現(xiàn)及其在文件壓縮中的應(yīng)用姜龍 2丁光輝 21，2（1. 西南科技大學(xué)計(jì)算機(jī)學(xué)院，綿陽 621010； 2. 西南科技大學(xué)，綿陽 621010）要： 在信息快速傳輸和的過程中，數(shù)據(jù)壓縮有著非常重要的作用。 介紹了基于樹摘的文本壓縮和解壓縮的原理與方法，現(xiàn)過程。編碼； 文本壓縮； 壓縮算法并給出了 Huffman 壓縮與解壓程序算法的實(shí)：引 言在數(shù)據(jù)結(jié)構(gòu)實(shí)踐課程中，通常會(huì)遇到讓學(xué)生利用編碼進(jìn)行文本壓縮和解壓縮這樣的課題。由于個(gè)結(jié)構(gòu)體 Infchar ch；ratio；，取 Inf 中的頻率信息0ratio 后，再去查看字符 ch 是哪一個(gè)。 這樣做的好處是節(jié)約了內(nèi)存，且在后面的壓縮

2、中，它也減小了輸入文件的大小。因?yàn)槿我馕募?shí)際都是二進(jìn)制編碼的，所以對(duì)選定的任意文件以二進(jìn)制方式讀入，一次讀入一定的長(zhǎng)度，例如 4096 bytes，然后對(duì)每一字節(jié)進(jìn)行統(tǒng)計(jì)，如此循換，統(tǒng)計(jì)出文件中各個(gè)字符的頻率，以這些頻率作上只是給出了樹的定義和編碼， 因此，很多學(xué)生在完成這個(gè)課題的時(shí)候感覺無從下手。本文將給出利用樹進(jìn)行文本壓縮和解壓縮的具體實(shí)現(xiàn)過程，以供參考。構(gòu)造要利用樹編碼對(duì)文本文件進(jìn)行壓縮，首先必1為權(quán)值，構(gòu)造樹。樹結(jié)構(gòu)采構(gòu)造1.2樹的親孩子表示法，即利樹需要的空間為的葉子結(jié)點(diǎn)個(gè)須知道其字符相應(yīng)的編碼。為了得到文本中字用結(jié)構(gòu)體數(shù)組來實(shí)現(xiàn)。 一顆2LeafNode-1，其中 LeafNod

3、e 是符出現(xiàn)的頻率， 一般的做法是掃描整個(gè)文本進(jìn)行統(tǒng)計(jì)，編寫程序統(tǒng)計(jì)文本中各個(gè)字符出現(xiàn)的頻率。由于數(shù)。給先初始化樹，即將上述統(tǒng)計(jì)的字符信息賦一個(gè)字符的范圍在0-255之間，即共有 256 個(gè)狀態(tài)，所以直接向系統(tǒng)靜態(tài)的申請(qǐng)一個(gè)長(zhǎng)度為 256 的整數(shù)數(shù)組，用于存放相應(yīng)的頻率。得到頻率后，進(jìn)行編碼，然后將數(shù)據(jù)輸出到文件保存。樹的葉子結(jié)點(diǎn)，然后循環(huán)提取樹中權(quán)值最小的兩個(gè)根結(jié)點(diǎn)，將它們合并起來，組成一個(gè)新的根結(jié)點(diǎn)， 直到最后止。樹只剩下一個(gè)根結(jié)點(diǎn)為統(tǒng)計(jì)字符信息首先定義一個(gè)存放字符頻率信息的整數(shù)數(shù)組 Ar ray。 本文采用了一種默認(rèn)方案， 即數(shù)組中第 N 個(gè)數(shù)據(jù)所對(duì)應(yīng)的就正好是 ASCII 編碼為 N

4、的字符頻率。如表 1 所示。表 1 字符頻率表1.1構(gòu)建樹時(shí)， 直接調(diào)用堆進(jìn)行數(shù)據(jù)篩選，首先查看類 HeapNode，它是一個(gè)堆結(jié)點(diǎn)類。 在類中，定義了 3 個(gè)元素，sum weight（總權(quán)值）、sum leaf(此結(jié)點(diǎn)現(xiàn)代計(jì)算機(jī)（總第二九五期）的葉子結(jié)點(diǎn)的總數(shù))、本結(jié)點(diǎn)在樹ition（中的具置）。定義了 3 個(gè)重載函數(shù)，即按照多關(guān)鍵字規(guī)則，給結(jié)點(diǎn)一個(gè)大小關(guān)系，使得后面的程序可以直接對(duì)此類進(jìn)行比較大小。獲得編碼1.3當(dāng)使用到 ArrayN這個(gè)數(shù)組時(shí)，就知道它一定是ASCII 編碼為 N 這個(gè)字符的頻率，而無需再去定義一定義一個(gè) HaffCodes 類數(shù)組并對(duì)其進(jìn)行初始化。收稿日期：2008作

5、者簡(jiǎn)介：07 03 修稿日期：2008 10 30（1977 ），綿陽人，講師，研究方向?yàn)閳D形圖像處理技術(shù)、算法分析趽趬M O D E R N C OM P U T E R 200811 實(shí)踐與經(jīng)驗(yàn)要處理的關(guān)鍵問題是應(yīng)該給字符編碼一個(gè)多長(zhǎng)的數(shù)組， 因?yàn)轭A(yù)先不知道字符的最長(zhǎng)編碼應(yīng)該是多少，如果只是簡(jiǎn)單的選擇 256 個(gè)，太浪費(fèi)空間，所以最好的/ 將葉子結(jié)點(diǎn)的權(quán)值存入壓縮文件for (x=0; xm iNumOfNode; x+)itoHaffmanTreex.weight, pChar, 10); /將權(quán)值轉(zhuǎn)化為 char 型方法是實(shí)時(shí)計(jì)算樹的深度，以深度為字符的最長(zhǎng)編碼長(zhǎng)度。 得到存放編碼空間

6、后，需要對(duì)其每個(gè)位z += ( ) strlehar) + 1;置填充字符/0。規(guī)定在樹中，左分支為 0，右for (w = 0; yz 1; y+)Stringy = pCharw+;Stringz 1 = ; /每個(gè)數(shù)據(jù)用空格隔開y = z;分支為 1，從葉子結(jié)點(diǎn)出發(fā)，到根結(jié)點(diǎn)為止，即到相應(yīng)字符的編碼。壓縮文件計(jì)算出每個(gè)字符的2編碼后，即可對(duì)應(yīng)文本文件進(jìn)行編碼，這里就不再詳細(xì)敘述。上述方法中，每個(gè)“0”或“1”實(shí)際上占用了一個(gè)字節(jié)的空間，只起到示意或模擬的作用，如果不進(jìn)行處理，利用上述方法對(duì)文本文件進(jìn)行壓縮，壓縮后文件反而更大，根本沒有起到真正的壓縮作用。下面介紹如何把編碼轉(zhuǎn)為真正的二進(jìn)制

7、，進(jìn)行真正的文本壓縮。先從文件中一次讀入一定長(zhǎng)度如 4096 bytes，然后對(duì)每一字符逐一處理。 讀到一個(gè)字符，則找出它的編碼，將字符編碼不夠 8 bit 的，讀入下一個(gè)字符，找其編碼，取其適當(dāng)?shù)奈谎a(bǔ)齊前面不夠 8 bit 的編碼，然后轉(zhuǎn)換為對(duì)應(yīng) ASCII 碼字符， 然后寫入這個(gè)字符，超過 8 bit 就分開，寫入后繼續(xù)處理后面的字符。 舉例如下：已知：a: 1010 b: 00 c: 10000 d: 1001 e: 11 f:10001 g: 01 h: 1001如果文件中的一段是 “acdef”， 則處理如表 2 所示。outfile.write(String, ( ) strlen

8、(String); /將權(quán)值寫入 index;char bufferBUFFERLENGTH; string compleCode = ;string binaryStrCode = ; /二進(jìn)制代碼value;/計(jì)算 8bits 的 char 值 ( 與 unsigned char區(qū)分)char ch; doinfile.read(buffer, BUFFERLENGTH); /以 二 進(jìn) 制 形 式 讀入 BUFFERLENGTH 個(gè)字符/將上次循環(huán)的補(bǔ)碼賦binaryStrCode = compleCode;給 binaryStrCodecompleCode = ;for (i=0; i

9、infile.gcount(); i+)表 2編碼處理/buffer 數(shù)組不是 unsigned charif (bufferi 0)類型index = 127bufferi;elseindex = bufferi; j = MAXCODECODE 22;如上述， 這樣就把編碼按真正的二進(jìn)制編碼處理，把 5 個(gè)字符壓為 3 個(gè)字符，這里還應(yīng)該注意，當(dāng)讀文件到達(dá)文件尾時(shí)， 一般不能剛好湊夠 8 bit 所以需m iHaffmanCode index MAX現(xiàn)代計(jì)算機(jī)（總第二九五期）for (; jMAXCODE 2; j+)if (m iHaffmanCodeindexj = 0) binary

10、S trCode.append(0);else binaryStrCode.append(1);strLength = ( ) (binaryStrCength() / 8);/有多少個(gè)整 8要補(bǔ)上“0”直到夠 8 bit。 而補(bǔ)上的 0 的個(gè)數(shù)為補(bǔ)位數(shù)。 壓縮文件開頭存放補(bǔ)碼的信息，接著存放權(quán)值以及空格字符的長(zhǎng)度，長(zhǎng)度后存一個(gè)空格，其后存每個(gè)葉子結(jié)點(diǎn)的權(quán)值本壓縮的代碼段。void權(quán)值之間用空格隔開下面是文，。prepressText(CString pCompressTextName)compleSize = ( ) (binaryStrC/本次循環(huán)的補(bǔ)碼ength() % 8);貋貖財(cái)MO

11、 DE RN C OMP U T ER 200811 實(shí)踐與經(jīng)驗(yàn)函數(shù)轉(zhuǎn)換為 8 個(gè)字符（用一個(gè)數(shù)組一個(gè)“0”或一個(gè)“1”），然后按，其元素只是樹從頂向下查找，for (k=0; k=k; l)if (binaryStrCode.at(l) = 1)value +=實(shí)驗(yàn)結(jié)果與分析圖 1 是利用本文方法對(duì)文本文件進(jìn)行壓縮的例子，圖 2 是對(duì)壓縮后的文件進(jìn)行解壓。 實(shí)驗(yàn)結(jié)果表明，本文方法能夠正確處理 doc 文件、tex 文件、exe 文件等，并且有較高的壓縮率，其中對(duì) doc 文件的壓縮率在 70%左右。4( )(2, k+7 l);/將其 if (value 127) ch =放入壓縮文本里面e

12、lse ch = value;127value;outfile.ph);/計(jì) 算 壓 縮 文m iCompressedTextSize+;件的大小/處理補(bǔ)碼size = 8 * strLength; if (size =0; n )if (compleCode.at(n) = 1) value += ()(2, 7 n); if (value 127) ch = 127value;elsech = value;圖 2解壓結(jié)果現(xiàn)代計(jì)算機(jī)（總第二九五期）結(jié) 語5編碼是數(shù)據(jù)壓縮領(lǐng)域中最著名的編碼方式之一，它通過對(duì)象頻率出現(xiàn)的不等性，構(gòu)造最優(yōu)編解壓文件有了上述壓縮文件3信息的基礎(chǔ)，自然能方便碼，達(dá)到減

13、小文件大小的目的。目前廣泛應(yīng)用的許多地解壓出原來的文件。讀出結(jié)點(diǎn)數(shù)就知道樹存其他高效的數(shù)據(jù)壓縮算法（例如算術(shù)編碼、可編碼等）也是在編碼的基礎(chǔ)上發(fā)展起來的，所以， 對(duì)于深入理解數(shù)據(jù)結(jié)構(gòu)、程入部分的總長(zhǎng)，方便讀出樹樹（子結(jié)點(diǎn)值和權(quán)研究編碼的值），就能由這些信息重新構(gòu)造完整的樹，和各序設(shè)計(jì)等學(xué)科中的相關(guān)課題是十分有益的。個(gè)結(jié)點(diǎn)的編碼。解壓時(shí)，一個(gè)字節(jié)，用一個(gè)貋貖貢MODE RN C OM PUTE R 200811實(shí)踐與經(jīng)驗(yàn)參考文獻(xiàn):技大學(xué)3, 2003. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)案例精編M. 數(shù)據(jù)結(jié)構(gòu)M.1, 2003M. 陜西:西安電子科:2高一凡. 數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及, 2007Implement o

14、f Huffman Tree and Its Application in FileCompresCAI Mao rong1 ,JIANG Long2, DING Guang hui2 ,Wen hui2（1. Computer Academy，Southwest University of Science and Technology, Mian2. Software Engineering，Southwest University of Science and Technology, Mian621010；621010）Abstract： It is very important to c

15、ompress datahe ratransmisandand storage of information.roduthe principle and method aboomprespresof text based onHuffman tree and presents the implement course of the core algorithm of a Huffman compresandpresprogram.Keywords： Huffman Coding； Text Compres； CompresAlgorithm!（上接第 82 頁）參考文獻(xiàn)Michelineber

16、 著. 數(shù)據(jù)挖掘概念與技術(shù)機(jī)工程與應(yīng)用,2004,22:177, 劉衛(wèi)國. 數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則挖掘算法比較研1Jiawei Han4譯.,，2005：機(jī)械工業(yè)究J. 計(jì)算機(jī)工程與設(shè)計(jì),2005,5:1265M.,，20052毛國君,華大學(xué). 數(shù)據(jù)挖掘原理與算法M.：清. 關(guān)聯(lián)規(guī)則挖掘綜述J. 計(jì)算機(jī)5,工程,2001,5:31, 尹關(guān)聯(lián)規(guī)則的改進(jìn)算法J. 計(jì)算3,.The Improvement of Apriori Algorithm and ItsApplicationerce現(xiàn)代計(jì)算機(jī)（總第二九五期）XU Xue fei，QING Peng tao（Computer Center of Nanchang University, Nanchang 330031）Abstract： Proes a methodt gives the weight on the element of itemset, during compute the support of the itemset (commodities) and at the same t