12.10 Datenkompression

Damit Daten weniger Platz auf dem Datenträger einnehmen, werden sie komprimiert. Bei Netzwerkverbindungen ist die logische Konsequenz, dass weniger Daten natürlich auch schneller übertragen werden.

Über alle Plattformen hinweg haben sich Standards gebildet. Zwei Kompressionsstandards sollen an dieser Stelle beschrieben werden.

compress/decompress, GZip/GunZip

Seitdem der LZW-Algorithmus im Juni 1984 im IEEE Journal beschrieben wurde, gibt es unter jedem Unix-System die Dienstprogramme compress und uncompress, die verlustfrei Daten zusammenpacken.¹ Über dieses Format wird ein Datenstrom gepackt und entpackt. gzip und gunzip² sind freie Varianten von compress beziehungsweise uncompress und unterliegen der GNU Public Licence. Das Format enthält eine zyklische Überprüfung bezüglich defekter Daten. Die Endung einer Datei, die mit gzip gepackt ist, ist mit ».gz« angegeben, wobei die Endung unter compress nur ».Z« ist. gzip behält die Rechte und Zeitattribute der Datei bei.

Komprimieren mit tar?

tar ist kein Programm, mit dem sich Dateien komprimieren lassen. tar bündelt lediglich mehrere Dateien zu einer neuen Datei, ohne sie zu komprimieren. Oftmals werden die mit tar gepackten Dateien anschließend mit gzip beziehungsweise bzip2 gepackt. Die Endung ist dann ».tar.Z«. Werden mehrere Daten erst in einem Tar-Archiv zusammengefasst und dann gepackt, ist die Kompressionsrate höher, als wenn jede Datei einzeln komprimiert wird. Der Grund ist einfach, denn das Kompressionsprogramm kann die Redundanz besser ausnutzen. Der Nachteil ist freilich, dass für eine Datei gleich das ganze Tar-Archiv ausgepackt werden muss.

Zip

Das Utility zip erzeugt ein Archiv aus mehreren Dateien. Der Unterschied zu gzip liegt darin, dass zip kein Filterprogramm mit einem Datenstrom ist, sondern ein Programm, welches sich Dateien nimmt, die zu einem Archiv zusammengebunden werden. Auf jede Datei lässt sich anschließend individuell zugreifen. PkZip ist unter MS-DOS ein Standardprogramm, unter Windows ist es oft WinZip. Obwohl Zip und GZip von der Anwendung her unterschiedlich arbeiten, verwenden sie denselben Algorithmus. Beide basieren auf Algorithmen, die im RFC 1952 definiert sind.

Es gibt auch unkomprimierte Zip-Archive, obwohl diese selten sind. Ein Beispiel dafür sind die Java-Archive des Internet Explorers. Die größte Datei ist unkomprimiert 5,3 MB groß, gepackt wäre sie 2 MB groß. Sie wurden vermutlich aus Gründen der Geschwindigkeit nicht gepackt, da sich die Daten aus unkomprimierten Archiven schneller lesen lassen, weil keine Prozessorleistung für das Entpacken aufgewendet werden muss.

12.10.1 Die Java-Unterstützung beim Komprimieren und Zusammenpacken

Unter Java ist ein Paket java.util.zip eingerichtet, um mit komprimierten Dateien zu operieren. Das Paket bietet zur Komprimierung zwei allgemein gebräuchlich Formate: GZip/GunZip zum Komprimieren beziehungsweise Entkomprimieren für Datenströme und Zip zum Behandeln von Archiven und Komprimieren von Dateien. Ebenfalls wird das eigene Archiv-Format Jar durch das Paket java.util.jar unterstützt. Jar ist eine Erweiterung des Zip-Formats.

Tar-Archive werden nicht unterstützt, jedoch gibt es eine Reihe freier Implementierungen, unter anderem von der Apache-Group: http://cvs.apache.org/viewcvs.cgi/jakarta-ant/src/main/org/apache/tools/tar/; sie definieren Ein- und Ausgabeströme.

12.10.2 Datenströme komprimieren

