蔣覲陽，曹 亮

蘭州大學信息科學與工程學院，甘肅蘭州 730000

電力線載波通信是利用已有的電力線路進行數據傳輸的一種通信方式，無需專門架設通信基礎設施并且具有相當廣泛的網絡分布，具有投資小、設備簡單、通信可靠性高等優點。然而，由于電力線載波通信存在著一些技術難題，如傳輸信道間歇噪聲大、阻抗隨負載變化大、信號衰減大等問題，我們將數據壓縮技術引入電力線載波通信，在數據傳輸前進行壓縮，這樣就可以盡可能在有限的帶寬內傳輸盡可能多的數據。

1 數據壓縮原理

數據壓縮是指在不丟失信息的前提下，縮減數據量以減少存儲空間，提高其傳輸、存儲和處理效率的一種技術方法。或按照一定的算法對數據進行重新組織，減少數據的冗余和存儲的空間。壓縮的理論基礎是信息論[1]。從信息的角度來看，壓縮就是去除掉信息中的冗余，即去除掉確定的或可推知的信息，而保留不確定的信息，也就是用一種更接近信息本質的描述來代替原有的冗余的描述，這個本質的東西就是信息量。

關于數據壓縮有很多算法，針對不同特點的數據選擇不同的壓縮算法從而達到最優的壓縮效果。LZW繼承了LZ77和LZ78壓縮效果好、速度快的優點，且算法描述易于接受。該算法能在不了解數據統計特性前提下，使壓縮比接近已知統計特性時所能達到的壓縮比，且易于實現，是目前最常用的算法。

1.1 LZW算法基本原理

LZW壓縮算法是一種新穎的壓縮方法，Lemple-Ziv-Welch 三人共同創造，用他們的名字命名。它采用了一種先進的串表壓縮，將每個第一次出現的串放在一個串表中，用一個數字來表示串，壓縮文件只存貯數字，則不存貯串，從而使圖像文件的壓縮效率得到較大的提高。奇妙的是，不管是在壓縮還是在解壓縮的過程中都能正確的建立這個串表，壓縮或解壓縮完成后，這個串表又被丟棄[2]。

LZW算法中，首先建立一個字符串表，把每一個第一次出現的字符串放入串表中，并用一個數字來表示，這個數字與此字符串在串表中的位置有關，并將這個數字存入壓縮文件中，如果這個字符串再次出現時，即可用表示它的數字來代替，并將這個數字存入文件中。壓縮完成后將串表丟棄。如"print" 字符串，如果在壓縮時用266表示，只要再次出現，均用266表示，并將"print"字符串存入串表中，在圖像解碼時遇到數字266，即可從串表中查出266所代表的字符串"print"，在解壓縮時，串表可以根據壓縮數據重新生成。

LZW算法流程：

1）初始化：將所有的單字符串放入串表；2）讀第一個輸入字符給前綴串ω；3）Step: 讀下一個輸入字符K。

if 沒有這樣的K(輸入已窮盡)：

碼字(ω) 輸出；結束。

If ωK 已存在于串表中：

ω:=ωK；repeat Step；

else ωK不在于串表中:

碼字 (ω) 輸出 ；

ωK加進串表；

ω:=K；repeat Step.

例子：

input:ababcbababaaaaaaa

ω:a->ab->ba->ab->4c->cb->ba->5b->8a->aa->aa->10a->aa->11a->a#->#

串 表：1(a) 2(b) 3(c) 4(ab) 5(ba) 6(4c) 7(cb) 8(5b) 9(8a) 10(aa)11(10a) 12(11a)

output:a b 4 c 5 8 a 10 11 a

1.2 電力線通信報文壓縮算法設計

將LZW壓縮算法應用在電力線通信中，數據采樣利用率提高了兩倍，使報文傳遞更可靠；通過控制信息位（bit）級檢錯、數據信息分組檢錯等手段，增強檢錯能力，降低誤同步概率；數據信息分組檢測糾錯，報文長度不再受鏈路層程序邏輯限制；糾錯方式不再是唯一的擴頻，支持不同長度的擴頻編碼，速率的提高可減少報文沖突幾率，有利于并行路由的順暢運行；報文壓縮后不僅可以提高傳輸速率，還可以提升數據傳輸成功機率[3]。

例如，報文原始數據為：255，24，54，255，24，255，255，24，5，123，45，255，24，5，24，54...如何對它進行壓縮，因為原始數據可以用8bit來表示，故清除標志Clear=255+1 =256，結束標志為End=256+1=257，目前標號集為0 1 2 3......255 CLEAR END

第一步，讀取第一個字符為255，在標記表里面查找，255已經存在，不做處理；

第二步，取第二個字符，此時前綴為A，形成當前的Entry為(255，24)，在標記集合不存在，把它在標記集合中標記為258，然后輸出前綴A，保留后綴24，并作為下一次的前綴（后綴變前綴)；

第三步，取第三個字符為54，當前Entry(24，54)，記錄(24，54)為標號259，并輸出24，后綴變前綴；

第四步：取第四個字符255，Entry=(54，255)，記錄(54，255)為標號260，輸出54，后綴變前綴。.......

