利用 XOR 處理 time series data 壓縮資料

在「The simple beauty of XOR floating point compression (clemenswinter.com)」這邊看到的內容,原文在「The Simple Beauty of XOR Floating Point Compression」這邊。這也是上一篇文章「Golomb coding」的延續。

文章作者在處理 time series data 時預先用 XOR 處理過 (對上一筆資料做),因為 time series data 的特性,通常 XOR 出來的結果會有很多都是 0 (表示相同的 bit),然後再用自己設計的演算法讓 raw data 變小。

以作者拿的第一個範例可以看到變小很多 (開原圖可以看比較清楚),不過這邊 low bit 都是 0 有點作弊:

後面有 unix timestamp 的部分,這個部分的資料就比較接近實際情況,也可以看出來效果不錯:

這邊似乎也可以選擇套 Golomb coding 或是 Rice coding (i.e. M 是 2 的冪次的特殊情況,2^n,這時候 Truncated binary encoding 剛好就是 Binary encoding)。

算是個有趣的處理法... 不過我猜大多數人為了方便處理,還是只會用 framework 提供的壓縮演算法,在底層透明地處理掉,像是 LZ4gzip 或是 zstd

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 codingTruncated binary encoding

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

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

Truncated binary encoding (中文維基百科剛好有條目:「截斷二進制編碼」) 則是很有趣的一個 encoding 方式。先提到傳統的方式,在表示 n 種可能的組合 (0, 1, ..., n-1) 時,會需要 \lceil\log_2 {n}\rceil bit 表達,像是 n = 5 時,會需要 3 個 bit 表達,從 000001010011100

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

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

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

x = M * q + r

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

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

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

Fabrice Bellard 的新作品 TSAC codec

昨天在 Hacker News 上看到「TSAC: Low Bitrate Audio Compression (bellard.org)」這則 Fabrice Bellard 的新作品:「TSAC: Very Low Bitrate Audio Compression」。

Fabrice Bellard 這兩年玩很多 ML 相關的東西,像是 2021 的「LibNC: C Library for Tensor Manipulation」,以及 2023 的「ts_zip: Text Compression using Large Language Models」,這次則是用上了 transformer

tsac is based on a modified version of the Descript Audio Codec extended for stereo and a Transformer model to further increase the compression ratio. Both models are quantized to 8 bits per parameter.

翻了一下 Descript Audio Codec,已經算是很厲害的了,在 44.1KHz mono 的情況下可以做到 8kbps (~1KB/sec):

With Descript Audio Codec, you can compress 44.1 KHz audio into discrete codes at a low 8 kbps bitrate.

TSAC 則是將 mono 的版本做到 5.5kbps,另外 7.5kbps 就能傳雙聲道,也還是低於原來的 8kbps:

TSAC is an audio compression utility reaching very low bitrates such as 5.5 kb/s for mono or 7.5 kb/s for stereo at 44.1 kHz with a good perceptual quality. Hence TSAC compresses a 3.5 minute stereo song to a file of 192 KiB.

聽了一下算蠻厲害的,直接拿音樂來壓還是有不錯的效果?

從技術上的情境可以知道兩端都需要有足夠的算力 (得跑 ML algorithm),然後在頻寬很不足的情況下通訊?商用的情境好像偏少一點,現在連沙漠與深山中都有衛星可以用,也許還是有些情境下用的到,像是 LoRa 的速度就差不多在這個區間。

倒是軍事上面需要考慮不少極端情況,用的機會可能比較高?

把文字檔壓成 PNG 跟 Gzip 比較壓縮率

Hacker News 上看到「Compressing Text into Images (shkspr.mobi)」這個奇怪的方法,是把文字轉成灰階的 PNG 檔案,然後跟 ZIP 比較壓縮率,居然是能打的。原文則是在「Compressing Text into Images」這邊。

這是屬於週末奇怪的 side project,作者也覺得這樣很白爛 XDDD

(This is, I think, a silly idea. But sometimes the silliest things lead to unexpected results.)

作者是拿羅密歐與茱麗葉的小說當資料 (Romeo and Juliet),這可以在 Project Gutenberg 的網站上下載到 txt 檔案。

基本的想法是把每個文字轉成灰階圖片的像素,然後用 PNG 無損輸出,最後再用 Squoosh 處理:

The English language and its punctuation are not very complicated, so the play only contains 77 unique symbols. The ASCII value of each character spans from 0 - 127. So let's create a greyscale image which each pixel has the same greyness as the ASCII value of the character.

結果居然是跟一般的壓縮軟體差不多:

That's down to 55KB! About 40% of the size of the original file. It is slightly smaller than ZIP, and about 9 bytes larger than Brotli compression.

我試著驗證作者的想法,用 Go 寫了個小程式輸出操作圖片,產稱一張寬度是小說的 byte 數,高度只有 1 的 PNG 檔輸出,最後再用 pngcrush 處理:「gslin/text-to-image-compression」。

另外我是與 gzip 比較 (原作者是與 ZIP 比較),結果是:

