πFS - le système de fichiers qui stocke les données dans π au lieu d’un disque dur

 (github.com/philipl)
2 points par GN⁺ 3 시간 전 | 1 commentaires | Partager sur WhatsApp
  • πfs est un système de fichiers qui met en œuvre l’idée de stocker les données dans π au lieu de les enregistrer sur un disque dur, sans utiliser d’espace, avec pour principe central que π contient tous les fichiers possibles
  • Cela repose sur l’explication selon laquelle, si la conjecture que π est normal est vraie, alors tout fichier fini existe dans sa représentation hexadécimale
  • Si l’on connaît l’indice du fichier dans π et sa longueur, il est possible d’extraire le fichier avec la formule de Bailey–Borwein–Plouffe ; cette implémentation interroge individuellement chaque octet dans π pour des raisons de performances
  • À l’exécution, on utilise le format πfs -o mdd=<metadata directory> <mountpoint> ; le metadata directory stocke des métadonnées comme le nom de fichier et sa position dans π
  • La compilation nécessite les paquets autoconf, automake, libfuse, et suit le flux ./autogen.sh, ./configure, make, make install
  • L’implémentation actuelle est un prototype initial ; un exemple indique qu’il a fallu 5 minutes pour stocker un fichier texte de 400 lignes
  • Parmi les possibilités futures figurent la recherche et l’accès à longueur d’exécution variable, l’Arithmetic Coding, l’accès parallèle, l’accès à π via le cloud, et πfs pour Hadoop

À lire aussi

