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

有效

• 申請(qǐng)?zhí)枺?/td>: 201410283510.4
• 申請(qǐng)日: 2014-06-23
• 公開（公告）號(hào): CN104077272B
• 公開（公告）日: 2017-01-04
• 發(fā)明（設(shè)計(jì)）人: 鄭妍妍
• 申請(qǐng)（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號(hào): G06F17/22
• 分類號(hào): G06F17/22
• 代理公司: 北京中博世達(dá)專利商標(biāo)代理有限公司11274
• 代理人: 王亞沛

1.一種字典壓縮的方法，其特征在于，該方法包括：

獲取通信報(bào)文中第一字串的個(gè)數(shù)占總字串個(gè)數(shù)的比值x，其中，所述通信報(bào)文中的每個(gè)字串都由m個(gè)字符組成，所述第一字串是由關(guān)鍵字符組成的字串，所述關(guān)鍵字符的個(gè)數(shù)為n，字典的大小為H；

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

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

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

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

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

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述獲取通信報(bào)文中第一字串的個(gè)數(shù)占總字串個(gè)數(shù)的比值x之前，該方法還包括：

按照出現(xiàn)次數(shù)由大到小的順序，獲取所述通信報(bào)文的L個(gè)字符中的前n個(gè)字符作為所述關(guān)鍵字符，其中，所述L個(gè)字符為所述通信報(bào)文中所有兩兩不同的字符。

3.根據(jù)權(quán)利要求2所述的方法，其特征在于，所述按照出現(xiàn)次數(shù)由大到小的順序，獲取所述通信報(bào)文的L個(gè)字符中的前n個(gè)字符作為所述關(guān)鍵字符之后，該方法還包括：

設(shè)置第1至第M個(gè)關(guān)鍵字符組，所述每個(gè)關(guān)鍵字符組中的字符都屬于所述n個(gè)字符，所述每個(gè)關(guān)鍵字符組中的字符數(shù)小于n，所述M大于等于2；

獲取所述通信報(bào)文中第三字串的個(gè)數(shù)占中字串個(gè)數(shù)的比值y，其中，所述第三字串是由所述第1至第M個(gè)關(guān)鍵字符組中的任一關(guān)鍵字符組中的字符組成的字串，所述通信報(bào)文中的每個(gè)字串都由m個(gè)字符組成，字典的大小為H；

獲取第1至M個(gè)關(guān)鍵字符組中每個(gè)關(guān)鍵字符組的關(guān)鍵字符的個(gè)數(shù)的m次方的和值T；

判斷所述和值T是否小于H*y；

若是，為每個(gè)關(guān)鍵字符組分配對(duì)應(yīng)的哈希鏈表頭的存儲(chǔ)空間，并為所述第二哈希鏈表頭分配存儲(chǔ)空間，其中，所述第N個(gè)關(guān)鍵字符組所對(duì)應(yīng)的哈希鏈表頭的存儲(chǔ)空間的大小為t的m次方，其中，所述t為所述第N個(gè)關(guān)鍵字符組中關(guān)鍵字符的個(gè)數(shù)，所述第二哈希鏈表頭的存儲(chǔ)空間的大小為H*(1-y)；

判斷所述通信報(bào)文中的第二字串是否是由第N個(gè)關(guān)鍵字符組中的字符組成的，其中，所述1＜＝N＜＝M；

若是，通過所述第N個(gè)關(guān)鍵字符組所對(duì)應(yīng)的哈希函數(shù)計(jì)算所述第二字串的哈希值，并將所述第二字串的哈希值以及所述第二字串在字典中的地址信息存入所述第N個(gè)關(guān)鍵字符組所對(duì)應(yīng)的哈希鏈表頭中；

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

4.根據(jù)權(quán)利要求3所述的方法，其特征在于，所述第N個(gè)關(guān)鍵字符組所對(duì)應(yīng)的哈希函數(shù)為全映射函數(shù)或非全映射函數(shù)，所述第二哈希函數(shù)為非全映射函數(shù)。

5.一種字典壓縮的裝置，其特征在于，該裝置包括：第一獲取單元，第一判斷單元、分配單元、第二判斷單元和計(jì)算單元；

所述第一獲取單元，用于獲取通信報(bào)文中第一字串的個(gè)數(shù)占總字串個(gè)數(shù)的比值x，其中，所述通信報(bào)文中的每個(gè)字串都由m個(gè)字符組成，所述第一字串是由關(guān)鍵字符組成的字串，所述關(guān)鍵字符的個(gè)數(shù)為n，字典的大小為H；

所述第一判斷單元，用于判斷n的m次方是否小于H*x；

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

所述第二判斷單元，用于判斷所述通信報(bào)文中的第二字串是否屬于所述第一字串；

所述計(jì)算單元，用于若是，通過第一哈希函數(shù)計(jì)算所述第二字串的哈希值，并將所述第二字串的哈希值以及所述第二字串在字典中的地址信息存入第一哈希鏈表頭中；

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