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

有效

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

根據本發明的一種對數據進行壓縮的方法包括以下步驟：為第一字符串集合創建第一前綴樹，其中所述第一字符串集合包括多個原始字符串，其中前綴樹由父?子結點關系連接的多個結點構成，前綴樹的每條邊表示包含至少一個字符的字符串，該字符串對應于從該條邊的父結點到子結點的狀態轉移；把所述第一前綴樹中的邊所對應的、長度至少為2的字符串作為第一字符串子集；當所述第一字符串子集中的任一字符串滿足預定條件時，將該字符串分割為二個或多個字符串片段，所述字符串片段與所述第一字符串子集中未被分割的字符串一起形成分割字符串集合；使用所述第一前綴樹和所述分割字符串集合來保存所述第一字符串集合，以利用原始字符串之間的冗余而實現數據壓縮。本發明還提供了對數據進行壓縮的裝置、系統和計算機程序產品。

技術領域

本發明涉及數據庫領域，特別涉及一種利用前綴樹進行數據壓縮的方法、裝置、系統和計算機程序產品。

背景技術

數據檢索(data retrieval)是指通過數據庫管理系統(DBMS)從數據庫中獲得數據的處理。不同類型的數據存儲形式適用于不同類型的應用，并且一些類型的存儲形式則特別適用于執行特定的處理任務。

例如，樹形結構是一種普遍采用的非線性數據存儲形式，其通過一組相連的結點的形式表示，以便于描述具有分支和層次特性的數據集合。

在樹形結構中，經常會用到以下基本術語：

根結點：樹中位于頂端的結點；

子結點：沿著離開根結點的方向，直接與前一結點相連的結點；

父結點：與子結點對應的結點；

后代結點：通過重復地由一父結點前往一子結點可達的結點；

祖先結點：通過重復地由一子結點前往其父結點可達的結點；

葉結點/外部結點：沒有子結點的結點；

內部結點：具有至少一個子結點的結點；

邊：從父結點到子結點的連接；

子樹：由樹中的一個結點及其全部后代結點組成的樹。

以下介紹數據壓縮領域的近期發展。

前綴樹

前綴樹(又稱trie樹、字典樹)是一種類型的樹形結構。在前綴樹中，一個結點的全部后代結點具有相同的前綴，該前綴即為關聯于該結點的字符串(根結點對應于空的字符串)。并且，在前綴樹中，結點并不存儲與其關聯的鍵，而是通過其在樹中所處的位置來定義與其關聯的鍵，每個結點都對應從其父結點鏈接過來的邊。

一個標準的前綴樹具有以下基本性質：1)根結點無對應的邊(每條邊包含一個字符)，除根結點外每一個結點都對應一條邊(從而包含一個字符)；2)一個結點包含的字符在其對應的邊上標注，從根結點到某一結點的路徑(即，對應的一組邊)上經過的字符連接起來，為該結點對應的字符串(即，鍵)；3)每個結點的所有子結點包含的字符都不相同。

圖1示出了前綴樹的一個實例，該前綴樹由abc、abcd、abd、b、bcd、efg、hii這7個字符串構成。圖中雙圈結點表示該節點具有終止狀態(即前綴樹中存在與該節點對應的字符串)，單圈結點表示該節點不具有終止狀態。

前綴樹支持以下基本操作。

正向搜索：指在前綴樹中搜索一個已知的字符串。從根結點開始，搜索字符串的第一個字符，并根據該字符對應的邊轉到相應的子樹繼續進行搜索；在相應的子樹上，搜索字符串的第二個字符，并進一步選擇相應的子樹進行搜索；進行迭代操作，直到在某個結點處，如果所有字符都被找到，則讀取附在該結點上的信息，完成搜索，否則表示未搜索到字符串。