格倫布編碼

格倫布編碼（）是一種無失真資料壓縮方法，由數學家所羅門·格倫布在1960年代提出。其優點為易於編碼與解碼，另外對於擁有機率分布為幾何分佈的資料，格倫布編碼是最佳的前綴碼，且能無限逼近該資料的熵，目前廣泛用於無損影像壓縮。

編碼的建立

Image:golomb rice code.svg

令輸入值為正整數，參數值為正整數 ，輸出值格倫布碼為 ，其中  由兩種編碼組合而成，

，：一进制編碼，：截斷二進制編碼。

計算  與 。

 。

將  做一进制編碼， 做截斷二進制編碼即可得到。

格倫布-萊斯編碼中的商數指示了所在區塊，而指示所在區塊內部的位置。如上圖，對整數  做格倫布-萊斯編碼， 代表區塊、 表示區塊內部位置、 為參數，每個區塊的大小皆相等且長度為 ，特別注意當編碼方式為格倫布-萊斯編碼時，即  為  的整數次方，所有的編碼長度相等。

參數  是伯努利過程的函數，其中伯努利過程的參數  定義為 ，則  的所在區間為此伯努利過程的中位數-1到中位數+1之間。如下式：

當  足夠大時，我們可以將其表示成，。

 使用符號整數 
格倫布編碼主要是針對非負整數進行編碼，但也可以使用重疊(Overlap)與交錯(Interleave)擴展至對所有整數進行編碼。令一串用於編號的數列，(0,1,2,...)，給予非負整數偶數編號，給予負整數奇數編號，使得排列方式如下，(0,-1,1,-2,2,...)，即非負整數  映射至 ，負整數  映射至 。

萊斯編碼

萊斯編碼（Rice coding，由Robert F. Rice所提出），為一種前綴碼，歸屬於格倫布編碼的子集合，參數  為  的整數次方，即 。此種特例未必是所有格倫布編碼中的最佳編碼方式，但由於目前電腦為二進位運算，萊斯編碼能快速且有效地以二進位運算實現。

性質
范氏霍夫曼編碼

格倫布編碼為一種范氏霍夫曼編碼。

 演算法 
選擇參數 
待編碼數值為 ，計算：
商數： 
餘數： 。
編碼
商數編碼，對  進行一进制編碼，得到 。
餘數編碼，對  進行截斷二進制編碼，得到 。
合併，。
輸出 

 範例 

設 M = 10。則 . 

商數編碼q輸出位元00110211031110411110511111061111110N餘數編碼r偏移二進位輸出位元00000000011000100122001001033001101144010010055010110161211001100713110111018141110111091511111111

選擇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.

Category:无损压缩算法