πFS – das Dateisystem, das Daten statt auf einer Festplatte in π speichert

 (github.com/philipl)
2 Punkte von GN⁺ 3 시간 전 | 1 Kommentare | Auf WhatsApp teilen
  • πfs ist ein Dateisystem, das die Idee umsetzt, Daten nicht auf einer Festplatte, sondern in π zu speichern und dadurch keinen Speicherplatz zu verbrauchen; im Kern steht die Annahme, dass π alle denkbaren Dateien enthält
  • Es beruht auf der Erklärung, dass bei Zutreffen der Vermutung, π sei normal, in seiner hexadezimalen Darstellung alle endlichen Dateien vorkommen
  • Wenn man den Index einer Datei in π und ihre Länge kennt, kann man sie mit der Bailey–Borwein–Plouffe formula extrahieren; diese Implementierung liest aus Performancegründen jedes Byte der Datei einzeln aus π aus
  • Zur Ausführung wird das Format πfs -o mdd=<metadata directory> <mountpoint> verwendet; im metadata directory werden Metadaten wie Dateinamen und die Position der Datei in π gespeichert
  • Für den Build werden die Pakete autoconf, automake und libfuse benötigt; gebaut wird mit dem Ablauf ./autogen.sh, ./configure, make, make install
  • Die aktuelle Implementierung ist ein früher Prototyp; als Beispiel wird genannt, dass das Speichern einer 400-Zeilen-Textdatei 5 Minuten dauerte
  • Als künftige Möglichkeiten werden Suche und Abruf mit variabler Run-Length, Arithmetic Coding, paralleler Abruf, Cloud-basierter π-Abruf und πfs für Hadoop genannt

Verwandte Beiträge

