Wie berechnet man die Entropie einer Datei?

74

Wie berechnet man die Entropie einer Datei? (Oder sagen wir einfach ein paar Bytes)
Ich habe eine Idee, bin mir aber nicht sicher, ob sie mathematisch korrekt ist.

Meine Idee ist folgende:

  • Erstellen Sie ein Array mit 256 Ganzzahlen (alle Nullen).
  • Durchlaufen Sie die Datei und erhöhen Sie für jedes ihrer Bytes
    die entsprechende Position im Array.
  • Am Ende: Berechnen Sie den "Durchschnittswert" für das Array.
  • Initialisieren Sie einen Zähler mit Null
    und
    addieren Sie für jeden Eintrag des Arrays die Differenz des Eintrags zu "Durchschnitt" zum Zähler.

Nun, jetzt stecke ich fest. Wie kann man das Zählerergebnis so "projizieren", dass alle Ergebnisse zwischen 0,0 und 1,0 liegen? Aber ich bin mir sicher, die Idee ist sowieso inkonsistent ...

Ich hoffe jemand hat bessere und einfachere Lösungen?

Hinweis: Ich brauche das Ganze, um Annahmen über den Inhalt der Datei zu treffen:
(Klartext, Markup, komprimiert oder eine Binärdatei, ...)

ivan_ivanovich_ivanoff
quelle
1
Du meinst eine metrische Entropie? Entropie geteilt durch die Länge der Nachricht
user2622016
Autsch, diese Notiz, die Sie hinzugefügt haben: Note: I need the whole thing to make assumptions on the file's contents: (plaintext, markup, compressed or some binary, ...)... Sie haben gerade nach gottähnlicher Magie gefragt, viel Glück bei der Entwicklung einer nachweislich optimalen Datenkomprimierung.
MickLH
Können Sie bitte einen Pseudocode Ihres Endergebnisses veröffentlichen?
Guy Kahlon

Antworten:

51
  • Am Ende: Berechnen Sie den "Durchschnittswert" für das Array.
  • Initialisieren Sie einen Zähler mit Null und addieren Sie für jeden Eintrag des Arrays die Differenz des Eintrags zu "Durchschnitt" zum Zähler.

Mit einigen Modifikationen können Sie Shannons Entropie erhalten:

Benennen Sie "Durchschnitt" in "Entropie" um

(float) entropy = 0
for i in the array[256]:Counts do 
  (float)p = Counts[i] / filesize
  if (p > 0) entropy = entropy - p*lg(p) // lgN is the logarithm with base 2

Bearbeiten: Wie Wesley erwähnt hat, müssen wir die Entropie durch 8 teilen, um sie im Bereich 0 einzustellen . . 1 (oder alternativ können wir die logarithmische Basis 256 verwenden).

Nick Dandoulakis
quelle
2
Eine Korrektur: Sie müssen die Elemente mit Counts [i] == 0 überspringen.
Igor Krivokon
Sie haben Recht, Krivokon, danke! Ich sehe, dass Wesley es richtig gemacht hat, außer dass er eine 'seltsame' Logarithmusbasis gewählt hat.
Nick Dandoulakis
3
Ja, es ist definitiv komisch. Da Sie jedoch die konventionellere Protokollbasis 2 verwenden, erhalten Sie einen Wert zwischen 0 und 8. Möglicherweise möchten Sie dies erwähnen, damit der Fragesteller daran denken kann, das Ergebnis durch 8 zu teilen, um einen Wert zwischen 0 und 1 zu erhalten. (Herzlichen Glückwunsch zu der schnellen Antwort - ich musste dieses Zeug auf Wikipedia nachschlagen, um mich daran zu erinnern .: P)
Wesley
Dies ist eine gute Methode. Ich habe sie verwendet, um die "Entropie" des Bildes durch Vergleichen der Pixeldaten zu analysieren, und sie ergab gute Ergebnisse.
Matt Warren
4
Diese Schätzung der Entropie setzt voraus, dass die Bytes unabhängig sind, was im Allgemeinen falsch ist. Nehmen Sie beispielsweise ein Graustufenbild mit einem gleichmäßigen horizontalen Farbverlauf von Weiß nach Schwarz auf.
Leonbloy
34

