Gibt es Komprimierungsalgorithmen, die auf PI basieren?

11

Was wir wissen ist, dass π unendlich ist und höchstwahrscheinlich jede mögliche endliche Folge von Ziffern enthält ( disjunktive Folge ).

Ich habe kürzlich einen Prototyp von πfs gesehen, der davon ausgeht , dass jede Datei, die Sie erstellt haben (oder jemand anderes) oder die Sie erstellen werden, bereits vorhanden ist. Es geht also darum, sie zu extrahieren. Es gibt auch piFile, mit dem Sie Ihre Dateien in pi-Metadaten konvertieren können.

Es gibt bereits eine BBP-Formel (als Teil der experimentellen Mathematik), mit der wir die n- te Binärziffer von pi berechnen können . Wenn wir also die Position unseres Starts und die Länge der Daten speichern, können wir theoretisch die Daten extrahieren, die für uns von Interesse sind. Es gibt einige Argumente dagegen, dass unsere Metadaten (z. B. der Versatz zu unseren Daten) größer sein könnten als die extrahierten Daten. Die Matrixsymbole und π können in Base-256 codiert werden, um die Effizienz zu erhöhen (siehe Witz ).

Aufgrund der obigen Ausführungen lautet meine Hauptfrage:

  • Gibt es Komprimierungsalgorithmen, die auf PI basieren?

Wenn nicht, macht es Sinn? Oder gab es Forschungen in diesem Bereich?

Oder vielleicht ist π nicht das richtige, also was ist mit Eulers Konstante oder Tau (τ)? Würde es einen Unterschied machen?


Das Nachschlagen von schmutzigen Wörtern in Zahlen macht viel mehr Spaß als das Nachschlagen im Wörterbuch!  ASS: pi Position 590.725 (ASCII-Codierung).  BUTT: Position 177.031.174.  BOOB: Position 32.355.500.  8 == D befindet sich an Position 158.907.339.  Darf ich nur sagen: Wie erotisch

Bildnachweis: Dinosaurier-Comics


Siehe auch:

Kenorb
quelle
15
Lieber T-rex, Ihre Schlussfolgerung in Bild 2 folgt in keiner Weise aus der Aussage in Bild 1. Kein Wunder, dass Ihre Art ausgestorben ist. Ihr
David Richerby
2
Tatsächlich ist es ein offenes und / oder wahrscheinlich unentscheidbares Problem , festzustellen, ob in im Allgemeinen eine lange Ziffernfolge vorkommt. Schlagen Sie vor , die Kolmogorov-Komplexitätstheorie zu studierenπ
vzn
1
Sind Sie sicher, für alle möglichen Bits (Daten), könnten Sie meist die Instanz auf der pi herauszufinden, innerhalb 2 N ten Position (Metadaten)? Es muss sein, damit es als "Komprimierung" bezeichnet wird. N2N.
16онстантин Ван

Antworten:

17

Ihr Vorschlag macht aus vielen Gründen wenig Sinn. Wenn Sie versuchen, eine große Datei zu komprimieren, beispielsweise eine Datei mit einer Größe von Byte, müssen Sie zunächst einen Platz in der binären Erweiterung von π finden, der mit Ihrer Datei übereinstimmt. Da sich die Datei 128 lange Bits, würde man diese Stelle erwarten , dass die auf rund 2 128 - te Bit. Es wäre also ziemlich schwer zu finden. Dies liegt nicht nur daran, dass wir weit in die Erweiterung vordringen müssen, sondern auch daran, dass wir 2 128 verschiedene Standorte ausprobieren müssen, bevor wir einen Treffer finden.16π12821282128

Zweitens, während in einigen Fällen Ihr Schema zu einer starken Komprimierung führt, geschieht dies nur, wenn eine bestimmte Zeichenfolge vergleichsweise früh in der Erweiterung von . Es gibt keinen Grund, warum Sie jemals eine solche Zeichenfolge komprimieren möchten. Im Gegensatz dazu versuchen andere Komprimierungsalgorithmen, eine Struktur in den Daten zu finden, und haben Garantien, die zeigen, dass sie eine solche Struktur immer ausnutzen können, wenn sie existiert.π

