[發(fā)明專利]使用前綴預測的位自適應編碼方法

有效

• 申請?zhí)枺?/td>: 02104553.4
• 申請日: 2002-02-08
• 公開（公告）號: CN1369970A
• 公開（公告）日: 2002-09-18
• 發(fā)明（設計）人: 胡笑平
• 申請（專利權）人: 胡笑平
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 中原信達知識產(chǎn)權代理有限責任公司
• 代理人: 陳肖梅,王達佐

技術領域

本發(fā)明涉及數(shù)據(jù)的壓縮技術，用于實現(xiàn)有效的存儲和傳輸。

背景技術

由于內存容量和傳輸帶寬資源的有限性，在對大量數(shù)據(jù)進行存儲和傳輸?shù)倪^程中，需要對數(shù)據(jù)進行壓縮。經(jīng)過壓縮，數(shù)據(jù)量變少，不但節(jié)省了帶寬，而且能更加有效地利用信息通道；同樣，壓縮后的數(shù)據(jù)比未被壓縮的數(shù)據(jù)占用更小的內存。為此，人們提出了各種不同的編碼技術，例如：跑長編碼、哈夫曼編碼、算術編碼和適應性統(tǒng)計技術等等，這些技術都能以無損的形式壓縮數(shù)據(jù)。把這些無損編碼技術和其它的一些算法(例如：Burrows-Wheeler?transform)結合使用還能取得更好的壓縮效果。

但是，這些技術存在的不足在于：

跑長編碼的一種簡單形式是首先找出數(shù)據(jù)中的一個或多個出現(xiàn)頻率較高的字符串，例如單詞“the”，然后把這些高頻率詞匯用一些比其本身短很多的碼字來代表。這種方法對英文文本能達到將近4∶1的壓縮率。跑長編碼的一些較為復雜的形式也被經(jīng)常使用。跑長編碼的一個主要缺點是那些出現(xiàn)頻率高的數(shù)據(jù)串常常不能作為先驗知識事先知道，于是需要建立模型：即假定一些字符作為高頻率字符，并為其分配相應的碼字。然而當實際數(shù)據(jù)中經(jīng)常重復的字符和事先定好的模型有出入時，壓縮率便不能達到預期目標。

哈夫曼編碼及其變種算法在從摩爾斯碼到UNIX的打包/解包、壓縮/解壓縮命令的許多領域都有應用。哈夫曼編碼及其變種算法包括決定字符的出現(xiàn)頻率，并為不同的頻率分配不同的碼字。頻繁出現(xiàn)的字符具有較短的碼字，而較少出現(xiàn)的字符則有較長的碼字。一般從底部最長的碼字開始，逐步向上結束于最短的碼字來產(chǎn)生二值樹結構。雖然由下到上的方式對于建樹比較適合，但在實際讀取時還是采用由上向下的方式，例如解碼器就是從頂部根節(jié)點出發(fā)，根據(jù)位編碼信息，按照樹的不同分支追溯下去。按照這種方法，最經(jīng)常出現(xiàn)的字符會最先被找到。哈夫曼編碼的一個缺點是每個字符的出現(xiàn)概率不能預先知道，于是，通常用預先建立的頻率來產(chǎn)生哈夫曼二值樹，而對于一組特定字符集合，這些頻率可能適合，也可能不適合。

算術編碼也有著廣泛的應用。和哈夫曼編碼一樣，算術編碼也是一種基于數(shù)據(jù)概率模型的無損壓縮技術。和哈夫曼編碼不同的是，算術編碼產(chǎn)生的是一個單獨的符號而非若干獨立的碼字，數(shù)據(jù)被作為0到1之間的一個實數(shù)來進行編碼。不湊巧的是，算術編碼也有一系列的缺點：首先，算術編碼比其它編碼算法慢得多，當算術編碼使用了高階預測模型時，這一點表現(xiàn)得尤為嚴重；其次，由于算術編碼會更加真實的反映在編碼過程中使用的概率分布模型，因而不準確或是不正確的概率模型會導致低下的壓縮效率。

一般來說，當數(shù)據(jù)的概率較為隨機時，算術編碼的壓縮效率高于哈夫曼編碼。

適應性統(tǒng)計技術可以解決先驗模型帶來的某些問題。一般來說，適應性編碼技術提供了對從未在字符表或是前綴表中出現(xiàn)的字符的一種編碼方法。當一個未知的字符出現(xiàn)時，首先編一個“殊況”ESC碼，將其送入碼流中，然后編碼器繼續(xù)用較低階的前綴對其進行編碼，并將增加的數(shù)據(jù)也送入碼流。最低階的預測表(通常為0階表)必須包含所有可能的字符，便于每一個可能字符都能在其中被找到，ESC碼也必須以一定的概率來編碼。然而，由于新字符的不可預知性，僅從前面的數(shù)據(jù)不可能對ESC碼的概率進行精確的估計，因此，一般具有給定前綴的ESC值概率只能按經(jīng)驗確定，導致編碼效率不能達到最優(yōu)。這樣，在適應性編碼中引進ESC碼帶來了兩個問題。一個是ESC碼只能給出關于新字符的有限信息，新字符仍然按照較低階的前綴預測表來編碼；第二個問題是ESC碼的概率不能被精確地建模。

發(fā)明內容

本發(fā)明的目的在于克服上述現(xiàn)有技術的不足和缺陷，提出一種高倍的無損壓縮技術，使其不再具有前面所述技術的各種缺點，降低在自適應性編碼算法中ESC碼概率模型的不精確性對編碼帶來的影響，從而有效壓縮數(shù)據(jù)。

實現(xiàn)上述目的的技術方案是一種使用前綴預測的位自適應編碼方法，包括如下步驟：

a、對字符串里的字符進行排序，每一字符用二進制表示。

b、每一個相關字符都包含在具有一個上下文的字符集合里，上下文中包含一個前綴。

c、前綴和一個字符集合對應，對字符串的前綴進行判定，并對可能跟在該前綴后的所有字符的概率進行預測，為此前綴產(chǎn)生一個預測表。一般情況下，前綴包含一個或兩個元素。雖然前綴的尺寸可以變化，但其階數(shù)最好小于或等于3以便控制數(shù)據(jù)量；

d、基于預測表，產(chǎn)生一棵對應的二值樹結構，這種樹是為了使預測表中的字符盡可能的不均衡。