| 本條目存在以下問題,請協助 改善本條目或在 討論頁針對議題發表看法。
| 此條目缺少有關应用的信息。 (2022年12月27日) 請擴充此條目相關信息。討論頁可能有詳細細節。 |
|
格倫布編碼(英語:Golomb coding)是一種無失真資料壓縮方法,由數學家所羅門·格倫布在1960年代提出。其優點為易於編碼與解碼,另外對於擁有機率分布為幾何分佈的資料,格倫布編碼是最佳的前綴碼,且能無限逼近該資料的熵,目前廣泛用於無損影像壓縮。
編碼的建立[编辑]
令輸入值為正整數,參數值為正整數 ,輸出值格倫布碼為 ,其中 由兩種編碼組合而成,
,:一进制編碼,:截斷二進制編碼。
計算 與 。
。
將 做一进制編碼, 做截斷二進制編碼即可得到。
格倫布-萊斯編碼中的商數指示了所在區塊,而指示所在區塊內部的位置。如上圖,對整數 做格倫布-萊斯編碼, 代表區塊、 表示區塊內部位置、 為參數,每個區塊的大小皆相等且長度為 ,特別注意當編碼方式為格倫布-萊斯編碼時,即 為 的整數次方,所有的編碼長度相等。
參數 是伯努利過程的函數,其中伯努利過程的參數 定義為 ,則 的所在區間為此伯努利過程的中位數-1到中位數+1之間。如下式:
當 足夠大時,我們可以將其表示成,。
格倫布編碼主要是針對非負整數進行編碼,但也可以使用重疊(Overlap)與交錯(Interleave)擴展至對所有整數進行編碼。令一串用於編號的數列,(0,1,2,...),給予非負整數偶數編號,給予負整數奇數編號,使得排列方式如下,(0,-1,1,-2,2,...),即非負整數 映射至 ,負整數 映射至 。
萊斯編碼[编辑]
萊斯編碼(Rice coding,由Robert F. Rice所提出),為一種前綴碼,歸屬於格倫布編碼的子集合,參數 為 的整數次方,即 。此種特例未必是所有格倫布編碼中的最佳編碼方式,但由於目前電腦為二進位運算,萊斯編碼能快速且有效地以二進位運算實現。
格倫布編碼為一種范氏霍夫曼編碼。
演算法[编辑]
- 選擇參數
- 待編碼數值為 ,計算:
- 商數:
- 餘數: 。
- 編碼
- 商數編碼,對 進行一进制編碼,得到 。
- 餘數編碼,對 進行截斷二進制編碼,得到 。
- 合併,。
- 輸出
設 M = 10。則 .
商數編碼
|
q |
輸出位元
|
0 |
0
|
1 |
10
|
2 |
110
|
3 |
1110
|
4 |
11110
|
5 |
111110
|
6 |
1111110
|
|
|
N |
|
|
餘數編碼
|
r |
偏移 |
二進位 |
輸出位元
|
0 |
0 |
0000 |
000
|
1 |
1 |
0001 |
001
|
2 |
2 |
0010 |
010
|
3 |
3 |
0011 |
011
|
4 |
4 |
0100 |
100
|
5 |
5 |
0101 |
101
|
6 |
12 |
1100 |
1100
|
7 |
13 |
1101 |
1101
|
8 |
14 |
1110 |
1110
|
9 |
15 |
1111 |
1111
|
|
選擇42作為編碼時,42會被拆成 及 ,編碼為11110010,而商數編碼尾數必為0,能標示商數編碼位元的結束。
參考來源[编辑]
- Golomb, S.W. (1966). , Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401 (页面存档备份,存于互联网档案馆)
- R. F. Rice (1971) and R. Plaunt, , "Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data, " IEEE Transactions on Communications, vol. 16(9), pp. 889–897, Dec. 1971. (页面存档备份,存于互联网档案馆)
- R. F. Rice (1979), "Some Practical Universal Noiseless Coding Techniques, " Jet Propulsion Laboratory, Pasadena, California, JPL Publication 79—22, Mar. 1979.
- Witten, Ian Moffat, Alistair Bell, Timothy. "Managing Gigabytes: Compressing and Indexing Documents and Images." Second Edition. Morgan Kaufmann Publishers, San Francisco CA. 1999 ISBN 1-55860-570-3
- David Salomon. "Data Compression",ISBN 0-387-95045-1.
- S. Büttcher, C. L. A. Clarke, and G. V. Cormack. Information Retrieval: Implementing and Evaluating Search Engines (页面存档备份,存于互联网档案馆). MIT Press, Cambridge MA, 2010.
- https://en.wikipedia.org/wiki/Golomb_coding (页面存档备份,存于互联网档案馆)