[發(fā)明專利]進行數據壓縮的方法、裝置、系統和計算機程序產品

有效

• 申請?zhí)枺?/td>: 201610118629.5
• 申請日: 2016-03-02
• 公開（公告）號: CN107153647B
• 公開（公告）日: 2021-12-07
• 發(fā)明（設計）人: 雷鵬
• 申請（專利權）人: 北京字節(jié)跳動網絡技術有限公司
• 主分類號: G06F16/2453
• 分類號: G06F16/2453;G06F16/22
• 代理公司: 泰和泰律師事務所 51219
• 代理人: 祝海燕

1.一種對數據進行壓縮的方法，包括：

(1)為第一字符串集合創(chuàng)建第一前綴樹，其中所述第一字符串集合包括多個原始字符串，其中前綴樹由父-子結點關系連接的多個結點構成，前綴樹的每條邊表示包含至少一個字符的字符串，該字符串對應于從該條邊的父結點到子結點的狀態(tài)轉移；

(2)把所述第一前綴樹中的邊所對應的、長度至少為2的字符串作為第一字符串子集；

(3)當所述第一字符串子集中的任一字符串滿足預定條件時，將該字符串分割為二個或多個字符串片段，所述字符串片段與所述第一字符串子集中未被分割的字符串一起形成分割字符串集合；

(4)使用所述第一前綴樹和所述分割字符串集合來保存所述第一字符串集合，以利用原始字符串之間的冗余而實現數據壓縮。

2.根據權利要求1所述的方法，其中所述步驟(3)包括：

把所述第一字符串子集中的字符串所包含的預定符號作為分割標記符，基于分割標記符將所述字符串分割為二個或更多個分割字符串。

3.根據權利要求1所述的方法，其中所述分割步驟(3)包括：

把所述第一字符串子集中的字符串與預定字符串庫進行匹配以尋找所述字符串中的匹配片段，將所述字符串分割為盡量長的與預定字符串庫匹配的片段。

4.根據權利要求1所述的方法，其中所述預定條件為字符串的長度達到預定值。

5.根據權利要求1所述的方法，其中所述步驟(4)包括：

將所述分割字符串集合作為第二字符串集合，為該第二字符串集合創(chuàng)建第二前綴樹和第二字符串子集；

基于所述第二前綴樹和第二字符串子集來保存所述分割字符串集合。

6.根據權利要求5所述的方法，其中所述步驟(4)還包括：

將所述分割字符串集合中的字符串翻轉后作為第二字符串集合。

7.根據權利要求5所述的方法，其中所述步驟(4)還包括：

將所述第一前綴樹的相應結點關聯到所述第二前綴樹的對應結點。

8.根據權利要求5所述的方法，其中所述步驟(4)還包括：

把所述第二字符串子集保存為字符串數組，其中在所述字符串數組中，所述第二字符串子集中的各個字符串通過對應的偏移量和長度來表示。

9.根據權利要求1所述的方法，其中所述原始字符串由各國語言的字母、數字、符號組成。

10.根據權利要求1所述的方法，其中所述原始字符串包括搜索關鍵字及與搜索關鍵字匹配的搜索結果。

11.根據權利要求1所述的方法，其中所述原始字符串包括即時通訊工具的聊天記錄。

12.根據權利要求1所述的方法，其中所述原始字符串包括網頁文本。

13.根據權利要求1所述的方法，其中所述前綴樹支持反向搜索操作，以實現對所述第一字符串集合的訪問。

14.根據權利要求13所述的方法，其中使用LOUDS型前綴樹(Level Ordered UnaryDegree Sequence Trie)來實現所述前綴樹。

15.根據權利要求14所述的方法，其中所述LOUDS型前綴樹依賴succinct數據架構中的rank和select操作。