Links und Details zum Vortrag über Datenkompression
Helmut Richter
Zunächst für das Rechnerbetriebspraktikum 2003/04 wurde ein neuer Vortrag über Datenkompression zusammengestellt. Zu diesem Vortrag gibt es keine Folien und auch kein Skriptum. In diesem Beitrag werden Links zum Thema zusammengestellt und die im Vortrag vorgestellten Zahlenbeispiele veröffentlicht.
Einen Überblick über Kompressionsverfahren (Huffman-Codes, Lempel-Ziv) bekommt man auf den Seiten http://www.data-compression.com/ und http://www.faqs.org/faqs/compression-faq/ . Auf der ersteren sind hübsche Animationen zu den Dingen, die im Vortrag auf der handgeschriebenen Overhead-Folie gelandet sind. Dort findet man auch Beispiele zur verlustbehafteten Kompression mit JPEG und JPEG2000. (Das im Vortrag gezeigte Bild der Filmschauspielerin Sophie Marceau ist möglicherweise urheberrechtlich geschützt und wird deswegen nicht ins Web gestellt.)
Speziell über die Wavelets, die bei der Kompression nach JPEG2000 eine ähnliche Rolle spielen wie harmonische Schwingungen bei der Fourieranalyse, findet man Links in http://www.amara.com/current/wavelet.html .
Das Verfahren von Burrows-Wheeler, das dem Programm bzip2
zugrundeliegt, ist in http://marknelson.us/1996/09/01/bwt/
beschrieben; das ist auch die Webseite, die im Vortrag projiziert
wurde.
Es folgt die Tabelle der Buchstabenhäufigkeiten (Häufigkeit, Länge der Codierung, Huffman-Codierung, Zeichen) im Jahresbericht 2001 des LRZ mit einer Länge von 531702 Zeichen. Rechts davon stehen die Codes geordnet, so dass man die Fano-Bedingung überprüfen kann.
77844 3 001 » «
65035 3 011 »e«
40394 4 0100 »n«
30674 4 1001 »r«
29113 4 1011 »i«
26689 4 1100 »t«
22586 5 00000 »s«
18963 5 01010 »a«
17277 5 10000 »u«
16126 5 10001 »d«
13076 5 11011 »h«
12826 5 11100 »l«
11644 5 11111 »g«
11450 6 000010 »o«
9980 6 000110 »c«
9065 6 010110 »m«
7429 6 101010 »b«
6389 6 111010 »f«
6047 6 111100 »[LF]«
5687 6 111101 »z«
5554 7 0000110 ».«
5550 7 0000111 »-«
4672 7 0001111 »w«
4304 7 1010000 »k«
3586 7 1010110 »v«
3564 7 1010111 »,«
3486 7 1101001 »S«
3307 7 1101010 »0«
2989 7 1110111 »p«
2709 8 00010000 »A«
2692 8 00010010 »ü«
2630 8 00010011 »D«
2569 8 00010101 »B«
2404 8 00011101 »P«
2267 8 01011101 »M«
2221 8 01011111 »R«
2131 8 10100010 »1«
1947 8 10100100 »2«
1884 8 10100101 »L«
1782 8 10100111 »ä«
1735 8 11010001 »I«
1575 8 11101100 »W«
1375 9 000100010 »N«
1327 9 000100011 »E«
1313 9 000101000 »V«
1263 9 000101100 »y«
1254 9 000101110 »Z«
1253 9 000101111 »)«
1237 9 000111000 »(«
1143 9 010111001 »F«
1131 9 010111100 »H«
1093 9 010111101 »C«
1067 9 101000110 »K«
946 9 101001100 »G«
937 9 101001101 »T«
880 9 110100000 »3«
851 9 110101100 »U«
832 9 110101101 »ö«
788 9 110101111 »4«
763 9 111011010 »5«
651 10 0001010010 »8«
650 10 0001010011 »*«
630 10 0001011010 »[TAB]«
626 10 0001011011 »:«
626 10 0001110010 »6«
605 10 0001110011 »x«
599 10 0101110000 »7«
545 10 1010001110 »9«
475 10 1010001111 »"«
454 10 1101000010 »j«
423 10 1101000011 »/«
409 10 1101011100 »O«
399 10 1110110110 »ß«
344 10 1110110111 »J«
130 12 010111000110 »X«
121 12 010111000111 »Ü«
101 12 110101110110 »;«
87 12 110101110111 »%«
83 13 0101110001001 »§«
64 13 0101110001011 »q«
56 13 1101011101000 »>«
55 13 1101011101001 »=«
51 13 1101011101011 »Q«
41 14 01011100010001 »_«
23 14 11010111010101 »+«
22 15 010111000100000 »Ö«
20 15 010111000101000 »Ä«
20 15 010111000101001 »@«
19 15 010111000101010 »'«
16 15 110101110101000 »Y«
10 16 0101110001000011 »<«
8 16 0101110001010111 »!«
8 16 1101011101010010 »?«
6 16 1101011101010011 »[«
6 17 01011100010000100 »]«
5 17 01011100010101100 »&«
2 18 010111000101011010 »²«
2 18 010111000101011011 »`«
2 19 0101110001000010100 »à«
1 19 0101110001000010101 »µ«
1 19 0101110001000010110 »[82]«
1 19 0101110001000010111 »è«
|
00000 000010 0000110 0000111 00010000 000100010 000100011 00010010 00010011 000101000 0001010010 0001010011 00010101 000101100 0001011010 0001011011 000101110 000101111 000110 000111000 0001110010 0001110011 00011101 0001111 001 0100 01010 010110 0101110000 010111000100000 01011100010000100 0101110001000010100 0101110001000010101 0101110001000010110 0101110001000010111 0101110001000011 01011100010001 0101110001001 010111000101000 010111000101001 010111000101010 01011100010101100 010111000101011010 010111000101011011 0101110001010111 0101110001011 010111000110 010111000111 010111001 01011101 010111100 010111101 01011111 011 10000 10001 1001 1010000 10100010 101000110 1010001110 1010001111 10100100 10100101 101001100 101001101 10100111 101010 1010110 1010111 1011 1100 110100000 1101000010 1101000011 11010001 1101001 1101010 110101100 110101101 1101011100 1101011101000 1101011101001 110101110101000 1101011101010010 1101011101010011 11010111010101 1101011101011 110101110110 110101110111 110101111 11011 11100 111010 11101100 111011010 1110110110 1110110111 1110111 111100 111101 11111 |
Dieselbe Tabelle für Quintupel von Zeichen beginnt so:
11636 6 000010 » «
1975 8 10011011 »-----«
1837 8 10101110 » der «
1724 8 11001001 » und «
1691 8 11001101 » die «
927 9 101011010 » eine«
914 9 101100000 » von «
888 9 110000010 » für «
784 9 111001000 » des «
700 10 0001010101 »ation«
626 10 0010111010 » den «
606 10 0011011001 »chen «
592 10 0011100101 »ystem«
577 10 0011101111 »ungen«
572 10 0100010101 »erden«
572 10 0100010110 »werde«
562 10 0100100000 » werd«
520 10 0101100011 »enutz«
512 10 1001010010 »ngen «
502 10 1001011110 » mit «
497 10 1001100001 »chner«
485 10 1001111000 » auf «
484 10 1001111010 »erver«
484 10 1001111011 »echne«
482 10 1001111100 » das «
480 10 1010010101 »ische«
474 10 1010011010 »rbeit«
473 10 1010011100 »n der«
458 10 1010111111 »ung d«
454 10 1011001000 »n und«
440 10 1100001110 »erung«
440 10 1100001111 »rden «
433 10 1100010100 »utzer«
428 10 1100101011 »nutze«
423 10 1100110011 » LRZ «
|
Der Effizienzvergleich zwischen den Komprimierungsverfahren zeigt folgende Werte:
| Länge | n-Tupel | Forts. | min | max | Bit | Bit/Zeichen | Kompression |
|---|---|---|---|---|---|---|---|
| 1 | 102 | 102.00 | 3 | 19 | 2584280 | 4.86 | 39.25 |
| 2 | 2803 | 27.48 | 5 | 19 | 4523526 | 4.25 | 46.83 |
| 3 | 18568 | 6.62 | 5 | 19 | 5966505 | 3.74 | 53.24 |
| 4 | 53069 | 2.86 | 8 | 19 | 6968074 | 3.28 | 59.05 |
| 5 | 98915 | 1.86 | 6 | 19 | 7677360 | 2.89 | 63.90 |
| compress | 1766392 | 3.32 | 58.47 | ||||
| gzip | 1443696 | 2.72 | 66.06 | ||||
| bzip2 | 1095520 | 2.06 | 74.24 |
"Länge" ist die Länge der Blöcke für den Huffmann-Code oder der Name eines anders arbeitenden Kompressionsprogramms. Die Anzahl der im Text vorkommenden n-Tupel von Zeichen steht daneben; unter "Forts." steht der Quotient zum Vorgängerwert dieser Anzahl; beispielsweise kommen zu einem Quadrupel im Schnitt nur 1.86 Quintupel vor, die damit beginnen. "min" und "max" bezeichnen die minimal und maximale Länge der generierten Huffman-Codes; ob die einheitliche Obergrenze von 19 Zufall ist oder eine Bedeutung hat, ist nicht bekannt. Unter "Bit" steht die Summe der Produkte Zeichenlänge·Häufigkeit; da es im Text fast so viele n-Tupel wie Zeichen gibt, muss man die Zahl vor dem Weiterrechnen durch n dividieren. Der Kompressionsfaktor ist in Prozent angegeben.
Schließlich ist hier noch das Ergebnis des Sprachvergleichs. Die Texte waren jeweils der vollständige Text der Apostelgeschichte des Lukas ohne Zwischenüberschriften des Übersetzers und ohne Kapitel- und Versnummern in folgenden Bibelübersetzungen:
-
deutsch: Martin Luther, Version 1984, 132952 Zeichen
-
deutsch: Einheitsübersetzung, 131387 Zeichen
-
englisch: New American Standard Bible, 130779 Zeichen
-
französisch: Louis Segond, 131846 Zeichen
-
swahili: Habari Njema, 130981 Zeichen
In der Tabelle steht links die Übersetzung, aus der der gesamte Text verwendet wurde und rechts die, aus der nur ein Textanfang von 2000 Zeichen verwendet wurde; ganz rechts steht, um wieviel Bytes durch die Anfügung dieser 2000 Zeichen der bzip2-komprimierte Text länger wurde. Die Tabelle ist nach diesen Zahlen geordnet. Gleiche Sprachen sind mit gleichen Farben dargestellt, und zwar blasse Farben für Sprachen, bei denen nur ASCII-Zeichen im Text als Buchstaben auftauchen (englisch, swahili) und kräftigere Farben für Sprachen, die häufig andere Zeichen (Umlaute, Akzente) einsetzen.
| New American Standard Bible (en) | New American Standard Bible (en) | 253 |
| Einheitsübersetzung (de) | Einheitsübersetzung (de) | 326 |
| Habari Njema (sw) | Habari Njema (sw) | 328 |
| Segond (fr) | Segond (fr) | 331 |
| Einheitsübersetzung (de) | Luther (de) | 348 |
| Luther (de) | Luther (de) | 358 |
| Luther (de) | Einheitsübersetzung (de) | 523 |
| Einheitsübersetzung (de) | New American Standard Bible (en) | 1141 |
| New American Standard Bible (en) | Luther (de) | 1153 |
| New American Standard Bible (en) | Habari Njema (sw) | 1169 |
| Einheitsübersetzung (de) | Habari Njema (sw) | 1195 |
| Segond (fr) | New American Standard Bible (en) | 1228 |
| Luther (de) | New American Standard Bible (en) | 1236 |
| New American Standard Bible (en) | Einheitsübersetzung (de) | 1256 |
| Einheitsübersetzung (de) | Segond (fr) | 1257 |
| New American Standard Bible (en) | Segond (fr) | 1257 |
| Segond (fr) | Habari Njema (sw) | 1258 |
| Segond (fr) | Einheitsübersetzung (de) | 1267 |
| Luther (de) | Habari Njema (sw) | 1352 |
| Habari Njema (sw) | Luther (de) | 1353 |
| Habari Njema (sw) | New American Standard Bible (en) | 1361 |
| Habari Njema (sw) | Einheitsübersetzung (de) | 1365 |
| Habari Njema (sw) | Segond (fr) | 1384 |
| Segond (fr) | Luther (de) | 1397 |
| Luther (de) | Segond (fr) | 1459 |
Eindeutig ist die Erkennung der Sprache (die obersten sechs Zeilen); interessant ist, dass Sprachen mit kleinem Alphabet eine schlechtere Umgebung für Sprachen mit reichhaltigerem Alphabet abgeben als umgekehrt (also blasse Felder konzentrieren sich in der linken Spalte eher unten). Das ist an sich nicht verwunderlich, zeigt aber, dass die Statistik durch marginale Änderungen an der Darstellung gewaltig verzerrt werden kann und daher mit viel Vorsicht zu genießen ist. Im Vortrag gab es denselben Effekt für die beiden deutschen Texte (Luther vor und Einheitsübersetzung nach der Rechtschreibreform); der ist aber bei den unten stehenden Tabellen bereits bereinigt. - Die unterschiedliche Positionierung von Englisch und Swahili hat die Ursache nicht im Alphabet, sondern in der Phonologie: weitaus die meisten Silben in Swahili beginnen einem einzigen Konsonanten, mit einem Vokal oder mit einer der für die Sprache besonders typischen Konsonantenverbindungen (bw, mb, mv, mw, nd, nj, ny, nz, ng): zusammen deutlich über 90% die meisten englischen Silben kommen also in Swahili-Texten nicht vor; umgekehrt wohl eher.