# Entropie Berechnung



## Plackan (15. Nov 2006)

Hallo Leute, 

ich habe da eine Aufgabe, die die Entropie von Dateien berechnen soll. Hier mal die genaue Formulierung dessen was gemacht werden soll:



> Schreiben Sie eine Anwendung, um den Informationsgehalt von Dateien zu messen.
> Die Anwendung soll als Argument einen Namen für entweder eine Datei oder
> ein Verzeichnis übernehmen. Handelt es sich um ein Verzeichnis, so werden im
> weiteren alle Dateien in diesem Verzeichnis betrachtet. Berechnen Sie für jede
> ...




Ich komme da irgendwie nicht mehr Weiter. Ich weiß nicht, wie ich die Formel zur Berechnung der Entropie in Java umsetzen kann: 




> He = log 1=p(X) = ¡log p(X)



Mein Code sieht bisher wie folgt aus: 








```
mport java.io.*;
/**
 * Beschreiben Sie hier die Klasse Entropie.
 * 
 * @author (Ihr Name) 
 * @version (eine Versionsnummer oder ein Datum)
 */
public class Entropie
{
    // Definieren Sie ab hier die Klassenvariablen für Entropie
    
    long[] zaehler;
    
    // Definieren Sie ab hier die Objektvariablen für Entropie

    // Definieren Sie ab hier die KOnstruktoren für Entropie
    /**
     * Konstruktor für Objekte der Klasse Entropie
     */
    public Entropie()
    {
        // Objektvariable initialisieren
    }

    // Definieren Sie ab hier die Methoden für Entropie
    
    void entropie()
    { 
        int i;
        try {
        DataInputStream quelle = new DataInputStream( new FileInputStream( "test.dat" ) );
        
       
        
        for (i=0;i<=256;i++);
        zaehler = new long[256];
        
        quelle.readUnsignedByte();
}
        catch (EOFException e) 
        {
        // Dateiende
        System.exit(0);
}
        catch (IOException e) {
                // Fehler beim Lesen
                    System.out.println(e.getMessage());
}
   

    /**
     * Diese Methode leistet....
     * 
     * @param   Parameter...
     * @return  Rückgabewert...
     */
}
    void readUnsignedByte()
    {
        double entropie;
  
      
     
    }
}
```


----------



## SlaterB (15. Nov 2006)

zunächst mal vergiss alles was mit Dateien zu tun hat und berechne einfach die Entropie des Teststrings 'test'

dafür musst du natürlich erstmal wissen, was Entropie heißt,

deine Formel ist ohne genaure Erklärung aller benutzen Zeichen nutzlos, was ist p, was ist x,

vielleicht versuchst du es überhaupt lieber umgangssprachlich, was soll eigentlich erreicht werden,
z.B. alle Zeichen als Bytes betrachen, den Mittelwert ausrechnen und dann die durchschnittliche Abweichung?


----------



## Plackan (15. Nov 2006)

Zu der Formel:

He = log 1=p(X) = -log p(X)

P ist die Wahrscheinlichkeit mit der ein Zeichen x vorkommt.

Die Entropie ist ein Maß für den mittleren Informationsgehalt pro Zeichen einer Nachricht. Also wohl so wie du das auch geschrieben hast, zuerst die Bytes betrachten und dann den Mittelwert berechnen.


----------



## Leroy42 (15. Nov 2006)

Was soll das für eine Formel sein?  :shock: 



> log 1=p(X) = -log p(X)



Also log 1 = p(X) <==> 0 = p(X)  :autsch: 

oder p(X) = -log p(X)  :autsch:  :autsch:


----------



## dsv fritz (15. Nov 2006)

Also die Formel lautet richtig: He = 1/log(p(x)) = -log(p(x))


----------



## SlaterB (15. Nov 2006)

-> 1/y = -y 
-> -1 = y^2 
-> y = Wurzel aus -1?


----------



## Plackan (15. Nov 2006)

dsv fritz hat gesagt.:
			
		

> Also die Formel lautet richtig: He = 1/log(p(x)) = -log(p(x))



Danke, aber wie setze ich das jetzt in Java um?


----------



## dsv fritz (15. Nov 2006)

10er-Logrithmus: Math.log10()

oder ist deine Frage etwas genereller? Also wie berechne ich die Wahrscheinlichkeit für die Byte-Einheit etc?


----------



## Plackan (15. Nov 2006)

dsv fritz hat gesagt.:
			
		

> 10er-Logrithmus: Math.log10()
> 
> oder ist deine Frage etwas genereller? Also wie berechne ich die Wahrscheinlichkeit für die Byte-Einheit etc?



Genau allgemein wie man die Wahrscheinlichkeit also die Formel jetzt umsetzt, damit auch die Entropie von verschiedenen Dateien berechnet werden kann. Als basis des Logarithmus sollten wir die 2 nehmen. 

