für seine maßgebenden Beiträge zur Informations- und Codierungstheorie, insbesondere für die Arbeiten zu einer Informationstheorie für individuelle Datenfolgen, die zur Konstruktion des universellen, verlustlosen Lempel-Ziv-Datenkompressionsalgorithmus führten.

Beiträge zur Informations- und Codierungstheorie

Professor Jacob Ziv vom TECHNION Haifa, Israel, erhält den Eduard-Rhein-Preis für mehrere grundlegende und jede für sich richtungsweisende Arbeiten zur Theorie der Informationstechnik. Da Begriffe wie verkettete Kanalcodierung, die Ziv-Zakai-Grenze der Schätztheorie oder Maße für die Komplexität von Symbolketten recht spröde sind, soll hier beispielhaft versucht werden, ein heute von jedem Internetbenutzer angewendetes Textcodierverfahren von Ziv näher zu beleuchten.

Nehmen Sie an, sie geben einen Text in Ihren PC ein, um ihn zu verarbeiten, zu speichern oder über das Internet zu versenden. Dann wird er zunächst in eine Folge von Nullen und Einsen, den Bits, umgeformt. Die Speicherung und Übertragung des Textes wird um so schneller und billiger, mit je weniger Bits dieses Codierverfahren auskommt. Schon Samuel Morse hatte dies erkannt und dazu den häufig vorkommenden Buchstaben des Alphabets besonders kurze Morsezeichen zugeordnet. Eine solche Sparaktion, die man Datenkompression nennt, wird noch viel wirksamer, wenn man die Häufigkeit längerer Buchstabenfolgen berücksichtigt. Sicher ist in normalen deutschen Texten die Buchstabenfolge die viel häufiger als etwa the, also kann man die Bits entsprechend sparsamer zuordnen. Claude E. Shannon hat I 948 in seiner Informationstheorie (Eduard-Rhein-Preis 1991 ) gezeigt, daß für eine solche Datenkompression, wenn sie fehlerfrei sein soll, eine kleinste Bitzahl pro Buchstabe existiert. Diese „Entropie“ läßt sich aber mit der skizzierten Methode nur unter großem Aufwand annähern. Eine solche Codierung ist weiter stark von der Art, also insbesondere der Sprache des Textes abhängig, wie das Beispiel die und the zeigt.

Ein von Jacob Ziv (Idee und theoretische Grundlagen) und Abraham Lempel (Programmstruktur) angegebenes Codierverfahren löst dieses Problem auf sehr elegante Weise: Es werden neue Textteile so codiert, daß dazu möglichst lange, bereits vorher codierte Abschnitte in einem fortlaufend aktualisierten Speicher gesucht und als öpfe neuer Codewörter benutzt werden, Beispiel: dies. Ein solches Codierverfahren ist universell, also von der Art und der Sprache des Textes unabhängig, und es nähert sich, wie Ziv in den 70er Jahren zeigen konnte, bei gleichförmigen Texten überraschend schnell dem idealen Ziel, nämlich der durch die „Entropie“ gegebenen Grenze einer fehlerfreien Datenkompression minimaler Bitzahl. Schließlich läßt sich der ursprüngliche Text auch wieder auf ebenso einfache Weise zurückgewinnen.

Fachleute werten dieses Codierverfahren als den wichtigsten Schritt in der bisherigen Entwicklung der Textcodierung.