Golomb coding

在 Hacker News 上看到 id=40008133 這篇提到 Golomb coding 覺得很有趣，花了些時間把演算法以及使用的場景搞清楚...

Golomb coding 用在 input 是數字 (或是 fixed size 時硬當作一個數字處理)，而且大多數的資料都偏小的情境下，像是「I don't get Golomb / Rice coding: It does make more bits of the input, or does it?」這邊解釋 Golomb coding 時提到的：

they reduce the average length per encoded value compared to fixed-width encoding, if the encoded values are from a large range, but the most common values are generally small (and hence are using only a small fraction of that range most of the time).

Golomb coding 演算法上用到了兩個特殊的表達方式，Unary coding 與 Truncated binary encoding。

Unary coding 很簡單，把 n 表達成 n 個 bit 的 1，再加上一個 0，所以 3 表達成 1110，7 表達成 11111110。

Unary coding 最主要就是要用到他只用一個 bit 0 來表達 n = 0 的情況。

Truncated binary encoding (中文維基百科剛好有條目：「截斷二進制編碼」) 則是很有趣的一個 encoding 方式。先提到傳統的方式，在表示 n 種可能的組合 時，會需要 bit 表達，像是 時，會需要 3 個 bit 表達，從 000、001、010、011 到 100。

Truncated binary encoding 則是找到一個方法，編碼成 00 (對應到 0)、01 (1)、10 (2)、110 (3)、111 (4)，針對 n = 0～2 的部分只用 2 bits 表示，省下 1 個 bit。

Truncated binary encoding 的重點在於在可能性非 的情況下，要怎麼省儲存空間。

而 Golomb coding 需要預先指定一個 ，對於每一個 輸入，拿 去除他，就會得到一個商 與餘數 ：

這邊把商 用 Unary coding 表示，餘數 用 Truncated binary encoding 表示，就是 Golomb coding 了。

而就如同前面提到的，Golomb coding 會用在資料數字都偏小的情況，當 挑的夠好就可以讓 常常是 0 或是 10 而省下空間。

這剛好就對到「The simple beauty of XOR floating point compression (clemenswinter.com)」這則提到的東西，在處理 time-series data 時就有機會用這個方式搭配處理...