Eine einfachere Lösung: gzip die Datei. Verwenden Sie das Verhältnis der Dateigrößen: (Größe des gezippten) / (Größe des Originals) als Maß für die Zufälligkeit (dh Entropie).

Diese Methode gibt nicht den genauen absoluten Wert der Entropie an (da gzip kein "idealer" Kompressor ist), ist aber gut genug, wenn Sie die Entropie verschiedener Quellen vergleichen müssen.

Igor Krivokon
quelle
1
Ich hatte auch diese Idee (als letzte Option), aber ich muss viele Dateien analysieren, daher ist es keine effiziente Option, ALLE zu komprimieren.
ivan_ivanovich_ivanoff
3
Es hängt davon ab, wie groß dein ALL ist. Ich habe gerade versucht, alle Dateien in / usr / bin zu komprimieren, es sind ungefähr 1000 Dateien, 200 MB. Es dauerte ungefähr 7 Sekunden. Dies ist der Befehl, mit dem Sie einmal die Größe ermitteln können: cat * | gzip --fast | wc -c. Es ist langsamer als nur das byteweise Lesen der Dateien, aber nicht viel.
Igor Krivokon
gzip's hatte viele Mannjahre Programmieraufwand und so viel Optimierung. Könnte es auch ausnutzen.
Nosredna
3
Dies kann tatsächlich eine bessere Schätzung der Entropie sein als die der akzeptierten Antwort - insbesondere wenn die Datei groß ist.
Leonbloy
2
Ich bin damit einverstanden, dass dies eine bessere Schätzung ist als die akzeptierte Antwort. Tatsächlich gibt es mehrere wissenschaftliche Arbeiten, die diese Art der Annäherung verwenden.
Hugo Sereno Ferreira
33

Um die Informationsentropie einer Sammlung von Bytes zu berechnen, müssen Sie etwas Ähnliches wie die Antwort von tydok tun. (tydoks Antwort funktioniert mit einer Sammlung von Bits.)

Es wird angenommen, dass die folgenden Variablen bereits vorhanden sind:

  • byte_countsist eine Liste mit 256 Elementen der Anzahl der Bytes mit jedem Wert in Ihrer Datei. Zum Beispiel byte_counts[2]ist die Anzahl der Bytes, die den Wert haben 2.

  • total ist die Gesamtzahl der Bytes in Ihrer Datei.

Ich werde den folgenden Code in Python schreiben, aber es sollte offensichtlich sein, was los ist.

import math

entropy = 0

for count in byte_counts:
    # If no bytes of this value were seen in the value, it doesn't affect
    # the entropy of the file.
    if count == 0:
        continue
    # p is the probability of seeing this byte in the file, as a floating-
    # point number
    p = 1.0 * count / total
    entropy -= p * math.log(p, 256)

Es gibt mehrere Dinge, die wichtig sind.

  • Die Prüfung count == 0ist nicht nur eine Optimierung. Wenn count == 0, dann p == 0und log ( p ) undefiniert sind ("negative Unendlichkeit"), was einen Fehler verursacht.

  • Das 256im Aufruf von steht math.logfür die Anzahl der möglichen diskreten Werte. Ein aus acht Bits bestehendes Byte hat 256 mögliche Werte.

Der resultierende Wert liegt zwischen 0 (jedes einzelne Byte in der Datei ist das gleiche) und 1 (die Bytes werden gleichmäßig auf jeden möglichen Wert eines Bytes aufgeteilt).


Eine Erklärung für die Verwendung der Protokollbasis 256

Es ist wahr, dass dieser Algorithmus normalerweise unter Verwendung der Protokollbasis 2 angewendet wird. Dies ergibt die resultierende Antwort in Bits. In einem solchen Fall haben Sie maximal 8 Entropiebits für eine bestimmte Datei. Probieren Sie es selbst aus: Maximieren Sie die Entropie der Eingabe, indem Sie byte_countseine Liste aller 1oder 2oder erstellen 100. Wenn die Bytes einer Datei gleichmäßig verteilt sind, gibt es eine Entropie von 8 Bit.

Es ist möglich, andere Logarithmusbasen zu verwenden. Die Verwendung von b = 2 ermöglicht ein Ergebnis in Bits, da jedes Bit 2 Werte haben kann. Bei Verwendung von b = 10 wird das Ergebnis in Dits oder Dezimalbits angegeben, da für jeden Dit 10 mögliche Werte vorhanden sind. Die Verwendung von b = 256 ergibt das Ergebnis in Bytes, da jedes Byte einen von 256 diskreten Werten haben kann.