Zum Packen und Entpacken von Strömen wird GZip verwendet. Wir sehen uns nun einige Datenströme an, die auf der Klasse FilterOutputStream basieren.

Daten packen

Die Klasse java.util.zip bietet zwei Unterklassen von FilterOutputStream, die das Schreiben von komprimierten Daten erlauben. Um Daten unter dem GZip-Algorithmus zu packen, müssen wir einfach einen vorhandenen Datenstrom zu einem GZIPOutputStream erweitern.

FileOutputStream out = new FileOutputStream( Dateiname );
GZIPOutputStream zipout = new GZIPOutputStream( out );

class java.util.zip.GZIPOutputStream
extends DeflaterOutputStream

GZIPOutputStream( OutputStream out) Erzeugt einen packenden Datenstrom mit der voreingestellten Puffergröße von 512 Byte.

GZIPOutputStream( OutputStream out, int size ) Erzeugt einen packenden Datenstrom mit einem Puffer der Größe size.

Listing 12.26 gzip.java

import java.io.*;
import java.util.zip.*;
class gzip
{
  private static int BLOCKSIZE = 8192;
  public static void main( String args[] )
  {
    if ( args.length != 1 ) {
      System.out.println( "Usage: gzip source" );
      return;
    }
    try
    {
      GZIPOutputStream zipout =
        new GZIPOutputStream( new FileOutputStream(args[0] + ".gz") );

      byte buffer[] = new byte[blockSize];
      FileInputStream in = new FileInputStream( args[0] );
      for ( int length; (length = in.read(buffer, 0, BLOCKSIZE)) != -1; )
        zipout.write( buffer, 0, length );
      in.close();
      zipout.close();
    }
    catch ( IOException e )
    {
      System.out.println( "Error: Couldn't compress "+args[0] );
    }
  }
}

Zunächst überprüfen wir, ob ein Argument auf der Kommandozeile vorhanden ist. Aus diesem Argument konstruieren wir mit der Endung ».gz« einen FileOutputStream. Um diesen manteln wir dann noch einen GZIPOutputStream. Mittels read() lesen wir aus dem FileInputStream einen Block Daten und schreiben ihn in den GZIPOutputStream, der die Daten dann komprimiert.

Hier klicken, um das Bild zu Vergrößern

Daten entpacken

Um die Daten zu entpacken, müssen wir nur den umgekehrten Weg beschreiten. Zum Einsatz kommt hier eine der zwei Unterklassen von FilterInputStream. Wieder wickeln wir um einen InputStream einen GZIPInputStream und lesen dann daraus.

class java.util.zip.GZIPInputStream
extends InflaterInputStream

GZIPInputStream( InputStream in, int size ) Erzeugt einen auspackenden Datenstrom mit einem Puffer der Größe size.

GZIPInputStream( InputStream in ) Erzeugt einen auspackenden Datenstrom mit der voreingestellten Puffergröße von 512 Byte.

Listing 12.27 gunzip.java

import java.io.*;
import java.util.zip.*;
public class gunzip
{
  private static int BLOCKSIZE = 8192;
  public static void main( String args[] )
  {
    if ( args.length != 1 ) {
      System.out.println( "Usage: gunzip source" );
      return;
    }
    String zipname, source;
    if ( args[0].endsWith(".gz") ) {
      zipname = args[0];
      source = zipname.substring(0, zipname.length() - 3);
    }
    else {
      zipname = args[0] + ".gz";
      source = args[0];
    }
    try
    {
      GZIPInputStream zipin =
        new GZIPInputStream( new FileInputStream( zipname ) );
      byte buffer[] = new byte[blockSize];
      FileOutputStream out = new FileOutputStream( source );
      for ( int length; (length = zipin.read(buffer, 0, BLOCKSIZE)) != -1; )
        out.write( buffer, 0, length );
      out.close();
      zipin.close();
    }
    catch ( IOException e ) {
      System.out.println("Error: Couldn't decompress "+args[0]);
    }
  }
}

