Entropie berechnen



  • Hallo,

    ich befasse mich gerade etwas mit komprimieren. Ich habe den ISO Latin 1 Zeichensatz mit 191 Zeichen, die Information pro Zeichen in Bit ist Logarithmus zu Basis 2 von 191. Jetzt habe ich ein Dokument in dem die 26 Buchstaben des lateinischen Alphabetes jeweils in der relativen häufigkeit 1/26 vorkommen. Wie kann man jetzt die Entropie pro Zeichen in dieser Datei berechnen? Ich weiß nicht wieviele Zeichen das Dokument hat nur das die lateinischen Buchstaben mit der Häufigkeit 1/26 vorkommen. Da stehe ich im Moment auf dem Schlauch 😕 😕



  • Das Problem ist völlig unabhängig vom Zeichensatz. Du hast eine Quelle (Dein Dokument) und nimmst an, dass die Zeichen da zufällig und unabhängig voneinander mit immer derselben Verteilung rauskommen. Nämlich zeichen x mit Wahrscheinlichkeit p(x).

    Um die Entropie Deiner Quelle zu berechnen mußt Du nun einfach über alle Zeichen x den Wert p(x)*log(p(x)) aufsummieren und das Ergebnis noch mit einem Minuszeichen versehen.

    Bei Dir gibt es 26 Zeichen, jedes davon hat Wahrscheinlichkeit 1/26.
    Also kommt dan raus -26*1/26*log(1/26) = -log(1/26) = log(26)-log(1) = log(26). Was bei lauter gleich auftretenden Zeichen ja auch gerade zu erwarten war...

    Achtung: log bezeichnet in diesem Beitrag den Logarithmus zur Basis 2!



  • Mhhh ja das klingt irgendwie logisch 🙂 Aber kann man mit diesem Ergebnis nun eine Aussgae darüber treffen ob das Dokument (verlustfrei) zu komprimieren kann? Redundanz ist ja anscheind vorhanden oder ?



  • Offensichtlich trägt jedes der Zeichen, eine Information von log(26) bit. So viele Bits mußt Du also pro Zeichen speichern. Wenn Du die Zeichen einzeln abspeicherst brauchst Du also 5 Bit pro Zeichen.

    Allerdings ist das derzeitige Format anscheinend so, dass 8 Bit pro Zeichen veranschlagt werden. Da ist offensichtlich Redundanz drin, weil man ja auch mit 5 Bit auskommen kann.


  • Mod

    Die Annahme dass alle Zeichen gleich wahrscheinlich und unabhängig sind ist natürlich nicht richtig. Die Information pro Zeichen ist daher noch viel geringer, als meine Vorredner vorgerechnet haben. Daher kann man Text noch viel stärker komprimieren.



  • SeppJ schrieb:

    Die Annahme dass alle Zeichen gleich wahrscheinlich und unabhängig sind ist natürlich nicht richtig.

    Woran genau kannst Du das erkennen? Wenn jedes Zeichen gleichhäufig vorkommt (und das hat der OP gesagt), dann handelt es sich zumindest schonmal nicht um einen Text in einer mir bekannten Sprache. Warum sollten dann die Zeichen nicht unabhängig sein? Mir scheint, Du weißt da mehr über das Dokument als der OP und ich zusammen. 🙂



  • Wenn ich jetzt ein Dokument habe das aus 1900 Zeichen besteht es gibt 95 verschiedene Zeichen und alle kommen mit der Wahrscheinlichkeit 1/95 vor.
    Die Entropie der Nachricht ist dann -95*1/95*log(1/95) = -log(1/95) = log(95)-log(1) = log(95) ?


Anmelden zum Antworten