PNG: 64379
Gzip: 64563
Gzip (-9): 64331

的確是差不多的等級?

gzip 的 --rsyncable (zstd 也有)

查資的時候 gzip 發現有 --rsyncable 這個參數,號稱是產生出對 rsync 友善的壓縮檔:

When you synchronize a compressed file between two computers, this option allows rsync to transfer only files that were changed in the archive instead of the entire archive. Normally, after a change is made to any file in the archive, the compression algorithm can generate a new version of the archive that does not match the previous version of the archive. In this case, rsync transfers the entire new version of the archive to the remote computer. With this option, rsync can transfer only the changed files as well as a small amount of metadata that is required to update the archive structure in the area that was changed.

這個參數的說明可以參考「Rsyncable gzip」這篇,從發表的日期是 2005 年就可以看出來這個參數已經很久了:

With this option, gzip will regularly “reset” his compression algorithm to what it was at the beginning of the file. So if for example there was a change at byte 23, this change will only affect the output up to maximum (for example) byte #9999. Then gzip will restart ‘at zero’, and the rest of the compressed output will be the same as what it was without the changed byte 23. This means that rsync will now be able to re-synchronise between the old and new compressed file, and can then avoid sending the portions of the file that were unmodified.

這個參數的想法是,正常狀態下的 gzip 會因為來源的微小改變,造成後續壓縮的內容都完全不一樣。

但加上 --rsyncable 後,gzip 就會定時重設壓縮狀態 (reset),於是讓壓縮後的輸出內容有大部分的內容重複,於是 rsync 就能夠偵測到相同內容而避免大量重傳。

但反過來的缺點面也就馬上可以想到,這是犧牲一些壓縮演算法的效率,付出的代價就是輸出的檔案會大一點。

這個功能在 zstd 上也有,不過 xz 就沒有...

我拿 zstd -19 (zstd 最高的壓縮率?) 測試 BBS 的備份,一般壓縮是 513672097 bytes,而加上 --rsyncable 後的壓縮是 513831761 bytes,發現是萬分之幾的增加,等於是只多了零頭...?

看起來會是蠻好用的參數,特地寫一篇記錄起來...

Facebook 使用 AV1 的記錄

Facebook 整理了一份他們採用 AV1 的記錄:「How Meta brought AV1 to Reels」,要注意這邊的產品線是短影片類型。

因為之前剛好也有碰到 codec 這塊,但最後是因為 AV1 在 client 的支援度還跟不上,而選了在 Android 上支援度更好的 VP9

在文章前面有提到 server 端的需求,也就是 encoder 的部份,這是因為 AV1 的 encoding 真的很慢 (i.e. 外星技術),還在每過幾個月就會看到 encoder 技術重大突破的階段,所以得花時間去研究。

Facebook 後來決定用 SVT-AV1,因為效能上好很多 (以他們測試的那個時間點):

At any given point on the y-axis, SVT-AV1 can maximize encoding speed compared with any other production encoder. For example, the M8 preset is about as efficient as libvp9 preset 0, but M8 is almost 10 times faster.

而在 client 端的 decoder 部份,他們評估了 dav1dlibgav1 之後,選擇用 dav1d (iOS 與 Android 都是):

Two major open source software decoders are compatible with multiple platforms: dav1d was developed by VideoLAN and the open source community and can serve as an app-level decoder, while Google’s libgav1 is integrated into the Android SDK.

[W]e decided to integrate dav1d into the player for both iOS and Android platforms.

但在軟解的情況下只能解 720p30,然後中高階的才能解 1080p30,不過這對於短影片來說夠用:

dav1d can support 720p30 real-time playback on most of the devices in our sample, achieving 1080p30 on certain mid-range and high-end models.

所以就 Facebook 目前提供的資料來看,這部份還沒到輕鬆應對的情況,還得繼續看各家 library 的進展...

SQLite 的 zstd extension

看到「sqlite-zstd」這個實驗性質的專案,可以針對 SQLite 的 row-level 層壓縮:

Extension for sqlite that provides transparent dictionary-based row-level compression for sqlite. This basically allows you to compress entries in a sqlite database almost as well as if you were compressing the whole DB file, but while retaining random access.

看起來在空間上有很不錯的成果:

作者在他自己的 blog 上面有給了一篇比較完整的說明,除了空間上的優勢以外,還包含了效能上的分析:「sqlite-zstd: Transparent dictionary-based row-level compression for SQLite」。

在文章裡面測出來的數據看起來在效能上就不一定有比較好的結果,本來的 SQLite 就已經處理的還不錯了。

但看起來是個還蠻有趣的東西,舉例來說,如果可以透過 WebAssembly 編譯,再配合之前的「把 SQLite 的 VFS 掛上 WebTorrent 的 PoC Demo」,可以省下不少傳輸的量...

可以看看後續會不會真的有人這樣幹 XD

圖片無損壓縮下的演算法比較

