PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : [Matlab] Histogramm und Entropie von Dateien


Spasstiger
2009-04-13, 16:29:38
Das hier ist kein Hilfegesuch, sondern einfach nur ein Beitrag.
Ich habe in Matlab ein kleines Skript zur Bestimmung des Histogramms und der Entropie von Dateien geschrieben und wollte es euch einfach nur anbieten. Gezählt wird im Histogramm die Anzahl der verschiedenen Bytes (x00 bis xFF).
Das Skript ist nützlich, um Packmethoden für Dateien zu vergleichen.

Hier das Skript:

clear;
close all;
[filename, pathname] = ...
uigetfile('*.*','Select a file ...');
show_plots=1;
fid = fopen([pathname,filename]);
values=0:1:255;
content=fread(fid);
fclose(fid);
n=hist(content,values); % absolute Häufigkeiten ermitteln
p = n ./ sum(n); % Häufigkeiten prozentual
E = -nansum(p.*log2(p)) % Entropie in Bits pro Zeichen (Byte)
F = sum(n); % Dateigröße in Bytes
S = floor(F*(8-E)/8) % theoretisch mögliche Ersparnis in Bytes
if show_plots==1
figure;
hist(content,values)
title(['Histogramm von ',filename],'Interpreter','none','FontWeight','bold');
xlabel('Byteinhalt dezimal')
ylabel('Häufigkeit')
text(127.5,max(n),...
['Dateigröße: ',num2str(F),' Bytes',sprintf('\n'),...
'Entropie: ',num2str(E),' Bits/Byte',sprintf('\n'),...
'Optimale Dateigröße: ',num2str(F-S),' Bytes',sprintf('\n'),...
'Theoretische Ersparnis: ',num2str(S),' Bytes'],...
'VerticalAlignment','bottom',...
'HorizontalAlignment','center');
ylim([0 1.3*max(n)]);
end;

Und hier zwei Beispielplots:

http://www.abload.de/img/histo_wmvndvr.png

http://www.abload.de/img/hist_optmfsd.png

Vielleicht kann ja jemand was damit anfangen. Wenn nicht, störts mich auch nicht.

rotalever
2009-04-13, 16:59:57
Was sagt denn die optimale Dateigröße bzw. theoretische Ersparnis aus?

Gnafoo
2009-04-13, 17:33:24
Ich versuchs mal zu beantworten:

Wenn die Datei nur noch die puren Informationen und keinerlei Redundanz enthält, dann bist du bei der optimalen Dateigröße. Das ist die Untergrenze, die du mittels verlustfreier Kompression nie unterschreiten kannst, wenn die Datei die selben Informationen tragen soll, d. h. eine Rekonstruktion möglich sein soll.

Die theoretische Ersparnis ist einfach die Differenz aus Dateigröße und der optimalen Größe.

Spasstiger
2009-04-13, 17:34:29
Was sagt denn die optimale Dateigröße [...] aus?
Wie groß die Datei bei gegebener Informationsmenge minimal sein kann. Also Entropie in bits pro Byte multipliziert mit der Anzahl von Bytes in der Datei.

/EDIT: Die Erklärung von Gnafoo ist natürlich ganz richtig. Redundanzfreiheit trifft es am Besten. Die theoretische Ersparnis entspricht der Redundanz in der Datei.

Monger
2009-04-13, 18:29:52
Ich bin nicht sicher ob ich den Code verstehe, aber: der berücksichtigt nur die Entropie eines einzelnen Zeichens, oder? Nicht von ganzen Wörtern, oder Wiederholungen. Die "optimale" Größe wäre das dann also nicht. Ein guter Kompressionsalgorithmus müsste da eigentlich noch mehr rausholen können.

Gast
2009-04-13, 18:43:10
bla
fängst du jetzt an, wahllos gastposings zu löschen, nur weil du unfähig bist den code zu verstehen?

Monger
2009-04-13, 18:46:45
fängst du jetzt an, wahllos gastposings zu löschen, nur weil du unfähig bist den code zu verstehen?


Wenn du nicht Willens bist, konstruktiv zum Thema beizutragen, werde ich auch weiterhin deine Beiträge trashen.
Wenn hier schon ein Beitrag à la "du schreibst Schrott" kommt, schreib wenigstens warum, und stell es richtig.

