πFS - un sistema de archivos que guarda datos en π en lugar de un disco duro

 (github.com/philipl)
2 puntos por GN⁺ 4 시간 전 | 1 comentarios | Compartir por WhatsApp
  • πfs es un sistema de archivos que implementa la idea de guardar datos en π en lugar de almacenarlos en un disco duro, por lo que no usa espacio, y se basa en la premisa central de que π contiene todos los archivos posibles
  • Se explica a partir de la conjetura de que π es normal (normal number), lo que implicaría que en su representación hexadecimal existen todos los archivos finitos
  • Si se conoce el índice del archivo dentro de π y su longitud, es posible extraerlo con la fórmula Bailey–Borwein–Plouffe; esta implementación consulta cada byte del archivo individualmente dentro de π por razones de rendimiento
  • Al ejecutarlo se usa el formato πfs -o mdd=<metadata directory> <mountpoint>, y el metadata directory almacena metadatos como el nombre del archivo y su ubicación dentro de π
  • Para compilarlo se requieren los paquetes autoconf, automake y libfuse, y el proceso de compilación sigue el flujo ./autogen.sh, ./configure, make, make install
  • La implementación actual es un prototipo inicial, y se menciona como ejemplo que guardar un archivo de texto de 400 líneas tomó 5 minutos
  • Entre las posibilidades futuras se mencionan búsqueda y consulta con longitud de ejecución variable, Arithmetic Coding, consultas en paralelo, consultas de π basadas en la nube y πfs para Hadoop

Lecturas relacionadas

