【文章內(nèi)容簡(jiǎn)介】 哈夫曼編碼必須對(duì)文本進(jìn)行兩遍掃描的缺點(diǎn)，壓縮效率大幅度提高。尤其對(duì)一些龐大的原文件而言，壓縮和解壓效率可以提高一倍至三倍。下面對(duì)這種高效的算法作詳細(xì)的分析，為了便于說(shuō)明首先進(jìn)行一些定義:n : 字母表的長(zhǎng)度；aj : 字母表中第j個(gè)字符；t : 已經(jīng)處理的原始數(shù)據(jù)中的字符的總個(gè)數(shù)；k : 已經(jīng)處理的數(shù)據(jù)中各不相同字符的個(gè)數(shù)；顯然， j ≥1，k ≤ n 。在壓縮開始之前，需要引進(jìn)一個(gè)空葉結(jié)點(diǎn)，它的權(quán)重始終為0。在以后的壓縮和解壓縮過(guò)程中，如果kn，則用它來(lái)表示nk個(gè)字母表中還未出現(xiàn)的字符。初始化的哈夫曼樹中只有一個(gè)根結(jié)點(diǎn)和一個(gè)空葉結(jié)點(diǎn)。壓縮算法執(zhí)行的過(guò)程是這樣的讀進(jìn)一個(gè)字符后，將該字符加到根結(jié)點(diǎn)的右分枝上，而空葉結(jié)點(diǎn)仍然保留在左分枝上，然后將該字符以ASCII碼方式輸出。解壓子程序?qū)蚵鼧渥鐾瑯拥恼{(diào)整。以后每讀進(jìn)一個(gè)字符ait，壓縮子程序都執(zhí)行以下的步驟:首先檢查ait是否出現(xiàn)在編碼樹中，如果是，壓縮子程序就以與靜態(tài)哈夫曼編碼中相同的方式對(duì)ait進(jìn)行編碼；如果ait不在編碼樹中，壓縮子程序首先對(duì)空葉結(jié)點(diǎn)進(jìn)行編碼，然后將ait以ASCII碼方式輸出，最后在編碼樹中增加兩個(gè)結(jié)點(diǎn):在空葉結(jié)點(diǎn)的右分枝上加入一個(gè)新的結(jié)點(diǎn)，并將ait放在里面，然后在其左分枝上加入一個(gè)新的空葉結(jié)點(diǎn)。解壓子程序?qū)鈮嚎s樹也做同樣的調(diào)整，因?yàn)樗蛪嚎s子程序具有相同的哈夫曼樹。當(dāng)遍歷到空葉結(jié)點(diǎn)時(shí)，解壓子程序就從壓縮數(shù)據(jù)中取出一個(gè)ASCII字符，然后對(duì)解壓樹做與壓縮子程序相同的調(diào)整。每處理一個(gè)字符，壓縮和解壓程序都需要修改各自的哈夫曼樹，為了修改的方便，樹中每個(gè)結(jié)點(diǎn)都具有一個(gè)序號(hào)，它是根據(jù)結(jié)點(diǎn)的權(quán)重由大到小排列而確定的一個(gè)遞減序列。對(duì)于圖31中的例子，已經(jīng)處理了32個(gè)字符，即個(gè)字符，即:t=32，ait + 1=“b”，此時(shí)并不是簡(jiǎn)單地將葉結(jié)點(diǎn)ait + 1和它的父結(jié)點(diǎn)的權(quán)重加1，因?yàn)檫@樣做之后，該樹就不再是哈夫曼樹，且各個(gè)結(jié)點(diǎn)的序號(hào)也不再是按結(jié)點(diǎn)權(quán)重由大到小排列而確定的遞減序列，結(jié)點(diǎn)4和結(jié)點(diǎn)6的權(quán)重為6，而結(jié)點(diǎn)5的權(quán)重為5。1132102111 f98111075565653423 eb 2 a 1圖31 編碼示例132動(dòng)態(tài)哈夫曼編碼技術(shù)的關(guān)鍵就是如何將前t個(gè)字符的哈夫曼樹調(diào)整成一棵前t+1個(gè)字符的哈夫曼樹，為了解決上述問(wèn)題，可以分為兩步來(lái)執(zhí)行:第一步把前t個(gè)字符的哈夫曼樹轉(zhuǎn)換成它的另一種形式，在該樹中只需在第二步中簡(jiǎn)單地把由根到葉結(jié)點(diǎn)ait +1路徑上的所有結(jié)點(diǎn)權(quán)重加1，就可以變成前t+1個(gè)字符的哈夫曼樹。其過(guò)程就是以葉結(jié)點(diǎn)ait + 1為初始的當(dāng)前結(jié)點(diǎn)，重復(fù)地將當(dāng)前結(jié)點(diǎn)與具有相同權(quán)重的序號(hào)最大的結(jié)點(diǎn)進(jìn)行交換，并使得后者的父結(jié)點(diǎn)成為新的當(dāng)前結(jié)點(diǎn)，直到遇到根結(jié)點(diǎn)為止。以圖31為例，結(jié)點(diǎn)2無(wú)需進(jìn)行交換，所以結(jié)點(diǎn)4成為新的當(dāng)前結(jié)點(diǎn)，結(jié)點(diǎn)4與結(jié)點(diǎn)5交換后，結(jié)點(diǎn)8就成為當(dāng)前結(jié)點(diǎn)，最后結(jié)點(diǎn)8與結(jié)點(diǎn)9進(jìn)行交換，結(jié)點(diǎn)11成為當(dāng)前結(jié)點(diǎn)，循環(huán)結(jié)束。到此為止第一步已經(jīng)完成，其結(jié)果如圖32所示。11211191065111056f 8e73255d 4c 3b 2a 1圖32編碼示例2容易驗(yàn)證它也是前t個(gè)字符的一種哈夫曼樹形式，因?yàn)榻粨Q只是在相同權(quán)重的結(jié)點(diǎn)之間進(jìn)行。第二步通過(guò)將由根結(jié)點(diǎn)到葉結(jié)點(diǎn)ait + 1路徑上的所有結(jié)點(diǎn)權(quán)重加1，該樹就變成了前t+1個(gè)字符的哈夫曼樹。如圖33所示。1132109211256668711105524d 4c 3b 2a 1圖33 編碼示例3一個(gè)比較完整的動(dòng)態(tài)哈夫曼編碼實(shí)例如圖34所示。圖34 動(dòng)態(tài)哈夫曼編碼實(shí)例 自適應(yīng)哈弗曼編碼的應(yīng)用 電力系統(tǒng)通信隨著微型計(jì)算機(jī)與通信技術(shù)的發(fā)展與日益成熟，一大批新型的電力系統(tǒng)故障錄波裝置和SCADA系統(tǒng)源源不斷地被引入電力系統(tǒng)，由微波信道(或電力載波、公用電話線等信道)將大批量數(shù)據(jù)傳送到電網(wǎng)調(diào)度中心，是目前廣為采用的方法。波特率不可能太高，所需通信時(shí)間太長(zhǎng)的問(wèn)題已成為一大難題。解決這一難題的有效途徑是數(shù)據(jù)的壓縮與解壓技術(shù)，即將發(fā)送端待傳輸?shù)臄?shù)據(jù)進(jìn)行壓縮，而接收端將接收到的壓縮數(shù)據(jù)解壓以獲得原始數(shù)據(jù)。如傳輸電力系統(tǒng)某一波形數(shù)據(jù)文件的長(zhǎng)度為23376字節(jié)，若不采用壓縮而直接傳輸，所需時(shí)間為40min，若采用自適應(yīng)的哈夫曼數(shù)據(jù)壓縮與解壓技術(shù)壓縮后再傳輸，只需22min左右(與波形數(shù)據(jù)有關(guān))。 數(shù)據(jù)庫(kù)壓縮盡管計(jì)算機(jī)存儲(chǔ)器的價(jià)格有降低的趨勢(shì)，但在數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)中，數(shù)據(jù)存儲(chǔ)仍然占有相當(dāng)大的額外費(fèi)用。因此，采用自適應(yīng)哈夫曼編碼在數(shù)據(jù)庫(kù)系統(tǒng)中，對(duì)數(shù)據(jù)進(jìn)行壓縮是減少數(shù)據(jù)存儲(chǔ)費(fèi)用和提高性能的一個(gè)很有效的辦法。 數(shù)字圖像壓縮處理人們獲取的外部信息大部分是以圖像形式存在的。隨著信息技術(shù)的發(fā)展，大量的圖片、氣象云圖、遙感圖像等靜止圖像以及可視電話、廣播電視等活動(dòng)圖像也隨即產(chǎn)生。處于信息高速流通時(shí)代，不僅要大量存儲(chǔ)和傳輸圖像，而且要在保證質(zhì)量的前提下以較小空間存儲(chǔ)和較少比特率實(shí)時(shí)傳輸圖像，這就需要采用各種圖像壓縮技術(shù)。而才用自適應(yīng)哈夫曼編碼進(jìn)行數(shù)據(jù)壓縮就很好的完成了圖像壓縮處理的許多要求。 電子文件完整性與一致性隨著電子信息技術(shù)的發(fā)展，越來(lái)越多的電子文件形成于我們的日常辦公與檔案管理之中。無(wú)論是政府公務(wù)還是企業(yè)辦公，許多文件都是以電子文件的形式發(fā)布與保存。與紙制文件不同的是電子文件具有易改動(dòng)性，易復(fù)制性。通常為了保護(hù)電子文件的安全，我們可以采用安全認(rèn)證，防復(fù)制技術(shù)來(lái)組織文件的改動(dòng)和非法傳播，例如，數(shù)字版權(quán)管理DRM(Digital Rights Management)技術(shù)就是今年來(lái)發(fā)展起來(lái)的一種新的信息安全技術(shù)，通過(guò)數(shù)字產(chǎn)品版權(quán)管理和防復(fù)制技術(shù)實(shí)現(xiàn)對(duì)數(shù)字產(chǎn)品的保護(hù)。但是這些技術(shù)所帶來(lái)的問(wèn)題是對(duì)于支持公開性的文件在一定程度上限制了其共享性，對(duì)于電子政務(wù)所產(chǎn)生的電子文件來(lái)說(shuō)，其所涉及的安全問(wèn)題不是傳播性，防復(fù)制問(wèn)題，更大程度上是在傳播與使用過(guò)程中保證文檔的完整性與一致性，即在電子文件產(chǎn)生后，在轉(zhuǎn)發(fā)及保存過(guò)程中保證其內(nèi)容不被輕易修改，保持其原始性和有效性才是最重要的，而不是僅僅保證其在外在形式上不可修改，也就是說(shuō)即使電子文件本身在計(jì)算機(jī)上不能修改或復(fù)制，但是完全可以參照其內(nèi)容和形式仿制出修改過(guò)的電子文件[11]。通過(guò)文件的無(wú)損壓縮，一方面縮小了文檔的體積易于維護(hù)和保存，另一方面使得文檔不可以被顯式更改，即刻意對(duì)文檔的某些內(nèi)容進(jìn)行修改從而保證了電子文件的完整性。在壓縮中如果采用了二進(jìn)制編碼的方式，則可以對(duì)壓縮后的二進(jìn)制序列進(jìn)行散列運(yùn)算，通過(guò)單向的散列運(yùn)算形成壓縮文件的唯一性數(shù)字指紋，任何對(duì)壓縮文件的非法操作都將同不過(guò)數(shù)字指紋的驗(yàn)證，這就進(jìn)一步增加了文檔的不可隨意修改性與可靠性保證了電子文件的一致性。這種無(wú)損壓縮所采用的編碼方式大多數(shù)就是基于自適應(yīng)哈夫曼編碼[8]。4 編程環(huán)境及相關(guān)編程技術(shù)本系統(tǒng)編程環(huán)境采用Visual C++，并結(jié)合MFC做出界面。 VC++簡(jiǎn)介 Visual C++概述只要提到在Windows 95和Windows NT下進(jìn)行32位的應(yīng)用程序開發(fā)，就不能不提到Visual C++。相比其他的編程工具而言，Visual C++在提供可視化的編程方法的同時(shí)，也適用于編寫直接對(duì)系統(tǒng)進(jìn)行底層操作的程序，其生成代碼的質(zhì)量，也要優(yōu)于其他的很多開發(fā)工具。隨Visual C++所提供的Microsoft基礎(chǔ)類庫(kù)（Microsoft Foundation Class Library，簡(jiǎn)寫為MFC），對(duì)Windows 95/NT所用的Win32應(yīng)用程序接口（Win32 Application Programming Interface）進(jìn)行了十分徹底的封裝，這使得可以使用完全的面向?qū)ο蟮姆椒▉?lái)進(jìn)行Windows95/NT應(yīng)用程序的開發(fā)，從而大量地節(jié)省了應(yīng)用程序的開發(fā)周期，降低了開發(fā)成本，也使得Windows程序員從大量的復(fù)雜勞動(dòng)中獲得解救。1998年9月Microsoft公司推出了Visual Studio98系列開發(fā)工具，Visual C++，在這個(gè)版本的Visual C++中，可視化開發(fā)的概念得到進(jìn)一步拓展，融合了Microsoft公司其它編譯器產(chǎn)品的優(yōu)點(diǎn)，使開發(fā)者的開發(fā)工作變得更有趣、方便，工作效率也大大提高。Visual C++的核心是Microsoft基礎(chǔ)類庫(kù)，即通常所說(shuō)的MFC。MFC相當(dāng)徹底地封裝了Win32軟件開發(fā)工具包(Software Development Kit，即SDK)中的結(jié)構(gòu)、功能，它為編程者提供了一個(gè)應(yīng)用程序框架，這個(gè)應(yīng)用程序框架為編程者完成了很多Windows編程中的例行性工作，如管理窗口、菜單和對(duì)話框，執(zhí)行基本的輸入和輸出、使用集合類來(lái)保存數(shù)據(jù)對(duì)象等等，并且，MFC使得在程序中使用很多過(guò)去很專業(yè)、很復(fù)雜的編程課題，如ActiveX、OLE、本地?cái)?shù)據(jù)庫(kù)和開放式（Open Database Connectivity，ODBC）、Windows套接字和Internet應(yīng)用程序設(shè)計(jì)等，以及其他的應(yīng)用程序界面特性，如屬性頁(yè)（也叫標(biāo)簽對(duì)話框）、打印和打印預(yù)覽、浮動(dòng)的和可定制的工具條變得更加的容易[3]。 集成開發(fā)環(huán)境Visual C++軟件包包含了許多單獨(dú)的組件，如編輯器、編譯器、鏈接器、生成實(shí)用程序、調(diào)試器以及各種各樣為開發(fā)Microsoft Windows下的C/C++程序而設(shè)計(jì)的工具。它還包含有一個(gè)名為Developer Studio的開發(fā)環(huán)境。Developer Studio把所有的Visual C++工具結(jié)合在一起，集成為一個(gè)整體，通過(guò)一個(gè)由窗口、對(duì)話框、菜單、工具欄、快捷鍵及宏組成的和諧系統(tǒng)，你可以觀察和控制整個(gè)開發(fā)進(jìn)程。集成開發(fā)環(huán)境就像一間帶有監(jiān)視器、刻度盤和操縱桿的控制室。該環(huán)境幾乎就是Visual C++中所能“看見(jiàn)”的所有東西。所有其他事情都在其管理下在幕后運(yùn)行。VC++軟件操作環(huán)境如下圖41所示。圖4 1 VC++軟件操作環(huán)境Microsoft Developer Studio用于Visual J++、Visual InterDev、Visual C++。它有以下的特性：(1) 自動(dòng)化和