Wie kann man die Entropie einer Datei praktisch messen?

9

Ich versuche jetzt, viele nicht redundante (tatsächliche) Informationen zu messen, die meine Datei enthält. Einige nennen dies die Menge an Entropie.

Natürlich gibt es das Standard-p (x) -Protokoll {p (x)}, aber ich denke, dass Shannon es nur unter dem Gesichtspunkt der Übertragung durch einen Kanal in Betracht gezogen hat. Daher erfordert die Formel eine Blockgröße (etwa in Bits, typischerweise 8). Für eine große Datei ist diese Berechnung ziemlich nutzlos und ignoriert Kurz- bis Fernkorrelationen zwischen Symbolen.

Es gibt binäre Baum- und Ziv-Lempel-Methoden, aber diese scheinen sehr akademischer Natur zu sein.

Die Komprimierbarkeit wird auch als Maß für die Entropie angesehen, es scheint jedoch keine Untergrenze für den Grad der Komprimierung zu geben. Für meine Datei hiss.wav,

  • original hiss.wav = 5,2 MB
  • Entropie über die Shannon-Formel = 4,6 MB
  • hiss.zip = 4,6 MB
  • hiss.7z = 4,2 MB
  • hiss.wav.fp8 = 3,3 MB

Gibt es eine vernünftigerweise praktikable Methode, um zu messen, wie viel Entropie in hiss.wav vorhanden ist?

entropy Paul Uszak
quelle
1
Ich verstehe nicht, was Sie unter "hoch akademisch" verstehen.
David Richerby
Dead 'ard. Ich hätte gedacht, dass es angesichts des Umfangs der Forschungsgelder, die weltweit für die Maximierung der Datenübertragung und -speicherung aufgewendet werden, eine besser entwickelte Methode gibt, um abzuschätzen, mit wie viel von dem verdammten Material Sie tatsächlich zu tun haben. Ich hätte es nicht für unmöglich gehalten, dass es ein Dateidienstprogramm gibt, mit dem Sie einige Daten übergeben, die die theoretische Entropieschätzung ausgeben. Worauf spielen die Telekommunikations- und Festplattenhersteller?
Paul Uszak

Antworten:

9

Entropie ist ein Merkmal einer Zufallsvariablen . Eine gegebene Datei hat keine Entropie, da sie konstant ist. Entropie ist in vielen Situationen sinnvoll, in denen es keinen Kanal gibt, und Sie können sie auf ein zufälliges Ensemble von beispielsweise WAV-Dateien anwenden, die aus einer bestimmten Quelle generiert wurden. In diesem Fall ist Ihr die gesamte WAV-Datei.x

Man kann sich vorstellen, dass die eigentliche WAV-Datei (mit Ausnahme des Headers) von einer Markovian-Quelle generiert wurde. Diese Quelle erzeugt Klangamplituden ("Samples") in einer Sequenz, die jeweils von den vorhergehenden abhängen. Nachdem der Prozess sehr lange ausgeführt wurde, kommt die Entropie jeder Probe (genauer gesagt die bedingte Entropie bei den vorhergehenden Proben) einem Grenzwert sehr nahe, den wir als Entropie der Quelle definieren. Die Entropie von Proben ist das N- fache dieser Zahl (im Grenzfall; genauer gesagt messen wir die bedingte Entropie). Lempel und Ziv zeigten, dass, wenn die Probenentropie H- Bits beträgt , ihr Algorithmus N Proben auf H N + o komprimiertN.N.H.N. Bits mit hoher Wahrscheinlichkeit (die Wahrscheinlichkeit liegt über den Abtastwerten). Die Lempel-Ziv-Komprimierung ist in der Praxis sehr beliebt und wird beispielsweise im gängigenFormat verwendet.H.N.+Ö(N.)gzip

Aufgrund dieses Ergebnisses von Lempel und Ziv kann die Entropie einer Quelle durch Komprimieren einer langen Folge von Abtastwerten unter Verwendung des Lempel-Ziv-Algorithmus angenähert werden. Dies schätzt nicht die Entropie der spezifischen Proben, was kein genau definiertes Konzept ist (eine konstante Sequenz hat keine Entropie), sondern die Entropie der Quelle, die sie erzeugt.

Ein verwandtes Konzept ist die algorithmische Entropie , auch als Kolmogorov-Komplexität bekannt . Dies ist die Länge des kürzesten Programms, das Ihre Datei generiert. Diese Menge ist für eine einzelne Datei sinnvoll. Im Fall einer Datei, die von einer zufälligen Quelle generiert wurde, zeigt das Lempel-Ziv-Theorem, dass die algorithmische Entropie einer Datei mit hoher Wahrscheinlichkeit durch ihre Shannon-Entropie begrenzt ist. Leider ist die algorithmische Entropie nicht berechenbar, daher handelt es sich eher um ein theoretisches Konzept.

Um das Bild zu vervollständigen, schlage ich vor, Shannons Artikel über Vorhersage und Entropie des gedruckten Englisch zu lesen, um einen anderen Ansatz zur Schätzung der Entropie einer Quelle zu finden.

Yuval Filmus
quelle
Ich habe. Und das Papier von Schurmann & Grassberger. Basierend auf ihren geschätzten Entropien für Englisch scheint es, dass die beste Entropieschätzung, die wir erhalten können, die Komprimierung mit einer PAQ8-Variante wie fp8 ist. Es gibt und meine Ergebnisse heiraten ziemlich gut für Shakespeares Prosa.
Paul Uszak
Das Problem scheint jedoch zu sein, dass ich gedacht hätte, dass es einen begrenzenden theoretischen Wert für die Entropie einer Quelle geben muss. Die Bestimmung durch Komprimierung spiegelt nur die Effizienz des Komprimierungsalgorithmus wider. Empirisch ist Ihr gzip gut, aber 7z ist besser. Und fp8 ist viel besser, wie in meiner Frage gezeigt. Könnte ich feststellen, dass hiss.wav nur 10 Bytes Gesamtentropie enthält, wenn ich in ferner Zukunft fp12000 verwende?
Paul Uszak
Entropie ist keine Eigenschaft einer Datei. Jede einzelne Datei hat keine Entropie. Entropie ist vielmehr eine Eigenschaft einer zufälligen Quelle. Ein für bestimmte Dateien geeignetes Maß für die Zufälligkeit ist die Kolmogorov-Komplexität (auch als algorithmische Entropie bezeichnet). Leider ist dieses Maß nicht berechenbar.
Yuval Filmus
Wenn Sie eine Datei komprimieren, um die Entropie einer Quelle zu schätzen, verwenden Sie einen Satz, der garantiert, dass sich die Komprimierungsrate der von der Quelle generierten Daten der Entropie der Quelle nähert. Die eigentlichen Komprimierungsprogramme wenden jedoch nicht den Vanilla-Lempel-Ziv-Algorithmus an, sondern eine praktischere Version davon. Wenn Sie die Entropie schätzen möchten, sollten Sie den Algorithmus möglicherweise unter Berücksichtigung dieses Ziels erneut implementieren.
Yuval Filmus
Ich habe eine unkonstruktive Diskussion entfernt. Kommentare sind nicht für langwierige Diskussionen gedacht, außer zur Verbesserung des vorliegenden Beitrags. Wenn Sie ehrlich über Entropie sprechen möchten, erstellen Sie bitte einen Chatraum. Denken Sie daran, es höflich zu halten.
Raphael