資源描述：
《比較應用stl實現(xiàn)huffman編碼的兩種方法》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、第18卷第2期jt京電子科技學院學報2010年6月Vo1．18No．2JournalofBeijingElrctroninScienceandTechnologyInstituteJun．2010比較應用STL實現(xiàn)Huffman編碼的兩種方法孫宏章小莉趙越(1．公安部消防產品合格評定中心，北京：100039；2．北京電子科技學院計算機科學與技術系，北京：100070)摘要：Hufman編碼作為信息不丟失壓縮方法在現(xiàn)代通信、多媒體技術等領域廣泛運用。研究用C++的標準模板庫STL實現(xiàn)Hufman編碼算法具有現(xiàn)實意義。本文討論用STL資源的vector容器和heap技術
2、實現(xiàn)Hufman編碼算法編程，并比較兩種實現(xiàn)方法的性能，指出使用STL資源時需要注意的事項。關鍵詞：Huffman編碼；標準模板庫STL；vector；heap；復雜度；中圖分類號：TN911．21文獻標識碼：A文章編號：1672—464X(2010)06—0020—06ComparingTwoWaysaboutProgrammingofHufmanCodingwithSTLSUNHong，ZHANGXiao—Il，ZHAOYue(1．ChinaCertificationCenterforFireProductsMinistryofPublicSecurity，Be
3、ijing100039，China；2．BeijingElectronicScienceandTechnologyInstitute，Beijing100070，China)Abstract：HufmanCodingisusedwidelyincommunicationandmultimediatechnology．DiscussHuffmanCodingarithmeticprogrammingisnecessarywithSTL．ThispaperimplementsHufmanCodingprogramwithvectororheaptechnologyofS
4、TL，andcomparestheirperformances，indicatessomenoteswhileusingSTLresource．Keywords：HufmanCoding；StandardTemplateLibrary；vector；heap；complication；刖罱現(xiàn)代人的生活離不開通信，多媒體技術正在改變著人們的生活品質，但是信息通信的帶寬非常有限，數據壓縮是保證信息快速傳送的重要技術。Huffman編碼作為一種不丟失信息的壓縮編碼被廣為運用。c++標準模板庫STL支持代碼復用，支持算法快速實現(xiàn)。本文用STL中的vector容器和heap算
5、法完成Huffman編碼算法編程，比較兩種資源運用效果之不同，提出選用STL資源時需要注意的事項。一Huffman編碼算法思想]、Huffman編碼是一種前綴碼，它是Huffman樹上葉子結點的編碼。Huffman樹是：當信息中有n個數據符號，每種符號出現(xiàn)的概率值為wi，編碼長度為u，當把Wi作為二叉樹上葉子結點的權值(weight)，L／作為從二叉樹的樹根到葉子結點之間的路經長度，則n個結點的WiL／之和恰好為二叉樹上最短帶權路經的長度。Hufman樹又稱為最優(yōu)二叉樹。于是，當已知若干權值，構造一棵Hufman樹的步驟是：收稿日期：2010—05—02第18卷孫宏
6、章小莉趙越比較應用STL實現(xiàn)Huffman編碼的兩種方法‘21·(1)根據給定的I1個權值{w1，w2，?，wn}構成n棵-y．．樹集合F={T1，，?，Tn}，其中每棵二叉樹rfi中只有一個權值為wi的根結點，其左右子樹均為空。(2)在F中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點權值為其左、右子樹上根結點的權值之和。(3)在F中刪除兩棵已經用過的二叉樹，同時將新得到的二叉樹加入F中。(4)重復步驟(2)～(3)，直到F只含一棵樹為止。完成Huffman編碼的方法是：從根結點開始設二叉樹的左子樹編碼為0，'右子樹編碼為1依次
7、編碼至葉結點。這個從根到每個葉結點依次寫出的葉結點編碼，就是葉結點擁有的權值對應的數據符號Huffman編碼。用最優(yōu)二叉樹構造的Huffman編碼雖然可能不唯一，但是利用Hufman編碼編出的信息能在不丟失信息量的情況下保證編碼長度最短。二、STL資源c++語言支持庫中的標準模板庫STL使用模板技術實現(xiàn)常用的數據結構和算法，大大改善了程序設計的環(huán)境。模板技術實質上是利用泛化技術把參數一般化，使得數據結構和算法的實現(xiàn)函數或類代碼得于復用。另外一些經典算法在STL中也已經實現(xiàn)。1．vector容器vector是線性表在STL中的順序實現(xiàn)，它是一個容器，經迭代器ite