Ein normales Forenmitglied hätte ich deswegen freundlich ermahnt. Das ist bei Gästen ja leider nicht möglich.

Monger

Gast
2009-04-13, 18:50:25
Was bitte soll daran nicht konstruktiv sein, wenn man darauf hinweist, dass der Code in dieser Form so viel Ram verbraucht, dass man ihn nicht für größere Dateien benutzen kann?
Mein Matlab hat beim Versuch eine ~300MB Datei damit zu öffnen 2,5GB RAM zugemüllt und dann mit Out Of Memory aufgegeben, also halt ich das sehrwohl für konstruktiv.

Monger
2009-04-13, 18:54:49
Gut, das ist doch schonmal ne Aussage. Wesentlich besser, als hier nen Einzeiler hinzurotzen. Da du den Code ja besser verstehst als ich, wirst du sicherlich einen Vorschlag dazu machen können wie man den Speicherverbrauch reduziert.

pest
2009-04-13, 19:16:19
Du berechnest nur die Entropie der Ordnung 0 - also keine wirkliche Aussage über irgendwelche theoretischen Ersparnisse

rotalever
2009-04-13, 19:31:43
Wie groß die Datei bei gegebener Informationsmenge minimal sein kann. Also Entropie in bits pro Byte multipliziert mit der Anzahl von Bytes in der Datei.
Hmm.. Wie ist es denn mit einer 512Byte großen Datei die die Daten 00 01 ... FE FF zwei mal hintereinander enthält und einer, bei der diese bytes an zufälligen Positionen sind.
Müsste nach deinem Algorithmus nicht bei beiden Dateien der selbe Wert rauskommen? Die erste Datei kann man aber noch sehr gut komprimieren.

pest
2009-04-13, 19:36:36
Hmm.. Wie ist es denn mit einer 512Byte großen Datei die die Daten 00 01 ... FE FF zwei mal hintereinander enthält und einer, bei der diese bytes an zufälligen Positionen sind.
Müsste nach deinem Algorithmus nicht bei beiden Dateien der selbe Wert rauskommen? Die erste Datei kann man aber noch sehr gut komprimieren.

das liegt daran das er nur die Entropie der Ordnung 0 berechnet ;)

rotalever
2009-04-13, 19:46:51
das liegt daran das er nur die Entropie der Ordnung 0 berechnet ;)
Wie muss man denn dann vorgehen?
Zusätzlich alle Bytefolgen der Länge 2,3,4,... betrachten käme mir da in den Sinn, aber reicht das?

pest
2009-04-13, 19:59:45
betrachten käme mir da in den Sinn, aber reicht das?

es ist abhängig vom verwendeten (Daten-)Modell. Du kannst mit diesem Vorgang Datenstrukturen abbilden die gut durch partielles Matching erkannt werden, z.B. Texte, bei Binärdateien funktioniert das wiederum nicht so gut.

Ein (nach oben berechnetes) Modell, wird auch immer nur eine Aussage über ein anderes Modell machen können, was ähnlich arbeitet.

Spasstiger
2009-04-13, 20:24:09
Das es verschiedene Entropien gibt, war mir nicht bewusst. Ich jenne aus meinen Vorlesungen nur den Entropiebegriff wie ich ihn in meinem Skript verwendet habe, also offenbar Entropie der Ordnung 0.
Informatiker behandeln das vermutlich etwas gründlicher als wir E-Techniker.
Der Begriff Entropie kam in meinen Vorlesungen eh nur selten vor. Die ganze stochastiche Signalverarbeitung wurde bei mir ohne den Entropiebegriff aufgezogen.

Aber jetzt verstehe ich auch, warum es in der Image-Processing-Toolbox von Matlab einen Entropie-Schätzer gibt. Eine einfache, analytische Funktion wie bei mir berücksichtigt nicht alle Entropien.

pest
2009-04-13, 20:27:19
Das es verschiedene Entropien gibt, war mir nicht bewusst.

naja, es gibt nur eine Entropie, über einem variablen Alphabet ;) - wobei ein Alphabet dann halt beliebige Zustände darstellen kann.
Entropie der Ordnung 0 ist ein Begriff von mir :D

