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:

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.