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

有效

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

1.一種基于分區的正整數序列壓縮方法，其特征在于，包括：

通過正整數序列X構造單調遞增正整數序列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；根據區塊Part_i+1，j計算序列C_i+1，j，

C_i+1，j＝{c_i+1，c_i+2，...，c_j}＝{s_i+1-s_i，s_i+2-s_i，...，s_j-s_i}，假設s₀＝0；

對序列C_i+1，j進行差分處理得到序列D_i+1，j＝{c_i+1-0，c_i+2-c_i+1，...，c_j-c_j-1}；

計算區塊Part_i+1，j的元素個數Count_i+1，j和序列D_i+1，j采用Golomb-Rice編碼時需要的參數b_i+1，j；采用Elias Gamma編碼對元素個數Count_i+1，j進行編碼，計作Elias_Gamma(Count_i+1，j)；采用Elias Gamma編碼對參數b_i+1，j進行編碼，計作Elias_Gamma(b_i+1，j)；將所述Elias_Gamma(Count_i+1，j)和Elias_Gamma(b_i+1，j)拼接在一起，計作info(Part_i+1，j)；

采用以b_i+1，j為參數的Golomb-Rice編碼對D_i+1，j的所有元素進行編碼，然后拼接在一起計作GRCode_i+1，j；

按照最優劃分區塊Part_i+1，j的順序拼接所述info(Part_i+1，j)，拼接為info；按照最優劃分區塊Part_i+1，j的順序拼接所述GRCode_i+1，j，拼接為Golomb-Rice-code；把info和Golomb-Rice-code拼接在一起，作為所述單調遞增正整數序列S的壓縮結果。