[發明專利]基于LZSS算法和Sunday算法的數據壓縮方法及系統

有效

• 申請號: 202011559946.3
• 申請日: 2020-12-25
• 公開（公告）號: CN112671413B
• 公開（公告）日: 2022-09-06
• 發明（設計）人: 吳楠;曹博;高翔宇
• 申請（專利權）人: 浪潮云信息技術股份公司
• 主分類號: H03M7/40
• 分類號: H03M7/40
• 代理公司: 濟南信達專利事務所有限公司 37100
• 代理人: 孫園園

1.一種基于LZSS算法和Sunday算法的數據壓縮方法，其特征在于，該方法是利用熵編碼對待壓縮數據進行預處理并選取壓縮標準，同時將窗口變為動態設置大小，設定一個最小的匹配長度，并找到匹配的最大字符串提高壓縮效率，再通過Sunday字符串匹配算法降低字符串匹配時的時間消耗；具體步驟如下：

S1、對應不同的壓縮數據，采用不同熵編碼進行預處理；

S2、確定選取的壓縮標志并置于數據首位；

S3、將窗口大小設為動態可變；

S4、在將字符串匹配時，設定一個最小匹配長度，將小于此長度的字符串正常打印到動態窗口；

S5、開始進行壓縮處理；

S6、匹配第一次的字符串；

S7、采用Sunday算法找尋是否有字符串的匹配項：

①、若是，則執行步驟S8；

②、若否，則跳轉至步驟S10；

S8、在最新位置查看是否順延：

①、若是，則執行步驟S9；

②、若否，則跳轉至步驟S7；

S9、得到新的字符串并記錄，下一步跳轉至步驟S7；

S10、得到存在的最大字符串；

S11、要壓縮的字符串是否結束：

①、若是，則執行步驟S12；

②、若否，則跳轉至步驟S6；

S12、結束。

2.根據權利要求1所述的基于LZSS算法和Sunday算法的數據壓縮方法，其特征在于，步驟S1中的熵編碼進行預處理前，通過LSZZ算法找尋之前出現的字符串中是否已出現相同的字符串段落，對未重復出現過的字符串段落原樣輸出。

3.根據權利要求1所述的基于LZSS算法和Sunday算法的數據壓縮方法，其特征在于，壓縮數據中超過60%的內容格式固定時，采用huffman編碼方式進行熵編碼。

4.根據權利要求1所述的基于LZSS算法和Sunday算法的數據壓縮方法，其特征在于，壓縮標志選取原則如下：

①、選取不常用到的壓縮標志；

②、找尋未出現過的標志或出現頻率最小的標志并注明；

③、若出現相同標注需要壓縮，則進行一次重復來區別。

5.根據權利要求1-4中任一所述的基于LZSS算法和Sunday算法的數據壓縮方法，其特征在于，步驟S3中將窗口大小設為動態可變具體如下：

延用LZSS算法中的動態窗口和預讀窗口方法，將固定長度的窗口變為長度動態可變的窗口；

在壓縮時，偏移執行靠近窗口末尾的部分；

在窗口大小固定的情況下，編碼需要的大小為upper-bound（log2（n））。

6.一種基于LZSS算法和Sunday算法的數據壓縮系統，其特征在于，該系統包括，

預處理模塊，用于對不同的壓縮數據，采用不同熵編碼進行預處理；

選取模塊，用于確定選取的壓縮標志并置于數據首位；

設定模塊一，用于將窗口大小設為動態可變；

設定模塊二，用于在將字符串匹配時，設定一個最小匹配長度，將小于此長度的字符串正常打印到動態窗口；

壓縮模塊，用于開始進行壓縮處理；

匹配模塊，用于匹配字符串；其中，匹配模塊工作過程步驟如下：

（1）、匹配第一次的字符串；

（2）、采用Sunday算法將此字符串和其位置后需要匹配的字符串進行匹配，并找尋是否有字符串匹配項：

①、若后續不存在匹配項，則跳轉至步驟（5）；

②、若后續存在匹配項，則執行步驟（3）；

（3）、繼續嘗試將字符串進行后延來找到更大的匹配字符串，即在最新位置查看是否順延：

①、若存在更大的字符串，則執行步驟（4）；

②、若匹配成功時，則不能后延，保留原紀錄并繼續向后匹配來找尋下一個匹配字符串的位置，則跳轉至步驟（2）；

（4）、將其記錄下來并重復進行字符串匹配操作，下一步跳轉至步驟（2）；

（5）、得到存在的最大字符串，將已得的字符串進行正常壓縮處理。