Spasstiger
2009-04-13, 20:36:56
Ich bin auf jeden Fall über eine bedingte Entropie bei Wikipedia gestoßen. Die berücksichtigt den den Fall von Rotalever. Bei Wikipedia gibts ein Beispiel dazu:
http://de.wikipedia.org/wiki/Bedingte_Entropie#Beispiel

Vielleicht baue ich mein Skript auch so um, dass ich den Entropie-Schätzer aus der Image-Processing-Toolbox verwenden kann. Allerdings steht die Toolbox wohl nicht Jedem zur Verfügung, der Matlab verwendet.

Mein Matlab hat beim Versuch eine ~300MB Datei damit zu öffnen 2,5GB RAM zugemüllt und dann mit Out Of Memory aufgegeben, also halt ich das sehrwohl für konstruktiv.
Das Problem ist mir bekannt. Ich könnte es leicht beheben, indem ich den verfügbaren Speicher auslese und dann entsprechend die Dateien Stück für Stück auslese, für jedes Teilstück die Entropie berechne und am Ende daraus die Gesamtentropie ermittle. Aber für meine Zwecke ist das nicht notwendig (zumal ich Matlab x64 verwende und 6 GiB RAM habe ;)). Wer mein Skript verwenden möchte, kann es leicht umbauen.

pest
2009-04-13, 20:49:17
Die berücksichtigt den den Fall von Rotalever.

Du bekommst ja aber je nach Ordnung einen anderen Informationsgehalt.

Am Ende bildest du praktisch ein PPM-Modell (http://de.wikipedia.org/wiki/Prediction_by_Partial_Matching) nach. Daher auch meine Verwendung des Wortes Ordnung, was eig. einen Anderen Inhalt besitzt.

Monger
2009-04-13, 23:26:20
Wie muss man denn dann vorgehen?
Zusätzlich alle Bytefolgen der Länge 2,3,4,... betrachten käme mir da in den Sinn, aber reicht das?
Das kann beliebig komplex werden. Stell dir mal zwei Sinuswellen vor, die phasenversetzt gegeneinander laufen, und dann stell dir die aufaddierten Werte vor.
Die zugrundeliegende Information wäre dann supersimpel - nämlich sin(x) + sin(z) plus irgendeine Phase. Die Zahlenfolge dazu kann aber total chaotisch aussehen. Ein guter Kompressionsalgorithmus erkennt solche Regelmäßigkeiten, aber da muss schon gewaltiger Hirnschmalz dahinterstecken.
Noch extremer: Stell dir vor du hast die Zahlenfolge von einem vielfachen von Pi dastehen, auf meinetwegen 1000 Stellen gerundet. Mathematisch lässt sich das ganz kurz und knapp beschreiben - ein Kompressionsalgorithmus beißt sich daran wahrscheinlich die Zähne aus, weil es keine sich wiederholende Folge gibt.

Klartextformate sind in der Hinsicht mittlerweile recht gut erforscht, deshalb ist da die Kompression mitunter höllisch gut.

Also: wenn es irgendein Verfahren gibt was den tatsächlichen, minimalen Informationsgehalt von etwas bestimmen kann (und zwar nicht nur näherungsweise), würde mich das auch interessieren. Halte ich aber für nahezu unmöglich.
Macht aber wahrscheinlich in der Realität auch kaum einen Unterschied.

pest
2009-04-14, 07:31:33
nämlich sin(x) + sin(z) plus irgendeine Phase. Die Zahlenfolge dazu kann aber total chaotisch aussehen. Ein guter Kompressionsalgorithmus erkennt solche Regelmäßigkeiten, aber da muss schon gewaltiger Hirnschmalz dahinterstecken.


kompressionsprogramme bedienen sich zu 99% statistischer mittel,
wenn ein programm erst gut ist, wenn es das kann was du forderst, sind alle beschissen ;)


weil es keine sich wiederholende Folge gibt.

so arbeitet aber ein kompressionsalgorithmus nicht


Klartextformate sind in der Hinsicht mittlerweile recht gut erforscht, deshalb ist da die Kompression mitunter höllisch gut.


