πFS - データをハードドライブではなくπに保存するというファイルシステム

 (github.com/philipl)
2 ポイント 投稿者 GN⁺ 3 시간 전 | 1件のコメント | WhatsAppで共有
  • πfsは、データをハードドライブに保存する代わりに π に保存して容量を使わないという発想を実装したファイルシステムで、πが存在しうるすべてのファイルを含むという前提を中核としている
  • πが 正規数(normal) であるという予想が正しければ、16進表現の中にあらゆる有限ファイルが存在するという説明に基づいている
  • ファイルのπ内の インデックス と長さが分かれば、Bailey–Borwein–Plouffe formula によってファイルを取り出すことができ、この実装では性能のためにファイルの各バイトを個別にπから参照する
  • 実行時は πfs -o mdd=<metadata directory> <mountpoint> 形式を使用し、metadata directory にはファイル名やπ内のファイル位置のようなメタデータを保存する
  • ビルドには autoconf、automake、libfuse パッケージが必要で、./autogen.sh、./configure、make、make install の流れでビルドする
  • 現在の実装は 初期プロトタイプ であり、400行のテキストファイルの保存に5分かかったという例がある
  • 今後の可能性として、可変実行長検索・参照、Arithmetic Coding、並列参照、クラウドベースのπ参照、Hadoop向けπfsが挙げられている

関連記事