1 commentaires

 
GN⁺ 3 시간 전
Réactions sur Hacker News

  • Cela me rappelle l’époque où j’avais essayé d’utiliser la Bibliothèque de Babel comme outil de compression de données
    Ça m’avait entraîné dans un rabbit hole passionnant, et c’est comme ça que j’ai découvert la théorie de l’information pour la première fois
    La conclusion, c’est qu’il faut presque autant d’information pour exprimer l’adresse de l’emplacement des données que pour les données elles-mêmes, donc ce n’est pas très efficace pour la compression, et c’est plutôt une expérience de pensée amusante
    Ce qui est intéressant aujourd’hui, c’est que les LLM constituent en quelque sorte une forme de compression avec perte qui réalise effectivement l’essentiel de l’objectif que ce genre d’outils n’a pas réussi à atteindre. Bien sûr, il y a de la perte, et il faut une base énorme

    • Cette vidéo devrait être intéressante : Reinventing Entropy Compression is Intelligence Part 1, 3Blue1Brown
      https://youtu.be/l6DKRf-fAAM?is=ne73FCJ7ErXhzZ-v
    • 3Blue1Brown vient justement de publier une vidéo sur le lien entre intelligence et compression
      https://youtu.be/l6DKRf-fAAM
    • D’une certaine manière, la science est la forme de compression la plus extrême. La mécanique newtonienne explique une quantité énorme de phénomènes en quelques lignes
    • Quand on pense au niveau de compression, c’est assez impressionnant. Je pense qu’un commentaire que j’avais écrit auparavant reste correct, sauf sur un point : il faudrait parler de bits et non d’octets : https://news.ycombinator.com/item?id=39559969
      Une estimation grossière pour stocker des 4-grammes valides, c’est-à-dire des séquences de quatre mots, donne environ 10 milliards × 14 bits par mot = environ 17 Go pour l’ensemble des 10 milliards. Pourtant, des LLM 100 fois plus petits peuvent déjà écrire une prose cohérente

  • Ça me fait penser à nsafs, pour National Security Agency Filesystem. L’idée, c’est que c’est « gratuit » puisque c’est le gouvernement qui paie : https://github.com/freedomtools/nsafs

    • C’est une mémoire en écriture seule avec plus d’étapes procédurales
      https://en.wikipedia.org/wiki/Write-only_memory_(joke)
    • Lors d’un entretien dans une entreprise il y a longtemps, l’intervieweur m’avait dit qu’en tant que capital-risqueur, il avait investi dans un projet visant à générer un gigantesque flux aléatoire
      L’idée était de choisir un index arbitraire et d’en partager la clé privée avec l’autre partie, puis d’utiliser ensuite le texte comme un one-time pad. Le raisonnement était que, pour le déchiffrer, la NSA devrait mettre en tampon et stocker l’intégralité du flux généré à des Go/s, mais ça ne m’avait pas semblé très pratique

  • Il vaut la peine de souligner que plus la longueur des données augmente, plus la probabilité que l’index et la longueur de cette séquence dans π soient plus petits que les données d’origine devient extrêmement faible

    • Ça semble facile à résoudre. Il suffit d’enregistrer à nouveau l’index et la longueur dans π sous forme d’un autre index et d’une autre longueur dans π
    • À l’université, je m’étais dit qu’on pourrait compresser un numéro de téléphone en le donnant comme index dans π, mais un numéro à 7 chiffres se trouvait à un index sur 8 chiffres
      Je n’avais pas les ressources de calcul pour trouver un numéro à 10 chiffres avec l’indicatif régional
    • L’index d’un fichier de 20 lignes devient un <nombre de 20 To>
    • L’article original parle bien de ce point

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

  • Voici des billets liés. Il y en a d’autres ?
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=36357466 - juin 2023, 107 commentaires
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=28699499 - septembre 2021, 30 commentaires
    PiFS – The Data-Free Filesystem - https://news.ycombinator.com/item?id=26208704 - février 2021, 1 commentaire
    Πfs: Never worry about data again - https://news.ycombinator.com/item?id=21359338 - octobre 2019, 1 commentaire
    The π Filesystem for FUSE: Store Your Data in π - https://news.ycombinator.com/item?id=19223032 - février 2019, 1 commentaire
    pifs - Avoid disk space usage by saving your files in the digits of Pi - https://news.ycombinator.com/item?id=18687275 - décembre 2018, 1 commentaire
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=13869691 - mars 2017, 105 commentaires
    Πfs: Stores your data in π - https://news.ycombinator.com/item?id=10856108 - janvier 2016, 1 commentaire
    Πfs: Never worry about data again - https://news.ycombinator.com/item?id=10847693 - janvier 2016, 1 commentaire
    File system that stores location of file in Pi - https://news.ycombinator.com/item?id=8018818 - juillet 2014, 98 commentaires
    100% Compression Using Pi - https://news.ycombinator.com/item?id=6698852 - novembre 2013, 32 commentaires
    Les reposts sont acceptables après environ un an, et les liens vers les anciens fils servent aux lecteurs qui veulent creuser davantage

    • Je me demande comment ce genre de liste est généré

  • Ça m’y fait aussi penser : https://www.spronck.net/sloot.html
    Lecture complémentaire : https://en.wikipedia.org/wiki/Sloot_Digital_Coding_System

    • J’avais un peu regardé ça il y a longtemps, et ce que Sloot faisait était au moins légèrement novateur
      La méthode d’encodage réelle consistait à stocker chaque ligne de la vidéo dans une base de données, puis à encoder chaque frame comme une séquence de consultations de lignes, avant de stocker à son tour cette frame encodée dans une autre base de données. Chaque vidéo devenait alors une séquence de consultations de frames
      C’est pour cela qu’il pouvait faire une démo avec 16 vidéos lues simultanément de façon fluide sur du matériel de la fin des années 90. Comme chaque frame était une séquence de consultations de lignes, diviser l’écran en 16 bandes verticales pour lire 16 vidéos en parallèle n’était pas plus coûteux que d’afficher une seule vidéo en plein écran
      De même, comme chaque frame était décodée individuellement, l’avance rapide et le retour arrière restaient fluides. Contrairement à la compression vidéo traditionnelle, il n’était pas nécessaire de calculer les différences à partir de keyframes, donc la lecture en 2x n’était pas plus difficile que la lecture en 1x
      Bien sûr, il n’aurait pas pu stocker des fichiers vidéo dans seulement 8 KB, mais si, par exemple, toute une saison d’une série TV se trouvait dans la base de données, il suffisait de stocker le générique de début et de fin une seule fois

    • 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.
      Mais π est infini. Donc tant que la loi de Moore continue de jouer en notre faveur, cette machine géniale fonctionnera

  • One of the properties that π is conjectured to have is that it is normal
    Le mot clé ici, c’est conjectured
    Je suis content de voir apparaître une petite question de rigueur qui m’obsède souvent. On n’a encore prouvé pour aucun irrationnel non construit qu’il est normal ou qu’il contient toutes les chaînes finies

    • Je me demande ce que signifie ici « non construit »

  • In this implementation, to maximise performance, we consider each individual byte of the file separately, and look it up in π.
    En considérant chaque bit séparément, ce serait encore plus performant. Il suffirait des indices 2 et 33, et on pourrait les mapper efficacement sur les bits du stockage

  • Il est dérangeant de réaliser que π contient toute la connaissance du passé et du futur, y compris la date de ma mort

    • C’est vrai de toute autre suite infinie aléatoire de bits aussi. La partie contre-intuitive ne vient pas de π, mais de l’infini
      On ne peut d’ailleurs pas vraiment dire qu’elle contient toute la connaissance du passé et du futur. Elle contient aussi tous les mensonges possibles sur le passé et le futur, d’une manière impossible à distinguer de la vérité
      Encoder de l’information comme un décalage dans une séquence pseudo-aléatoire est moins efficace en stockage que stocker directement l’information
    • Le pire, c’est qu’elle contient aussi l’épisode IV à VI de Star Wars dans une ligne temporelle alternative où Chris Pratt a été choisi pour jouer Han Solo
      Anecdote amusante : « Chrispratt » signifie en ancien californien « Joel McHale ne voulait pas du rôle »
    • Il apprécierait probablement The Library of Babel de Jorge Borges
      https://dn760100.eu.archive.org/0/items/TheLibraryOfBabel/ba...
    • Celui qui commence à lire π en avance obtient toujours les chiffres les plus frais. C’est le chiffrement parfait
    • Elle contient aussi toutes les fake news du passé et du futur, et il est impossible de savoir lesquelles sont vraies

  • Je me souviens vaguement qu’une participation à un benchmark de compression avait jadis contourné le test en traitant le nom du fichier comme une partie de l’entrée de l’algorithme de décompression
    Comme le benchmark ne mesurait que la taille du fichier, cela permettait de battre cette métrique

  • Est-ce que cela ne repose pas sur des propriétés de π qui n’ont pas encore été démontrées ? Il faudrait la présence de toutes les chaînes finies ou la normalité, et aucune des deux n’a été prouvée