Datenkomprimierung mit Primzahlen

22

Ich bin kürzlich auf den folgenden interessanten Artikel gestoßen, der behauptet, zufällige Datensätze unabhängig von Art und Format der Daten immer um mehr als 50% effizient zu komprimieren.

Grundsätzlich werden Primzahlen verwendet, um eine eindeutige Darstellung von 4-Byte-Datenblöcken zu erstellen, die sich leicht dekomprimieren lassen, da jede Zahl ein eindeutiges Produkt von Primzahlen ist. Um diese Sequenzen mit den Primzahlen zu verknüpfen, wird ein Wörterbuch verwendet.

Meine Frage ist:

  • Ist das wirklich machbar, wie die Autoren es vorschlagen? Dem Papier zufolge sind ihre Ergebnisse sehr effizient und komprimieren Daten immer auf eine kleinere Größe. Wird das Wörterbuch nicht riesig groß sein?
  • Könnte dies nicht verwendet werden, um die komprimierten Daten unter Verwendung desselben Algorithmus iterativ neu zu komprimieren? Es ist offensichtlich und wurde gezeigt, dass solche Techniken (bei denen die komprimierten Daten so oft wie möglich erneut komprimiert werden, wodurch die Dateigröße drastisch reduziert wird) unmöglich sind. In der Tat gäbe es keinen Unterschied zwischen der Menge aller Zufallsdaten und den komprimierten Daten. Warum fühlt es sich also möglich an?
  • Auch wenn die Technik noch nicht perfekt ist, kann sie offensichtlich optimiert und stark verbessert werden. Warum ist dies nicht allgemein bekannt / untersucht? Wenn diese Behauptungen und experimentellen Ergebnisse in der Tat zutreffen, könnte dies dann nicht das Computing revolutionieren?
Klangen
quelle
5
Wie Sie bemerkt haben, macht das Papier wirklich starke Behauptungen. Seien Sie solchen Behauptungen gegenüber immer sehr misstrauisch, insbesondere, wenn die Zeitung an einem ungewöhnlichen Ort veröffentlicht wird (erstaunliche Zeitungen, die "Computing revolutionieren", sollten an angesehenen, bekannten Orten erscheinen, oder?).
Juho
2
es ist unmöglich, "immer zufällige Daten zu komprimieren", zB basierend auf der Kolmogorov-Komplexitätstheorie . und ein Disproof ähnelt dem, was Sie skizziert haben. Ich bin nicht sicher, ob dies eine Fehlinterpretation des Papiers oder des Originalpapiers ist. warum heben Sie nicht hervor, wo diese bestimmte Behauptung hereinkommt?
vzn
6
"Konnte dies nicht verwendet werden, um die komprimierten Daten unter Verwendung desselben Algorithmus iterativ neu zu komprimieren?" - Ja. Jeder Algorithmus, der behauptet, alle beliebigen Daten komprimieren zu können, kann rekursiv auf seinen eigenen Ausgang angewendet werden, so dass alle Daten auf 0 Bits komprimiert werden. Somit ist diese Behauptung ausgeschlossen.
Jörg W Mittag
1
@ JörgWMittag Ich habe einen Algorithmus, mit dem Sie eine Datei wiederholt auf eine kleine Anzahl von Bits komprimieren können, aber er ist äußerst unpraktisch. Funktioniert auch nur mit Dateien, die mit 1 Bit beginnen: Behandle die gesamte Datei als große Binärzahl, dekrementiere sie und verwerfe führende Nullen. Erhöhen Sie zum Dekomprimieren den Wert, und fügen Sie gegebenenfalls eine führende 1 hinzu.
user253751
3
Hinweis für sich selbst: Machen Sie sich nicht die Mühe, Beiträge in Elsevier-Journalen einzureichen - niemals.
500 - Interner

Antworten:

34

Komprimiere zufällige Datensätze immer um mehr als 50%

Das ist nicht möglich. Sie können keine zufälligen Daten komprimieren , Sie benötigen eine Struktur, die Sie ausnutzen können. Die Komprimierung muss reversibel sein, sodass Sie möglicherweise nicht alles um 50% komprimieren können, da es weitaus weniger Zeichenfolgen mit der Länge als mit der Länge n gibt .n/2n

