Weicht die stochastische Verteilung von Symbolen sehr stark von der Gleichverteilung ab, so ist die Abbildung dieser Symbole auf gleich lange Codewörter offenbar ineffizient, da dann die Entropie - also die im Mittel pro Codewort übertragene Information - viel kleiner als die Zahl der zu übertragenden Binärstellen ist.
Beispiel
Eine Strichzeichnung in den Farben "schwarz", "blau", "grün", "rot" und "gelb" auf
weißem Grund soll in 100 Zeilen zu je 100 Pixeln gespeichert werden. Ein Beispiel
ist das "Haus vom Nikolaus" im folgenden Bild:
A = ones(100,100); % weißer Untergrund
A(90,25:75) = 2; % Fundamentplatte
A(40:90,[25,75]) = 3; % Wände
A(40,25:75) = 4; % Decke
for k=0:50 A(90-k,25+k) = 6; end % Verstrebung
for k=0:50 A(90-k,75-k) = 6; end % Verstrebung
for k=0:25 A(40-k,25+k) = 5; end % Dach
for k=0:25 A(40-k,75-k) = 5; end % Dach
pixelgraphik(A, {'w'; 'k'; 'b'; 'g'; 'r'; 'y'})
Dieser Matlabcode ist Kern der Funktion nikohaus :
nikohaus
Zur Kodierung der 6 verschiedenen Pixel sind wenigstens 3 Bit nötig. Die Entropie ist allerdings wesentlich kleiner, nämlich 0.2944 :
for k=1:6 pixelanzahl(k) = sum(sum((A==k))); end p = pixelanzahl/10000 % Wahrscheinlichkeiten der Pixelfarben I = log2(1./p) % Informationsgehalte der Farben H = sum(p.*log2(1./p)); result2fig(H) % Entropie
Mit 3 Binärstellen würden also weniger als 0.3 Bit an Information übertragen. In einem solchen Fall ist eine Kodierung mit Kodewörtern verschiedener Länge günstiger.
Shannon-Fano-Codes sind solche Codes, bei denen man die Länge ni der einzelnen Codewörter direkt aus der Wahrscheinlichkeit der Symbole Ai bestimmt:
ni = log2(1/pi)
So gut wie immer werden die Logarithmen nicht ganze Zahlen sein. Dann muss man auf- und abrunden, um einen optimalen Code zu finden. Bei der Zuordnung beginnt man zweckmäßigerweise mit den Symbolen größter Wahrscheinlichkeit.
Beispiel
Angenommen, 7 Farben in Pixelgraphiken haben die Wahrscheinlichkeiten
p = [ 0.30 0.20 0.15 0.10 0.10 0.09 0.06 ] n = round(log2(1./p)); result2fig(n)
Eine Codierungmöglichkeit ist z.B. durch folgende Codewörter:
w = {[0 0]; [0 1]; [1 0 0]; [1 0 1]; [1 1 0]; [1 1 1 0]; [1 1 1 1]};
Man beachte, dass das sechste Codewort um ein Bit länger ist als bei der Rundung vorhergesagt. Mit den angenommenen Wahrscheinlichkeiten pi kann man nun einerseits den mittleren Informationsgehalt H und andererseits die mittlere Codewortlänge berechnen:
for k=1:length(w) n(k) = length(w{k}); end % Längen aller Codewörter
mn = sum(p.*n) % gewichtetes Mittel der Codewortlängen
H = sum(p.*log2(1./p)); result2fig({mn;H}) % Entropie = gew. Mittel des Informationsgehaltes
Damit dies berechnet werden kann müssen vorher p und w durch Klicken der vorangegangenen zwei MATLAB-Skripte schon vorliegen.
Mittlere Codewortlänge und mittlerer Entscheidungsgehalt liegen hier sehr nahe beieinander.
Wenn die Wahrscheinlichkeit eines der Symbole über 0.5 liegt, so müsste dieses Symbol mit weniger als einem Bit codiert werden. Da das nicht möglich ist, wird auch diese Shannon-Fano-Codierung ineffizient. Ein Beispiel gibt die oben schon benutzte Codierung für farbige Strichzeichnungen.
Zwei mögliche Codes für diesen Fall sind:
p = [0.9654 0.0049 0.0098 0.0049 0.0051 0.0099];
w1 = {[0]; [1 0]; [1 1 0];[1 1 1 0];[1 1 1 1 0];[1 1 1 1 1]};
for k=1:length(w1) n1(k) = length(w1{k}); end % Längen aller Codewörter
m1 = sum(p.*n1) % gewichtetes Mittel der Codewortlängen
w2 = {[0]; [1 0 0];[1 0 1];[1 1 0]; [1 1 1 0]; [1 1 1 1]};
for k=1:length(w2) n2(k) = length(w2{k}); end % Längen aller Codewörter
m2 = sum(p.*n2) % gewichtetes Mittel der Codewortlängen
H = sum(p.*log2(1./p)) % Entropie = gew. Mittel des Informationsgehaltes
Der zweite Code ist offenbar geringfügig besser als der erste, aber sehr schlecht im Vergleich mit der Entropie. In solch einem Fall muss man andere Wege der Codierung gehen. Z.B. ist es möglich die Koordinaten von der Grundfarbe abweichender Pixel zu übertragen.
Für englischen Text hat Huffman einen Code angegeben, dessen Codewortlänge entsprechend der Wahrscheinlichkeit des Auftretens gewählt wurde. Der Code ist gegeben durch folgende Tabelle der Codewörter für alle ASCII-Zeichen geordnet nach Häufigkeit, LSB (zuerst gesendet) links (entnommen aus der Beschreibung des Pactor-Protokolls, SCS):
openbyextension('pt-huffman-tabelle.txt')
Der Huffman-Code ist relativ unempfindlich gegenüber Abweichungen der realen von der theoretischen Buchstabenhäufigkeit, so dass fast gleich gute Ergebnisse bei deutschem und englischem Klartext erreicht werden. Der erreichbare Kompressionsfaktor gegenueber ASCII beträgt ca. 1.7 (bei einer Entropie von 4.5 Bit/Zeichen). Wesentliche Verbesserungen könnten bei Beruecksichtigung der statistischen Abhängigkeiten der einzelnen Zeichen erzielt werden (Markow-Quellencodierung).
Die Quellencodierung eines Textstrings mit diesem Code ist möglich mit der folgenden Funktion. Die verschieden langen Codewörter der einzelnen Zeichen werden einfach aneinander gefügt:
s = huffman('Dies ist ein Probetext!'); result2fig(s)
Die Decodierung erfolgt mithilfe eines Entscheidungsbaumes bitweise bis ein Zeichen erkannt wird. Dann wird zum Stamm des Baumes zurückgesprungen und mit der Decodierung des nächsten Zeichens begonnen. In MATLAB geschieht dies mit der fogenden Funktion:
t = huffman2text(s); result2fig(t)