把文字檔壓成 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 的歷史真的太久,這邊淘汰的速度不快...

用在 IoT 裝置上的壓縮演算法 Heatshrink

在「Heatshrink – An ultra-lightweight compression library for embedded systems」這邊看到的演算法 Hearshrink,可以看到主打是在記憶體的用量受限的環境下壓縮。

在 2013 年的資料就有壓縮率的比較了:「heatshrink: An Embedded Data Compression Library」。

像是目前常被拿來使用的 ESP32 就只有 320KB 記憶體,gzip 就明顯太肥大了,HS 在這邊就可以犧牲壓縮率來換效能...

另外找了一下資料,發現有 lowzip 這個東西,走 ZIP 格式,記憶體用量也不高,不過軟體本身還掛 alpha:

Current x64 code footprint (for lowzip.c, excluding the test program) is about 3.2kB and RAM footprint is about 1.1kB.

如果之後打算要透過 LPWAN 之類的網路傳東西的話好像有可能會用到,先寫下來...

cURL 支援 Zstandard

在「curl 7.72.0 – more compression」這邊看到新版的 cURL 要支援 Zstandard 了,查了一下發現 Zstandard 有對應的 RFC,在 RFC 8478:「Zstandard Compression and the application/zstd Media Type」。

對應到 server 端的部份,看起來可以用 tokers/zstd-nginx-module 搭 (在 nginx 環境下),不然就是 application 端要自己壓縮了。

不過普及率比較高的演算法是 Google 主導的 Brotli,查了一下壓縮率大概在同一個等級。

Facebook 沒有自家瀏覽器,推這些東西比較辛苦一點,但這次 cURL 決定支援 Zstandard 算是一個開始,讓開發者多了一個選擇可以用...

補上 nginx 對 favicon 的壓縮...

從「Compressed favicons are 70% smaller but 75% of them are served uncompressed」這邊看到的,他們發現大約有 73.5% 的網站沒有壓縮 favicon.ico 檔:

The HTTP Archive dataset of favicons from 4 million websites crawled from desktop devices on May 2019 shows that 73,5 % of all favicons are offered without any compression with an average file size of 10,5 kiB, 21,5 % are offered with Gzip compression at an average file size of 4 kiB, and 5 % offer Brotli compression at an average file size of 3 kiB.

我自己的也沒加... 補上 gzip 相關的設定後,favicon.ico 的傳輸量從 4.2KB 降到 1.2KB。

我是使用 nginx,在 Ubuntu 上 nginx 的 nginx.conf 內 gzip 預設已經有開,所以只要增加一些設定讓他知道要處理 ico 檔案就可以了。

方法是在 /etc/nginx/conf.d/gzip.conf 裡面放:

gzip_comp_level 9;
gzip_types image/vnd.microsoft.icon image/x-icon;
gzip_vary on;

跟文章裡面提到的多了兩個設定,一個是 gzip_comp_level 改成 9 (預設是 1),另外有 gzip 時應該要在 Vary 表示,避免 cache 出錯。