[發明專利]基于分區的正整數序列壓縮方法

有效

• 申請號: 201710110815.9
• 申請日: 2017-02-28
• 公開（公告）號: CN107026652B
• 公開（公告）日: 2020-02-14
• 發明（設計）人: 瞿有利;李俊廷
• 申請（專利權）人: 北京交通大學
• 主分類號: H03M7/40
• 分類號: H03M7/40
• 代理公司: 11255 北京市商泰律師事務所
• 代理人: 黃曉軍

本發明提供了一種基于分區的正整數序列壓縮方法。該方法主要包括：通過正整數序列X構造單調遞增正整數序列S；構造所述單調遞增正整數序列S的有向無環圖G；使用迪杰斯特拉算法計算所述有向無環圖G中從源點到匯點的最短路徑；根據上述最短路徑，得到單調遞增正整數序列S的最優劃分；計算最優劃分中每一個區塊的元素個數和每一個區塊采用Golomb?Rice編碼時需要的參數b；采用Elias Gamma編碼對元素個數進行編碼和參數b進行編碼，采用Golomb?Rice編碼對每一個區塊內所有元素進行編碼，根據編碼結果得到單調遞增正整數序列S的壓縮結果。本發明綜合了序列分區編碼利用正整數序列的局部“聚集”性質與Golomb?Rice編碼的高效性等優點，提高了正整數序列的壓縮性能。

技術領域

本發明涉及數據處理技術領域，尤其涉及一種基于分區的正整數序列壓縮方法。

背景技術

正整數序列壓縮的主要目的是減少正整數序列占用的存儲空間、減少使用時磁盤讀取次數和加快數據的傳輸效率。比如：在信息檢索中，正整數序列的壓縮常用于壓縮倒排索引中文檔標識符(docID)序列、頻率(frequency)序列和位置(position)序列，一方面可以節省倒排索引文件占用的存儲空間；另一方面可以減少查詢時的磁盤和內存讀取次數。

互聯網上數據呈現爆炸式增長，由這些數據構造的倒排索引需要的存儲空間也越來越大，因此，開發一種對正整數序列進行有效的壓縮編碼方法是一個亟待解決的問題。

發明內容

本發明的實施例提供了一種基于分區的正整數序列壓縮方法，以實現對正整數序列進行有效的壓縮編碼。

為了實現上述目的，本發明采取了如下技術方案。

一種基于分區的正整數序列壓縮方法，包括：

通過正整數序列構造單調遞增正整數序列S；

構造所述單調遞增正整數序列S的有向無環圖G，該有向無環圖G的頂點為v₀，v₁，...，v_n-1，v_n；

使用迪杰斯特拉算法計算所述有向無環圖G的從v₀到v_n的最短路徑π＝(v₀，v_i)(v_i，v_j)...(v_m，v_n)；

根據所述最短路徑π＝(v₀，v_i)(v_i，v_j)...(v_m，v_n)，得到所述單調遞增正整數序列S的最優劃分為δ＝{s₁，s₂，...，s_i}{s_i+1，s_i+2，...，s_j}...{s_m+1，s_m+2，...，s_n}，區塊{s_i+1，s_i+2，...，s_j}記作Part_i+1，j；