Betrachten Sie folgende Nachricht:

die puppen puppen mit kleinen puppen,
die kleinen puppen puppen mit winzigen puppen,
die winzigen puppen puppen mit pueppchen,
die pueppchen puppen mit kleinen pueppchen,
die kleinen pueppchen puppen mit winzigen pueppchen,
die winzigen pueppchen puppen,
keiner puppt mit ihr.

  • (a) Wie lang (in Bits) ist die kodierte Botschaft im ASCII-Code (Zeilenumbruch gilt als 1 Zeichen)? Wie lang wäre die kürzeste mögliche Kodierung der Nachricht (in Bits) bei Codewörtern konstanter Länge? (3 Punkte)
  • (b) Entwerfen Sie eine effiziente Huffman-Kodierung für die Nachricht! Erstellen Sie einen korrekten Codebaum und ermitteln Sie die Länge (in Bits) der so kodierten Nachricht! Die kodierte Nachricht müssen Sie nicht explizit angeben. (6 Punkte)
  • (c) Berechnen Sie die Entropie der Nachricht und vergleichen Sie diese mit dem mittleren Speicherplatzbedarf pro Zeichen bei den Kodierungen aus den Aufgabenteilen a) und b)! (3 Punkte)

Approach

Länge (in Zeichen): ´276´
Größe (in Bit): ´276 * 7 = 1932´
Anzahl verschiedener Zeichen: ´20´
Mindestwortlänge für (binäre) Codierung:

´2^n >= 20´
´n >= ln(20)/ln(2)´
´n >= 4.322´ ´n = 5´

Länge der gesamten Botschaft (in Bit): ´275 * 5 = 1380´
Länge der gesamten Huffman-kodierten Botschaft (in Bit): ´1281´ \

digraph G {
    edge [label=0];
    graph [ranksep=0];
    P [shape=record, label=\"{{P|54}|00}\"];
    Y [shape=record, label=\"{{\\\
    |6}|01000}\"];
    DOT [shape=record, label=\"{{.|1}|0100100}\"];
    R [shape=record, label=\"{{R|2}|0100101}\"];
    G [shape=record, label=\"{{G|4}|010011}\"];
    H [shape=record, label=\"{{H|7}|01010}\"];
    T [shape=record, label=\"{{T|7}|01011}\"];
    SPACE [shape=record, label=\"{{' '|33}|011}\"];
    N [shape=record, label=\"{{N|34}|100}\"];
    L [shape=record, label=\"{{L|4}|101000}\"];
    W [shape=record, label=\"{{W|4}|101001}\"];
    Z [shape=record, label=\"{{Z|4}|101010}\"];
    K [shape=record, label=\"{{K|5}|101011}\"];
    U [shape=record, label=\"{{U|18}|1011}\"];
    E [shape=record, label=\"{{E|43}|110}\"];
    M [shape=record, label=\"{{M|6}|111000}\"];
    COMA [shape=record, label=\"{{,|6}|111001}\"];
    C [shape=record, label=\"{{C|6}|111010}\"];
    D [shape=record, label=\"{{D|6}|111011}\"];
    CD [label=12];
    I [shape=record, label=\"{{I|26}|1111}\"];
    276 -> 114 -> P;
    60 -> 27 -> 13 -> Y;
    7 -> 3 -> DOT;
    14 -> H;
    162 -> 69 -> N;
    35 -> 17 -> 8 -> L;
    9 -> Z;
    93 -> E;
    50 -> 24 -> 12 -> M;
    CD -> C;3 -> R [label=1];
    13 -> 7 -> G [label=1];
    27 -> 14 -> T [label=1];
    114 -> 60 -> SPACE [label=1];
    8 -> W [label=1];
    17 -> 9 -> K [label=1];
    69 -> 35 -> U [label=1];
    12 -> COMA [label=1];
    24 -> CD -> D [label=1];
    276 -> 162 -> 93 -> 50 -> I [label=1];
}

Entropie der Nachricht:

´H(X) = -[(0.12lb0.12) + (0.022lb0.022) + (0.004lb0.004) + (0.022lb0.022) + ´
´(0.022lb0.022) + (0.156lb0.156) + (0.014lb0.014) + (0.025lb0.025) + ´
´(0.094lb0.094) + (0.018lb0.018) + (0.014lb0.014) + (0.022lb0.022) + ´
´(0.123lb0.123) + (0.196lb0.196) + (0.007lb0.007) + (0.025lb0.025) + ´
´(0.065lb0.065) + (0.014lb0.014) + (0.022lb0.022) + (0.014lb0.014)]´
´H(X) = -[(-0.366) + (-0.12) + (-0.029) + (-0.12) + (-0.12) + (-0.418) + ´
´(-0.089) + (-0.134) + (-0.321) + (-0.105) + (-0.089) + (-0.12) + (-0.372) + ´
´(-0.46) + (-0.052) + (-0.134) + (-0.257) + (-0.089) + (-0.12) + (-0.089)]´
´H(X) = -[-3.60395]´
´H(X) = 3.60395´

Vergleich (in Bit/Zeichen)
ASCII7
Feste Wortlänge7
Huffman´1281/276´ = 4.6413

Die Huffmann-Kodierung ist die effizienteste Kodierung der drei, aber immer noch größer als die Entropie.


Solution
    • (a)
      Länge der gesamten Botschaft (in Bit): ´1380´
      Länge der gesamten Huffman-kodierten Botschaft (in Bit): ´1281´
    • (b)
    • (c) Die Huffmann-Kodierung ist die effizienteste Kodierung der drei, aber immer noch größer als die Entropie.