[發明專利]一種通用的基于分塊排序思想的壓縮預處理方法及應用

在審

• 申請號: 201610831693.8
• 申請日: 2016-09-20
• 公開（公告）號: CN106936439A
• 公開（公告）日: 2017-07-07
• 發明（設計）人: 王剛;劉博;黃曦;徐明;樊巖;劉曉光;郭東東;肖康
• 申請（專利權）人: 南開大學;北京奇虎科技有限公司
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 天津佳盟知識產權代理有限公司12002
• 代理人: 侯力

1.一種通用的基于分塊排序思想的壓縮預處理方法，其特征在于，包括：

步驟1，按照預設尺寸或規則將信源分塊，稱作信源塊，并按信源塊的順序進行編號；

步驟2，每一個信源塊視作一個整體，依照字典序對信源塊排序，按照排序后的順序記錄信源塊編號；

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

步驟4，將壓縮結果以二進制形式輸出至文件；

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

2.根據權利要求1所述的方法，其特征在于，步驟1所述的分塊形式和編號方式包括：

分塊形式：嚴格按照固定尺寸將完整信源切分成若干塊；或按照設定的尺寸閾值，在保證信息完整的情況下分塊大小在閾值上下波動；或在保證信息完整的情況下，根據信源特征預設分塊規則，將信源切分成若干塊，對信源塊的尺寸沒有強制要求；

編號方式：包括顯式編號和隱式編號；顯示編號是指通過添加額外信息來記錄信源塊在信源中的位置信息，隱式編號是指將信源塊中某一成分作為編號的依據，不在塊中添加新的信息；

編號類型包括：使用數字進行編號，或者使用字母進行編號。

3.根據權利要求2所述的方法，其特征在于，步驟2所述對信源塊排序方式和記錄排序后信源塊的編號的方式包括：

排序方式：根據信源的數據特征，信源包括字符型信源和數字型信源，選擇按照字典序排序或是按照數值關系排序。或者根據實際生產要求包括對處理速率的要求和對資源占用的要求，選擇按照首幾位字符字典序排序或按照特定信息字典序排序的排序方式；

記錄編號的方式：對于顯式編號的信源，統一將編號進行順序存儲，或者分開將每一塊的編號與信源塊一起存儲；對于隱式編號的信源，不需要對編號進行額外的存儲。

4.根據權利要求1所述的方法，其特征在于，步驟3所述對記錄的信源塊編號進行降位處理，包括：

根據編號的特征，通過二進制化、減掉數值分布下確界或者編碼的手段，降低編碼存儲所需的位數。

5.權利要求1所述的通用的基于分塊排序思想的壓縮預處理方法，在對NGINX格式訪問日志的壓縮預處理中的應用，其特征在于具體步驟包括：

第1，將整個信源切割為預設尺寸大小的組，每次處理一組數據；

第2，以“$request”為界將每一組中的每一條日志記錄分割，“$request”之前的成分為第一段，“$request”及其之后的成分為第二段；

第3，將當前處理的組內的所有第一段成分順序存儲zone 1，不進行排序處理；

第4，對當前處理的組內的所有第二段成分編號，然后按字典序對所有第二段排序并存儲為zone2，同時按排序后的順序保存它們的編號；

第5，使用Lz77系列算法對經過二進制化處理的zone 1、編號組、zone 2進行壓縮；

第6，重復第2步～第5步，直至所有的組都被處理；

其中第1步所述分組為預備操作，是為后續排序操作劃定范圍；分塊思想對應每次處理一行數據即一次訪問記錄，排序思想對應對每行數據的第二段即zone2進行排序。

6.根據權利要求5所述的應用，其特征在于，所述的NGINX格式支持自定義，包括log_format access$remote_addr–$remote_user[$time_local]“$request”$status$body_bytes_sent“$http_referer”“$http_user_agent”$http_x_forwarded_for信息，對任何由NGINX格式中元素組成的日志均在解決方案處理范疇。

7.根據權利要求5所述的應用，其特征在于，第1步所述的信源切割是非嚴格的，真實切割點以保證信息完整性為原則，在閾值切割點的附近移動，具體移動范圍無數值約束；切割的閾值根據信源特征進行設定，對于一條日志較長的信源，閾值設定的大一些；反之閾值設定的小一些，閾值大小的設定對所述方法沒有實質影響。