[發明專利]一種支持SQL查詢的無損壓縮查詢方法

有效

• 申請號: 202011362702.6
• 申請日: 2020-11-27
• 公開（公告）號: CN112506876B
• 公開（公告）日: 2022-05-13
• 發明（設計）人: 陳剛;龐志飛;魯鵬;伍賽;姚暢;趙岑炯
• 申請（專利權）人: 浙江大學計算機創新技術研究院
• 主分類號: G06F16/174
• 分類號: G06F16/174;G06F16/2455;G06F16/31
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 林超

本發明公開了一種支持SQL查詢的無損壓縮查詢方法。本發明將文本數據根據預設的分隔符進行分割，分割后的文本數據形成序列集合，利用基于n?gram(n元語法)的上下文概率模型估計序列集合中各個序列的每個字符的潛在概率分布，獲得每個字符的潛在概率分布后對序列集合中各個序列進行壓縮，壓縮后的序列通過線性掃描的不解壓順序進行多種方式的查詢。本發明在保證概率分布的準確性以更好地適應數據分布的變化，并且能夠確保編碼后的數據支持不解壓的查詢，提高了查詢的效率。

技術領域

本發明涉及了一種數據壓縮領域的無損壓縮查詢方法，具體涉及了一種支持SQL查詢的無損壓縮查詢方法。

背景技術

近年來，隨著互聯網以及計算機技術的發展，網絡上的信息也呈現出爆炸式的增長。這些信息中，除了圖片視頻等數據外，由各類系統和設備產生的日志信息等文本數據也占了相當大的比重。面對如此龐大的數據量，如何更加有效地存儲和傳輸這些海量數據成了大數據時代的一項重要挑戰。在實際應用中，人們往往需要在存儲和傳輸數據之前，首先對數據進行壓縮，以此來減小數據量，從而緩和存儲和傳輸的壓力。

數據壓縮技術是減少存儲數據所需的空間大小的技術，通常分為有損壓縮和無損壓縮。本發明所涉及到的是無損壓縮技術，具體涉及到算術編碼器技術。其核心思想是將待編碼的字符序列映射到[0，1)之間的一個概率區間，每個待編碼字符都會使得原有的概率區間上繼續縮小，并且無論有多長的原始字符序列，最終都只會被編碼成一個概率區間中的值，即只有一個碼字。

算術編碼器是一種基于熵的編碼器。熵編碼器通常包含兩個核心模塊，一是用于估計字符概率的概率模型，另一個則是利用概率模型計算得到的概率進行編碼操作的編碼器。概率模型越是準確，計算得到的概率分布越是接近真實值，則編碼器得到的編碼結果越是接近原始數據的信息熵，壓縮效果則越好。在實際使用中，算術編碼器往往使用靜態概率分布，通常基于該假設的編碼方法都達不到理想的壓縮效果。

發明內容

為了解決背景技術中存在的問題和需求，本發明提供一種支持SQL查詢的無損壓縮方法。

本發明采用的技術方案如下：

本發明將文本數據根據預設的分隔符進行分割，分割后的文本數據形成序列集合，利用基于n-gram(n元語法)的上下文概率模型估計序列集合中各個序列的每個字符的潛在概率分布，獲得每個字符的潛在概率分布后對序列集合中各個序列進行壓縮，壓縮后的序列通過線性掃描的不解壓順序進行多種方式的查詢。

方法具體步驟如下：

1.按照預設的分隔符將文本數據進行切分，分割后的文本數據形成序列集合；

2.根據序列集合來建立基于n-gram(n元語法)的上下文概率模型并以前綴樹的形式存儲上下文概率模型；

3.利用算數編碼器根據序列所在路徑上的各個概率將序列集合中每一個序列編碼成碼字，完成對序列集合的壓縮過程；

4.將碼字打包成固定長度的數據包，存儲到磁盤上，獲得壓縮數據；

5.在壓縮數據上集成B+樹，提高查詢效率；

6.在壓縮數據上進行查詢。

所述步驟2具體為：

2.1建立基于n-gram的上下文概率模型，上下文概率模型是用n元語法以序列集合的前若干個字符的概率來估計下一個字符出現的概率；

針對每個序列集合中的每個字符用公式處理獲得概率：