Es gibt einige Hauptprobleme mit dem Papier:

  • Sie verwenden 10 Testdateien ohne Angabe ihres Inhalts. Sind die Daten wirklich zufällig? Wie sind sie entstanden?

  • Sie behaupten, Kompressionsverhältnisse von mindestens 50% zu erreichen, während ihre Testdaten zeigen, dass sie höchstens 50% erreichen.

Dieser Algorithmus definiert eine verlustfreie Strategie, bei der die im Dezimalzahlensystem vorhandenen Primzahlen verwendet werden

  • Was? Primzahlen sind Primzahlen unabhängig von der Basis.

  • Problem Nr. 1 bei der Dekomprimierung: Primfaktorisierung ist ein schwieriges Problem. Wie können sie es effizient erledigen?

  • Problem Nr. 2 mit der Dekomprimierung ( dies ist der Kicker ): Sie multiplizieren die Primzahlen miteinander, aber dabei verlieren Sie alle Informationen über die Reihenfolge, da . Ich glaube nicht, dass es möglich ist, mit ihrer Technik überhaupt zu dekomprimieren.25=10=52

Ich denke nicht, dass dieses Papier sehr gut ist.

Tom van der Zanden
quelle
Soweit ich verstanden habe, speichern sie die Reihenfolge der Zeichenfolgen mit der gleichen Vielzahl im Wörterbuch. Sollte dies in zufälligen Datensätzen nicht zu einem riesigen Wörterbuch führen, da es viele 4-Byte-Zeichenfolgen mit der Multiplizität 1 (oder der gleichen Multiplizität) gibt?
Klangen
@Pickle In ihrem Beispiel hat der String "@THE" die Multiplizität 2. Ich verstehe nicht, wie sie rekonstruieren können, an welchen beiden Stellen das Wort "the" stehen soll.
Tom van der Zanden
1
Ah ich sehe. Gute Beobachtung. Das ist in der Tat ein großes Problem. Wie wurde dieses Papier angenommen, um in der Zeitschrift zu erscheinen? Sollte es keine strengeren Peer-Reviews geben?
Klangen
4
@ Pickle Ja, es sollte eine strengere Überprüfung geben. Dies ist jedoch nicht immer der Fall. Manchmal schaffen es unerfahrene / faule / inkompetente Konferenzorganisatoren nicht, Peer-Reviewer rechtzeitig zu finden. Es kommt mehrfach vor, dass Artikel mit zufällig erzeugtem Kauderwelsch akzeptiert werden, und in einem Journal wurde sogar ein Artikel mit dem Titel "Hol mich von deiner verdammten Mailingliste" veröffentlicht .
Tom van der Zanden
Hahaha, das ist unglaublich. Aber gleichzeitig traurig.
Klangen
15

Ich werde mich an Tom van der Zanden wenden, der die Zeitung gelesen zu haben scheint und eine Schwäche in der Methode entdeckt hat. Obwohl ich das Papier nicht im Detail gelesen habe, scheint es eine allgemein glaubwürdige Behauptung zu sein.

Was sie behaupten, ist eine konsistente Komprimierungsrate von 50% für Textdateien (nicht "alle Dateien"), die in etwa der von LZW entspricht und etwa 10% schlechter ist als die Huffman-Codierung (vermutlich nullter Ordnung). Das Komprimieren von Textdateien um 50% ist mit einigermaßen einfachen Methoden nicht schwer zu erreichen. Es ist ein Undergraduate-Auftrag in vielen Informatikkursen.

Ich stimme zu, dass das Papier als veröffentlichte Forschung nicht sehr gut ist, und ich denke nicht, dass es gut von den Rezensenten spricht, dass dies akzeptiert wurde. Abgesehen von den offensichtlichen fehlenden Details, die es unmöglich machen, die Ergebnisse wiederzugeben (z. B. was die Textdateien waren), und von dem Versuch, sie in den Bereich der Komprimierung einzubeziehen, macht es keinen Sinn, dass sie wirklich verstehen, was ihr Algorithmus tut.

Auf der Konferenzwebsite wird ein Akzeptanzverhältnis von 1: 4 angegeben, sodass Sie sich fragen, was die Konferenz abgelehnt hat.

Pseudonym
quelle
12

