格倫布編碼

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

編碼的建立

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

$c=(u,b)$，$u$：一进制編碼，$b$：截斷二進制編碼。

計算 $u$ 與 $b$。

$q=\lfloor \frac{n}{m}\rfloor ,$ $r=n-q$。

將 $q$ 做一进制編碼，$r$ 做截斷二進制編碼即可得到$(u,b)$。

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

參數 $M$ 是伯努利過程的函數，其中伯努利過程的參數 $p$ 定義為 $p=P(X=0)$，則 $M$ 的所在區間為此伯努利過程的中位數-1到中位數+1之間。如下式：

$(1-p{)}^M+(1-p{)}^{M+1}\le 1<(1-p{)}^{M-1}+(1-p{)}^M.$

當 $M$ 足夠大時，我們可以將其表示成，$M=\lfloor \frac{-1}{{\log }_2(1-p)}\rfloor$。

使用符號整數

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

萊斯編碼

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

性質

范氏霍夫曼編碼

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

演算法

1. 選擇參數 $M$
2. 待編碼數值為 $n$，計算：
   1. 商數： $q=\lfloor \frac{n}{m}\rfloor ,$
   2. 餘數： $r=n-q$。
3. 編碼
   1. 商數編碼，對 $q$ 進行一进制編碼，得到 $u$。
   2. 餘數編碼，對 $r$ 進行截斷二進制編碼，得到 $b$。
   3. 合併，$c=(u,b)$。
4. 輸出 $c=(u,b)$

範例

設 M = 10。則 $b=\lceil {\log }_2(10)\rceil =4$. $2^b-M=16-10=6$

商數編碼 q 輸出位元 0 0 1 10 2 110 3 1110 4 11110 5 111110 6 1111110 $⋮$ $⋮$ N $\underset{N}{\underbrace{111\cdots 111}}0$

餘數編碼 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會被拆成 $q=4$ 及 $r=2$，編碼為11110010，而商數編碼尾數必為0，能標示商數編碼位元的結束。

參考來源

• Golomb, S.W. (1966). , Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401 Template:Wayback
• 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. Template:Wayback
• 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 Template:Wayback. MIT Press, Cambridge MA, 2010.
• -{R|https://en.wikipedia.org/wiki/Golomb_coding}- Template:Wayback

Template:压缩方法