Exercise 2.5Z: Compression Factor vs. Residual Redundancy

Wir betrachten wie in der Aufgabe 2.5 die Datenkomprimierung mit dem 1983 veröffentlichten Lempel–Ziv–Welch–Algorithmus. Dabei gilt:

Die Eingangsfolge habe die Länge N.
Die Länge der LZW–Coderausgabe ist L.

Die Grafik zeigt für zwei verschiedene binäre Nachrichtenquellen BQ1 und BQ2 den Zusammenhang zwischen den Folgenlängen N und L, dargestellt durch den Funktionsverlauf L(N). Die beiden Nachrichtenquellen besitzen die gleichen statistischen Eigenschaften wie in Aufgabe 2.5:

BQ1 ist aufgrund von ungleichen Symbolwahrscheinlichkeiten (p_A = 0.89, p_B = 0.11) redundant. Es bestehen keine Bindungen zwischen den einzelnen Symbolen. Die Entropie ist H = 0.5 bit/Quellensymbol.
BQ2 ist redundanzfrei und weist die Entropie H = 1 bit/Quellensymbol auf.

Weiter benötigen Sie für die Lösung dieser Aufagbe noch zwei Definitionen:

Der Komprimierungsfaktor ist definitionsgemäß K(N) = L(N)/N.
Die relative Redundanz der LZW–Coderfolge (im Folgenden Restredundanz genannt) ist

$$r(N) = \frac{L(N) - N \cdot H}{L(N)}= 1 - \frac{ N \cdot H}{L(N)}\hspace{0.05cm}.$$

Hinweise:

Die Aufgabe gehört zum Kapitel Komprimierung nach Lempel, Ziv und Welch.
Insbesondere wird Bezug genommen auf die Seiten Restredrundanz als Maß für die Effizienz von Codierverfahren, Effizienz der Lempel-Ziv-Codierung sowie Quantitative Aussagen zur asymptotischen Optimalität.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

Musterlösung

Solution

(1) Der Komprimierungsfaktor ist definiert als der Quotient der Längen von LZW–Ausgangsfolge (L) und Eingangsfolge (N = 10000):

$${\rm BQ1:}\hspace{0.3cm} K \hspace{0.2cm} = \hspace{0.2cm} \frac{6800}{10000}\hspace{0.15cm}\underline{= 0.680}\hspace{0.05cm},$$

$$ {\rm BQ2:}\hspace{0.3cm} K \hspace{0.2cm} = \hspace{0.2cm} \frac{12330}{10000}\hspace{0.15cm}\underline{= 1.233}\hspace{0.05cm}. $$

Die LZW–Codierung macht natürlich nur bei der redundanten Binärquelle BQ1 Sinn. Hier kann die Datenmenge um 32% gesenkt werden.
Bei der redundanzfreien Binärquelle BQ2 führt dagegen die LZW–Codierung zu einer um 23.3% größeren Datenmenge.

(2) Aus der angegebenen Gleichung erhält man mit N = 10000:

$${\rm BQ1:}\hspace{0.3cm} H = 0.5\hspace{0.05cm},\hspace{0.2cm} r(N=10000) \hspace{0.2cm} = \hspace{0.2cm}1 - \frac{0.5 \cdot N}{L } = 1 - \frac{5000}{6800 } \hspace{0.15cm}\underline{\approx 26.5\,\%}\hspace{0.05cm},$$

$$ {\rm BQ2:}\hspace{0.3cm} H = 1.0\hspace{0.05cm},\hspace{0.2cm} r(N=10000) \hspace{0.2cm} = \hspace{0.2cm}1 - \frac{N}{L } = 1 - \frac{10000}{12330 } \hspace{0.15cm}\underline{\approx 19\,\%}\hspace{0.05cm}.$$

Die Restredundanz gibt die (relative) Redundanz der LZWQ–Ausgangsfolge an.
Obwohl die Quelle BQ1 für die LZW–Codierung besser geeignet ist als die redundanzfreie Quelle BQ2, ergibt sich bei BQ1 wegen der Redundanz in der Eingangsfolge eine größere Restredundanz.
Eine kleinere Restredundanz r(N) bei gegebenem N sagt also nichts darüber aus, ob die LZW–Codierung für die vorliegende Quelle sinnvoll ist.
Hierzu muss der Komprimierungsfaktor K betrachtet werden. Allgemein gilt folgender Zusammenhang zwischen r(N) und K(N):

$$r(N) = 1 - \frac{H}{K(N)}\hspace{0.05cm},\hspace{0.2cm} K(N) = H \cdot (1- r(N)) \hspace{0.05cm}.$$

(3) Aus der Tabelle auf der Angabenseite kann man ablesen (bzw. daraus ableiten)

für die redundante Binärquelle BQ1:

$$L(N = 50000) = 32100\hspace{0.05cm},\hspace{0.2cm} K(N = 50000) = 0.642\hspace{0.05cm},\hspace{0.2cm}r(N = 50000) \hspace{0.15cm}\underline {= 22.2\,\% \hspace{0.05cm}},$$

für die redundanzfreie Binärquelle BQ2:

$$L(N = 50000) = 59595\hspace{0.05cm},\hspace{0.2cm} K(N = 50000) = 1.192\hspace{0.05cm},\hspace{0.2cm}r(N = 50000) \hspace{0.15cm}\underline {= 16.1\,\% \hspace{0.05cm}}.$$

Richtig sind somit die Aussagen 1 und 2:

Für beide Quellen ist der Komprimierungsfaktor K(N) für N = 50000 kleiner als für N = 10000.
Gleiches gilt für die Resrredundanz: r(N = 50000) ist kleiner als r(N = 10000).
Sowohl hinsichtlich K(N) als auch hinsichtlich r(N) ergeben sich also bei größerem N „günstigere” Werte, auch dann, wenn eigentlich wie bei der redundanzfreien Binärquelle BQ2 die Anwendung von Lempel–Ziv zu einer Verschlechterung führt.

	Bei beiden Quellen ist K(N = 50000) kleiner als K(N = 10000).
	Bei beiden Quellen ist r(N = 50000) kleiner als r(N = 10000).
	Nur bei BQ1 ergeben sich mit N = 50000 günstigere Werte.