Können Daten auf eine Größe komprimiert werden, die kleiner als das Shannon-Datenkomprimierungslimit ist?

Ich las über Datenkomprimierungsalgorithmen und die theoretische Grenze für die Datenkomprimierung. Kürzlich bin ich auf eine Komprimierungsmethode mit dem Namen "Combinatorial Entropy Encoding" gestoßen. Die Hauptidee dieser Methode besteht darin, die Datei als die in der Datei dargestellten Zeichen, ihre Häufigkeiten und den Index dieser durch die Datei dargestellten Zeichenpermutation zu codieren.

Diese Dokumente können zur Erläuterung dieser Methode beitragen:

https://arxiv.org/pdf/1703.08127

http://www-video.eecs.berkeley.edu/papers/vdai/dcc2003.pdf

https://www.thinkmind.org/download.php?articleid=ctrq_2014_2_10_70019

Im ersten Dokument habe ich jedoch gelesen, dass sie mit dieser Methode Text unter das Shannon-Limit komprimieren können (sie haben den zum Speichern der Zeichenhäufigkeit erforderlichen Speicherplatz und den zum Speichern des Metas erforderlichen Speicherplatz nicht berücksichtigt) Daten der Datei). Ich habe darüber nachgedacht und festgestellt, dass diese Methode für sehr kleine Dateien nicht sehr effizient ist, aber auf der anderen Seite funktioniert sie möglicherweise gut mit großen Dateien. Eigentlich verstehe ich diesen Algorithmus oder das Shannon-Limit nicht ganz, ich weiß nur, dass es die Summe der Wahrscheinlichkeit jedes Zeichens multipliziert mit des Reziprokwerts der Wahrscheinlichkeit ist.$log_2$

Ich habe also einige Fragen:

1. Komprimiert diese Komprimierungsmethode Dateien wirklich auf einen Wert unterhalb der Shannon-Grenze?

2. Gibt es einen Komprimierungsalgorithmus, der Dateien unter dem Shannon-Grenzwert komprimiert (die Antwort auf diese Frage lautet meines Wissens nein)?

3. Kann es jemals eine Komprimierungsmethode geben, die Dateien auf einen Wert komprimiert, der unter dem Shannon-Grenzwert liegt?

4. Wenn die kombinatorische Codierung Dateien wirklich über die Shannon-Grenze hinaus komprimiert, ist es dann nicht möglich, die Datei immer wieder zu komprimieren, bis die gewünschte Dateigröße erreicht ist?

Eigentlich verstehe ich diesen Algorithmus oder das Shannon-Limit nicht sehr gut. Ich weiß nur, dass es die Summe der Wahrscheinlichkeit jedes Zeichens multipliziert mit log2 des Reziprokwerts der Wahrscheinlichkeit ist.

Darin liegt der Kern. Die Shannon-Grenze ist keine universelle Eigenschaft einer Textfolge. Es ist die Eigenschaft einer Textfolge und eines Modells, das (möglicherweise kontextabhängige) Wahrscheinlichkeiten für Symbole bereitstellt. Hier erfahren wir, wie gut dieses Modell den Text komprimieren kann, vorausgesetzt, das Modell ist korrekt .

Wenn Sie ein Modell zum Berechnen des Shannon-Grenzwerts verwenden und dann ein anderes Modell zum Komprimieren. Wenn das zweite Modell genauer ist, können Sie den ursprünglich berechneten Shannon-Grenzwert übertreffen, aber das ist nicht wirklich relevant.

Es ist trivial einfach zu zeigen, dass Sie unter der Shannon-Grenze komprimieren können - nehmen Sie einen betrügerischen Kompressor, der eine Reihe allgemeiner Dateien enthält, die Token zugewiesen sind. Diese Dateien werden als diese Token gespeichert. (Offensichtlich muss der Kompressor sehr groß sein oder auf einer sehr großen Bibliothek basieren.)

Der Komprimierer ist inhärent weniger effizient im Umgang mit Dateien, die sich nicht in seiner Bibliothek befinden, da er ein Token in irgendeiner Weise von einer normalen Komprimierung unterscheiden muss.

Was Sie nicht tun können, ist ein Kompressor, der das Shannon-Limit für alle Dateien übertrifft .

Sie wenden das Modell zunächst auf die Daten an und berechnen die Reihenfolge der Wahrscheinlichkeiten, z. B. , , . Um dann jedes Symbol mit der Wahrscheinlichkeit zu codieren , benötigen Sie Bits. Und angesichts eines bestimmten Modells können Sie Daten nicht besser komprimieren als die Shannon-Entropie der Wahrscheinlichkeiten, die von diesem bestimmten Modell erzeugt werden.1 / 3 1 / 6 p l o g 2 ( 1 / p $1/2$$1/3$$1/6$$p$$log_2(1/p)$

Wenn Sie jedoch ein anderes Modell anwenden, erhalten Sie eine andere Reihenfolge von Wahrscheinlichkeiten. ZB ist der Buchstabe "u" eher selten, daher kann seine Wahrscheinlichkeit über den gesamten Text 3% betragen, und es ist die Wahrscheinlichkeit, dass Sie diesem Buchstaben ein Markov-Modell der Ordnung 0 zuweisen müssen .

Da in englischen Texten nach "q" in der Regel ein "u" steht, können Sie bei Verwendung eines Modells der Ordnung 1 "u" eine viel höhere Wahrscheinlichkeit nach "q" zuweisen und so das Kompressionsverhältnis verbessern.

Darüber hinaus geben einige Modelle weniger Symbole aus als eingegebene, z. B. ersetzt LZ77 Textwiederholungen durch Rückverweise, sodass "abababab" zu "ab [2,8]" wird.

Wenn jemand über die Shannon-Entropie einiger Daten spricht, anstatt über die Daten, die von einem bestimmten Modell komprimiert wurden, meint er normalerweise die Shannon-Entropie, die von einem Modell der Ordnung 0 erzeugt wird, dh, jedem Symbol seine Wahrscheinlichkeit für den gesamten Text zuzuweisen. Offensichtlich können Sie diesen Spielraum überschreiten, indem Sie ein komplexeres Modell auf die Daten anwenden.

Eine weitere mögliche Interpretation des Textes: Mit dem angegebenen Komprimierungsalgorithmus können Sie einige Texte besser und andere schlechter komprimieren. Im Allgemeinen interessieren sich Benutzer jedoch mehr für bestimmte Dateitypen (HTML-Seiten in Englisch, 80386-Maschinencode) als für andere (Tabellen mit wirklich zufälligen Zahlen, bedeutungsloses Rauschen, das ausgewählt wurde, um Wiederholungen zu minimieren). Jedes Komprimierungsschema hat den Nachteil, dass es Daten aus der realen Welt besser komprimiert als bestimmte andere Arten von Zeichenfolgen.