Du fragst:

  • Ist das wirklich machbar, wie die Autoren es vorschlagen? Dem Papier zufolge sind ihre Ergebnisse sehr effizient und komprimieren Daten immer auf eine kleinere Größe. Wird das Wörterbuch nicht riesig groß sein?

Ja natürlich. Selbst für ihr handverlesenes Beispiel ("Der schnelle Silberfuchs springt über den faulen Hund") erzielen sie keine Komprimierung, da das Wörterbuch jede 4-Byte-Teilzeichenfolge des Texts enthält (minus 4 Byte für die eine Wiederholung von " DAS ") ... und die" komprimierte "Version des Textes müssen das ganze Wörterbuch plus all diesen Primzahlen-Mist enthalten.

  • Könnte dies nicht verwendet werden, um die komprimierten Daten unter Verwendung desselben Algorithmus iterativ neu zu komprimieren? Es ist offensichtlich und wurde gezeigt, dass solche Techniken (bei denen die komprimierten Daten so oft wie möglich erneut komprimiert werden, wodurch die Dateigröße drastisch reduziert wird) unmöglich sind. In der Tat gäbe es keinen Unterschied zwischen der Menge aller Zufallsdaten und den komprimierten Daten. Warum fühlt es sich also möglich an?

Sie scheinen wieder ein gutes intuitives Verständnis für die Situation zu haben. Sie haben intuitiv erkannt, dass kein Komprimierungsschema jemals für alle Eingaben wirksam sein kann , denn wenn dies der Fall wäre, könnten wir es einfach immer wieder anwenden, um Eingaben auf ein einzelnes Bit zu komprimieren - und dann auf Nichts!

Anders ausgedrückt: Wenn Sie alle .wav-Dateien in .mp3 komprimiert haben, können Sie die Dateigröße nicht verbessern, indem Sie sie komprimieren. Wenn Ihr MP3-Kompressor seine Arbeit erledigt hat, sind keine Muster mehr für den ZIP-Kompressor verfügbar.

(Gleiches gilt für die Verschlüsselung: Wenn ich eine Datei mit Nullen nehme und sie gemäß dem von mir gewählten Verschlüsselungsalgorithmus verschlüssele, sollte die resultierende Datei nicht komprimierbar sein , da sonst mein Verschlüsselungsalgorithmus "Muster" in die Ausgabe verliert!)

  • Auch wenn die Technik noch nicht perfekt ist, kann sie offensichtlich optimiert und stark verbessert werden. Warum ist dies nicht allgemein bekannt / untersucht? Wenn diese Behauptungen und experimentellen Ergebnisse in der Tat zutreffen, könnte dies dann nicht das Computing revolutionieren?

Diese Behauptungen und experimentellen Ergebnisse sind nicht wahr.

Wie Tom van der Zanden bereits bemerkte, ist der "Komprimierungsalgorithmus" von Chakraborty, Kar und Guchait dahingehend fehlerhaft, dass er nicht nur kein Komprimierungsverhältnis erreicht, sondern auch irreversibel ist (in mathematischer Sprache "nicht bijektiv"): Es gibt Eine Vielzahl von Texten, die alle zum selben Bild "komprimieren", weil ihr Algorithmus im Grunde genommen eine Multiplikation ist und die Multiplikation kommutativ ist.

Sie sollten sich wohl fühlen, dass Ihr intuitives Verständnis dieser Konzepte Sie sofort zum richtigen Ergebnis geführt hat. Und wenn Sie Zeit sparen können, sollten Sie Mitleid mit den Autoren des Papiers haben, die offensichtlich viel Zeit damit verbracht haben, über das Thema nachzudenken, ohne es überhaupt zu verstehen.

Das Dateiverzeichnis, das eine Ebene über der von Ihnen angegebenen URL liegt, enthält 139 "Artikel" derselben Qualität, die anscheinend alle in den "Proceedings of the International Conference on Emerging Research in den Bereichen Computer, Information, Kommunikation und Anwendungen" aufgenommen wurden. Dies scheint eine Scheinkonferenz des üblichen Typs zu sein. Der Zweck solcher Konferenzen ist es, betrügerischen Akademikern die Möglichkeit zu geben, "Veröffentlichung in einer Zeitschrift" zu behaupten, und skrupellosen Organisatoren die Möglichkeit zu geben, eine Menge Geld zu verdienen. (Weitere Informationen zu gefälschten Konferenzen finden Sie in diesem reddit-Thread oder in verschiedenen StackExchange-Beiträgen zu diesem Thema .) Scheinkonferenzen gibt es in allen Bereichen. Lerne einfach, deinem Instinkt zu vertrauen und nicht alles zu glauben, was du in einem "Konferenzablauf" liest, und du wirst es gut machen.