Interessanterweise können Sie mithilfe von Protokollidentitäten herausfinden, wie die resultierende Entropie zwischen Einheiten konvertiert wird. Jedes in Biteinheiten erhaltene Ergebnis kann durch Teilen durch 8 in Byteeinheiten umgewandelt werden. Als interessanter, absichtlicher Nebeneffekt ergibt dies die Entropie als Wert zwischen 0 und 1.

Zusammenfassend:

  • Sie können verschiedene Einheiten verwenden, um Entropie auszudrücken
  • Die meisten Menschen drücken Entropie in Bits aus ( b = 2)
    • Für eine Sammlung von Bytes ergibt dies eine maximale Entropie von 8 Bits
    • Da der Fragesteller ein Ergebnis zwischen 0 und 1 wünscht, teilen Sie dieses Ergebnis durch 8, um einen aussagekräftigen Wert zu erhalten
  • Der obige Algorithmus berechnet die Entropie in Bytes ( b = 256)
    • Dies entspricht (Entropie in Bits) / 8
    • Dies ergibt bereits einen Wert zwischen 0 und 1
Wesley
quelle
Danke für den Kommentar ... oh, wohin ist es gegangen? Wie auch immer, ich stimme zu, dass die Verwendung der "Byte-Frequenz" etwas verwirrend ist. Dieser Begriff wurde entfernt.
Wesley
+1 jetzt. Ich stimme Ihren Kommentaren und Änderungen zu, insbesondere der wichtigen Klarstellung, dass dieser Ansatz die Entropie in Bytes angibt, während der übliche Wert in Bits angegeben wird, obwohl Bytes eher den Anforderungen des OP entsprechen. (Entschuldigung für die Löschung vorhin. Ich entschied, dass ich mich nicht darauf
einlassen
Dies ist nicht die Entropie, dies setzt voraus, dass die Bytes unabhängig sind. Siehe meinen Kommentar zu Nicks Antwort
Leonbloy
20

Für das, was es wert ist, ist hier die traditionelle (Entropiebits) Berechnung, die in C # dargestellt wird:

/// <summary>
/// returns bits of entropy represented in a given string, per 
/// http://en.wikipedia.org/wiki/Entropy_(information_theory) 
/// </summary>
public static double ShannonEntropy(string s)
{
    var map = new Dictionary<char, int>();
    foreach (char c in s)
    {
        if (!map.ContainsKey(c))
            map.Add(c, 1);
        else
            map[c] += 1;
    }

    double result = 0.0;
    int len = s.Length;
    foreach (var item in map)
    {
        var frequency = (double)item.Value / len;
        result -= frequency * (Math.Log(frequency) / Math.Log(2));
    }

    return result;
}
Jeff Atwood
quelle
Dies ist eine fantastische Antwort. Wie würden Sie die ursprüngliche Frage berechnen, wenn die Antworten eher relativ als absolut wären? Angenommen, Sie suchen nach geografischer Entropie. Eine Werbekampagne wird national geschaltet und Sie erfassen die Geokoordinaten der Befragten. Es ist wahrscheinlich, dass keine zwei Einträge identische Koordinaten haben, aber eine Entropiefunktion sollte Ihnen dennoch sagen können, dass es wahrscheinlich einige lokalisierte Hotspots gibt oder dass eine umfassende nationale Verteilung effektiver sein wird.
Paul Smith
1
Sollte nicht nach Nullwerten gesucht werden map? Andernfalls Math.Log(frequency)kann zurückkehren -INF.
Executifs
(Math.Log (Häufigkeit) / Math.Log (2)) == Math.Log (Häufigkeit, 2)
Citykid
16

Ist das etwas, das entdamit umgehen könnte? (Oder vielleicht ist es auf Ihrer Plattform nicht verfügbar.)

$ dd if=/dev/urandom of=file bs=1024 count=10
$ ent file
Entropy = 7.983185 bits per byte.
...

Als Gegenbeispiel ist hier eine Datei ohne Entropie.

$ dd if=/dev/zero of=file bs=1024 count=10
$ ent file
Entropy = 0.000000 bits per byte.
...
Peter Kovacs
quelle
1
Vielen Dank! Gut, dieses Tool zu kennen. Aber ich muss dies programmatisch und plattformunabhängig lösen, daher meine Frage.
ivan_ivanovich_ivanoff
1
+1 Danke für den Zeiger. Dies existiert zumindest in Debian: packages.debian.org/wheezy/ent
Tripleee
14

Ich bin zwei Jahre zu spät in der Beantwortung. Bitte bedenken Sie dies trotz nur weniger Stimmen.

Kurze Antwort: Verwenden Sie meine ersten und dritten fettgedruckten Gleichungen unten, um herauszufinden, woran die meisten Leute denken, wenn sie "Entropie" einer Datei in Bits sagen. Verwenden Sie nur die 1. Gleichung, wenn Sie Shannons H-Entropie wollen, die tatsächlich Entropie / Symbol ist, wie er 13 Mal in seiner Arbeit angegeben hat, die den meisten Menschen nicht bekannt ist. Einige Online-Entropie-Rechner verwenden diesen, aber Shannons H ist "spezifische Entropie", nicht "totale Entropie", was so viel Verwirrung verursacht hat. Verwenden Sie die 1. und 2. Gleichung, wenn Sie eine Antwort zwischen 0 und 1 wünschen, bei der es sich um normalisierte Entropie / Symbol handelt (es handelt sich nicht um Bits / Symbol, sondern um ein echtes statistisches Maß für die "entropische Natur" der Daten, indem Sie die Daten ihre eigene Protokollbasis auswählen lassen anstatt willkürlich 2, e oder 10 zuzuweisen).

Es gibt 4 Arten der Entropie von Dateien (Daten) von N Symbolen mit n eindeutigen Arten von Symbolen. Beachten Sie jedoch, dass Sie durch Kenntnis des Inhalts einer Datei den Status kennen, in dem sie sich befindet, und daher S = 0. Um genau zu sein, wenn Sie eine Quelle haben, die viele Daten generiert, auf die Sie Zugriff haben, können Sie die erwartete zukünftige Entropie / den erwarteten zukünftigen Charakter dieser Quelle berechnen. Wenn Sie Folgendes für eine Datei verwenden, ist es genauer zu sagen, dass die erwartete Entropie anderer Dateien aus dieser Quelle geschätzt wird.

  • Shannon (spezifisch) Entropie H = -1 * Summe (count_i / N * log (count_i / N))
    wobei count_i die Häufigkeit ist, mit der das Symbol i in N aufgetreten ist.
    Einheiten sind Bits / Symbole, wenn log Basis 2 ist, nats / symbol wenn natürliches log.
  • Normalisierte spezifische Entropie: H / log (n)
    Einheiten sind Entropie / Symbol. Bereiche von 0 bis 1. 1 bedeutet, dass jedes Symbol gleich häufig vorkommt und in der Nähe von 0 alle Symbole außer 1 nur einmal vorkamen und der Rest einer sehr langen Datei das andere Symbol war. Das Protokoll befindet sich in derselben Basis wie das H.
  • Absolute Entropie S = N * H
    Einheiten sind Bits, wenn log Basis 2 ist, nats, wenn ln ()).
  • Normalisierte absolute Entropie S = N * H / log (n) Die
    Einheit ist "Entropie" und variiert von 0 bis N. Das log befindet sich auf derselben Basis wie das H.

