[發明專利]基于多層哈希結構與游程編碼的數據無損壓縮方法

有效

• 申請號: 201310161380.2
• 申請日: 2013-05-06
• 公開（公告）號: CN103236847A
• 公開（公告）日: 2013-08-07
• 發明（設計）人: 宋彬;郭潔;宋秉璽;秦浩;胡襯
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H03M7/30
• 分類號: H03M7/30;G06F17/30
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華;朱紅星

技術領域

本發明屬于數據無損壓縮技術領域，涉及圖像、文本、程序等常見數據的壓縮，可用在對數據的壓縮速度和壓縮效率均有要求的存儲設備中。

背景技術

隨著信息科技日新月異的發展，人們對于數據的存儲需求日益提升，此外，網絡的蓬勃發展，使得傳輸通道上的數據流量也越來越大，然而帶寬卻無法負荷這么龐大的數據量。為了解決以上問題，數據就必須先經過壓縮編碼，使得原本數據的大小降低，從而節省數據存儲的使用空間，提升傳送數據的速度。

目前，數據無損壓縮方法有很多，可以分為兩類：基于統計的無損壓縮方法和基于字典的無損壓縮方法。基于統計的無損壓縮方法以霍夫曼編碼方法為代表。這種壓縮方法通常需要統計每個符號出現的次數，一般都需要耗費大量的時間，但是壓縮率很高；基于字典的無損壓縮方法以Lempel-Ziv系列為代表，LZW(Lempel?Ziv?Walch),LZSS（Lempel?Ziv?Storer?Szymanski）等等，在這類方法中LZO（Lempel?Ziv?Oberhumer）是目前最快速的無損壓縮方法；此外還有把這兩類方法結合的無損壓縮方法。

霍夫曼編碼方法，是目前應用最廣的基于統計的無損壓縮方法，它通過統計每個符號出現的概率，建立霍夫曼樹，使得出現概率高的字符用較少的比特表示，出現頻率低的用較多的比特來表示，從而盡可能減少傳送所需的總比特數，因為這種編碼方法編碼之后的字符串的平均期望長度最低，有時也稱為最佳編碼。然而在實際應用時，對信源進行霍夫曼編碼后，形成一個霍夫曼編碼表，必須通過查表的方法來進行編、譯碼。在信源存儲與傳輸過程中必須首先存儲這一霍夫曼編碼表，若先基于大量概率統計，建好霍夫曼編碼表，則所需存儲碼表的容量增大，使設備復雜化，同時也使得查表搜索時間增大。

LZO算法，是目前應用最廣泛的基于字典的無損壓縮方法，其具有以下特點：解壓簡單，解壓速度快，允許在壓縮編碼時以損失壓縮速度為代價提高壓縮率，并且可以選擇與實際應用相匹配壓縮級別。另外LZO的算法是線程安全的，在進行編碼時，LZO的兩次哈希運算與其設置的五種不同的壓縮格式保證了它的解壓縮速度。在實際編碼時，尋找匹配字符串時，如若發生碰撞，即經哈希運算后結果相同的兩個字符串不是完全相同的字符串，LZO沒有用偏移的方法來尋找新的存儲單元而是直接把這些字符串當作新符號直接傳送出去，這樣避免了用大量的時間來尋找新的存儲單元。

LZO雖然具有壓縮快速的優點，但是其壓縮率卻由于內在的特點而比霍夫曼等無損壓縮方法要低，尤其對有較多重復內容的數據壓縮效果不佳。

發明內容

本發明目的在于針對上述LZO方法的不足，提出一種基于多層哈希結構與游程編碼的數據無損壓縮方法，在保證其壓縮和解壓縮速度的前提下，改進LZO方法的數據壓縮效果，提高LZO的壓縮率。

實現本發明的基本思想是：使用游程編碼對原始數據進行預處理并對LZO編碼的哈希表構建方法進行改進，其具體實現步驟包括如下：

（1）初始化：讀入原始數據，用游程編碼方法對其進行預處理，即把原始數據中有重復的字符串編碼為重復字符加上重復長度的格式，得到待壓縮數據；

（2）初始化讀取位置為待壓縮數據中第一個字符位置，初始化哈希表為空表，并設置讀取規則，即每次從初始化后的待壓縮數據中讀取四個字符，每一次讀取后，讀取位置后移四個字符；

（3）區分新字符和匹配字符，若是匹配字符則在哈希表中尋找最長匹配字符串：

（3a）按照讀取規則從待壓縮數據中讀取四個字符，若這四個字符沒有記錄在哈希表中，則判為新字符，執行步驟（4），并把該新字符存入哈希表中，初始化匹配次數p為0；若哈希表中有記錄，則不是新字符，即當前字符與哈希表中記錄字符匹配，進行步驟（3b），更新匹配次數p為1；

（3b）按照讀取規則繼續從待壓縮數據中讀取四個字符，若該四個字符與步驟（3a）中找到的哈希表中記錄的字符串依然匹配，則令匹配次數p加1，更新哈希表中記錄的字符位置為當前匹配字符位置；否則，執行步驟（4），并把當前字符串存入哈希表；

（3c）重復執行步驟（3b），至多5次，在哈希表記錄的字符串中找出與當前字符串最長的匹配字符串并將其存入哈希表；

（4）若是新字符，則按照LZO新字符的編碼方法進行壓縮編碼；否則根據字符重復長度和指回距離即當前字符位置與哈希表內記錄位置之間的距離，按照LZO的編碼格式進行壓縮編碼；

（5）判斷是否編碼至待壓縮數據結尾，若是，則輸出壓縮后數據和壓縮后數據的長度，并記下結束標志，否則，執行步驟（6）；