ハクソク

世界を動かす技術を、日本語で。

ファブリス・ベラールのTS Zip（2024）

94日前原文(www.bellard.org)

概要

ts_zipは、大規模言語モデルを利用したテキストファイル専用の高圧縮率圧縮ツール。
GPUと4GB RAMが必須で、速度は従来ツールより遅い。
英語中心に学習されたモデルを採用し、他言語やソースコードにも対応。
実験的な性質のため、バージョン間の互換性なし。
小規模メッセージ圧縮にはts_smsも推奨。

ts_zipの特徴

  • **大規模言語モデル（RWKV 169M v4）**によるテキストファイル圧縮
  • 従来ツール（xz等）より高い圧縮率を実現
  • 圧縮・展開速度：最大1MB/s（RTX 4090使用時）
  • 対応ファイル：テキストファイルのみ
  • バイナリファイルの圧縮効果は限定的
  • 必要環境：GPU、4GB以上のRAM
  • 英語データ中心の学習だが、他言語・ソースコードにも対応
  • 実験的ツールのため、バージョン間の後方互換性なし
  • 小規模メッセージ用圧縮ツール：ts_smsも利用可能

圧縮率比較

  • 圧縮率はbits per byte (bpb)で表示

  • 代表的なファイルの比較例：

    • alice29.txt

      • 元サイズ：152,089 bytes
      • xz圧縮：48,492 bytes（2.551 bpb）
      • ts_zip圧縮：21,713 bytes（1.142 bpb）

    • enwik8

      • 元サイズ：100,000,000 bytes
      • xz圧縮：24,865,244 bytes（1.989 bpb）
      • ts_zip圧縮：13,825,741 bytes（1.106 bpb）

    • linux-1.2.13.tar

      • 元サイズ：9,379,840 bytes
      • xz圧縮：1,689,468 bytes（1.441 bpb）
      • ts_zip圧縮：1,196,859 bytes（1.021 bpb）

    • 他のプログラムとの比較結果はLarge Text Compression Benchmark参照

ダウンロード

  • Linux版：ts_zip-2024-03-02.tar.gz
  • Windows版：ts_zip-2024-03-02-win64.zip

技術情報

  • RWKV 169M v4モデル採用
    • 速度と圧縮率のバランスに優れる
    • 8ビット量子化＋BF16浮動小数点で評価
  • トークン確率の予測と算術符号化による圧縮
  • 決定的かつ再現性のある評価方式
    • GPU/CPUやスレッド数に依存しない結果
    • 異なるハードウェアやソフトウェアでも展開可能

注意点・補足

  • 実験段階のため、将来のバージョンとの互換性保証なし
  • Fabrice Bellardによる開発
  • 公式サイト：https://bellard.org/

Hackerたちの意見

