Übung — AFB III (Verallgemeinern und Reflektieren)

Musterlösung: Es gibt \(2^{n}\) Dateien mit genau \(n\) Bit, aber nur \(2^{0}+2^{1}+\dots+2^{n-1}=2^{n}-1\) kürzere Bitfolgen. Ein verlustfreies Verfahren muss verschiedene Dateien auf verschiedene Ergebnisse abbilden, sonst ließe es sich nicht umkehren. Also bleibt mindestens eine Datei übrig, die nicht kürzer wird — die Behauptung ist falsch.

Musterlösung: In Fotos unterscheiden sich benachbarte Pixel fast immer leicht (Rauschen, Verläufe). Es entstehen fast nur Läufe der Länge 1; jedes Paar kostet dann Anzahl-Bits plus 24 Bit Farbe — mehr als das Original. Lauflänge eignet sich für Grafiken mit großen einfarbigen Flächen, nicht für Fotos.

Musterlösung: Wäre Codewort \(u\) Präfix von \(v\), läge der Knoten von \(u\) auf dem Weg von der Wurzel zu \(v\). Dann hätte er Kinder, wäre also kein Blatt. Zeichen stehen aber nur in Blättern — Widerspruch. Also ist kein Codewort Anfang eines anderen.

Musterlösung: Alle Blätter haben die Häufigkeit \(h\). Zuerst werden je zwei zu Knoten \(2h\) verbunden; erst wenn alle Blätter verbraucht sind, sind die \(2h\)-Knoten die kleinsten. So entsteht Ebene für Ebene ein vollständiger Binärbaum; nach \(k\) Ebenen bleibt die Wurzel. Alle Blätter liegen in Tiefe \(k\) — jedes Codewort hat \(k\) Bit.

Musterlösung: Kommt eine Quittung erst nach dem Timeout an, hat der Sender das Paket schon erneut geschickt. Ohne Nummer könnte er diese späte Quittung für die des nächsten Pakets halten und weiterzählen, obwohl dieses verloren ging. Mit Nummer ordnet er jede Quittung eindeutig zu.

Musterlösung: Ein zu kurzer Timeout läuft ab, bevor die Quittung da sein kann: Pakete werden unnötig wiederholt, der Empfänger erhält Duplikate, die Leitung wird belastet. Ein zu langer Timeout verschenkt nach jedem echten Verlust viel Zeit. Sinnvoll ist ein Wert etwas über der Zeit für Hin- und Rückweg samt Bearbeitung.

Musterlösung: Gut verschlüsselte Daten sehen wie Zufall aus: keine Läufe, gleich verteilte Häufigkeiten — Kompression danach bringt nichts. Deshalb komprimiert man zuerst und verschlüsselt dann. Einschränkung: Die Länge der komprimierten Daten kann Rückschlüsse auf den Inhalt erlauben; in sensiblen Anwendungen wird das berücksichtigt.

Musterlösung: Beim festen Code liegen die Grenzen fest; ein gekipptes Bit verfälscht genau ein Zeichen. Beim Huffman-Code kann das Bit ein Codewort verlängern oder verkürzen — alle folgenden Grenzen verschieben sich, bis der Strom zufällig wieder synchron ist. Kompression macht Daten also fehleranfälliger.

Musterlösung: Variante 1: Der Kopf enthält die Anzahl der Datenzeichen; der Empfänger liest genau so viele Zeichen, egal was sie enthalten. Variante 2: Maskierung — im Datenteil wird $ als \$ und \ als \\ geschrieben; ein einzelnes $ bedeutet dann immer Rahmenende. Variante 1 ist leichter zu implementieren, Variante 2 braucht keine Längenangabe vorab.

Musterlösung: Der Mittelwert der Einsparungen gewichtet jede Datei gleich, egal wie groß sie ist. Spart ein Programm bei vielen kleinen Dateien viel, bei großen aber wenig, ist der tatsächlich gewonnene Speicher viel kleiner als 60 %. Aussagekräftig ist das Gesamtverhältnis: Summe komprimiert durch Summe original, an typischen Daten gemessen.