[發明專利]一種壓縮和解壓縮有序整數數組的方法

有效

• 申請號: 201710786051.5
• 申請日: 2017-09-04
• 公開（公告）號: CN110019184B
• 公開（公告）日: 2021-04-27
• 發明（設計）人: 雷鵬
• 申請（專利權）人: 北京字節跳動網絡技術有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 泰和泰律師事務所 51219
• 代理人: 祝海燕

本申請公開了一種數據壓縮和解壓縮方法，該壓縮方法包括：數據提取步驟，即提取預定個數據記為數組并計算數組中相鄰兩數的差值，以及形成與數組對應的索引和數據塊；索引設置步驟，設置索引條目至少包括記錄數據塊與第一數據塊的相對位置的偏移量和記錄數組中最小數據的最小值；元數據設置步驟，根據差值設置數據塊中的元數據部分，元數據至少包括下閾值和小位寬數據的位寬，以確定數據塊的數據壓縮規則；數據壓縮步驟，即根據元數據壓縮數組中各數據以生成壓縮數值，并將壓縮數值以小位寬數據和大位寬數據形式儲存在數據塊中數據部分的詞中。解壓縮方法對應于該壓縮方法，以此提供一種存儲效率高、訪問速度快的壓縮算法。

發明領域

本申請涉及計算機機技術領域，尤其涉及數據壓縮技術領域。

背景技術

在數據庫等應用中，常常需要存儲一些整數數組的索引數據。如果直接將這些索引數據存儲在數據庫中，不僅會占用較多的磁盤空間，而且在讀取數據時會占用更多內存，使得讀取時間更長，無法滿足性能要求。

針對此場景下存儲整數數組減少存儲空間和提高讀取效率的性能要求，目前已開發出多種數據壓縮算法。其中，PForDelta算法是目前解壓縮速度較快的一種倒排文件索引壓縮算法。PForDelta算法的基礎思想是：對于待編碼的連續k個數值(如128個)，找出其中10％比例的較大數，對剩下90％的數值采取一個設定的比特寬度，而10％的大數當做異常數據單獨存儲。但是這種方法也有缺點：對兩個異常數據的間隔有限制，如果間隔過大，則需要加入更多的空間來存儲間隔，降低了數據壓縮率和訪問速度。

因此，需要一種存儲效率更高、隨機訪問速度更快的壓縮算法。

發明內容

本申請針對數據壓縮率和隨機訪問的需求，開發了一種存儲效率更高、隨機訪問速度更快的有序整數數組的壓縮算法。

本申請的目的在于，提供一種支持高速隨機訪問的壓縮有序整數數組的方案。根據該方案，可以在不損失信息的前提下對數據進行壓縮(無損壓縮)，并且可以直接在壓縮的數據上進行高速隨機訪問。該方案有效提高了存儲設備的利用率和隨機讀取數據的速度。

具體地，根據本申請的一方面，提供一種數據壓縮方法，包括：數據提取步驟，用于從待壓縮的有序數據中提取預定個數據記為一個數組(array)，并且計算所述數組中相鄰兩個數的差值(diff)，以及形成與所述數組對應的索引(index)和數據塊(block)；索引設置步驟，用于設置所述索引的索引條目，所述索引條目至少包括：用于記錄所述數據塊與第一數據塊的相對位置的偏移量(offset)，和用于記錄所述數組中的最小數據的最小值(minval)；元數據設置步驟，用于根據所述差值設置所述數據塊中的元數據部分，所述元數據至少包括：下閾值(lowater)和小位寬數據的位寬(smallbits)以用于確定所述數據塊的數據壓縮規則；以及數據壓縮步驟，用于根據所述元數據來壓縮所述數組中的各個數據以生成壓縮數值，并將所述壓縮數值以小位寬數據和大位寬數據的形式儲存在所述數據塊中的數據部分的詞中。

根據本申請的另一方面，提供一種數據解壓縮方法，用于對多個壓縮數據中的待提取數據進行解壓縮，包括：待提取數據位置確定步驟，用于計算所述待提取數據所在的數據塊的位置以及在所述數據塊的相應詞中的位置，并在所述數據塊的數據部分中獲取相應的壓縮數值；索引條目獲取步驟，用于基于所述數據塊獲取相應的索引條目，其中所述索引條目至少包括：用于記錄所述數據塊與第一數據塊的相對位置的偏移量，和用于記錄所述數據塊對應的數組中的最小數據的最小值；元數據獲取步驟，用于獲取所述數據塊的元數據部分記錄的下閾值和小位寬數據的位寬，以確定所述數據塊對應的數據壓縮規則；待提取數據恢復步驟，用于基于所述數據塊的數據壓縮規則、所述偏移量和所述最小值，計算所述壓縮數值對應的待提取數據的實際數值。