Obwohl die letzte die wahrste "Entropie" ist, ist die erste (Shannon-Entropie H) das, was alle Bücher "Entropie" ohne (die erforderliche IMHO) Qualifikation nennen. Die meisten klären nicht (wie Shannon), dass es sich um Bits / Symbol oder Entropie pro Symbol handelt. H "Entropie" zu nennen, spricht zu locker.

Für Dateien mit gleicher Häufigkeit jedes Symbols: S = N * H = N. Dies ist bei den meisten großen Bitdateien der Fall. Entropy führt keine Komprimierung der Daten durch und kennt daher keine Muster. Daher hat 000000111111 das gleiche H und S wie 010111101000 (6 1 und 6 0 in beiden Fällen).

Wie andere bereits gesagt haben, liefert die Verwendung einer Standardkomprimierungsroutine wie gzip und das Teilen vor und nach ein besseres Maß für die Menge der bereits vorhandenen "Reihenfolge" in der Datei. Dies ist jedoch voreingenommen gegenüber Daten, die besser zum Komprimierungsschema passen. Es gibt keinen perfekt optimierten Allzweckkompressor, mit dem wir eine absolute "Reihenfolge" definieren können.

Eine andere zu berücksichtigende Sache: H ändert sich, wenn Sie ändern, wie Sie die Daten ausdrücken. H ist unterschiedlich, wenn Sie verschiedene Gruppierungen von Bits auswählen (Bits, Halbbytes, Bytes oder Hex). Sie dividieren also durch log (n), wobei n die Anzahl der eindeutigen Symbole in den Daten ist (2 für binär, 256 für Bytes) und H im Bereich von 0 bis 1 liegt (dies ist eine normalisierte intensive Shannon-Entropie in Entropieeinheiten pro Symbol). . Aber technisch gesehen ist n = 100, nicht 256, wenn nur 100 der 256 Bytetypen auftreten.