Endet die Datei mit ».gz«, so entwickeln wir daraus den herkömmlichen Dateinamen. Endet sie nicht mit diesem Suffix, so nehmen wir einfach an, dass die gepackte Datei diese Endung besitzt, der Benutzer dies aber nicht angegeben hat. Nach dem Zusammensetzen des Dateinamens holen wir von der gepackten Datei einen FileInputStream und packen einen GZIPInputStream darum. Nun öffnen wir die Ausgabedatei und schreiben in Blöcken zu 8 KB die Datei vom GZIPInputStream in die Ausgabedatei.

12.10.3 Zip-Archive

Der Zugriff auf die Daten eines Zip-Archivs unterscheidet sich schon deshalb vom Zugriff auf die Daten eines GZip-Streams, weil diese in Form eines Archivs vorliegen. Unter Zip wird jede Datei einzeln und unabhängig komprimiert. Wurden etwa über Tar vorher alle Dateien in ein unkomprimiertes Archiv übernommen, kann der Packalgorithmus GZip beim Packen dieser Dateisammlung bessere Ergebnisse erzielen, als wenn wie beim Zip-Verfahren alle Dateien einzeln gepackt würden.

Die Klassen ZipFile und ZipEntry

Objekte der Klasse ZipFile repräsentieren ein Zip-Archiv und bieten Funktionen, um auf die einzelnen Dateien (Objekte der Klasse ZipEntry) des Archivs zuzugreifen. Intern nutzt ZipFile eine Datei mit wahlfreiem Zugriff (Random Access File), so dass wir auf spezielle Einträge sofort zugreifen können. Ein Zip-Archiv der Reihe nach auszulesen, so wie ein gepackter Strom es vorschreibt, ist überflüssig.

Unter Java ist jeder Eintrag in einem Zip-Archiv durch ein Objekt der Klasse ZipEntry repräsentiert. Liegt einmal ein ZipEntry-Objekt vor, so können ihm durch verschiedene Methoden Dateiattribute entlockt werden, beispielsweise die Originalgröße, das Kompressionsverhältnis, das Datum, wann die Datei angelegt wurde, und Weiteres. Auch kann ein Datenstrom erzeugt werden, so dass sich eine komprimierte Datei im Archiv lesen und schreiben lässt.

Um auf die Dateien eines Archivs zuzugreifen, muss ein ZipFile-Objekt erzeugt werden, was auf zwei Arten geschehen kann: entweder über den Dateinamen oder über ein File-Objekt. Es gibt drei Konstruktoren für Zip-Archive: Ein Standard-Konstruktor ist protected und kann daher nicht öffentlich verwendet werden. Bei den beiden anderen muss des Weiteren IOException und ZipException abgefangen werden.

Hier klicken, um das Bild zu Vergrößern

class java.util.zip.ZipFile
implements ZipConstants

ZipFile( String name ) throws ZipException, IOException Öffnet ein Zip-Archiv mit dem Dateinamen.

ZipFile( File file ) throws ZipException, IOException Öffnet ein Zip-Archiv mit dem gegebenen File-Objekt.

ZipFile( File file, int mode ) throws ZipException, IOException Öffnet ein Zip-Archiv mit dem gegebenen File-Objekt. Der Modus ZipFile.OPEN_READ oder ZipFile.OPEN_READ|ZipFile.OPEN_DELETE bestimmt den Zugriff auf das Archiv. Der Standard-Konstruktor öffnet mit OPEN_READ.

Anschließend lässt sich eine Enumeration mit der Methode entries() erzeugen, und alle Dateien lassen sich als ZipEntry zurückgeben.

ZipFile z = new ZipFile( "foo.zip" );
for ( Enumeration e = z.entries(); e.hasMoreElements(); )
{
  ZipEntry ze = (ZipEntry) e.nextElement();
  System.out.println( ze.getName() );
}

Neben der Enumeration gibt es noch eine weitere Möglichkeit, um an bestimmte Einträge heranzukommen: getEntry(String). Ist der Name der komprimierten Datei bekannt, gibt es sofort ein ZipEntry-Objekt zurück.

Wollen wir nun die gesuchte Datei auspacken, holen wir mittels getInputStream(ZipEntry) ein InputStream-Objekt und können dann auf den Inhalt der Datei zugreifen. Es ist bemerkenswert, dass getInputStream() keine Methode von ZipEntry ist, so wie wir es erwarten würden, sondern von ZipFile, obwohl dies mit den eigentlichen Dateien nicht viel zu tun hat.

