Grundlagen der Informationstheorie und Kodierung
Mit dem LZ77-Verfahren komprimierte Daten werden wiederhergestellt. Die Daten lauten in dieser Reihenfolge „Zeichen A“, „Zeichen B“, „(Entfernung 2, Länge 5)“. (Entfernung d, Länge L) bedeutet, L-mal Zeichen für Zeichen „das Zeichen, das d Zeichen vor dem Ende der bereits wiederhergestellten Zeichenkette steht, ans Ende kopieren“. Welche Zeichenkette ergibt sich?
- AABAB
- BABABABA
- CABAAAAA
Antwort und Erläuterung anzeigen
Antwort: B. ABABABA
Man beginnt mit „AB“ aus A und B. Das A 2 Zeichen zurück wird kopiert und ergibt „ABA“, dann das B, das nun 2 Zeichen zurück liegt, und ergibt „ABAB“; mit jedem kopierten Zeichen rückt auch die Kopierquelle um eins weiter, sodass nach 5 kopierten Zeichen „ABABABA“ mit 7 Zeichen entsteht. Die Länge darf also größer als die Entfernung sein, und indem gerade kopierte Zeichen als Quelle dienen, lässt sich eine lange Wiederholung eines kurzen Musters mit einem einzigen Paar darstellen.
Weiter: 9 weitere Fragen zu Grundlagen der Informationstheorie und Kodierung