[發(fā)明專利]一種通用的基于分塊排序思想的壓縮預(yù)處理方法及應(yīng)用

在審

• 申請?zhí)枺?/td>: 201610831693.8
• 申請日: 2016-09-20
• 公開（公告）號: CN106936439A
• 公開（公告）日: 2017-07-07
• 發(fā)明（設(shè)計）人: 王剛;劉博;黃曦;徐明;樊巖;劉曉光;郭東東;肖康
• 申請（專利權(quán)）人: 南開大學(xué);北京奇虎科技有限公司
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 天津佳盟知識產(chǎn)權(quán)代理有限公司12002
• 代理人: 侯力

【技術(shù)領(lǐng)域】

本發(fā)明屬于通用數(shù)據(jù)壓縮技術(shù)領(lǐng)域，特別涉及一種基于分塊排序思想的壓縮預(yù)處理方法及兩種解決方案。

【背景技術(shù)】

每天有大量的網(wǎng)絡(luò)數(shù)據(jù)產(chǎn)生于互聯(lián)網(wǎng)。據(jù)統(tǒng)計，每過一秒，twitter上有超過6000條信息發(fā)布，google上有超過4萬次搜索，全球有超過200萬封郵件被發(fā)送。截至2016年3月，至少有46.6億網(wǎng)頁是可檢索的。由此帶來的線下日志記錄數(shù)據(jù)，線下文件存儲數(shù)據(jù)等的規(guī)模也非常大。這類數(shù)據(jù)具有規(guī)模相當(dāng)巨大、格式相對一致的特點(diǎn)。高效的壓縮算法是降低存儲、傳輸開銷，提升用戶體驗(yàn)的最直接而有效的方式。現(xiàn)階段廣泛應(yīng)用于大規(guī)模數(shù)據(jù)壓縮的算法大部分都是Lz77系列的算法，如Gzip算法、Snappy算法等。Lz77系列算法的優(yōu)勢在于可以在相對短的時間內(nèi)獲得比較好的壓縮效果。

Lz77系列算法的原理為：將在當(dāng)前字符之前讀入的一部分字符串作為字典，當(dāng)新字符與字典中字符匹配時，用三元組(偏移量off，匹配長度length，下個字符c)表示新字符。偏移量off表示搜索緩存中的匹配字符串相對于搜索緩存的起始位置的偏移量，匹配長度length表示匹配字符串的字符數(shù)目，下個字符c表示先行緩存中匹配字符串之后的第一個字符。簡而言之，就是在一定范圍內(nèi)通過位置信息替換重復(fù)數(shù)據(jù)，以達(dá)到數(shù)據(jù)緊縮的目的。一個Lz77算法的例子如表1所示。其中第五步中字符串the被三元組(4，3，o)替換，達(dá)到降低存儲字節(jié)的目的。

表1

現(xiàn)實(shí)環(huán)境中，重復(fù)字符串的位置可能分布相對不集中，使得重復(fù)字符串的位置偏移量大于窗口長度，這樣重復(fù)字符串便不能被三元組替換掉。

【發(fā)明內(nèi)容】

本發(fā)明的目的是克服現(xiàn)有技術(shù)存在的上述不足，提供一種通用的基于分塊排序思想的壓縮預(yù)處理方法，本發(fā)明在現(xiàn)有的Lz77算法思想的基礎(chǔ)上，通過對信源的結(jié)構(gòu)化重組(分塊、排序)，將重復(fù)數(shù)據(jù)聚類，使Lz77算法的優(yōu)勢更好地展現(xiàn)出來，進(jìn)一步提高算法在壓縮率和壓縮速率上的表現(xiàn)。

本發(fā)明技術(shù)方案

一種通用的基于分塊排序思想的壓縮預(yù)處理方法，包括：

步驟1，按照預(yù)設(shè)尺寸或規(guī)則將信源分塊，稱作信源塊，并按信源塊的順序進(jìn)行編號；

步驟2，每一個信源塊視作一個整體，依照字典序?qū)π旁磯K排序，按照排序后的順序記錄信源塊編號；

步驟3，對步驟2記錄的信源塊的編號，首先進(jìn)行二進(jìn)制化以整數(shù)形式存儲而不是字符串形式的操作初步降低存儲字長，之后使用Lz77系列算法壓縮；對排序后的信源塊集合，直接使用Lz77系列算法壓縮；

步驟4，將壓縮結(jié)果以二進(jìn)制形式輸出至文件；

其中所述預(yù)設(shè)尺寸是根據(jù)實(shí)際信源的特征決定的，需要同時考慮到信息的完整性和信息塊的獨(dú)立性；對于日志一類的信源，適合將一行數(shù)據(jù)作為一個信源塊；對文件集一類的信源，適合取一個不大于平均文件大小的閾值作為信源塊的尺寸。

其中，步驟1所述的分塊形式包括：嚴(yán)格按照固定尺寸將完整信源切分成若干塊；或按照設(shè)定的尺寸閾值，在保證信息完整的情況下分塊大小在閾值上下波動；或在保證信息完整的情況下，根據(jù)信源特征預(yù)設(shè)分塊規(guī)則，將信源切分成若干塊，對信源塊的尺寸沒有強(qiáng)制要求。所述的編號方式包括：顯式編號和隱式編號；顯示編號是指通過添加額外信息來記錄信源塊在信源中的位置信息，隱式編號是指將信源塊中某一成分作為編號的依據(jù)，不在塊中添加新的信息；編號類型包括：使用數(shù)字進(jìn)行編號，或者使用字母進(jìn)行編號。

步驟2所述對信源塊排序方式包括：根據(jù)信源的數(shù)據(jù)特征，信源包括字符型信源和數(shù)字型信源，選擇按照字典序排序或是按照數(shù)值關(guān)系排序。或者根據(jù)實(shí)際生產(chǎn)要求包括對處理速率的要求和對資源占用的要求，選擇按照首幾位字符字典序排序或按照特定信息字典序排序的排序方式；記錄編號的方式包括：對于顯式編號的信源，統(tǒng)一將編號進(jìn)行順序存儲，或者分開將每一塊的編號與信源塊一起存儲；對于隱式編號的信源，不需要對編號進(jìn)行額外的存儲。

步驟3所述對記錄的信源塊編號進(jìn)行降位處理包括：根據(jù)編號的特征，通過二進(jìn)制化、減掉數(shù)值分布下確界或者編碼的手段，降低編碼存儲所需的位數(shù)。

實(shí)際生產(chǎn)中，NGINX文件格式是一種常用的日志記錄格式，其默認(rèn)格式為：

log_format access$remote_addr–$remote_user[$time_local]“$request”$status$body_bytes_sent“$http_referer”“$http_user_agent”$http_x_forwarded_for