das hat nicht viel mit Forschung zu tun. Natürliche Sprache bietet eine starke Kontextabhängigkeit,
d.h. die Wahrscheinlichkeit ist realitiv groß das du wenn ich "hall" sage "o" sagst


Also: wenn es irgendein Verfahren gibt was den tatsächlichen, minimalen Informationsgehalt von etwas bestimmen kann (und zwar nicht nur näherungsweise), würde mich das auch interessieren.


der minimale Informationsgehalt ist 0
man minimiert nicht den Informationsgehalt, man maximiert die Wahrscheinlichkeit dafür das etwas auftreten kann.
das heißt, bei dem Beispiel mit dem "hallo" das die Einzelwahrscheinlichkeit von "o" in einem Text rel. klein ist, die bedingte Wahrscheinlichkeit von "o" im Kontext von "hall" ist aber nahe 1.

Monger
2009-04-14, 08:18:25
kompressionsprogramme bedienen sich zu 99% statistischer mittel,
wenn ein programm erst gut ist, wenn es das kann was du forderst, sind alle beschissen ;)

Das hab ich nicht gesagt! ;)
Ich meinte nur, dass man sowas berücksichtigen müsste wenn man den minimalen Informationsgehalt wissen will. Dass kein aktuelles Zip Format so arbeitet, ist ja nachvollziehbar. Da müsste man höllisch viel Mathematik dahinter stecken, und die Rechenzeit fürs Zippen wäre vermutlich gigantisch.

pest
2009-04-14, 08:37:06
crap

pest
2009-04-14, 11:10:31
wenn man den minimalen Informationsgehalt wissen will.

kannst du das nochmal erläutern, ich verstehe nicht was du mit minimalem Informationsgehalt meinst.

Monger
2009-04-14, 11:21:06
kannst du das nochmal erläutern, ich verstehe nicht was du mit minimalem Informationsgehalt meinst.
Ja, war mies formuliert.

Ich meine das, was du mindestens an Information brauchst um etwas zu beschreiben. Also im Grunde die eigentliche Information, und nicht etwa die Beschreibung derselben.
Wobei man bei der Kompression ja da immer noch den Informationsaufwand für das Wörterbuch mit rein rechnen muss. Hilft ja nix, wenn du die Information in ein paar wenige Bit pressen kannst, und dafür die Metainformationen elends komplex sind.

AlSvartr
2009-04-14, 11:39:00
Will man damit nicht eigentlich im Endeffekt auf die Kolmogorov-Komplexität hinaus (also minimale Größe der Summe von Programm und Eingabedaten, die die gewünschte Information berechnen)?

