Nach meinem Verständnis der Entropieformel wird die minimale Anzahl von Bits berechnet, die für die Darstellung einiger Daten benötigt werden. Normalerweise wird es anders formuliert, wenn es definiert wird, aber auf das vorherige Verständnis habe ich mich bis jetzt verlassen.
Hier ist mein Problem. Angenommen, ich habe eine Folge von 100 '1', gefolgt von 100 '0' = 200 Bits. Das Alphabet ist {0,1}, die Basis der Entropie ist 2. Die Wahrscheinlichkeit des Symbols "0" ist 0,5 und "1" ist 0,5. Also ist die Entropie 1 oder 1 Bit, um 1 Bit darzustellen.
Sie können jedoch run-length es mit etwas wie 100/1/100/0 codieren, wobei es die Anzahl der auszugebenden Bit gefolgt von dem Bit ist. Es scheint, als hätte ich eine kleinere Darstellung als die Daten. Vor allem, wenn Sie die 100 bis viel größere Zahl erhöhen.
Ich benutze: Ссылка als Referenz im Moment. Was habe ich falsch gemacht? Ist es die Wahrscheinlichkeit, die Symbolen zugewiesen wird? Ich denke nicht, dass es falsch ist. Oder habe ich die Verbindung zwischen Kompression und Entropie falsch verstanden? Sonst noch etwas?
Danke.
Bearbeiten
Im Anschluss an einige der Antworten, die ich verfolge, gehen wir wie folgt vor: Würden Sie die Entropieformel auf eine bestimmte Instanz einer Nachricht anwenden, um zu versuchen, ihren Informationsinhalt herauszufinden? Wäre es sinnvoll, die Nachricht "aaab" zu nehmen und zu sagen, die Entropie sei ~ 0.811. Wenn ja, was ist die Entropie von 1 ... 10 .... 0, wobei 1s und 0s n-mal unter Verwendung der Entropieformel wiederholt werden. Ist die Antwort 1?
Ja Ich verstehe, dass Sie eine Zufallsvariable Ihrer Eingabesymbole erstellen und basierend auf Ihrer Nachricht die Wahrscheinlichkeitsmassfunktion erraten. Ich versuche zu bestätigen, dass die Entropieformel die Position der Symbole in der Nachricht nicht berücksichtigt.
Oder habe ich die Verbindung zwischen Komprimierung und Entropie falsch verstanden?
Sie sind ziemlich nah dran, aber diese letzte Frage ist, wo der Fehler war. Wenn Sie etwas in ein Formular komprimieren können, das kleiner als die ursprüngliche Darstellung ist, bedeutet dies, dass die ursprüngliche Darstellung mindestens eine gewisse Redundanz aufweist. Jedes Bit in der Nachricht hat wirklich keine 1 Bit Information übermittelt.
Da redundante Daten nicht zum Informationsgehalt einer Nachricht beitragen, erhöht sie auch nicht ihre Entropie. Stellen Sie sich beispielsweise einen "zufälligen Bitgenerator" vor, der nur den Wert "0" zurückgibt. Dies vermittelt überhaupt keine Information! (Tatsächlich liefert es eine undefinierte Menge an Informationen, da jede binäre Nachricht, die nur aus einer Art von Symbolen besteht, eine Division durch Null in der Entropieformel benötigt.)
Hätten Sie im Gegensatz dazu eine große Anzahl von zufälligen Münzwürfen simuliert, wäre es sehr schwierig, die Größe dieser Nachricht um ein Vielfaches zu reduzieren. Jedes Bit würde fast 1 Bit Entropie beitragen.
Wenn Sie Daten komprimieren, extrahieren Sie diese Redundanz. Im Gegenzug zahlen Sie einen einmaligen Entropiepreis, indem Sie ein Schema entwickeln müssen, das diese Daten komprimiert und dekomprimiert. Das selbst nimmt einige Informationen.
Sie können jedoch run-length es mit etwas wie 100/1/100/0 codieren, wobei es die Anzahl der auszugebenden Bit gefolgt von dem Bit ist. Es scheint, als hätte ich eine kleinere Darstellung als die Daten. Vor allem, wenn Sie die 100 bis viel größere Zahl erhöhen.
Zusammenfassend sagt Ihnen die Tatsache, dass Sie ein Schema entwickeln könnten, um die Kodierung der Daten kleiner als die ursprünglichen Daten zu machen, etwas Wichtiges. Es heißt nämlich, dass Ihre Originaldaten sehr wenige Informationen enthielten .
Für eine gründlichere Behandlung davon, einschließlich genau, wie Sie die Entropie für jede beliebige Ziffernfolge mit ein paar Beispielen berechnen würden, finden Sie dieses kurze Whitepaper .
Sehen Sie sich die Kolmogorov-Komplexität
anDie minimale Anzahl von Bits, in die eine Zeichenfolge komprimiert werden kann, ohne Informationen zu verlieren. Dies wird in Bezug auf ein festes, aber universelles Dekompressionsschema definiert, das durch eine universelle Turing-Maschine gegeben ist.
Und beschränken Sie sich in Ihrem speziellen Fall nicht auf das Alphabet {0,1}. Für Ihr Beispiel verwenden Sie {0 ... 0, 1 ... 1} (Hundert von Nullen und Hundert von Einsen)
Ihre Codierung funktioniert in diesem Beispiel, aber es ist möglich, einen gleichgültigen Fall zu erstellen: 010101010101 ..., der als 1/0/1/1 / ... codiert wäre.
Die Entropie wird über alle möglichen Nachrichten gemessen, die im gegebenen Alphabet konstruiert werden können, und nicht nur pathologische Beispiele!
John Feminella hat es richtig gemacht, aber ich denke, es gibt mehr zu sagen.
Shannon Entropie basiert auf der Wahrscheinlichkeit, und Wahrscheinlichkeit ist immer im Auge des Betrachters.
Sie sagten, dass 1 und 0 gleich wahrscheinlich sind (0,5). Wenn das so ist, dann hat die Folge von 100 1s gefolgt von 100 0s eine Wahrscheinlichkeit von 0,5 ^ 200, von denen -log (Basis 2) 200 Bits ist, wie Sie erwarten. Die Entropie dieser Zeichenkette (in Shannon-Termen) ist jedoch ihr Informationsgehalt multipliziert mit ihrer Wahrscheinlichkeit, oder 200 * 0,5 ^ 200, immer noch eine wirklich kleine Zahl.
Das ist wichtig, denn wenn Sie Run-Length-Coding durchführen, um die Zeichenfolge zu komprimieren, wird es im Fall dieser Zeichenfolge eine kleine Länge erhalten, aber gemittelt über alle 2 ^ 200 Zeichenfolgen, wird es nicht gut tun. Mit etwas Glück wird es durchschnittlich 200, aber nicht weniger sein.
Andererseits, wenn Sie Ihre ursprüngliche Saite betrachten und sagen, dass sie so auffällig ist, dass derjenige, der sie erzeugt hat, wahrscheinlich mehr Ähnliches erzeugt, dann sagen Sie wirklich, dass ihre Wahrscheinlichkeit größer als 0,5 ^ 200 ist eine andere Annahme über die ursprüngliche Wahrscheinlichkeitsstruktur des Generators der Kette treffen, nämlich dass sie eine niedrigere Entropie als 200 Bits hat.
Ich persönlich finde dieses Thema sehr interessant, besonders wenn man sich Kolmogorov (Algorithmische) Informationen ansieht. In diesem Fall definieren Sie den Informationsinhalt eines Strings als die Länge des kleinsten Programms, das ihn generieren könnte. Dies führt zu allen möglichen Einsichten in Software Engineering und Sprachdesign.
Ich hoffe, dass hilft, und danke für Ihre Frage.
Tags und Links compression entropy information-theory