[發明專利]一種字典壓縮的方法和裝置

有效

• 申請號: 201410283510.4
• 申請日: 2014-06-23
• 公開（公告）號: CN104077272B
• 公開（公告）日: 2017-01-04
• 發明（設計）人: 鄭妍妍
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F17/22
• 分類號: G06F17/22
• 代理公司: 北京中博世達專利商標代理有限公司11274
• 代理人: 王亞沛

技術領域

本發明涉及計算機技術領域，尤其涉及一種字典壓縮的方法和裝置。

背景技術

隨著互聯網技術、云計算技術的發展，手機等用戶群體的激增以及服務的多樣化，越來越多的數據需要存儲，而這些海量數據的存儲成本是非常高的。為了緩解這個問題，通常在數據進行存儲前會對數據進行壓縮處理，經過壓縮后的數據可以大幅度提高磁盤的有效容量，從而有效的降低互聯網數據中心的成本。

在壓縮算法中，字典壓縮算法LZ77及其變種是通用壓縮算法GZIP中的重要的一部分。在字典壓縮算法中，通常由字典壓縮模塊和輸出模塊組成，其中，字典壓縮模塊對一個文檔中的數據進行壓縮，輸出模塊輸出壓縮結果。字典壓縮模塊通常由三部分組成，字典(歷史數據窗口中的歷史數據)以及字典所對應的索引，其中，字典所對應的索引由哈希鏈表頭和哈希鏈表構成。

具體的壓縮過程，舉例來說，對于字串1，字典壓縮模塊先計算其哈希值，將其哈希值以及該字串1在歷史數據窗口的地址信息的對應關系存入哈希鏈表頭中，若該哈希值所對應的存儲空間已經有其他字串，例如字串2的地址信息，則將字串2的地址信息存放在哈希鏈表中，將字串1的地址信息存放在哈希鏈表頭的該哈希值所對應的存儲空間中。

再通過該字串1的哈希值，在哈希鏈表中尋找歷史數據窗口中是否出現過與該字串具有相同哈希值的字串，若出現過，例如上述字串2，且假設所述字串2與所述字串1是完全相同的字串，則獲取字串2的地址，并將以字串1為開頭的字串，以及以與字串2為開頭的字串進行匹配，例如以字串2為開頭的字串為字串2，字串3，字串4，字串5…，以字串1為開頭的字串為字串1，字串7，字串8，字串9…，其中，字串7和字串3完全相同，字串4和字串9完全相同，字串5和字串9不相同…，則以所述字串1為開頭的字串1，字串7和字串8組成的長字串，就可以根據字串2，字串3和字串4的位置和長度進行編碼，用所述編碼代替所述字串1，字串7和字串8，從而達到將字串1，字串7和字串8進行壓縮的目的。

此時，字串1，字串7和字串8作為歷史數據存放在歷史數據窗口中，成為字典的一部分，字串1，字串7和字串8的哈希值和每個字串對應的在歷史數據窗口的地址信息被存放在哈希鏈表或哈希鏈表中，將字串1，字串7和字串8進行編碼后得到的壓縮結果從所述輸出模塊被輸出。

在現有技術中，為盡量避免哈希沖突，為哈希鏈表頭和哈希鏈表分配的存儲空間與歷史數據窗口的大小一致，即歷史數據窗口中的數據的哈希值與其地址信息所占用的哈希鏈表頭的存儲空間為歷史數據窗口大小。

歷史數據窗口的大小通常設置為16K或者32K，以設置為16K為例，字典壓縮模塊所需要的存儲空間就是48K(字典，哈希鏈表頭和哈希鏈表各16K)，壓縮模塊所占用的總的存儲空間較大。

發明內容

本發明的實施例提供一種字典壓縮的方法和裝置，用于解決字典壓縮的過程中字典壓縮模塊需要占用的存儲空間過大的問題。

為達到上述目的，本發明的實施例采用如下技術方案：

第一方面，本發明實施例提供了一種字典壓縮的方法，該方法包括：

獲取通信報文中第一字串的個數占總字串個數的比值x，其中，所述通信報文中的每個字串都由m個字符組成，所述第一字串是由關鍵字符組成的字串，所述關鍵字符的個數為n，字典的大小為H；

判斷n的m次方是否小于H*x；

若是，分別為第一哈希鏈表頭和第二哈希鏈表頭分配存儲空間，其中，所述第一哈希鏈表頭的存儲空間大小為n的m次方，所述第二哈希鏈表頭的存儲空間為H*(1-x)；

判斷所述通信報文中的第二字串是否屬于所述第一字串；

若是，通過第一哈希函數計算所述第二字串的哈希值，并將所述第二字串的哈希值以及所述第二字串在字典中的地址信息存入第一哈希鏈表頭中；

若不是，通過第二哈希函數計算所述第二字串的哈希值，并將所述第二字串的哈希值以及所述第二字串在字典中的地址信息存入第二哈希鏈表頭中。

在第一種可能的實施方式中，結合第一方面，所述獲取通信報文中第一字串的個數占總字串個數的比值x之前，該方法還包括：

按照出現次數由大到小的順序，獲取所述通信報文的L個字符中的前n個字符作為所述關鍵字符，其中，所述L個字符為所述通信報文中所有兩兩不同的字符。

在第二種可能的實施方式中，結合第一種可能的實施方式，所述按照出現次數由大到小的順序，獲取所述通信報文的L個字符中的前n個字符作為所述關鍵字符之后，該方法還包括：