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

有效

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

1.一種使用前綴預測的位自適應編碼方法，其特征在于，包括如下步驟：

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

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

c、前綴和一個字符集合對應，對字符串的前綴進行判定，并對可能跟在該前綴后的所有字符的概率進行預測，為此前綴產生一個預測表；

d、基于預測表，產生一棵對應的使預測表中的字符盡可能不均衡的二值樹結構，結束于葉子節點，每一個葉子節點都包含一個單獨的字符；

e、確定從根節點到每一字符的路徑，樹中每個分支都被指定了一個概率；

f、利用從根節點到相關字符的葉子節點的一條最短路徑上所有分支指定的概率來編碼或解碼一個字符。

2.根據權利要求1所述使用前綴預測的位自適應編碼方法，其特征在，于二值樹結構的建立步驟包括：

a、從根節點開始，每一個節點都選擇一個區別位，此區別位是單個的數位；

b、所有的字符都以在步驟a中選擇的區別位為基礎，在每一個節點被分成0組和1組，分組是按區別位上的值來進行，結束于葉子節點，每一個葉子節點都包含一個單獨的字符，后繼節點、根節點以及葉子節點都包含在節點集合中，單個字符都包含在字符集合中；

c、區別位的選擇應使按此區別位產生的0組中的已知字符的概率總和與1組的已知字符的概率總和的差異應達到最大；

d、若某個位在一個父節點中已經用作過區別位，它就不能在后面的節點中被再次使用，如果一個節點只包含單個已知字符，那么將選擇區別位使得包含這個已知字符的字符組中的所有字符的概率和達到最大，如果一個節點不包含已知字符，選擇的區別位應使1組和0組中的未知字符的差異最大。

3.根據權利要求1所述使用前綴預測的位自適應編碼方法，其特征在于：

樹結構中為每一個分支指定概率對應于字符集合中包含的字符的概率；

概率已知的字符的概率用預測表來表示；

剩余的字符子集：即具有未知概率、不精確概率或人工指定的概率的字符的概率總和用ESC值表示；

和具有未知概率、不精確概率和人工指定概率的字符相比，那些具有已知概率的字符具有更高的優先級。

4.根據權利要求1所述使用前綴預測的位自適應編碼方法，其特征在于，為樹中的每一個分支指定概率的方法包括：每一個節點的分支概率都被表示為一對浮點數或是有理數，每個節點的左支和右支被同時賦值，且左支和右支的概率和應為1。

5.根據權利要求4所述使用前綴預測的位自適應編碼方法，其特征在于，賦值操作分為兩步：首先，對0組和1組的已知字符分別求概率和，這兩個和用Z_p和O_p表示，若其中一個為0，或兩個全為0，Z_p和O_p須重新用0組和1組中的所有字符的概率相加算得左支概率Z_p/(Z_p+O_p)和右支概率Z_p/(Z_p+O_p)。

6.根據權利要求1所述使用前綴預測的位自適應編碼方法，其特征在于，預測表包括產生一個或多個下列表：零階表、一階表、二階表和三階表。

7.根據權利要求1所述使用前綴預測的位自適應編碼方法，其特征在于，所述排序步驟可以包括或不包括進行一個或多個下列操作：一個巴羅斯—維勒(Burrows-Wheeler)變換和前移(Move-to-front)變換。

8.根據權利要求1所述使用前綴預測的位自適應編碼方法，其特征在于，所述編碼是標準算術編碼。

9.根據權利要求1所述使用前綴預測的位自適應編碼方法，其特征在于，通過對字符串進行編碼后，用來壓縮或解壓縮數據。

10.根據權利要求1所述使用前綴預測的位自適應編碼方法，其特征在于，終止葉子是和一個字符的概率相聯系的，此概率可能來自于先驗知識，也可能來自于之前的統計數據，也可能未知，但通過公式將其進行模型化。