ZipFile file = new ZipFile( "foo.zip" );
ZipEntry entry = file.getEntry( "largeFile" );
InputStream input = file.getInputStream( entry );

class java.util.zip.ZipFile
implements ZipConstants

ZipEntry getEntry( String name ) Liefert eine Datei aus dem Archiv. null, wenn kein Eintrag mit dem Namen existiert.

InputStream getInputStream( ZipEntry ze ) throws IOException Gibt einen Eingabestrom zurück, mit dem auf den Inhalt einer Datei zugegriffen werden kann.

String getName() Liefert den Pfadnamen des Zip-Archivs.

Enumeration entries() Gibt eine Aufzählung des Zip-Archivs in Form von ZipEntry-Objekten zurück.

int size() Gibt die Anzahl der Einträge im Zip-Archiv zurück.

void close() throws IOException Schließt das Zip-Archiv.

ZipEntry createZipEntry( String name ) Erzeugt ein neues ZipEntry-Objekt mit dem angegebenen Dateinamen.

Eine Funktion, die eine Datei auspackt

Um die Datei tatsächlich auszupacken, müssen wir nur noch eine neue Datei erzeugen, diese mit einem Datenstrom verbinden und dann die dekomprimierte Ausgabe dahin umleiten. Eine kompakte Funktion getEntry(ZipFile, ZipEntry), die auch noch aus Geschwindigkeitsgründen einen BufferedInputStream beziehungsweise BufferedOutputStream um die Kanäle packt, kann so aussehen:

public static void getEntry( ZipFile zipFile, ZipEntry target )
  throws ZipException,IOException
{
  try
  {
    File file = new File( target.getName() );
    BufferedInputStream bis = new BufferedInputStream(
                                zipFile.getInputStream( target ) );
    File dir = new File( file.getParent() );
    dir.mkdirs();
    BufferedOutputStream bos = new BufferedOutputStream(
                                 new FileOutputStream( file ) );
    for ( int c; ( c = bis.read() ) != EOF; )
      bos.write( (byte)c );
    bos.close();
  }
}

Das Objekt ZipEntry und die Datei-Attribute

Ein Objekt der Klasse ZipEntry repräsentiert jeweils eine Datei oder ein Verzeichnis eines Archivs. Diese Datei kann gepackt (dafür ist die Konstante ZipEntry.DEFLATED reserviert) oder auch ungepackt sein (angezeigt durch die Konstante ZipEntry.STORED). Auf dem Objekt können verschiedene Attribute gesetzt und abgefragt werden. Dadurch lassen sich Statistiken über Kompressionsraten und Weiteres ermitteln. Entsprechend den folgenden Funktionen überschreibt ZipEntry auch die Funktionen toString(), hashCode() und clone() der Klasse Object:

class java.util.zip.ZipEntry
implements ZipConstants, Cloneable

String getName() Liefert den Namen des Eintrags.

void setTime( long time ) Ändert die Modifikationszeit des Eintrags.

long getTime() Liefert die Modifikationszeit des Eintrags oder -1, wenn diese nicht angegeben ist.

void setSize( long size ) Setzt die Größe der unkomprimierten Datei. Wir werden mit einer IllegalArgument Exception bestraft, wenn die Größe kleiner 0 oder größer 0xFFFFFFFF ist.

long getSize() Liefert die Größe der unkomprimierten Datei oder -1, falls unbekannt.

long getCrc() Liefert die CRC-32-Checksumme der unkomprimierten Datei oder -1, falls unbekannt.

void setMethod( int method ) Setzt die Kompressionsmethode entweder auf STORED oder DEFLATED.

int getMethod() Liefert die Kompressionsmethode entweder auf STORED, DEFLATED oder -1, falls unbekannt.

void setExtra( byte extra[] ) Setzt das optionale Zusatzfeld für den Eintrag. Übersteigt die Größe des Zusatzfelds 0xFFFFF Bytes, dann wird eine IllegalArgumentException ausgelöst.

