Datei-Entropie in C bestimmen

Peter z80.eu · 15. Juni 2021

Da ich selbst kurzzeitig mit dem Problem gekämpft habe, die Entropie (bezogen auf 256 mögliche Byte-Werte) einer Datei (nach Shannon) zu bestimmen, anbei der Quellcode und die ausführbare Datei für DOS (kompiliert mit Turbo-C), sowie einer Beispieldatei mit geringerer Entropie.

Das Ganze sieht dann in der Programmausführung so aus:

Wenn jemand eine bessere Idee zum Logarithmus zu Basis 2 hat (ohne allzusehr Genauigkeit einzubüßen), einfach als Antwort hier als C-Code posten

P.S.: Falls jemand fragt für was das gut ist - damit kann man nicht nur bestimmen, wie gut etwas komprimierbar ist, sondern auch Rückschlüsse zur möglichen Verschlüsselung einer Datei ziehen (je höher die Entropie, desto wahrscheinlicher dass eine Datei verschlüsselt (oder bereits komprimiert) ist).

mdx · 15. Juni 2021

Warum dividierst du nicht einfach am Ende einmal durch log(2.0) statt in jedem Schleifendurchlauf?

edit: ebenso für die Division durch length.

Peter z80.eu · 15. Juni 2021

Weil das so nicht geht. Die Berechnung wird ja in der Schleife nicht immer durchgeführt, sondern nur, wenn bytecount[i]!=0 ist.

Wie willst Du das "am Ende" einmal machen ?

mdx · 16. Juni 2021

Ok, also für den log stimmt das schon was ich geschrieben habe. So brauchst du nur 1 mal den log(2) berechnen:

Code

      /* entropy calculation */
      for (i = 0; i < POSSIZE; i++)
        {
          if (byte_count[i] != 0)
            {
              count = (float) byte_count[i] / (float) length;
              entropy -= count * (float)log(count);
            }
        }

      return entropy / log_of_2;

Alles anzeigen

Was length angeht hast du wohl recht, da das ja auch im logarithmus nochmal auftaucht.

Peter z80.eu · 16. Juni 2021

mdx - Eigentlich kann man es ja nie einem Recht machen, egal was man postet. Dachte erst, es würde einigen gefallen, das hier ab und an auch Quellcode gepostet wird. Aber ich glaube, ich lasse es ganz, nochmal was zu posten - auch wenn Du natürlich mit dem Optimierungsschritt Recht hast. Mir ging's halt vordergründig um den (Shannon) Algorithmus und um die Idee, so was programmatisch zu machen.

mdx · 16. Juni 2021

Das verstehe ich jetzt nicht. Du hast doch selbst explizit geschrieben dass du gerne bessere Ideen sehen würdest?

Zitat von Peter z80.eu

Wenn jemand eine bessere Idee zum Logarithmus zu Basis 2 hat (ohne allzusehr Genauigkeit einzubüßen), einfach als Antwort hier als C-Code posten

Ich hatte keinesfalls die Absicht deinen Code schlecht zu reden oder dir sonstwie auf die Nerven zu gehen. Ich fand das Thema interessant, nur deshalb habe ich mir auch den Code angesehen.

Übrigens freue ich mich immer wenn hier Code gepostet wird und mache das auch gelegentlich selber.

Peter z80.eu · 16. Juni 2021

Ich war etwas unglücklich über die Logarithmus Funktion, es gibt in Turbo C leider auch kein Log2(). Ich hatte gesehen, dass es auch "Ersatzformeln" gibt, wo man den Log2 (statt des natürlichen Log oder den Log10 zu nehmen) auch ohne Library-Funktion ausrechnen kann. Das was ich (bisher) gefunden hatte, war aber deutlich ungenauer bei entsprechend häufiger Iteration...

ThoralfAsmussen · 16. Juni 2021

Vielleicht wäre ja eine Tabelle eine schöne Lösung ?

Tags