..klar, das ist dann die algorithmische Komplexität...naja, ist ja im Endeffekt ohnehin nicht berechenbar - eine traurige Geschichte! ;(

pest
2009-04-14, 11:54:24
Ich meine das, was du mindestens an Information brauchst um etwas zu beschreiben. Also im Grunde die eigentliche Information, und nicht etwa die Beschreibung derselben.


ich finde diese Formulierung bringt das ganze nicht auf den Punkt,
denn wie groß ist die Information die du benötigst um etwas zu beschreiben
was sicher eintritt? Und wie groß ist die Information die du benötigst
um etwas zu beschreiben was nie eintritt? Jedesmal keine.
Das ist der Knackpunkt, warum man das nicht so betrachten kann.


Wobei man bei der Kompression ja da immer noch den Informationsaufwand für das Wörterbuch mit rein rechnen muss. Hilft ja nix, wenn du die Information in ein paar wenige Bit pressen kannst, und dafür die Metainformationen elends komplex sind.

Ein Wörterbuch ist aber immer Teil der Information die du benötigst
um etwas zu beschreiben.

Will man damit nicht eigentlich im Endeffekt auf die Kolmogorov-Komplexität hinaus (also minimale Größe der Summe von Programm und Eingabedaten, die die gewünschte Information berechnen)?

..klar, das ist dann die algorithmische Komplexität...naja, ist ja im Endeffekt ohnehin nicht berechenbar - eine traurige Geschichte! ;(

Naja die algorithmische Komplexität von Pi ist sehr klein, aber
jedes Packprogramm würd sich daran die Zähne ausbeißen, und das ist es aber Spasstiger abschätzen will.

robobimbo
2009-04-14, 14:40:30
Obwohl sich von der Entropie eines Codewortes mit der Länge 1 auch direkt durch einfache Multiplikation alle Entropien von merhstelligen Codes ableiten lassen, der Mittlere Informationsgehalt pro Symbol ist immer gleich. Durch die Erweiterung kann man sich der Entropie immer weiter annhähern bzw. im Idealfall die Entropie erreichen.

Nasenbaer
2009-04-16, 22:28:19
Das hab ich nicht gesagt! ;)
Ich meinte nur, dass man sowas berücksichtigen müsste wenn man den minimalen Informationsgehalt wissen will. Dass kein aktuelles Zip Format so arbeitet, ist ja nachvollziehbar. Da müsste man höllisch viel Mathematik dahinter stecken, und die Rechenzeit fürs Zippen wäre vermutlich gigantisch.
Wenn man die Verfahrenweise nutzen will, dass man eine Funktion findet, die die gesuchten Daten repräsentiert, dann kann man das, soweit ich das überblicke, nur mit Interpolation machen. Die Bytes wären dann Samples der zu suchenden Funktion und per Polynominterpolation könnte man dann die Funktion interpolieren.
An sich ist das auch kein Problem aber man hätte nichts davon da man für bei n Samples n Koeffizientenspeichern müsste, was im Extramfall mehr Bytes benötigen könnte.

Deswegen gibt es wohl auch kein Verfahren, dass diesen Ansatz verfolgt. Und, dass sich hinter Binärdaten mal "einfache" Funktionen wie sin(x) verstecken ist im Normalfall sicher nicht zu erwarten.
Besitzt man natürlich genauere Informationen über den Datensatz ist es wesentlich leichter Redundanzen aufzuspüren aber im Normalfall hat man diese ja gerade nicht.

DocEW
2009-04-17, 09:50:32
Wenn man die Verfahrenweise nutzen will, dass man eine Funktion findet, die die gesuchten Daten repräsentiert, ...
Wenn man einen Schritt weiter geht, und eine Menge von Funktionen sucht, ist man schon fast bei JPEG! :D

Nasenbaer
2009-04-17, 11:00:14
Wenn man einen Schritt weiter geht, und eine Menge von Funktionen sucht, ist man schon fast bei JPEG! :D
Das stimmt so nicht. Denn JPEG komprimiert ja nicht indem das Bild als Summe von Funktionen gespeichert wird. Die DCT arbeitet ja verlustfrei - ihr Vorteil ist nur, dass sich so, bezogen auf Bilder, wichtige von unwichtigen Informationen trennen lassen. Die unwichtigen Informationen werden dann durch Quantisierung reduziert. Nur so wird im Zusammenhang mit der DCT Platz gewonnen.

pest
2009-04-17, 11:12:56
Das stimmt so nicht. Denn JPEG komprimiert ja nicht indem das Bild als Summe von Funktionen gespeichert wird.


Die Darstellung des Bildes ist eine Summe von orthogonalen Basisfunktionen.

DocEW
2009-04-17, 11:48:28
Denn JPEG komprimiert ja nicht indem das Bild als Summe von Funktionen gespeichert wird. Die DCT arbeitet ja verlustfrei - ihr Vorteil ist nur, dass sich so, bezogen auf Bilder, wichtige von unwichtigen Informationen trennen lassen. Die unwichtigen Informationen werden dann durch Quantisierung reduziert. Nur so wird im Zusammenhang mit der DCT Platz gewonnen.
Völlig richtig. Ich wollte allerdings auch nicht JPEG erklären, sondern nur die Parallelen zur hier diskutierten "Suche nach repräsentierenden Funktionen" aufzeigen. ;)

Nasenbaer
2009-04-17, 20:46:23
Die Darstellung des Bildes ist eine Summe von orthogonalen Basisfunktionen.
Ich habe nichts gegenteiliges behauptet. :confused:

@DocEW
Und ich wollte aufzeigen, dass der Ansatz ein ganz anderer ist. Während JPEG durch das Verwerfen von Details Platz spart, ist der Ansatz hier, dass man Platz spart indem man eine kompaktere Beschreibungsform für ein gegebenes Signal findet - halt eine Funktion statt einer Wertetabelle.