1 comentarios

 
GN⁺ 4 시간 전
Comentarios en Hacker News

  • Me hizo recordar cuando intenté usar la Biblioteca de Babel como herramienta de compresión de datos
    Gracias a eso me metí en un rabbit hole interesante y fue la primera vez que conocí la teoría de la información
    La conclusión era que, para representar la dirección de ubicación de los datos, también se necesita casi la misma cantidad de información que los propios datos, así que no sirve mucho para compresión y se parece más a un experimento mental interesante
    Lo interesante visto desde hoy es que los LLM son una forma de compresión con pérdida que sí logra en la práctica la esencia del objetivo que esas herramientas no pudieron alcanzar. Claro, hay pérdida y se necesita una base gigantesca

    • Este video probablemente resulte interesante: Reinventing Entropy Compression is Intelligence Part 1, 3Blue1Brown
      https://youtu.be/l6DKRf-fAAM?is=ne73FCJ7ErXhzZ-v
    • 3Blue1Brown acaba de publicar un video sobre la conexión entre inteligencia y compresión
      https://youtu.be/l6DKRf-fAAM
    • En cierto sentido, la ciencia es la forma más extrema de compresión. La mecánica newtoniana explica una enorme cantidad de fenómenos con apenas unas cuantas líneas de texto
    • Si piensas en el nivel de compresión, es bastante impresionante. Creo que un comentario que escribí antes sigue siendo correcto, aunque me equivoqué en que deberían ser bits y no bytes: https://news.ycombinator.com/item?id=39559969
      Un cálculo aproximado para almacenar 4-gramas válidos, es decir, secuencias de cuatro palabras, sería 10 mil millones × 14 bits por palabra = unos 17 GB para el total de 10 mil millones. Y aun así, un LLM 100 veces más pequeño puede escribir prosa coherente

  • Me hizo pensar en nsafs, es decir, el National Security Agency Filesystem. La idea es que es “gratis” porque el gobierno paga el costo: https://github.com/freedomtools/nsafs

    • Esto no es más que una memoria de solo escritura con pasos extra
      https://en.wikipedia.org/wiki/Write-only_memory_(joke)
    • Hace tiempo, en una entrevista en una empresa, el entrevistador dijo que como inversionista de venture capital había invertido en un proyecto para generar un enorme flujo de números aleatorios
      La idea era elegir un índice arbitrario y compartir esa clave privada con la otra parte; después de eso, el texto podría usarse como un one-time pad. La lógica era que, para descifrarlo, la NSA tendría que almacenar en buffer y guardar todo el flujo completo generado a GB/s, pero no parecía muy práctico

  • Vale la pena señalar que, a medida que crece la longitud de los datos, la probabilidad de que el índice y la longitud de esa secuencia dentro de π sean más pequeños que los datos originales se vuelve extremadamente baja

    • Parece fácil de resolver. Basta con registrar el índice y la longitud dentro de π otra vez como índice y longitud dentro de π
    • En la universidad pensé que podría comprimir un número de teléfono dándolo como índice dentro de π, pero un número telefónico de 7 dígitos estaba en un índice de 8 dígitos
      No tenía los recursos de cómputo para buscar un número de 10 dígitos incluyendo el código de área
    • El índice de un archivo de 20 líneas termina siendo <20TB number>
    • El artículo original habla de esto

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

  • Son publicaciones relacionadas. ¿Hay más?
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=36357466 - junio de 2023, 107 comentarios
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=28699499 - septiembre de 2021, 30 comentarios
    PiFS – The Data-Free Filesystem - https://news.ycombinator.com/item?id=26208704 - febrero de 2021, 1 comentario
    Πfs: Never worry about data again - https://news.ycombinator.com/item?id=21359338 - octubre de 2019, 1 comentario
    The π Filesystem for FUSE: Store Your Data in π - https://news.ycombinator.com/item?id=19223032 - febrero de 2019, 1 comentario
    pifs - Avoid disk space usage by saving your files in the digits of Pi - https://news.ycombinator.com/item?id=18687275 - diciembre de 2018, 1 comentario
    πfs – A data-free filesystem - https://news.ycombinator.com/item?id=13869691 - marzo de 2017, 105 comentarios
    Πfs: Stores your data in π - https://news.ycombinator.com/item?id=10856108 - enero de 2016, 1 comentario
    Πfs: Never worry about data again - https://news.ycombinator.com/item?id=10847693 - enero de 2016, 1 comentario
    File system that stores location of file in Pi - https://news.ycombinator.com/item?id=8018818 - julio de 2014, 98 comentarios
    100% Compression Using Pi - https://news.ycombinator.com/item?id=6698852 - noviembre de 2013, 32 comentarios
    Los reposts parecen aceptables después de más o menos un año, y los enlaces a hilos pasados son para lectores que quieran profundizar más

    • Me da curiosidad cómo generan este tipo de listas

  • Esto también me vino a la mente: https://www.spronck.net/sloot.html
    Lectura adicional: https://en.wikipedia.org/wiki/Sloot_Digital_Coding_System

    • Hace tiempo investigué un poco esto, y lo que hizo Sloot sí fue, al menos en cierta medida, novedoso
      El esquema real de codificación consistía en almacenar cada línea del video en una base de datos, codificar cada cuadro como una secuencia de búsquedas de líneas, y luego guardar ese cuadro codificado en otra base de datos. Cada video terminaba siendo una secuencia de búsquedas de cuadros
      Por eso era posible la demostración de reproducir 16 videos al mismo tiempo con fluidez en hardware de finales de los 90. Como cada cuadro era una secuencia de búsquedas de líneas, dividir la pantalla en 16 franjas horizontales y reproducir 16 videos simultáneamente no era más costoso que reproducir un solo video a pantalla completa
      Del mismo modo, como cada cuadro se decodificaba de manera individual, el avance rápido y el rebobinado también eran fluidos. A diferencia de la compresión de video tradicional, no hacía falta calcular diferencias desde cada keyframe, así que reproducir a 2x no era más exigente que a 1x
      Claro que no se podían guardar archivos de video en algo como 8 KB, pero, por ejemplo, si una temporada de una serie de TV estaba en la base de datos, los créditos iniciales y finales solo tenían que almacenarse una vez

    • 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.
      Pero π es infinito. Así que, mientras la ley de Moore siga jugando a nuestro favor, este ingenioso dispositivo funcionará

  • One of the properties that π is conjectured to have is that it is normal
    La palabra clave aquí es conjectured
    Me alegra ver aparecer este pequeño tema de rigor del que suelo obsesionarme. Todavía no se ha demostrado de ningún número irracional no construido que sea un número normal o que contenga todas las cadenas finitas

    • Me pregunto qué significa aquí “no construido”

  • In this implementation, to maximise performance, we consider each individual byte of the file separately, and look it up in π.
    Viendo cada bit por separado, el rendimiento sería aún mejor. Solo se necesitarían los índices 2 y 33, y eso se puede mapear eficientemente a los bits del almacenamiento

  • Es incómodo darse cuenta de que π contiene todo el conocimiento del pasado y del futuro, incluso cuándo voy a morir

    • Lo mismo aplica para cualquier otra secuencia infinita aleatoria de bits. Lo que va contra la intuición no viene de π, sino del infinito.
      Tampoco puede decirse que contenga todo el conocimiento del pasado y del futuro, porque también incluye todas las falsedades posibles sobre el pasado y el futuro, de una forma indistinguible de la verdad.
      Codificar información como un desplazamiento dentro de una secuencia seudorrandom es menos eficiente para almacenar que guardar la información directamente
    • Lo peor es que también contiene Star Wars 4~6 de una línea temporal alternativa en la que Chris Pratt fue elegido como Han Solo
      Dato curioso: “Chrispratt” en antiguo californiano significa “Joel McHale no quería ese papel”
    • Probablemente disfrutarías The Library of Babel de Jorge Borges
      https://dn760100.eu.archive.org/0/items/TheLibraryOfBabel/ba...
    • Quien empieza a leer adelantándose a π siempre obtiene los números más frescos. Es un cifrado perfecto
    • También contiene todas las fake news del pasado y del futuro, y no se puede saber cuál lado es el verdadero

  • Recuerdo vagamente que hace tiempo una entrada de cierto benchmark de compresión logró pasarlo de forma tramposa al tratar el nombre del archivo como parte de la entrada del algoritmo de descompresión
    Como el benchmark solo medía el tamaño del archivo, pudo ganarle a esa métrica

  • ¿No depende esto de una propiedad de π que todavía no ha sido demostrada? Haría falta la inclusión de todas las cadenas finitas o la normalidad, y ninguna de las dos ha sido probada