LLMがどうやって圧縮を実現するのか、ずっと気になってたんだ。出力にどんな偏りがあるのか知りたいな。なんか、電話ゲームみたいで、再圧縮するたびにデータが失われて、間違って再構築される感じがする。物語を思い出すのが間違ってて、時間が経つにつれて細かい部分が少しずつ変わっていくような。
└
LLMが次のトークンを予測するとき、実際には可能な次のトークンそれぞれの確率の分布を生成して、その中からサンプラーが一つを選ぶんだ。必ずしも最も可能性の高いものを選ぶわけじゃないよ！もしLLMの予測を実行して、次のトークンの確率をエンコードしたい入力テキストから算出（累積分布から、[0, 1]の数値）して算術コーディングを使えば、同じ操作を逆に行ってロスレス圧縮を実現できるよ。難しいのは、LLMが絶対に決定論的に動作するようにすること。エンコーダーとデコーダーが各ステップで同じ確率分布マップを持っていることを確認する必要があるからね。
└
そうだね。秘密は算術コーディングを理解することにあるよ。https://en.wikipedia.org/wiki/Arithmetic_coding 算術コーディングは次のビットの予測をして、その予測を修正するのに必要なビット数だけを書き出すんだ。すごいのは、分数ビットを書き出せるところ。例えば、次のビットが75%の確率で'1'だと予測したとする。もし1なら、1/2ビットだけ書き出せばいい（その25%の部分を修正するために）。もし0なら、2.4ビット書き出さなきゃいけない。1/2ビットで作業するのは変に思えるかもしれないけど、ちゃんと機能するんだ！（実際にはビットのもう半分が将来の修正を表してる）。ハフマンコーディングは分数ビットに対応できないけど、算術コーディングはそれを一般化したものなんだ。算術コーディングは数学的には完璧なアルゴリズムだから、データをエンコードする時に一切のビットを無駄にしないよ。だから、現代の圧縮技術はエンコード/デコードの部分には全く関わってないんだ。彼らが扱ってるのは、これまでのデータをモデル化して、次のデータのビット（またはバイト）についてできるだけ正確な予測をすること。ちなみに、エンコーダーとデコーダーは基本的に全く同じように動作する。読み取ったデータやデコードしたデータから次のビットを予測する部分は同じなんだ。デコーダーは圧縮ファイルを読み取って修正を行い、エンコーダーは入力ファイルを読み取って修正を書き出す。重要なのは「次のビットを予測する」こと。これが、さまざまな圧縮機を分けるポイントなんだ。ここで、経験者が間違った方向にいる人を修正しようとする理由でもある。圧縮アルゴリズムは決してエンコード側のことではなく、常にデータの予測に100%関わってるんだ。次に来るデータを正確に予測できるモデルを作れるか？それが良いファイル圧縮機を作るために必要なことだよ。エントロピーエンコーディングの部分はすでに完全に解決された問題だから、再解決しようとしない方がいいよ。
└
https://www.youtube.com/watch?v=QEzhxP-pdos
>> ts_zipユーティリティはテキストファイルを圧縮（そして、できれば解凍も）できるよ。うまくいくといいな :-)
└
データを読むのは過大評価されてるよ。S4を強くおすすめする！: http://www.supersimplestorageservice.com/
LLMと算術コーディングを組み合わせた面白い応用の一つがステガノグラフィーだよ。前に取り組んだプロジェクトがあって、ここでやってることとは逆の技術を使って、ステガノグラフィック変換を構築してるんだ： https://github.com/shawnz/textcoder
└
すごいね！とても信頼できるエンコーディングを作成する。 > このプロジェクトで使われているLlamaトークナイザーは、特定の文字列に対して複数のトークン化を許可することがある。トークンがプレフィックスコードでないのは本当に残念だね。Llamaチームはこれをバグだと考えてるのかな？残念ながら、完全に再学習しないと状況を修正する方法が見当たらないよ。
enwik8の大規模テキスト圧縮ベンチマークでは全てを上回ってるみたいだけど、enwik9ではいくつかのプログラムに負けてるね。なんでだろう？
└
実は、enwik8や9では一番じゃないんだよね。ここにある結果では、圧縮機自体のサイズも結果に加算されてるから注意してね。「enwik9+prog」っていう列がそれに基づいてる。理由は、ファイルを0バイトに「圧縮」する圧縮機を作るのは簡単だから。enwik9の辞書を持った実行可能ファイルを用意して、どんな入力でもそれを書き出せばいいだけ。だから、実際にはコルモゴロフの複雑さを測ってるんだ。結果を出すためのデータ+プログラム全体をね。だから、あの結果には圧縮機のサイズが加算されてる。そこにあるプログラムは、一般的に辞書が組み込まれてないか、LLMベースの圧縮機の場合は事前学習データがないんだ。データを処理しながらモデルを構築していく感じで、最初はあまり圧縮できなくて、徐々に良くなっていく。これが、大きなデータセットでこれらのプログラムがどんどん良くなる理由。最初は0の知識から始まって、1GBくらい経つと人間の言語のコーパスについてかなり良い知識を持つようになる。でも、ここで紹介してるプログラムは事前学習済みでモデルが付いてるから、サイズは150MB！つまり、あのリストのモデルよりも150MBの余分な初期知識を持ってるってこと。リストの上位モデルは優れた圧縮機だから、すぐにこの圧縮機を超えていくけど、スタートダッシュがないんだよね。公平に測るなら、比較する時にはこの150MBのプログラムサイズを結果に加えるべきだね。
ついに2019年の自分のリーディングプログラム、nncpを超えたんだね。
ジェフ・ディーンが行き詰まったら、ベルラードに助けを求めるんだ…
└
ジェフ・ディーンはファブリス・ベラールをデバッグのための「ラバーダック」として使ってるらしいよ。逆も然り。驚くことに、二人とも数分間何も言わずにお互いの目を見つめ合って、その後一緒に一つのキーボードで問題の解決策を打ち始めるんだ。
圧縮と知能の関係を考えると、10年以上前に出会ったこのサイトを思い出すなぁ。圧縮が知能やAGIに関係してるってのは新鮮だった。
└
そうだね。ニューラルネットワークをクロスエントロピーを最小化するように訓練すると、算術コーディングデータ圧縮器の基本要素として良くなるってことなんだ。詳しくはここを見てみてね。https://en.wikipedia.org/wiki/Arithmetic_coding それと、こっちも参考に。https://learnandburn.ai/p/an-elegant-equivalence-between-llm...
現在の大規模テキスト圧縮ベンチマークのリーダーはNNCP（ニューラルネットワークを使った圧縮）で、Fabrice Bellardによるものだよ。https://bellard.org/nncp/ それに、nncp-2024-06-05.tar.gzは1180969バイトで、ts_zip-2024-03-02.tar.gz（159228453バイト、uncompressed enwiki8よりも大きい）とは違うんだ。
└
これって、他のコメントで言及されてるハッタープライズの条件に合ってるんじゃない？ https://news.ycombinator.com/item?id=46595109
└
確かにすごいけど、英語のテキストに特化した圧縮のケースだよね。いろんなところで使われてるかもしれないけど、圧縮できるものはもっとたくさんあるし、ここで比較があったらいいな。https://morotti.github.io/lzbench-web/?dataset=silesia/sao&m...
piファイルシステムを思い出したなぁ。十分な桁数のπを事前計算しておけば、そこそこ良い圧縮プログラムができるかも。ポイントは、どれくらいの合理的な桁数が必要かってことだね。それが、その学習済みLLMよりも小さいか大きいか。
└
あなたの入力データのオフセットの長さは、入力データ自体の長さとほぼ同じだと思う。プラスマイナス数バイト程度で、入力データのサイズには関係なくね。つまり、圧縮はないけど、悪化することもないってこと。もちろん、入力データがπの桁数だったり、πに関する計算の結果だったりする場合は別だけど。
└
数学的にπがすべての部分文字列を含むことが証明されていないことを指摘するオタクになるつもりだよ。だから、pifsは理論的にも機能しないかもしれない（もちろん、全く実用的じゃないけどね）。もっと真面目な話をすると、これらの圧縮コンペティションでは静的データがサイズ計算に含まれる必要があるみたい。だから、1000MBを500MBに圧縮したとしても、デコンプレッサーに1MBのバイナリと100MBの初期辞書が必要なら、スコアは500 + 100 + 1 = 601MBになるんだ、500MBじゃなくてね。この議論に関連するのは、LLMの重みも静的データとして含める必要があるってこと。再生成する唯一の方法が初期のトレーニングデータからだから、そのデータは結果のモデルよりもずっと大きいんだ。対照的に、πベースの圧縮は逆の方向だよ。πは自然定数だから、デコンプレッサーが（例えば）1兆桁のπを必要とするなら、それを生成するための比較的小さなプログラム（数KB）を書くことができる。すごく遅いけど、圧縮率にはあまり影響しないんだ。
└
その観点から言うと、πは真の「違法な数」だね。今まで作られたすべての違法コンテンツは、最終的にπの数字の中に見つかるから。神が宇宙を作ったとき、CSAMやヘイトスピーチ、無断のバイアグラ広告で満たしたんじゃないかな… [1] https://en.wikipedia.org/wiki/Illegal_number
あんまり考えてなかったけど、普通の圧縮に対して50%の削減しかできないってのは驚きだね。