[發明專利]使用控制符的半動態數據壓縮算法

有效

• 申請號: 201910109403.2
• 申請日: 2019-02-10
• 公開（公告）號: CN109831211B
• 公開（公告）日: 2023-04-11
• 發明（設計）人: 張雪琴;請求不公布姓名
• 申請（專利權）人: 張元囝
• 主分類號: H03M7/40
• 分類號: H03M7/40
• 代理公司: 長春眾邦菁華知識產權代理有限公司 22214
• 代理人: 尹慶娟

本發明應用于數據的無損壓縮領域。本發明通過在壓縮編碼過程中使用控制符并可附加信息的方式對壓縮過程進行指導，控制編碼方式，從而實現數據壓縮。控制符所附加信息需要預先對待壓縮數據進行分析、評估而獲得。編解碼過程中使用碼表/樹，碼表/樹的生成和更新基本是在控制符的指導下半動態地實現的，更新較為及時，算力消耗也相對不高，并且擁有無需另外附加碼表/樹信息的優點。

技術領域

數據壓縮是指在不丟失有用信息的前提下，縮減數據量以減少存儲空間，提高其傳輸、存儲和處理效率，或按照一定的算法對數據進行重新組織，減少數據的冗余和存儲的空間的一種技術方法。一些機制是可逆的，這樣就可以恢復原始的數據，這種機制稱為無損數據壓縮；另外一些機制為了實現更高的壓縮率允許一定程度的數據損失，這種機制稱為有損數據壓縮。本發明被應用于數據的無損壓縮領域。

背景技術

常見的實用無損壓縮編碼算法有RLE、Huffman、LZ系列等等。人們一直在尋找適應于不同場合下具有更高效率的算法。在數據壓縮的不同階段、場合，有著對時間消耗、空間消耗、壓縮比率、算法的復雜程度等等的不同需求，本算法在這之間相對于其他算法取得了一定程度的平衡。

發明內容

本發明目的在于，提供一種數據壓縮算法方案，在時間消耗、空間消耗、壓縮比率、算法的復雜程度等等之間相對于其他算法取得一定程度的平衡。本發明主要是通過下述技術方案得以實現的。

正式開始壓縮編碼前，既可以通過對待壓縮數據進行掃描，也可以采用其他評估方法，預先獲取待壓縮數據的（可以是近似的）統計特征。典型的統計特征包括但不限于每個基本碼的出現頻次、首次出現位置、最后一次出現位置、基本碼的個數：這里基本碼是指待壓縮數據在壓縮編碼過程中使用的一個基本編碼符號，常常是1個字節，但也可能是連續的若干bit信息的組合，譬如一個詞組；待壓縮數據可完全劃分為若干基本碼；其中各基本碼的出現頻次是必須預先獲得的。

在壓縮編碼中使用控制符并可附加信息的方式對壓縮過程進行指導，控制編碼方式：所謂控制符類似計算機匯編語言的偽代碼概念，它并不直接對應待壓縮數據中的基本碼，僅用來控制編碼方式、指導編碼過程；典型的控制符包括但不限于：引導符、行程符、退出符；引導符類似與動態哈夫曼編碼中的NYT碼，它表示與之相關的編碼（基本碼或控制符）尚未在之前的壓縮編碼過程中出現，是首次出現；與之對應，退出符表示相關的編碼在其后的（一段或全部）編碼中將不再出現；行程符表示相關的基本碼會連續重復出現；典型的附加信息有與引導符配合的基本碼及該基本碼的頻次信息（既可以是精確的頻次數形式也可以是近似的出現概率的形式或其他形式）；與行程符配合的游程長度信息；退出符可不附加信息；其中引導符在本壓縮算法中是必需的。

并不需要預先構造類似Huffman編碼或Fano編碼所必須的較大規模的碼表/樹，待壓縮數據中的基本碼對應的壓縮數據中的壓縮碼表并不以附加碼表/樹的形式給出，這些信息直接在壓縮編碼過程中生成并更新。所有編碼（基本碼或控制符）與壓縮碼的對應關系組成了碼表/樹，本壓縮算法符合一般規律，碼表/樹中原則上使出現頻次高的編碼（基本碼或控制符）盡可能對應相對較短的壓縮碼。引導符、退出符等控制符可累次改變碼表/樹，行程符可改變編碼方式。引導符通常會在碼表/樹中增加一條對應信息，除非附加信息表明沒有必要增加；而退出符則相反，會刪除一條對應信息。

半動態的“半”這里意思是碼表/樹并不在一直試圖被改變。本壓縮算法通常并不像動態Huffman編碼那樣一直試圖改變碼表/樹，而是在遇到特定的控制符時才嘗試改變，因此也相對降低了算力的耗費；一種例外情形是解碼時可以得到編碼的精確出現頻次，譬如壓縮編碼時引導符所附加信息說明了精確的出現頻次，此時也就具備了隨時修正壓縮碼長度的條件。

半動態編碼也是具有一定動態特性的，表現為，同一個編碼（基本碼或控制符），可能在壓縮編碼過程中的不同時期對應不同的壓縮碼；同一壓縮碼也可能在壓縮編碼過程中的不同時期對應同一個編碼（基本碼或控制符）。這樣的特性可及時調整壓縮碼長度，為取得更好的壓縮率創造了必要的條件。