[發明專利]基于自適應瞬時熵的無損數據壓縮算法

在審

• 申請號: 202211089596.8
• 申請日: 2022-09-07
• 公開（公告）號: CN115913246A
• 公開（公告）日: 2023-04-04
• 發明（設計）人: 奚彩萍;武彥霞
• 申請（專利權）人: 江蘇科技大學
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 南京正聯知識產權代理有限公司 32243
• 代理人: 李寰

本發明屬于數據處理技術領域，具體地說，是一種基于自適應瞬時熵的無損數據壓縮算法，包括壓縮端與解壓縮端，所述壓縮端由輸入數據流、查找表、瞬時熵編碼、最高標志位、序列化器五個部分組成，所述解壓縮端由反序列化器、最高標志位、瞬時熵解碼、查找表、輸出數據流五個部分組成，具體包括壓縮流程、解壓縮流程和查找表更新流程，本發明的壓縮過程通過查找表的占用率計算瞬時熵并自適應熵編碼，支持連續快速數據流的處理；解壓縮端從接收到壓縮數據流的首位就開始解碼操作，有效提高了壓縮速率；而且該算法運算量小，可以在有限資源下實現。

技術領域

本發明屬于數據處理技術領域，具體地說，是一種基于自適應瞬時熵的無損數據壓縮算法。

背景技術

信息時代的來臨，每天都會產生數以億計的信息數據，這給數據的存儲、傳輸和處理帶來了巨大挑戰。為了節省存儲空間、提高數據傳輸速度，有必要使用數據壓縮技術。數據壓縮技術通過去除過多冗余信息，可以降低數據存儲成本并提高數據傳輸速度，因此，數據壓縮技術具有重要的研究意義與實際價值。數據壓縮算法是實現數據壓縮的前提和基礎，可分為無損壓縮和有損壓縮兩類。有損壓縮是指在允許損失一定信息的前提下，壓縮掉部分無關緊要的數據；而無損壓縮通過對數據進行編碼處理以保存原始信息，所以可以從被壓縮的數據中恢復其原始值，且沒有數據質量的損失。

無損數據壓縮算法按照壓縮模型主要分為兩類，基于統計壓縮算法和基于字典壓縮算法。算術編碼是著名的基于統計模型的壓縮算法，它采用了香農信息熵，通過將整個輸入字符串轉換為一個長度很長的數值，而表示這個數值所需要的二進制位數比源數據本身小，以此達到數據壓縮的目的；霍夫曼編碼也是基于統計模型的壓縮算法，它的工作原理是將數據字符出現的頻率排序后建立自下而上的二叉樹，然后從根節點一直往下遍歷直到所有的字符都出現在二叉樹的節點為止，接著為所有的左子樹賦值0，所有的右子樹賦值1，確定原始符號的碼字，通過將最短的代碼分配最常見的數據模式完成數據壓縮。另一種基于字典模型的無損壓縮算法是用簡單的代碼代替復雜的原數據字符串，例如LZW算法，它將每個第一次出現的字符串存儲到一個字符串表中，并用唯一的數字作為其代碼來代替字符串，壓縮時只存儲其代碼而不是原始字符串，從而進行數據壓縮，在解壓縮時，使用壓縮時生成的字符串表，在壓縮或解壓縮完成后，這個字符串表被丟棄，不會占用額外空間。霍夫曼編碼技術運算簡單，可使編碼之后的字符串平均長度降低，但是需要計算數據流出現符號的頻率，壓縮時間較長。而且當數據符號出現概率差距不明顯時，該編碼技術效果不理想。算術編碼理論上可達到良好的壓縮率，但在實際實現過程非常復雜，需要較大的存儲空間和功耗。基于字典壓縮算法的壓縮效果和數據出現的重復度、字典大小密切相關，因而壓縮效果不固定。基于深度學習的壓縮算法會使用大量的計算，是專門處理圖像數據的，而不處理數據流，不能應用于文本數據流壓縮。

發明內容

為了解決上述技術問題，本發明提出一種基于自適應瞬時熵的無損數據壓縮算法。該算法在壓縮端接收連續快速的輸入數據流，基于查找表的占用率計算瞬時熵并自適應熵編碼，輸出壓縮數據流；解壓縮端接收到壓縮數據流的首位就開始解碼操作，并始終保持使用與壓縮端相同的查找表，最終恢復出原始數據符號。

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

一種基于自適應瞬時熵的無損數據壓縮算法，該壓縮算法工作時會考慮查找表匹配結果和被占用率，根據接收到的數據流計算瞬時熵，自適應執行熵編碼，完成壓縮。壓縮端由輸入數據流、查找表、瞬時熵編碼、最高標志位、序列化器五個部分組成；解壓縮端由反序列化器、最高標志位、瞬時熵解碼、查找表、輸出數據流五個部分組成。

查找表總行數為K，被占用的行數為k，是由輸入數據流中出現概率較大的數據符號組成，每行的數據符號都是N位。查找表每行都有與之對應的一個M位的行索引，M的計算如下：