1 Kommentare

 
GN⁺ 3 시간 전
Hacker-News-Kommentare

  • Das erinnert mich daran, dass ich einmal versucht habe, die Bibliothek von Babel als Datenkomprimierungswerkzeug zu verwenden.
    Dadurch bin ich in ein interessantes rabbit hole geraten und habe zum ersten Mal etwas über Informationstheorie gelernt.
    Das Fazit war, dass man zur Darstellung der Positionsadresse der Daten fast genauso viel Information braucht wie für die Daten selbst, sodass es für Komprimierung kaum nützlich ist und eher ein interessantes Gedankenexperiment bleibt.
    Aus heutiger Sicht ist interessant, dass LLMs gewissermaßen tatsächlich den Kern dessen erreichen, woran solche Werkzeuge gescheitert sind: eine Form von verlustbehafteter Komprimierung. Natürlich mit Verlusten und auf einer riesigen Grundlage.

    • Dieses Video dürfte interessant sein: Reinventing Entropy Compression is Intelligence Part 1, 3Blue1Brown
      https://youtu.be/l6DKRf-fAAM?is=ne73FCJ7ErXhzZ-v
    • 3Blue1Brown hat gerade ein Video über die Verbindung zwischen Intelligenz und Komprimierung hochgeladen.
      https://youtu.be/l6DKRf-fAAM
    • In gewissem Sinne ist Wissenschaft die extremste Form von Komprimierung. Die Newtonsche Mechanik erklärt mit ein paar Zeilen Text eine enorme Menge an Phänomenen.
    • Wenn man über den Grad der Komprimierung nachdenkt, ist das ziemlich beeindruckend. Ich halte einen Kommentar, den ich früher geschrieben habe, immer noch für zutreffend, auch wenn er insofern falsch war, als es um Bits statt Bytes gehen müsste: https://news.ycombinator.com/item?id=39559969
      Eine grobe Rechnung für das Speichern gültiger 4-Gramme, also Vier-Wort-Sequenzen, ergibt 10 Milliarden × 14 Bit pro Wort = etwa 17 GB für alle 10 Milliarden. Dennoch kann ein 100-mal kleineres LLM konsistente Prosa schreiben.

  • Das erinnert mich an nsafs, also das National Security Agency Filesystem. In dem Szenario ist es „kostenlos“, weil der Staat die Rechnung bezahlt: https://github.com/freedomtools/nsafs

    • Das ist einfach nur Write-only Memory mit zusätzlichen Schritten.
      https://en.wikipedia.org/wiki/Write-only_memory_(joke)
    • Bei einem Firmeninterview vor langer Zeit erzählte mir der Interviewer, dass er als Venture-Capital-Investor in ein Projekt investiert habe, das einen gigantischen Zufallszahlenstrom erzeugen sollte.
      Die Idee war, einen beliebigen Index zu wählen und den privaten Schlüssel mit der Gegenstelle zu teilen, sodass man den darauffolgenden Text als One-Time Pad verwenden könnte. Die Logik war, dass die NSA zum Entschlüsseln den gesamten mit GB/s erzeugten Stream puffern und speichern müsste, aber praktisch wirkte das auf mich nicht besonders sinnvoll.

  • Erwähnenswert ist, dass es mit zunehmender Datenlänge extrem unwahrscheinlich wird, dass Index und Länge der entsprechenden Sequenz in π kleiner sind als die Originaldaten.

    • Scheint sich leicht lösen zu lassen. Man speichert Index und Länge in π einfach erneut als Index und Länge in π.
    • An der Uni dachte ich einmal, man könnte Telefonnummern komprimieren, indem man sie als Index in π angibt, aber meine 7-stellige Telefonnummer lag an einem 8-stelligen Index.
      Ich hatte nicht die Rechenressourcen, um eine 10-stellige Nummer inklusive Vorwahl zu finden.
    • Der Index für eine Datei mit 20 Zeilen wird dann zu <20TB number>
    • Im Originaltext wird genau das angesprochen.

      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 π.

  • Das sind verwandte Beiträge. Gibt es noch mehr?
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=36357466 - Juni 2023, 107 Kommentare
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=28699499 - September 2021, 30 Kommentare
    PiFS – The Data-Free Filesystem - https://news.ycombinator.com/item?id=26208704 - Februar 2021, 1 Kommentar
    Πfs: Never worry about data again - https://news.ycombinator.com/item?id=21359338 - Oktober 2019, 1 Kommentar
    The π Filesystem for FUSE: Store Your Data in π - https://news.ycombinator.com/item?id=19223032 - Februar 2019, 1 Kommentar
    pifs - Avoid disk space usage by saving your files in the digits of Pi - https://news.ycombinator.com/item?id=18687275 - Dezember 2018, 1 Kommentar
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=13869691 - März 2017, 105 Kommentare
    Πfs: Stores your data in π - https://news.ycombinator.com/item?id=10856108 - Januar 2016, 1 Kommentar
    Πfs: Never worry about data again - https://news.ycombinator.com/item?id=10847693 - Januar 2016, 1 Kommentar
    File system that stores location of file in Pi - https://news.ycombinator.com/item?id=8018818 - Juli 2014, 98 Kommentare
    100% Compression Using Pi - https://news.ycombinator.com/item?id=6698852 - November 2013, 32 Kommentare
    Reposts sind nach ungefähr einem Jahr in Ordnung, und Links zu früheren Threads sind für Leser gedacht, die tiefer einsteigen möchten

    • Ich frage mich, wie solche Listen erzeugt werden

  • Daran musste ich auch denken: https://www.spronck.net/sloot.html
    Zusätzliche Lektüre: https://en.wikipedia.org/wiki/Sloot_Digital_Coding_System

    • Ich habe mir das früher ein wenig angesehen, und was Sloot gemacht hat, war zumindest in gewissem Maß neuartig
      Die tatsächliche Kodierungsmethode bestand darin, jede Zeile des Videos in einer Datenbank zu speichern und jedes Frame als Sequenz von Zeilen-Lookups zu kodieren, woraufhin diese kodierten Frames wiederum in einer weiteren Datenbank gespeichert wurden. Jedes Video wurde so zu einer Sequenz von Frame-Lookups
      Deshalb war eine Demo möglich, die auf Hardware der späten 90er 16 Videos gleichzeitig flüssig abspielte. Jedes Frame war eine Sequenz von Zeilen-Lookups, daher war es nicht aufwendiger als ein einzelnes Video über den ganzen Bildschirm, wenn man den Bildschirm horizontal in 16 Teile aufteilte und 16 Videos gleichzeitig abspielte
      Aus demselben Grund waren auch Vor- und Rücklauf flüssig, weil jedes Frame einzeln dekodiert wurde. Im Gegensatz zu traditioneller Videokompression musste man nicht an jedem Keyframe Deltas berechnen, daher war 2x-Wiedergabe nicht schwieriger als 1x-Wiedergabe
      Natürlich hätte man Videodateien nicht in Größen wie 8 KB speichern können, aber wenn zum Beispiel eine Staffel einer Fernsehserie in der Datenbank lag, mussten Vor- und Abspann nur einmal gespeichert werden

    • 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.
      Aber π ist unendlich. Solange also Moores Gesetz weiter auf unserer Seite ist, wird dieses geniale Gerät funktionieren

  • One of the properties that π is conjectured to have is that it is normal
    Das entscheidende Wort hier ist conjectured
    Ich freue mich, diese Art von kleiner pedantischer Genauigkeit zu sehen, über die ich oft stolpere. Für nicht konstruierte irrationale Zahlen ist bislang weder bewiesen, dass sie normale Zahlen sind, noch dass sie jede endliche Zeichenfolge enthalten

    • Ich frage mich, was „nicht konstruiert“ hier bedeutet

  • In this implementation, to maximise performance, we consider each individual byte of the file separately, and look it up in π.
    Wenn man jedes Bit einzeln betrachtet, wäre die Performance noch besser. Man braucht nur die Indizes 2 und 33, und diese lassen sich effizient auf die Bits des Speichers abbilden

  • Es ist unangenehm, sich klarzumachen, dass π alles Wissen aus Vergangenheit und Zukunft enthält, sogar wann ich sterbe

    • Das gilt genauso für jede andere zufällige unendliche Bitfolge. Das, was der Intuition widerspricht, kommt nicht von π, sondern von der Unendlichkeit
      Außerdem kann man nicht wirklich sagen, dass sie alles Wissen über Vergangenheit und Zukunft enthält. Denn sie enthält ebenso alle möglichen Unwahrheiten über Vergangenheit und Zukunft, und zwar auf eine Weise, die sich nicht von den Wahrheiten unterscheiden lässt
      Informationen als Offset in einer pseudorandomisierten Sequenz zu kodieren, ist speichereffizienter nicht besser, als die Information direkt zu speichern
    • Das Schlimmste ist, dass auch Star Wars 4–6 aus einer alternativen Zeitlinie enthalten ist, in der Chris Pratt als Han Solo besetzt wurde
      Fun Fact: „Chrispratt“ bedeutet im Alt-Kalifornischen „Joel McHale wollte die Rolle nicht“
    • Wer daran Spaß hat, würde vermutlich The Library of Babel von Jorge Borges gerne lesen
      https://dn760100.eu.archive.org/0/items/TheLibraryOfBabel/ba...
    • Wer beginnt, π vorauszulesen, bekommt immer die frischesten Ziffern. Perfekte Verschlüsselung
    • Es enthält auch alle Fake News aus Vergangenheit und Zukunft, und man kann nicht erkennen, was davon echt ist

  • Ich erinnere mich dunkel daran, dass es früher mal einen Beitrag in einem Kompressions-Benchmark gab, der den Dateinamen als Teil der Eingabe für den Dekompressionsalgorithmus behandelte und so den Benchmark geschickt austrickste
    Der Benchmark maß nur die Dateigröße, daher konnte man diese Kennzahl schlagen

  • Beruht das nicht auf Eigenschaften von π, die bisher noch nicht bewiesen sind? Man bräuchte die Enthaltenheit aller endlichen Zeichenfolgen oder Normalität, aber beides ist nicht bewiesen