Das Ändern von mit einer anderen Zahl würde das Bild nicht ändern. Der Algorithmus ist zu spezifisch und komprimiert nur Zeichenfolgen, an denen wir nicht wirklich interessiert sind. und in der Kompressionsphase sehr ineffizient.π

Yuval Filmus
quelle
14

Basierend auf Yuvals Antwort, mit einer etwas anderen Erklärung und einem Beispiel, um das Problem zu beleuchten.

Theorie

Nehmen Sie eine Byte lange Datei ( 128 Bit). Der Komprimierungsalgorithmus folgt:16128

  1. Bestimmen Sie, wo die binäre Erweiterung von mit dem Inhalt übereinstimmt.π
  2. Speichern Sie den Offset und die Anzahl der sequenzierten Bits ( ).128

Der Offset für den Dateiinhalt sollte um das te Bit liegen. Das Auffinden des Offsets ist jedoch zeitaufwändig, da Folgendes erforderlich ist:2128

  • eine tiefe Suche nach dem Bitmuster; und
  • 2128

ππ

Siehe auch Informationsentropie .

Beispiel

log2(938933556)29.830

π597,507,393log2(597507393)29.230

Vielleicht können wir die Zahlen aufteilen?

  • 1,124
  • 1,216
  • 11,727

36

  • 15,312,393
  • 8

2730

N

Dave Jarvis
quelle
2

Gibt es Komprimierungsalgorithmen, die auf PI basieren?

Ja, https://github.com/divinity76/pi_compression

macht das Sinn?

Nein, das Speichern der Offsets benötigt normalerweise mehr Speicherplatz als Sie sparen, zumindest mit der obigen Implementierung (3 bemerkenswerte Dinge, die verbessert werden könnten, es werden jedoch nur die ersten 2 ^ 32 Bytes einer binären Darstellung von pi berücksichtigt, und es verwendet eine übermäßige Anzahl von Bits, um die Anzahl der übereinstimmenden Bytes pro Offset zu speichern, nämlich 8 Bits, während das Testen zeigt, dass 3 Bits optimal wären, und es werden nur Vollbyte-Übereinstimmungen berücksichtigt. Wenn also irgendwo eine 15-Bit-Übereinstimmung vorliegt, wird dies der Fall sein wird nur als 8-Bit-Übereinstimmung betrachtet. Auch wenn die letzten 4 Bits eines Bytes übereinstimmen, aber nicht Bit 3, und die ersten 4 Bits des nächsten Bytes übereinstimmen, aber nicht Bit 5, wird dies nicht als Übereinstimmung bei betrachtet alle)

Oder gab es Forschungen in diesem Bereich?

ähm sicher, deshalb habe ich die obige Implementierung geschrieben, und die Ergebnisse scheinen zu sein, dass Sie innerhalb der ersten 4 GB pi wahrscheinlich 4 passende Bytes von ... so ziemlich allem finden, was sehr schwierig, wenn nicht unmöglich ist. Um eine Komprimierung zu erreichen, habe ich zumindest versagt. (aber meine Implementierung ist nicht optimal, wie oben erläutert) - auch die Komprimierung ist sehr langsam, aber meine Implementierung ist Single-Threaded, aber der Algorithmus ermöglicht Multithreading, wenn jemand den Code schreiben könnte, was eine Skalierungsleistung mit ermöglichen würde die Anzahl der verfügbaren Kerne.

Die Dekompression ist jedoch sehr schnell.

hanshenrik
quelle
0

Gibt es Komprimierungsalgorithmen, die auf PI basieren?

ππ

XπX

ππ

Selbst wenn gezeigt würde, dass eine mathematische Konstante die bemerkenswerte Eigenschaft hat, "alle Zeichenfolgen zu enthalten", besteht ein einfaches Argument darin, dass der Komprimierungsalgorithmus "zu viel Zeit" damit verbringen würde, nach der Position der Zeichenfolge zu suchen, und die Beschreibung ihrer Position häufig a benötigt lange (er) Ziffernfolge.

siehe auch / kontrast / versuche mich mit einer ähnlich hochstimmigen Frage zu versöhnen, wie kann entschieden werden, ob pi eine Folge von Ziffern enthält . (cs.se) (Hinweis: Der Titel kann als etwas irreführend angesehen werden)

vzn
quelle