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

有效

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

1.一種基于多層哈希結構與游程編碼的數據無損壓縮方法，包括以下步驟：

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

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

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

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

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

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

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

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

（6）若匹配次數p等于1，按照新模式從待壓縮數據中讀取字符并存儲至哈希表，返回步驟（3）；否則，更新讀取位置為待編碼字符位置按照原讀取規則從待壓縮數據中讀取字符，返回步驟（3）。

2.根據權利要求1所述的方法，其中步驟（6）所述按照新模式從待壓縮數據中讀取字符存儲至哈希表，按如下步驟進行：

（6a）將讀取位置更新為當前已經編碼的四個字符中的第二個字符；

（6b）改變讀取規則，即每一次讀取四個字符后，讀取位置后移一個字符，重復讀取字符直至讀取位置為當前已經編碼的四個字符中的第四個字符；

（6c）把每次讀取的四個字符存入哈希表，讀取位置后移一個字符，再將讀取規則恢復為權利要求1中步驟（2）的原讀取規則。