[發明專利]基于熵判決最優差分編碼的LZW壓縮方法

有效

• 申請號: 201210176439.0
• 申請日: 2012-05-31
• 公開（公告）號: CN102710263B
• 公開（公告）日: 2015-04-08
• 發明（設計）人: 李贊;胡易俗;劉向麗;司江勃;韓維佳;郝本建;潘蕾;王彬哲;任蕓梅;陳俊杰
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華;朱紅星

技術領域

本發明屬于數據處理技術領域，特別是一種LZW(Lempel-Ziv-Welch)壓縮方法， 適合于無線傳感器網絡中慢變數據壓縮。

背景技術

無線傳感器網絡的重要工作之一是采集數據，并對采集的數據進行相應的處理， 然后發送到接收端。多個傳感器節點產生大量的數據，如果不進行相應的處理而直接 進行傳輸，這樣會消耗大量的節點能量。數據壓縮可以減少數據的傳輸量，對于節省 傳感器節點能量和帶寬具有重要的意義。

1977年以色列教授Jcacob?Ziv和Abraham?Lempel提出了著名的LZ77算法，并 于1978年對其進行改進，這就是LZ78，打開了基于字典壓縮的大門。Terry?A.Welch 在1984年對該算法進行改進，就形成了現在的LZW(Lempel-Ziv-Welch)壓縮編碼。 LZW算法采用了一種先進串表的無損數據壓縮算法，將每個第一次出現的串放在一 個串表中，用一個數字來表示串，如果新的組合數據再次出現時，即可用表示它的數 字來代替，并將這個數字存入文件中，壓縮文件只存儲壓縮后數據和極少原始數據的 特征數據。解壓時先根據原始數據特征建立初始字典表，然后根據接收的數據逐漸建 立字典，并把對應數據的串提取解壓出來。它的特點是在壓縮和解壓縮的過程中都能 正確的建立這個字典，壓縮或解壓縮完成后，這個字典又被丟棄。它是一種穩定有效 和快速的壓縮方法，在常用的PKZIP等壓縮軟件也用該算法，這種算法主要用在圖 像數據、文本程序壓縮中。現有的LZW改進算法主要是改進字典的存儲類型、輸出 碼字長度優化和對數據壓縮存儲長度的改進，然而對于慢變的數據直接進行LZW壓 縮，雖然有一定程度的壓縮比，壓縮比提高并不明顯。因此如何改進無線傳感器網絡 中LZW壓縮算法，提出快速有效的壓縮算法和LZW改進的壓縮算法就顯得尤為必 要。

發明內容

本發明的目的在于針對上述已有技術的不足，提出一種基于熵判決最優差分編碼 的LZW壓縮方法，以有效壓縮無線傳感器網絡中的緩慢變化數據，實現最優壓縮比。

實現本發明的技術方案是：利用無線傳感器網絡中慢變的數據，采用多次差分編 碼，通過計算熵值確定最優差分編碼次數，最后進行LZW壓縮、LZW解壓縮和m 次差分解碼，得到原始數據。具體步驟如下：

（1）設原始數據為x₀(i)，i=1,2,…,N，N為原始數據的長度，則第m次差分編 碼后數據x_m(i)為：

x_m(i)=x_m-1(i)-x_m-1(i-1)

其中設定x_m-1(0)=0，i=1,2,…N，m=1,2,3,…，x_m-1(i)為第m-1次差分編碼后 的數據；

（2）計算第m次差分編碼后數據x_m(i)的熵H_m(x_m)：