LZ4さんは負けました？

なんか調べていくと、zstandardが現状かなりいい感じらしい、ということが分かってきたので、これを調べることに。

LZ4に関しては、ここが一番わかりやすいと思います！
https://www.slideshare.net/komiyaatsushi/dsirnlp-3-lz4

zstandardとは？

Zstandardは、リアルタイム圧縮アルゴリズムであり、高い圧縮率を有する。非常に高速なデコーダによって、非常に広範囲の圧縮率/速度のトレードオフを提供します。また、圧縮辞書と呼ばれる小さなデータのための特別なモードによって、どんなサンプルセットからでも辞書を作成できる。ZstandardライブラリはBSDライセンスを使ったオープンソースソフトウェアとして提供されている。

どんなアルゴリズムなの？

アルゴリズムは、RFC8478として公開されている。
えっとですねえ…

https://mag.osdn.jp/16/09/01/163000
http://fastcompression.blogspot.com/2013/12/finite-state-entropy-new-breed-of.html

多分、こんな感じの話。

エントロピー via シャノン
↓
ハフマン符号化(整数のビット数を使用する制限付き）
↓
算術符号化(1bit未満で表現できるが、特許問題などなど＋複雑すぎる実装）
↓
↓　Jarek DudaのANS理論
↓　↓
有限状態エントロピー（1bit未満で表現できるうえに、除算などを含まないロジック）

となったと。

もっともっと詳しいのはこのあたり

と、今日はここまで…。