1件のコメント

 
GN⁺ 3 시간 전
Hacker Newsのコメント

  • データ圧縮ツールとしてバベルの図書館を使おうとしていた頃を思い出した
    そのおかげで面白い rabbit hole にハマり、情報理論に初めて触れた
    結論としては、データの位置アドレスを表現するのにもデータ本体とほぼ同じ量の情報が必要なので、圧縮にはあまり効果がなく、面白い思考実験に近いということ
    今の基準で興味深いのは、LLM がこうしたツールの失敗した目標の要点を実際に達成する損失圧縮の一形態だという点。もちろん損失はあり、巨大な基盤も必要だが

    • この動画は面白そう: Reinventing Entropy Compression is Intelligence Part 1, 3Blue1Brown
      https://youtu.be/l6DKRf-fAAM?is=ne73FCJ7ErXhzZ-v
    • 3Blue1Brown がちょうど知能と圧縮のつながりを扱った動画を公開した
      https://youtu.be/l6DKRf-fAAM
    • ある意味では、科学こそが最も極端な圧縮形態だ。ニュートン力学は数行の文章で膨大な現象を説明する
    • 圧縮の度合いを考えるとかなり印象的。以前書いたコメントは今でも正しいと思うが、バイトではなくビットであるべきなので、その点では間違っていた: https://news.ycombinator.com/item?id=39559969
      有効な 4-gram、つまり4語のシーケンスを保存する概算は、100億個 × 1語あたり14ビット = 全体で約17GB。ところが、これより100分の1小さい LLMでも一貫した散文を書ける

  • nsafs、つまり National Security Agency Filesystem を思い出した。政府が費用を払うので「無料」という設定だ: https://github.com/freedomtools/nsafs

    • これは手順を増やしただけの書き込み専用メモリだ
      https://en.wikipedia.org/wiki/Write-only_memory_(joke)
    • 以前ある会社の面接で、面接官がベンチャー投資家として巨大な乱数ストリームを生成するプロジェクトに投資したと話していた
      任意のインデックスを選び、その秘密鍵を相手と共有すれば、その後はテキストをワンタイムパッドとして使えるという構想だった。NSA が解読するには、GB/s で生成されるストリーム全体をバッファして保存しなければならない、という理屈だったが、あまり実用的には見えなかった

  • データ長が伸びるほど、π の中でそのシーケンスのインデックスと長さが元データより小さくなる可能性は極めて低い、という点は押さえておく価値がある

    • 簡単に解決できそうに見える。π の中でのインデックスと長さを、さらに π の中でのインデックスと長さとして記録すればいい
    • 大学時代、電話番号を π の中のインデックスとして伝えれば圧縮できるのではと思ったが、7桁の電話番号が8桁のインデックスにあった
      市外局番まで含めた10桁の番号を見つける計算資源はなかった
    • 20行のファイルのインデックスが <20TB number> になる
    • 原文でもこの部分に触れている

      Now, we all know that it can take a while to find a long sequence of digits in π, so for practical reasons, we should break the files up into smaller chunks that can be more readily found.
      In this implementation, to maximise performance, we consider each individual byte of the file separately, and look it up in π."

  • 関連する記事。まだある？
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=36357466 - 2023年6月、コメント107件
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=28699499 - 2021年9月、コメント30件
    PiFS – The Data-Free Filesystem - https://news.ycombinator.com/item?id=26208704 - 2021年2月、コメント1件
    Πfs: Never worry about data again - https://news.ycombinator.com/item?id=21359338 - 2019年10月、コメント1件
    The π Filesystem for FUSE: Store Your Data in π - https://news.ycombinator.com/item?id=19223032 - 2019年2月、コメント1件
    pifs - Avoid disk space usage by saving your files in the digits of Pi - https://news.ycombinator.com/item?id=18687275 - 2018年12月、コメント1件
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=13869691 - 2017年3月、コメント105件
    Πfs: Stores your data in π - https://news.ycombinator.com/item?id=10856108 - 2016年1月、コメント1件
    Πfs: Never worry about data again - https://news.ycombinator.com/item?id=10847693 - 2016年1月、コメント1件
    File system that stores location of file in Pi - https://news.ycombinator.com/item?id=8018818 - 2014年7月、コメント98件
    100% Compression Using Pi - https://news.ycombinator.com/item?id=6698852 - 2013年11月、コメント32件
    再投稿は1年くらい経てば問題なく、過去スレッドへのリンクはもっと知りたい読者向けのもの

    • こういう一覧をどうやって生成しているのか気になる

  • これも思い出した: https://www.spronck.net/sloot.html
    追加の読み物: https://en.wikipedia.org/wiki/Sloot_Digital_Coding_System

    • 昔少し調べたことがあるけれど、Slootがやったことは少なくとも多少は新しかった
      実際のエンコード方式は、動画の各ラインをデータベースに保存し、各フレームをライン参照のシーケンスとしてエンコードし、そのエンコード済みフレームをさらに別のデータベースに保存する構造だった。各動画はフレーム参照のシーケンスになる
      90年代後半のハードウェアで16本の動画を同時に滑らかに再生できるデモが可能だった理由はこれ。各フレームがライン参照のシーケンスなので、画面を横に16分割して16本の映像を同時再生しても、全画面に単一の映像を再生するより負荷が大きいわけではない
      同様に各フレームを個別にデコードするので、早送りや巻き戻しも滑らかだった。従来の動画圧縮のように各キーフレームから差分を計算する必要がないため、2倍速再生も1倍速より重くはなかった
      もちろん動画ファイルを8KBのようなサイズで保存することはできなかっただろうが、たとえばテレビシリーズの1シーズンがデータベースに入っているなら、オープニングとエンディングのクレジットは1回だけ保存すればよかった

    • The SDCS is only possible if keys are allowed to become infinite, or the data store is allowed to become infinite (...) This would, of course, make the idea useless.
      でも π は無限だ。だからムーアの法則が引き続き味方である限り、この天才的な装置は動くはず

  • One of the properties that π is conjectured to have is that it is normal
    ここで重要なのはconjecturedだ
    自分がよくこだわる些細な厳密性の話が出てきてうれしい。構成されていない無理数が正規数であるとか、あらゆる有限文字列を含むとかいうことは、まだ何一つ証明されていない

    • ここで「構成されていない」が何を意味するのか気になる

  • In this implementation, to maximise performance, we consider each individual byte of the file separately, and look it up in π.
    各ビットを別々に見たほうが、さらに性能が良くなるはず。必要なのはインデックス 2 と 33 だけで、それをストレージのビットへ効率的にマッピングできる

  • πに過去と未来のあらゆる知識、さらには自分がいつ死ぬかまで含まれていると気づくのは居心地が悪い

    • 他のあらゆる無作為な無限ビット列でも同じことが言える。直感に反している部分はπではなく、無限から来ている
      さらに、過去と未来のあらゆる知識を含んでいるとさえ言えない。過去と未来についてのあり得るあらゆる偽りも、真実と区別できない形で一緒に含まれているからだ
      情報を疑似乱数列のオフセットとしてエンコードするのは、情報を直接保存するより保存効率が悪い
    • 最悪なのは、Chris PrattがHan Soloにキャスティングされた別時間線のStar Wars 4〜6まで入っていることだ
      豆知識: 「Chrispratt」は古代カリフォルニア語で「Joel McHaleがその役を望まなかった」という意味だ
    • Jorge BorgesのThe Library of Babelを面白く読めそう
      https://dn760100.eu.archive.org/0/items/TheLibraryOfBabel/ba...
    • πを先回りして読み始めた人は、いつでもいちばん新鮮な数字を手に入れられる。完璧な暗号だ
    • 過去と未来のあらゆるフェイクニュースも入っていて、どちらが本物なのか分からない

  • 昔、ある圧縮ベンチマークの参加作品がファイル名を展開アルゴリズムの入力の一部として扱うことで、ベンチマークをうまくすり抜けていたのをぼんやり覚えている
    ベンチマークはファイルサイズしか測っていなかったので、その指標に勝ててしまった

  • これは、πについてまだ証明されていない性質に依存しているのでは？ あらゆる有限文字列を含むことや正規性が必要だが、どちらも証明されていない