H ist eine "intensive" Entropie, dh es ist pro Symbol analog zur spezifischen Entropie in der Physik, die Entropie pro kg oder pro Mol ist. Regelmäßige "umfangreiche" Entropie einer Datei analog zu Physik ist S = N * H, wobei N.ist die Anzahl der Symbole in der Datei. H wäre genau analog zu einem Teil eines idealen Gasvolumens. Informationsentropie kann nicht einfach in einem tieferen Sinne exakt gleich physikalischer Entropie gemacht werden, da physikalische Entropie "geordnete" sowie ungeordnete Anordnungen zulässt: Physikalische Entropie ist mehr als eine vollständig zufällige Entropie (wie eine komprimierte Datei). Ein Aspekt des Unterschiedlichen Für ein ideales Gas gibt es einen zusätzlichen 5/2-Faktor, der dies berücksichtigt: S = k * N * (H + 5/2) wobei H = mögliche Quantenzustände pro Molekül = (xp) ^ 3 / hbar * 2 * sigma ^ 2 wobei x = Breite der Box, p = gesamter ungerichteter Impuls im System (berechnet aus kinetischer Energie und Masse pro Molekül) und Sigma = 0,341 gemäß dem Unsicherheitsprinzip, das nur die Anzahl von angibt mögliche Zustände innerhalb 1 std dev.

Ein wenig Mathematik ergibt eine kürzere Form der normalisierten umfangreichen Entropie für eine Datei:

S = N * H / log (n) = Summe (count_i * log (N / count_i)) / log (n)

Einheiten davon sind "Entropie" (was nicht wirklich eine Einheit ist). Es wird normalisiert, um ein besseres universelles Maß als die "Entropie" -Einheiten von N * H zu sein. Es sollte aber auch nicht ohne Klärung als "Entropie" bezeichnet werden, da die normale historische Konvention darin besteht, H fälschlicherweise "Entropie" zu nennen (was im Gegensatz dazu steht die in Shannons Text gemachten Klarstellungen).

zawy
quelle
Ich möchte Ihre Antwort positiv bewerten, aber es gibt einige Unklarheiten, die Sie zuerst klären sollten: In Gleichung 2 und 4 und wo Sie sagen "Teilen Sie also durch log (n), wobei n die Anzahl der eindeutigen Symbole in den Daten ist", log was von n? Log natürlich, log2 (n)? Im Allgemeinen bedeutet log (n) in der Mathematik ohne Angabe einer Basis log10 (n). Bitte klären Sie.
Adam White
Ich habe in den Gleichungen 1 und 3 erwähnt, dass der Benutzer die Basis auswählt. Für die Gleichungen 2 und 4 sollte es dieselbe Basis sein (in der H war). Ich werde die Klarstellung hinzufügen.
zawy
10

Es gibt keine Entropie einer Datei. In der Informationstheorie ist die Entropie eine Funktion einer Zufallsvariablen , nicht eines festen Datensatzes (technisch gesehen hat ein fester Datensatz eine Entropie, aber diese Entropie wäre 0 - wir können die Daten als zufällige Verteilung betrachten, die hat nur ein mögliches Ergebnis mit Wahrscheinlichkeit 1).

Um die Entropie zu berechnen, benötigen Sie eine Zufallsvariable, mit der Sie Ihre Datei modellieren können. Die Entropie ist dann die Entropie der Verteilung dieser Zufallsvariablen. Diese Entropie entspricht der Anzahl der in dieser Zufallsvariablen enthaltenen Informationsbits.

