格伦布编码
本条目存在以下问题,请协助改善本条目或在讨论页针对议题发表看法。
|
格伦布编码是一种无失真资料压缩方法,由数学家所罗门·格伦布在1960年代提出。其优点为易于编码与解码,另外对于拥有几率分布为几何分布的资料,格伦布编码是最佳的前缀码,且能无限逼近该资料的熵,目前广泛用于无损影像压缩。
编码的建立
令输入值为正整数 ,参数值为正整数 ,输出之格伦布码为 ,其中 由两种编码组合而成,
, :一进制编码, :截断二进制编码。
计算 与 。
。
将 做一进制编码, 做截断二进制编码即可得到 。
格伦布-莱斯编码中的商数 指示了所在区块,而 指示所在区块内部的位置。如上图,对整数 做格伦布-莱斯编码, 代表区块、 表示区块内部位置、 为参数,每个区块的大小皆相等且长度为 ,特别注意当编码方式为格伦布-莱斯编码时,即 为 的整数次方,所有 的编码长度相等。
参数 是伯努利过程的函数,其中伯努利过程的参数 定义为 ,则 的所在区间为此伯努利过程的中位数-1到中位数+1之间。如下式:
当 足够大时,我们可以将其表示成, 。
使用符号整数
格伦布编码主要是针对非负整数进行编码,但也可以使用重叠(Overlap)与交错(Interleave)扩展至对所有整数进行编码。令一串用于编号的数列,(0,1,2,...),给予非负整数偶数编号,给予负整数奇数编号,使得排列方式如下,(0,-1,1,-2,2,...),即非负整数 映射至 ,负整数 映射至 。
莱斯编码
莱斯编码(Rice coding,由Robert F. Rice所提出),为一种前缀码,归属于格伦布编码的子集合,参数 为 的整数次方,即 。此种特例未必是所有格伦布编码中的最佳编码方式,但由于目前电脑为二进制运算,莱斯编码能快速且有效地以二进制运算实现。
性质
范氏霍夫曼编码
格伦布编码为一种范氏霍夫曼编码。
算法
- 选择参数
- 待编码数值为 ,计算:
- 商数:
- 余数: 。
- 编码
- 商数编码,对 进行一进制编码,得到 。
- 余数编码,对 进行截断二进制编码,得到 。
- 合并, 。
- 输出
范例
设 M = 10。则 .
|
|
选择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 (页面存档备份,存于互联网档案馆)