byte[] getExtra() Liefert das Extrafeld oder null, falls es nicht belegt ist.

void setComment( String comment ) Setzt einen Kommentar-String der 0xFFFF Zeichen lang sein darf (sonst wird eine IllegalArgumentException ausgelöst).

String getComment() Gibt den Kommentar oder null zurück.

long getCompressedSize() Liefert die Dateigröße nach dem Komprimieren oder -1, falls diese unbekannt ist. Ist der Kompressionstyp ZipEntry.STORED, dann stimmt diese Größe natürlich mit dem Rückgabewert von getSize() überein.

boolean isDirectory() Liefert true, falls der Eintrag ein Verzeichnis ist. Der Name der Datei endet mit einem Slash '/'.

Dateien und Attribute als Inhalte eines Archivs

Wir haben nun die Informationen, um uns den Inhalt eines Archivs mit den Attributen anzeigen zu lassen. Wir wollen im Folgenden zwei Klassen entwickeln, die dies umsetzen. Zunächst die allgemeine Klasse ZIPList:

Listing 12.28 ZIPList.java

import java.io.*;
import java.text.*;
import java.util.*;
import java.util.zip.*;
class ZIPList
{
  public ZIPList( File file ) throws IOException
  {
    ZipFile zipfile = new ZipFile( file );
    s = new String[ zipfile.size() ];
    int i = 0;
    for ( Enumeration e = zipfile.entries(); e.hasMoreElements(); )
      s[i++] = buildInfoString( (ZipEntry) e.nextElement() );
    // for sorting the entries
    collator = Collator.getInstance( Locale.GERMANY );
    collator.setStrength( Collator.PRIMARY );
  }
  public void sort()
  {
    Arrays.sort( s, collator );
  }
  public String[] getFileList()
  {
    return s;
  }
  // private
  private String buildInfoString( ZipEntry entry )
  {
    String fileName = entry.getName();
    long   size = entry.getSize(),
           compressedSize = entry.getCompressedSize(),
           time = entry.getTime();
    SimpleDateFormat format = new SimpleDateFormat();
    String outTime = format.format( new Date(time) );
    return (entry.isDirectory() ? "+" : "-") + fileName
      + "\tSize: " + size
      + "\tPacked: " + compressedSize
      + "\t" + outTime;
  }
  private Collator collator;
  private String s[];
}

Die Klasse enthält einen Konstruktor, der den Dateinamen des Archivs verlangt. Intern legt dieser ein Array von Zeichenketten an, welches alle Namen der Dateien im Archiv aufnimmt. Nach dem Aufruf enthält das Feld alle Dateien, und die Methode getFileList() gibt dieses Feld nach außen weiter. Den Weg, die Daten sofort auszugeben, haben wir hier absichtlich nicht gewählt, denn über sort() lassen sich die Einträge noch sortieren. Wir nutzen hier die statische Funktion Arrays.sort(), um ein Feld von Strings zu sortieren. Damit diese auch korrekt nach der deutschen Schreibweise einsortiert werden, nutzen wir einen Collator, der mit dem Exemplar von Locale.GERMANY initialisiert wird.

Der Konstruktor baut das Feld mit den Datei- und Verzeichnisnamen durch die Enumeration auf. Dabei wird für jedes ZipEntry eine private Funktion buildInfoString() genutzt. Sie baut einen primitiven String zusammen, der Dateiname, Größe, Packrate und Datum anzeigt. Daneben werden alle Verzeichnisse mit einem Pluszeichen markiert und Dateien mit einem Minuszeichen. Die Konsequenz dieser Notation ist, dass Verzeichnisse bei der Gesamtanzeige zuerst ausgegeben werden.

Die zweite Klasse ist ZIPListDemo. Sie öffnet eine Datei über die Kommandozeile und beschwert sich, falls der Parameter fehlt. Existiert die Datei nicht, so wird genauso eine Fehlermeldung ausgegeben wie beim nicht erteilten Zugriff. Der Dateiname wird zu ZIPList() weitergereicht, und die Daten werden dann sortiert ausgegeben:

