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?
Bildnachweis: Dinosaurier-Comics
Siehe auch:
Antworten:
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 π 128 2128 2128
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.π
quelle
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:16 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
Siehe auch Informationsentropie .
Beispiel
Vielleicht können wir die Zahlen aufteilen?
quelle
Ja, https://github.com/divinity76/pi_compression
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)
ä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.
quelle
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)
quelle