一直處理到最后一個字符，用一個表記錄處理過程，CLEAR=256，END=257。

表1 LZW算法舉例

2 算法改進

2.1 改進思路

LZW方法簡單易行，但是存在諸多不足，例如，對不同大小的文件，均使用12位輸出代碼。在壓縮的開始階段文件較小時，字典中的短語比較少，使用位數更少的壓縮代碼顯然能減少壓縮文件的大小[4]。當“next code”的值在256到511之間時，9位輸出代碼就足以表示所有短語；另一個有待改進的方面是壓縮率的監測。在壓縮進程中，當字典空間被填滿、新的短語不能加入到字典中時，對隨后的字典中無定義的字符串就無法進行壓縮，壓縮率將下降。

2.2 改進方法

1）可變代碼長度

發現字典填滿時，立即將字典清空，以便后續字符串能建立短語。首先在字典中設置清除標志，當字典填滿后，在進行閾值判斷時，對每一個碼字(Code Word)的使用情況計數。當進行閾值判斷所得到的壓縮比小于指定的閾值時，發出清除標志，這時根據字典中每一個碼字使用的計數值大小進行排序，對字典進行相應的重構，然后刪除排序靠后的若干項。這種方法較簡單，也有效果[5]。

STEPl初始化，使開始詞典包含所有可能的根(Root)，當前前綴P置空；

STEP2當碼字流有碼字要譯時，反復執行STEP3，STEP4，STEP5和STEP6；

STEP3讀入字符數據流中的下一個字符C；

STEP4如果字符串P+C在當前詞典中，

a P置P+C（用字符C擴展P）；

b 把代表當前前綴P的碼字輸出到碼字流;

否則，

c 輸出表示P的碼字到編碼數據流；

d 把字符串P+C添加到詞典；

e P置C（此時P僅含一個字符C）；

STEP5若字典未滿，則執行STEP3；

STEP6如果壓縮比小于指定闞值，則清除匹配率小的詞條，否則，返回STEPl;

STEP7結束。

2）監測壓縮率

要監控壓縮率的變化至少需要知道四個量。一是原始壓縮率，顯然壓縮率為100%。二是現在的壓縮率，由輸出壓縮代碼與輸入字符數的比值來確定，必須知道輸入字符數和輸出壓縮代碼。以上四個變量在程序中分別定義為ratio_old、ratio_new、bytes_in、bytes_out。其中

ratio_new=

當程序通過ratio_new值發現壓縮率已經低于100%，說明字典中的短語已經過時，不再適合壓縮之用，應建立新的字典。這里選擇在輸入字符號每增加一百個時計算一次，用一個標識通知還原算法原來的字典已經不再使用，還原算法即可從此開始建立新字典。壓縮程序改進如下：

while((character=getc(input))!=(unsigned)

EOF){

++bytes_in；／*計算輸入值*／

if(bytes_in>checkpoint){／*checkpoint初始值為100*／

if(num_bits==MAX_BITS){

ratio_new=bytes_out*100／bytes_in；∥計算新壓縮率

if(ratio_new>ratio_old){／壓縮率是否下降

OutputBits(output，CLEAR_TABLE，code_bits);／／輸出標識

code_bits=9；／／壓縮代碼位數從9開始

next_code=258；∥短語從258開始編碼

dict_byte=511； ∥字典容量為512

bytes_in=bytes_out=0； ∥ 復 位 bytes_in、bytes_out ratio_old=100；

for(i=0；i

code_value[i]=一1；}

else／*壓縮率沒有下降*／

ratio_old=ratio_new；∥以ratio_new作為ratio_old，以便下次比較

還原程序改進如下：

while((new_code=input_code(input))!=END_OF_STREAM)

{

if(new_code== CLEAR～TABLE){ ／*清空字典標識*／

code_bits=9；∥壓縮代碼位數從9開始

next_code=258； ∥短語從258開始編碼

dict_byte=511； ∥字典容量為512

continue；

}……

3 改進的LZW算法比較

給出算法比較圖

表2 LZW經典算法與改進算法壓縮性能比較

首先，由表中數據可以看出改進的LZW算法對各種不同類型的文件壓縮率都有了很大的提高，特別是對位圖文件的壓縮率改善更加顯著。

其次，改進的LZW算法不僅壓縮比較高，且壓縮用時也較短，在電力線載波通信中，報文數據經過壓縮，可以讓出帶寬，達到最初設想。

[1]袁枚.數據壓縮技術及其應用[M].北京：電子工業出社，1995.

[2]Mark Nelson.數據壓縮技術原理與范例[M].北京：科學出版社，1995.

[3]周天暉，王光.改進的LZW壓縮算法在語音數據復接器中的應用[J].電力系統通信，2002(12).

[4]劉萌，丁香乾.電力線窄帶通信報文壓縮算法研究[J].網絡與通信，2010(16).

[5]ZIV J，LEMPEL A.A universal algorithm for sequential data compression[J].IEEE Transactions on Information Theory，VOL.1T一23，NO.3，MAY 1977.