Adam Rosenfield
quelle
4
Die theoretische Definition von Entropie ist mir nicht bekannt. Es gibt jedoch immer zwei Semantiken für jedes Semester: die theoretische und die populäre. Nun, scheint, dass der populäre Teil von allen hier verstanden wurde;)
ivan_ivanovich_ivanoff
1
Es gibt mindestens zwei offensichtliche Interpretationen in den Antworten, wie jemand "die Entropie einer Datei" in eine strenge mathematische Definition übersetzen könnte. Wenn Sie wirklich verstehen möchten, was Sie tun, sollten Sie die statistische Art und Weise verstehen, in der die Entropie in diesen Antworten modelliert wird.
James Thompson
1
Oder Sie könnten in die Kolmogorov-Komplexität geraten, die eine bessere mathematische Definition darstellt, aber nicht berechenbar ist.
Jeffrey Hantin
@JamesThompson interessant, gibt es Hinweise darauf, wie Sie diese Zufallsvariable aus einer Reihe von Dateien ableiten würden, deren Entropie Sie messen möchten?
Vladtn
4
Ich glaube, dass bei diesem Problem die Zufallsvariable die Bytes sind, die in der Datei gefunden werden, wenn sie durchlaufen werden. Es handelt sich also um eine diskrete Zufallsvariable mit 256 möglichen Werten und einer eigenen Verteilung, die von der Datei abhängt. (Ich weiß, dass dieser Beitrag alt ist, aber dies könnte jeden klarstellen, der hierher kommt)
Anoyz
5

Wenn Sie die Entropie der Informationstheorie verwenden, denken Sie daran, dass es möglicherweise sinnvoll ist, sie nicht für Bytes zu verwenden. Wenn Ihre Daten aus Floats bestehen, sollten Sie stattdessen eine Wahrscheinlichkeitsverteilung an diese Floats anpassen und die Entropie dieser Verteilung berechnen.

Wenn der Inhalt der Datei aus Unicode-Zeichen besteht, sollten Sie diese usw. verwenden.

Bayer
quelle
Wenn ich Datenanalysen für Dateien aller Art durchführen möchte, ist Byte meiner Meinung nach die beste Wahl (als Kompromiss).
ivan_ivanovich_ivanoff
1
Natürlich können Sie das tun. Sie sollten jedoch alle zusätzlichen Informationen verwenden, die Sie erhalten können. Andernfalls können Ihre Ergebnisse extrem schlecht sein.
Bayer
Normalerweise ist nutzlos absolut richtig. Die Shannon-Entropie gibt Ihnen nicht genügend Informationen über den Dateiinhalt. Jeder Kompressor hat zwei Stufen: Modellierung und Entropiecodierung. Die Entropiecodierung ist erforderlich, aber der größte Teil der Redundanz wird in der Modellierungsphase erkannt (es sei denn, Sie arbeiten mit quasi zufälligen Daten).
Igor Krivokon
Normalerweise ist nutzlos genau hier. Eine Möglichkeit, dies herauszufinden, besteht darin, in Worten das Ganze zu sagen, das Sie berechnen: "Was ist die Entropie der ASCII-Symbole, mit denen ich meine Gleitkommazahlen darstelle", können Sie jedoch berechnen ist möglicherweise nicht das, was Sie anstreben.
Tom10
1
Dies ist ein Kommentar und keine Antwort.
JasonMArcher
2

Berechnet die Entropie einer beliebigen Zeichenfolge von Zeichen ohne Vorzeichen der Größe "Länge". Dies ist im Grunde ein Refactoring des Codes unter http://rosettacode.org/wiki/Entropy . Ich verwende dies für einen 64-Bit-IV-Generator, der einen Container mit 100000000 IVs ohne Dupes und einer durchschnittlichen Entropie von 3,9 erstellt. http://www.quantifiedtechnologies.com/Programming.html

#include <string>
#include <map>
#include <algorithm>
#include <cmath>
typedef unsigned char uint8;

double Calculate(uint8 * input, int  length)
  {
  std::map<char, int> frequencies;
  for (int i = 0; i < length; ++i)
    frequencies[input[i]] ++;

  double infocontent = 0;
  for (std::pair<char, int> p : frequencies)
  {
    double freq = static_cast<double>(p.second) / length;
    infocontent += freq * log2(freq);
  }
  infocontent *= -1;
  return infocontent;
 }