Hacker News 上看到「What’s the best lossless image format? Comparing PNG, WebP, AVIF, and JPEG XL」這篇,在講圖片的無損壓縮演算法。在 Hacker News 上的討論也可以看看:「What’s the best lossless image format? (siipo.la)」。

文章有點舊 (2021 年七月),但應該還行... 另外作者看起來是以 service bandwidth 考量為主,在這種情境下,自然圖片一般都會以非無損的方式提供 (像是 JPEG),而人造圖片則是以無損的方式提供 (像是 PNG),所以在這邊討論無損的時候會以人造圖片的 dataset 來挑選,於是作者是跑去 Dribbble 上翻圖片當 dataset:

What I ended up with was downloading a set of images from Dribbble, a portfolio site for designers.

最後的結果就是:

考慮到目前各家瀏覽器的支援性,可以看到 Lossless WebP 其實是個很好的選擇,檔案算蠻小的,而且 Apple ecosystem 的支援性也已經出來了:

如果不用考慮到瀏覽器的話,JPEG XL 也可以考慮,不過本來宣稱 royalty-free 的部份蒙上了陰影:「Alarm raised after Microsoft wins data-encoding patent」,用的人反而要注意到 patent 問題...

QOI 圖片無損壓縮演算法

Hacker News Daily 上看到「Lossless Image Compression in O(n) Time」這篇,作者丟出了一個圖片的無損壓縮演算法,壓縮與解壓縮的速度超快,但壓縮率又不輸 PNG 太多,在 Hacker News 上的討論也可以看一下:「QOI: Lossless Image Compression in O(n) Time (phoboslab.org)」。

裡面有提到在遊戲產業常用到的 stb_image.h

Yes, stb_image saved us all from the pains of dealing with libpng and is therefore used in countless games and apps. A while ago I aimed to do the same for video with pl_mpeg, with some success.

作者的簡介也可以看到他的主業也在遊戲這塊:

My name is Dominic Szablewski. I build games, experiment with JavaScript and occasionally tinker with low-level C.

圖片的無損壓縮與解壓縮算是遊戲創作者蠻常用到的功能,所以他想要看看這塊有沒有機會有更好的工具,於是他就用了四個很簡單的演算法幹完了 QOI (然後發現效果很讚):

  • A run of the previous pixel
  • An index into a previously seen pixel
  • The difference to the previous pixel
  • Full rgba values

其實從 Hacker News 的討論也可以看到這組演算法也常被拿出來在現代的壓縮演算法使用,所以雖然作者自稱不是 compression guy,但他用的演算法其實蠻專業的...

然後挑 single thread 主要是可以避免 threading 的複雜度以及 overhead,在「QOI Benchmark Results」這頁可以看到,無論是什麼類型的檔案,壓縮與解壓縮的速度都相當漂亮,而且壓縮率又沒有差 libpng 太多。

而且作者自己有提到,還沒用到 SIMD 指令集加速,這樣猜測應該還有不少空間...

PostgreSQL 14 支援的 LZ4 壓縮

Hacker News 上看到 PostgreSQL 14 新支援的 LZ4 壓縮:「The LZ4 introduced in PostgreSQL 14 provides faster compression (fastware.com)」,在討論裡面反而有提到可以用 ZFS 的壓縮,這樣所有的資料 (包括 index) 都可以被壓縮:

If you are using ZFS, I strongly recommend using LZ4 or ZSTD compression with PostgreSQL. Performance is still awesome. On average I get 2x compressionratio with LZ4 and 4x with ZSTD.

With this, you are compressing everything, not just columns. And ZFS has dynamic block sizes which works really great together with compression. For example a 8kb PostgreSQL page, may be stored as a 1kb compressed block on disk.

而且通常開了壓縮後,整機的效率都會比較好。主要是因為資料庫的資料夠大時 (超過記憶體大小) 通常效能會先卡在 Disk I/O 的部份,這時候 CPU 會太閒;如果挑個輕量的壓縮演算法的話,雖然 CPU 使用率會拉高一些,但會大幅降低 Disk I/O 的量,在很多情況下就會提昇效能...

上面提到主要是 OLTP 的情況下,如果是在 OLAP 的場景下就更明顯了,基本上大家都是預設開著壓縮在處理所有資料。

另外在很多 RPC 類的系統也有類似的現象,資料傳輸量已經太大會超過 Network I/O 可以提供的量,這時候導入一些輕量的壓縮演算法就能大幅提昇系統效能。

以前有讀到一些壓縮演算法的比較,像是先前有翻到的「Evaluating Database Compression Methods: Update」,針對演算法的部份分析,裡面最後一張圖可以看到比較:

從比較圖可以穿來 Snappy 後來被 LZ4 淘汰掉,主要就是 LZ4 的壓縮率比較好,壓與解的速度又比較快,沒有理由繼續 Snappy。

另外 Zstandard 也逐步在淘汰 gzipzlib 類的壓縮,不過畢竟 gzip 與 zlib 的歷史真的太久,這邊淘汰的速度不快...