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

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

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

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

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

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

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

7、，進(jìn)行真正的文本壓縮。先從文件中一次讀入一定長度如 4096 bytes，然后對每一字符逐一處理。 讀到一個字符，則找出它的編碼，將字符編碼不夠 8 bit 的，讀入下一個字符，找其編碼，取其適當(dāng)?shù)奈谎a齊前面不夠 8 bit 的編碼，然后轉(zhuǎn)換為對應(yīng) ASCII 碼字符， 然后寫入這個字符，超過 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;/計算 8bits 的 char 值 ( 與 unsigned char區(qū)分)char ch; doinfile.read(buffer, BUFFERLENGTH); /以 二 進(jìn) 制 形 式 讀入 BUFFERLENGTH 個字符/將上次循環(huán)的補碼賦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 個字符壓為 3 個字符，這里還應(yīng)該注意，當(dāng)讀文件到達(dá)文件尾時， 一般不能剛好湊夠 8 bit 所以需m iHaffmanCode index MAX現(xiàn)代計算機(jī)（總第二九五期）for (; jMAXCODE 2; j+)if (m iHaffmanCodeindexj = 0) binary

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

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

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

13、小文件大小的目的。目前廣泛應(yīng)用的許多地解壓出原來的文件。讀出結(jié)點數(shù)就知道樹存其他高效的數(shù)據(jù)壓縮算法（例如算術(shù)編碼、可編碼等）也是在編碼的基礎(chǔ)上發(fā)展起來的，所以， 對于深入理解數(shù)據(jù)結(jié)構(gòu)、程入部分的總長，方便讀出樹樹（子結(jié)點值和權(quán)研究編碼的值），就能由這些信息重新構(gòu)造完整的樹，和各序設(shè)計等學(xué)科中的相關(guān)課題是十分有益的。個結(jié)點的編碼。解壓時，一個字節(jié)，用一個貋貖貢MODE RN C OM PUTE R 200811實踐與經(jīng)驗參考文獻(xiàn):技大學(xué)3, 2003. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計案例精編M. 數(shù)據(jù)結(jié)構(gòu)M.1, 2003M. 陜西:西安電子科:2高一凡. 數(shù)據(jù)結(jié)構(gòu)算法實現(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ī)工程與設(shè)計,2005,5:1265M.,，20052毛國君,華大學(xué). 數(shù)據(jù)挖掘原理與算法M.：清. 關(guān)聯(lián)規(guī)則挖掘綜述J. 計算機(jī)5,工程,2001,5:31, 尹關(guān)聯(lián)規(guī)則的改進(jìn)算法J. 計算3,.The Improvement of Apriori Algorithm and ItsApplicationerce現(xiàn)代計算機(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