iggy_pop
quelle
2

Betreff: Ich brauche das Ganze, um Annahmen über den Inhalt der Datei zu treffen: (Klartext, Markup, komprimiert oder eine Binärdatei, ...)

Wie andere darauf hingewiesen haben (oder verwirrt / abgelenkt wurden), sprechen Sie tatsächlich von metrischer Entropie (Entropie geteilt durch die Länge der Nachricht). Weitere Informationen finden Sie unter Entropie (Informationstheorie) - Wikipedia .

Der Kommentar von Jitter, der auf das Scannen von Daten auf Entropieanomalien verweist, ist für Ihr zugrunde liegendes Ziel sehr relevant. Das verbindet sich schließlich mit libdisorder (C-Bibliothek zum Messen der Byte-Entropie) . Dieser Ansatz scheint Ihnen viel mehr Informationen zu geben, mit denen Sie arbeiten können, da er zeigt, wie sich die metrische Entropie in verschiedenen Teilen der Datei ändert. Sehen Sie sich beispielsweise dieses Diagramm an, wie sich die Entropie eines Blocks mit 256 aufeinanderfolgenden Bytes aus einem 4-MB-JPG-Bild (y-Achse) für verschiedene Offsets (x-Achse) ändert. Am Anfang und am Ende ist die Entropie auf halbem Weg geringer, beträgt jedoch für den größten Teil der Datei etwa 7 Bit pro Byte.

Geben Sie hier die Bildbeschreibung ein Quelle: https://github.com/cyphunk/entropy_examples . [ Beachten Sie, dass diese und andere Grafiken über die neuartige Lizenz http://nonwhiteheterosexualmalelicense.org verfügbar sind .... ]

Interessanter ist die Analyse und ähnliche Grafiken unter Analysieren der Byte-Entropie einer FAT-formatierten Platte | GL.IB.LY.

Statistiken wie max, min, mode und Standardabweichung der metrischen Entropie für die gesamte Datei und / oder den ersten und letzten Block davon können als Signatur sehr hilfreich sein.

Dieses Buch scheint auch relevant zu sein: Erkennung und Erkennung von File Masquerading für E-Mail- und Datensicherheit - Springer

nealmcb
quelle
-2

Ohne zusätzliche Informationen entspricht die Entropie einer Datei (per Definition) ihrer Größe * 8 Bit. Die Entropie der Textdatei hat ungefähr die Größe * 6,6 Bit, vorausgesetzt:

  • Jedes Zeichen ist gleich wahrscheinlich
  • Das Byte enthält 95 druckbare Zeichen
  • log (95) / log (2) = 6,6

Die Entropie der Textdatei in Englisch wird auf etwa 0,6 bis 1,3 Bit pro Zeichen geschätzt (wie hier erläutert ).

Im Allgemeinen können Sie nicht über die Entropie einer bestimmten Datei sprechen. Entropie ist eine Eigenschaft einer Reihe von Dateien .

Wenn Sie eine Entropie (oder Entropie pro Byte, um genau zu sein) benötigen, ist es am besten, sie mit gzip, bz2, rar oder einer anderen starken Komprimierung zu komprimieren und dann die komprimierte Größe durch die nicht komprimierte Größe zu teilen. Es wäre eine großartige Schätzung der Entropie.

Die Berechnung von Entropiebyte für Byte, wie von Nick Dandoulakis vorgeschlagen, ergibt eine sehr schlechte Schätzung, da davon ausgegangen wird, dass jedes Byte unabhängig ist. In Textdateien ist es beispielsweise viel wahrscheinlicher, einen kleinen Buchstaben nach einem Buchstaben zu haben als ein Leerzeichen oder eine Interpunktion nach einem Buchstaben, da Wörter normalerweise länger als 2 Zeichen sind. Die Wahrscheinlichkeit, dass sich das nächste Zeichen im Az-Bereich befindet, korreliert also mit dem Wert des vorherigen Zeichens. Verwenden Sie Nicks grobe Schätzung nicht für echte Daten, sondern verwenden Sie stattdessen das gzip-Komprimierungsverhältnis.

user2622016
quelle