Hatte es schon mit Math.log2() versucht, hat aber nicht so ganz funktioniert.


----------



## Plackan (15. Nov 2006)

Die Methode void readUnsignedByte() soll die Bytes die zuvor ausgelesen wurden und im Array gespeichert wurden nehmen und mit diesen dann rechnen. 

Nur wie mache ich das?


----------



## Murray (15. Nov 2006)

Für den Zweierlogarithmus gibt es int java.lang.Math keine direkte Funktion. Da man Logarithmen verschiedener Basen aber nach folgender Formel

logb(x) = loga(x) / loga(b)

ineinander umrechnen kann, ist das nicht weiter schlimm:


```
public static double log2( double wert) {
  return Math.log( wert) / Math.log( 2.0);
}
```


----------



## SlaterB (15. Nov 2006)

wenn schon dann

```
private static double log2 = Math.log( 2.0)

public static double log2( double wert) {
  return Math.log( wert) / log2;
}
```


----------



## dsv fritz (15. Nov 2006)

Ich habe mein altes Kommunikationstechnik-Skript hervor gegraben und hab nun folgenden Vorschlag:
Die Entropie lässt sich wie folgt berechnen:
H = p1 * log2(1/p1) + p2*log2(1/p2)+...+pn*log2(1/pn)

Was du nun machen musst, ist eigentlich die p's der einzelnen Zeichen berechnen. Das kannst du machen, indem du einfach die Anzahl jedes einzelnen Zeichens durch die Gesamte Anzahl an Zeichen dividierst.
Zum Schluss kannst du dann die Formel bequem anwenden.

Z.B.: Eine Datei beinhaltet folgenden Text:
"AAAAABBBCDD"

Somit ergibt sich für 
p(A) = 5 / 11
p(B) = 3 / 11
p(C) = 1 / 11
p(D) = 2 / 11

=> H = 1.78993 bit


----------



## Plackan (15. Nov 2006)

Danke das bringt mich schon etwas weiter. Da ich 256 bit insgesamt erlaube, müsste ich dann durch 256 teilen. Nur wie bekomme ich die p's aus einer Datei?


----------



## SlaterB (15. Nov 2006)

Datei als String einlesen (besser erstmal mit Teststring probieren), z.B. mit BufferedReader.readLine(),
Zeilenumbrüche nicht vergessen, sind ja auch irgendwie ein Zeichen,
dann String.charAt,

oder Datei gleich als byte[] einlesen, das ist wohl schlauer 
sowas liest man allgemein in einem Lehrbuch nach, z.B.

http://www.galileocomputing.de/openbook/javainsel5/


----------



## marble (15. Nov 2006)

Hier was allgemeines zur Entropie:

http://de.wikipedia.org/wiki/Entropie

Dann etwas zum Dateien einlesen:

http://java.sun.com/docs/books/tutorial/essential/io/


da du das ganze rekursiv machen sollst - also ein ordner hat dateien und unterordner - diese unterordner wieder unterordner.... solltest du dir auch mal zu gemüte führen wie man durch so ne baumartige dateistruktur rekursiv läuft:

brauchst also ne funktion die sich selbst aufruft wenn sie nen ordner hat, jedoch falls sie ne file hat nur dessen dieses zurückgibt (oder an ne liste anhängt). am ende hast du dann alle dateien in ner liste. die wird dann abgearbeitet.

öffne die datei lies daraus - zeichenweise - dann nimmst einfach nen array [256] der dann zu jedem buchstaben (der ja nichts anderes ist, als ein zahlenwert) eins dazuzählt. sozusagen 

array[buchstabe]++

so geht das wohl am schnellsten. am ende nimmst ein floatArray[256] und sagst in ner schleife einfach floatArray[x] = array[x]/256f . von mir aus kannst auch gerne doubles nehmen 

dann haste von jedem buchstaben die wahrscheinlichkeit. wie man die entropie dann ausrechnet haben ja hier schon einige erwähnt. es geht denke ich in der übung hauptsächlich um das file handling... dann handle mal schön... ;-)


----------



## dsv fritz (16. Nov 2006)

marble hat gesagt.:
			
		

> Hier was allgemeines zur Entropie:
> 
> http://de.wikipedia.org/wiki/Entropie



Dieser Artikel behandelt nicht direkt die Entropie, die in der Informationstechnik beschrieben wird (die Ansätze sind natürlich gleich). 
Die Entropie kann nämlich auch als Ungewissheit bezeichnet werden und somit kann der Informationsgehalt einer Nachricht bestimmt werden.


----------



## SnooP (16. Nov 2006)

jo - der link hier ist besser:
http://de.wikipedia.org/wiki/Entropie_(Informationstheorie)#Datenkompression_und_Entropie

guck dir mal den ByteArrayInputStream an


----------



## Plackan (16. Nov 2006)

Vielen vielen Dank das bringt mich alles echt weiter !


----------

