| 本条目存在以下问题,请协助 改善本条目或在 讨论页针对议题发表看法。
| 此条目缺少有关应用的信息。 (2022年12月27日) 请扩充此条目相关信息。讨论页可能有详细细节。 |
|
格伦布编码(英语:Golomb coding)是一种无失真资料压缩方法,由数学家所罗门·格伦布在1960年代提出。其优点为易于编码与解码,另外对于拥有几率分布为几何分布
的资料,格伦布编码是最佳的前缀码,且能无限逼近该资料的熵,目前广泛用于无损影像压缩。
编码的建立
令输入值为正整数
,参数值为正整数
,输出值格伦布码为
,其中
由两种编码组合而成,
,
:一进制编码,
:截断二进制编码。
计算
与
。
。
将
做一进制编码,
做截断二进制编码即可得到
。
格伦布-莱斯编码中的商数
指示了所在区块,而
指示所在区块内部的位置。如上图,对整数
做格伦布-莱斯编码,
代表区块、
表示区块内部位置、
为参数,每个区块的大小皆相等且长度为
,特别注意当编码方式为格伦布-莱斯编码时,即
为
的整数次方,所有
的编码长度相等。
参数
是伯努利过程的函数,其中伯努利过程的参数
定义为
,则
的所在区间为此伯努利过程的中位数-1到中位数+1之间。如下式:
当
足够大时,我们可以将其表示成,
。
格伦布编码主要是针对非负整数进行编码,但也可以使用重叠(Overlap)与交错(Interleave)扩展至对所有整数进行编码。令一串用于编号的数列,(0,1,2,...),给予非负整数偶数编号,给予负整数奇数编号,使得排列方式如下,(0,-1,1,-2,2,...),即非负整数
映射至
,负整数
映射至
。
莱斯编码
莱斯编码(Rice coding,由Robert F. Rice所提出),为一种前缀码,归属于格伦布编码的子集合,参数
为
的整数次方,即
。此种特例未必是所有格伦布编码中的最佳编码方式,但由于目前电脑为二进制运算,莱斯编码能快速且有效地以二进制运算实现。
性质
格伦布编码为一种范氏霍夫曼编码。
算法
- 选择参数
![{\displaystyle M}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
- 待编码数值为
,计算:
- 商数:
![{\displaystyle q=\left\lfloor {\frac {n}{m}}\right\rfloor ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/278d5d48090d633b137feada65bbbb7fc55f054a)
- 余数:
。
- 编码
- 商数编码,对
进行一进制编码,得到
。
- 余数编码,对
进行截断二进制编码,得到
。
- 合并,
。
- 输出
![{\displaystyle c=(u,b)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02d7e5fe4bcd06c6189de4c30ea8a5fb11b838ce)
范例
设 M = 10。则
.
商数编码
|
q |
输出位元
|
0 |
0
|
1 |
10
|
2 |
110
|
3 |
1110
|
4 |
11110
|
5 |
111110
|
6 |
1111110
|
![{\displaystyle \vdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8039d9feb6596ae092e5305108722975060c083) |
|
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 (页面存档备份,存于互联网档案馆)