Quuxplusone
quelle
Vielen Dank, dass Sie klar und deutlich angegeben haben, warum dieses Papier einfach nur Mist ist, und dass es überhaupt möglich ist, dass es ursprünglich geschrieben wurde und jede Art von Überprüfung durchlaufen hat.
Vaab
Vielen Dank für Ihre prägnante Antwort. Es ist wirklich traurig, wenn Sie nicht einmal darauf vertrauen können, dass Journaleinträge zumindest von einem Kollegen überprüft werden. Dies wirft wirklich viel Licht auf die Tatsache, dass man wachsam sein muss, auch wenn man "vermeintliche" wissenschaftliche Zeitschriftenveröffentlichungen liest. Man könnte meinen, dass solche Artikel nicht nur einer Peer-Review unterzogen werden, sondern auch einer minimalen Peer-Analyse, wie es in solchen Bereichen üblich ist. Ich hoffe, dass dies einigen Menschen die Augen öffnet.
Klangen
Ich habe heute erfahren, dass es mindestens zwei US-Patente für ähnliche "unendliche Kompressionsalgorithmen" gibt. Siehe gailly.net/05533051.html
Quuxplusone
5

Die Entropie begrenzt effektiv die Leistung einer möglichst starken verlustfreien Komprimierung. Daher gibt es keinen Algorithmus, der zufällige Datensätze immer um mehr als 50% komprimieren kann.

J.-E. Stift
quelle
8
Es gibt nicht einmal einen Algorithmus, der zufällige Datensätze um immer mehr als 0,0000001% komprimieren kann.
David Richerby
1

Wiederherstellbare Komprimierungsmethoden finden im Allgemeinen ein Muster und drücken es auf vereinfachte Weise erneut aus. Einige sind sehr schlau, andere sehr einfach. Irgendwann gibt es kein Muster. Die Prozesse haben den Datensatz auf das einfachste eindeutige Muster gebracht. Alle Komprimierungsversuche von diesem Punkt an führen zu einem größeren Datensatz oder verringern die Eindeutigkeit. In magischen Zahlenkomprimierungsschemata gibt es immer einen Fehler oder einen leichten Handgriff oder einen Verlust. Seien Sie vorsichtig bei Prozessen, die behaupten, die neuesten WinZip- oder RAR-Versionen nicht zu verwenden.

SkipBerne
quelle
2
sss
1
@DavidRicherby, dann erzeugt Ihre Komprimierung des leeren Strings einen größeren Datensatz, wie von SkipBerne behauptet. Dennoch denke ich, dass seine Antwort klarstellen sollte, dass er sich auf die Neukomprimierung der vorherigen Ausgabe mit demselben Algorithmus bezieht .
Ángel
2
@ Ángel SkipBernes Behauptung ist, dass es Strings gibt, die von keinem Algorithmus komprimiert werden können (" jeder Versuch, von diesem Punkt an zu komprimieren", meine Betonung). Das ist aus dem von mir angegebenen Grund falsch: Für jede Zeichenfolge gibt es einen Algorithmus, der diese Zeichenfolge komprimiert.
David Richerby
So wie ich es interpretiere, behauptet SkipBerne, dass es für jeden Komprimierungsalgorithmus einen String gibt, der nicht komprimiert werden kann. Was wahr ist. Diese unkomprimierbare Zeichenfolge ist natürlich für verschiedene Algorithmen unterschiedlich.
Jose Antonio Reinstate Monica
@DavidRicherby Sie verlegen die Quantifizierer - es ist ziemlich klar, dass SkipBerne Folgendes geschrieben hat (für jede Komprimierungsmethode gibt es einen Punkt, nach dem es keine Komprimierung gibt), nicht das (es gibt einen Punkt, nach dem es für jede Komprimierungsmethode gibt) keine Komprimierung). Diese Antwort ist sachlich korrekt, fügt aber den älteren, besser geschriebenen Antworten nichts hinzu.
Gilles 'SO- hör auf böse zu sein'