Listing 12.29 ZIPListDemo

class ZIPListDemo
{
  public static void main( String args[] ) throws IOException
  {
    String fileName = null;
    if ( args.length != 1 )
      fileName = args[0];
    File file = new File( fileName );
    if ( !file.isFile() ) {
      System.out.println( "Error: file \"" + fileName +
                          "\" not found." );
      System.exit(1);
    }
    if ( !file.canRead() ) {
      System.out.println("Error: file \"" + fileName +
                         "\" cannot be read.");
      System.exit(1);
    }
    ZIPList l = new ZIPList( file );
    l.sort();
    String s[] = l.getFileList();
    for ( int i = 0; i < s.length; i++ )
      System.out.println( s[i] );
  }
}

Ein ganzes Archiv Datei für Datei entpacken

Auch ein Programm zum Entpacken des gesamten Zip-Archivs ist nicht weiter schwierig. Wir müssen nur mit einer Enumeration durch das Archiv laufen und dann für jeden Eintrag eine Datei erzeugen. Dazu nutzen wir eine modifizierte Version von getEntry() aus dem vorigen Abschnitt. Die Methode saveEntry(ZipFile, ZipEntry) muss, wenn sie alle Dateien ordnungsgemäß auspacken soll, erkennen, ob es sich bei der Datei um ein Verzeichnis handelt oder nicht. Dazu verwenden wir die Funktion isDirectory() des ZipEntry-Objekts. Denn diese Funktion versichert uns, dass es sich um ein Verzeichnis handelt und wir daher einen Ordner mittels mkdirs() anlegen müssen und keine Datei. Wenn es allerdings eine Datei ist, so verhält sich saveEntry() wie getEntry().

Listing 12.30 UnZip.java

import java.util.zip.*;
import java.io.*;
import java.util.*;
public class UnZip
{
  public static final int EOF = -1;
  public static void main( String args[] )
  {
    if ( args.length != 1 )
      System.out.println( "Usage:java UnZip zipfile" );
    else
    {
      try
      {
        ZipFile zf = new ZipFile( args[0] );
        
        for ( Enumeration enum = zf.entries(); enum.hasMoreElements(); )
        {
          ZipEntry target = (ZipEntry) enum.nextElement();
          System.out.print( target.getName() + " ." );
          saveEntry( zf, target );
          System.out.println( ". unpacked" );
        }
      }
      catch( FileNotFoundException e ) {
        System.out.println( "zipfile not found" );
      }
      catch( ZipException e ) {
        System.out.println( "zip error..." );
      }
      catch( IOException e ) {
        System.out.println( "IO error..." );
      }
    }
  }
  
  public static void saveEntry( ZipFile zf, ZipEntry target )
                                throws ZipException,IOException
  {
    File file = new File( target.getName() );
    if ( target.isDirectory() )
      file.mkdirs();
    else
    {
      InputStream is = zf.getInputStream( target );
      BufferedInputStream bis = new BufferedInputStream( is );
      File dir = new File( file.getParent() );
      dir.mkdirs();
      FileOutputStream fos = new FileOutputStream( file );
      BufferedOutputStream bos = new BufferedOutputStream(fos);
      for ( int c; ( c = bis.read() ) != EOF; )  // oder schneller
        bos.write( (byte) c );
      bos.close();
      fos.close();
    }
  }
}

Kompressionsgrad einer Zip-Datei

Wird eine Datei über einen ZipOutputStream erzeugt, lässt sich die Kompressionsrate über die Methode setLevel(int) einstellen. Der Level ist eine Zahl zwischen 0 und 9. Die Kompression übernimmt ein Deflater-Objekt, welches im DeflaterOutputStream (die Oberklasse von ZipOutputStream) verwaltet wird. So ruft ZipOutputStream lediglich vom Deflater die Methode setLevel() auf.

¹ Interessanterweise wurde danach der LZW-Algorithmus von der Sperry Company patentiert - dies zeigt eigentlich, wie unsinnig das Patentrecht in den USA ist.

² Gibt es sogar für den C=64:>http://www.cs.tut.fi/~albert/Dev/gunzip/.