DE3485824T2

DE3485824T2 - Verfahren zur datenkompression.

Info

Publication number: DE3485824T2
Application number: DE19843485824
Authority: DE
Inventors: Victor Saul Miller; Mark N Wegman
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1983-06-01
Filing date: 1984-05-16
Publication date: 1993-03-04
Anticipated expiration: 2004-05-17
Also published as: EP0127815A3; DE3485824D1; EP0127815A2; JPS59231683A; JPS6356726B2; EP0127815B1; HK7895A

Description

Hintergrund der Erfindung

1. Gebiet der Erfindung

Die Erfindung betrifft ein Verfahren zur Datenkompression und hierbei insbesondere ein Verfahren zur Kompression von Daten zwecks Übertragung und Speicherung.

2. Beschreibung des Standes der Technik

Im Stand der Technik gibt es viele Verfahren zur Datenkompression. Im folgenden sind den Stand der Technik repräsentierende Verfahren aufgezeigt.
Ein Artikel mit dem Titel "Compression of Individual Sequences via Variable Rate Coding" von Ziv und Lempel, der in der IEEE Transactions on Information Theorie IT-24, Seiten 530-536 veröffentlicht wurde, offenbart einen Basisalgorithmus, der durch die gegenwärtige Erfindung verbessert wurde. Die Struktur, die Wirkungsweise, die Vorteile und die Nachteile des Lempel-Ziv Verfahrens werden ausführlicher in der Beschreibung einer bevorzugten, erfindungsgemäßen Ausführungsform diskutiert. Die hierin offenbarte und beanspruchte Erfindung wird durch den oben diskutierten Stand der Technik weder gelehrt noch nahegelegt.

Zusammenfassung der Erfindung

Daher liegt der Erfindung die Aufgabe zugrunde, Daten zur Speicherung oder Übertragung durch ein Verfahren zu komprimieren, welches eine Zeichenerweiterungs-Verbesserung, eine Zeichenfolge-Erweiterungs-Verbesserung und eine LRU-Algorithmus-Verbesserung enthält, um die Speichereffektivität zu vergrößern, um die Übertragungseffektivität zu vergrößern und um die Leitungsgebühren in Datenfernübertragungssystemen zu reduzieren.
Eine andere Aufgabe der Erfindung ist es, Daten zur Speicherung oder zur Übertragung durch ein Verfahren zu komprimieren, welches die folgenden Schritte enthält: Initialisierung einer Gruppe von Zeichenfolgen bestehend aus n-Folgen; Bestimmung einer längsten Zeichenfolge S aus dem Satz, welche mit einer gegenwärtigen Zeichenfolge übereinstimmt; Erzeugung einer Identifizierung I für S; Übertragung von I zu einer Benutzungseinrichtung; überprüfen des Wörterbuches auf leere Schlitze; Löschung einer LRU-Zeichenfolge (am längsten nicht benutzt) in dem Wörterbuch, um einen leeren Schlitz zu erzeugen, falls kein leerer Schlitz gefunden wird; Zuordnung eines Schlitz-Identifizierers j zu dem leeren Schlitz, der durch die obigen Schritte der Überprüfung und Löschung gefunden oder geschaffen wurde; Hinzufügung einer neuen Zeichenfolge S' zu dem Satz, wobei S' eine Verknüpfung einer vorhergehenden angepaßten Zeichenfolge und der gegenwärtigen angepaßten Zeichenfolge enthält; Zuweisung eines Identifizieres k zur Zeichenfolge S'; Voranschiebung der Eingabeposition zu einem nächsten Zeichen in dem Strom; Ausgabe eines Identifizieres m, um eine Übereinstimmung anzuzeigen; und Wiederholung der obigen Schritte für eine nächste Zeichenfolge.
Es ist eine weitere Aufgabe der gegenwärtigen Erfindung, die Datenübertragung zwischen einem Hauptrechner und einem oder mehreren fernen Datenstationen durch das oben beschriebene Verfahren zu steuern.
Somit enthält ein erfindungsgemäßes Datenkompressions-Verfahren und ein erfindungsgemäßes Datenfernübertragungs-Steuerungsverfahren für Datenstationen die folgenden Schritte: Initialisierung eines Satzes von Zeichenfolgen bestehend aus n-Folgen; Bestimmung einer längsten Zeichenfolge S aus dem Satz, welche mit einer gegenwärtigen Zeichenfolge übereinstimmt; Erzeugung eines Identifizieres I für S; Übertragung I zu einer Benutzungseinrichtung; Überprüfung des Wörterbuches auf einen leeren Schlitz; Löschung einer LRU-Zeichenfolge (am längsten nicht benutzt) aus dem Wörterbuch, um einen leeren Schlitz zu schaffen, falls kein leerer Schlitz gefunden wurde; Zuordnung eines Schlitz-Identifizieres j zu dem leeren Schlitz, der durch die obigen Schritte der Überprüfung und Löschung gefunden oder geschaffen wurde; Hinzufügung einer neuen Zeichenfolge S' zu dem Satz, wobei S' eine Verknüpfung einer vorhergehenden angepaßten Zeichenfolge und der gegenwärtigen angepaßten Zeichenfolge enthält; Zuordnung eines Identifizieres k zur Zeichenfolge S'; Voranschiebung der Eingabeposition zu einem nächsten Zeichen in dem Strom; Ausgabe eines Identifizierers m, um eine Übereinstimmung anzuzeigen; und Wiederholung der obigen Schritte für eine nächste Zeichenfolge.
Diese und andere Aufgaben, Merkmale und Vorteile der Erfindung werden durch die detaillierte Beschreibung einer bevorzugten, erf indungsgemäßen Ausführungsform sichtbar, wie sie in der anhängenden Zeichnung dargestellt ist.

Kurze Beschreibung der Zeichnung

Fig. 1 ist ein Flußdiagramm eines Verfahrens zur Datenkompression gemäß dem Stand der Technik.
Fig. 2 ist ein Flußdiagramm eines erfindungsgemäßen Datenkompressionsverfahrens mit allen seinen Komponenten.
Fig. 3 ist ein Flußdiagramm einer ersten Komponente eines erfindungsgemäßen Datenkompressionsverfahrens.
Fig. 4 ist ein Flußdiagramm einer zweiten Komponente eines erfindungsgemäßen Datenkompressionsverfahrens.
Fig. 5 ist ein Flußdiagramm einer dritten Komponente eines erfindungsgemäßen Datenkompressionsverfahrens.
In der Zeichnung sind vergleichbare Elemente mit ähnlichen Bezugszeichen versehen und identische Elemente in verschiedenen Ausführungsformen sind mit identischen Bezugszeichen versehen.

Beschreibung einer bevorzugten, erfindungsgemäßen Ausführungsform

Das bekannte Kompressionsverfahren nach Lempel und Ziv

Lempel und Ziv (LZ) schlagen zwei verwandte Verfahren zur Datenkompression vor, welche im Gegensatz zu den eher traditionellen auf Wahrscheinlichkeit basierenden Lösungswegen, auf der Theorie der komplexen Algorithmen basiert. Das zweite, einfachere Verfahren kann jederzeit und effektiv implementiert werden und erzeugt eine zufriedenstellende Kompression bei den meisten Daten. Jedoch hat dieses Verfahren einige Mängel, die durch die gegenwärtige Erfindung behoben werden. In der folgenden Diskussion wird der Ausdruck "Verschlüsseler" für das Kompressionsprogramm verwendet und der Ausdruck "Entschlüsseler" wird für die inverse Vorgehensweise verwendet. Der LZ-Algorithmus ist in Fig. 1 gezeigt.
Der Algorithmus ist lernfähig. Somit kann er für eine Vielzahl von unterschiedlichen Dateitypen eingesetzt werden und weist dennoch eine akzeptable Leistung auf.
Es kann als ein allgemeines Modell für die Kompression eingesetzt werden. Beide, der Verschlüsseler und der Entschlüsseler, enthalten ein Wörterbuch von Zeichenfolgen, und an jedem Punkt wechseln diese Wörterbücher in Sperrschritte, so daß keine Bits zur Übertragung des Wörterbuches benötigt werden. Dies ist möglich, weil die Zeichenfolgen nur zu dem Wörterbuch addiert werden, nachdem der Entschlüsseler sie gesehen haben würde und es verwendet die exakt gleiche Strategie für das Hinzufügen zum Wörterbuch wie der Verschlüsseler.
LZ registriert wahrscheinliche Ereignisse und verschwendet keinen Platz mit Informationen über unwahrscheinliche Ereignisse. Wenn man einen Huffmann-Code haben möchte, um alle Zeichenpaare zu komprimieren, dann würde man 64k Informationsteile benötigen. Und man würde lediglich Informationen über die Diagrammfrequenz haben (Ein n-Gram ist eine Zeichenfolge von n Zeichen). Wenn ein 100-Gram gegeben ist, was sehr viel üblicher als ein einzelner Buchstabe ist, dann wird das System mit dem obigen Verfahren das 100-Gram zuerst "lernen".
Es kann sehr wohl wichtiger sein, die Information zu speichern, daß Zeichenfolgen von 80 Leerstellen (Zeilen) bei einigen gegebenen Frequenzen öfter auftreten als der Buchstabe "z". Zeilen von Leerstellen werden wichtiger sein als der Buchstabe "z", wenn sie häufiger auftreten und genau das ist Fall, wenn LZ Informationen über sie speichert.
Das es eine gute Repräsentation für das Wörterbuch gibt, ist ein weiteres Merkmal. Es ist möglich, eine feste Anzahl von Bits für jede Wörterbucheintragung zu halten, unabhängig davon, wie lang die Zeichenfolge der durch die Wörterbucheintragung repräsentierten Zeichen ist.
Das erste Problem mit dem obigen Verfahren ist, daß ein Teil der Ausgabe aus unverdichteten Symbolen der Eingabe besteht. Während dieses asymptotisch nur geringe Auswirkungen hat, ist es von überragender Bedeutung für praktische Daten. Wenn z. B. eine Datei durch den obigen Algorithmus in 20.000 Folgen aufgeteilt ist, dann wird mehr als ein Drittel der Ausgabe aus unverdichteten Zeichen bestehen.

Die Erfindung

Die hier vorgeschlagene Lösung vermeidet die Übertragung jeglicher unverdichteter Daten. Die gesamte Ausgabe besteht aus einer Folge von Identifizierungsnummern. Die Erfindung wird mit Bezug auf die Fig. 2, 3, 4 und 5 beschrieben.
Zunächst wird das erfindungsgemäße Verfahren mit Bezug auf Fig. 2 beschrieben.
Anstatt einer Initialisierung des Wörterbuches mit einer leeren Zeichenfolge initialisiert der erste, erfindungsgemäße Schritt das Wörterbuch für alle Zeichenfolge der Länge 1. Daher wird eine Übereinstimmung immer gefunden. Das Wörterbuch muß durch Hinzufügung der mit dem ersten Zeichen der nachfolgenden, übereinstimmenden Zeichenfolge verknüpften Zeichenfolge S vergrößert werden. Diese neue Zeichenfolge wird hinzugefügt, nachdem die nächste Übereinstimmung gefunden wurde.
Weil das erste Zeichen einer Zeichenfolge immer bekannt ist, wird in Schritt 2 als nächstes die längste Zeichenfolge S in dem Wörterbuch gefunden, welche mit der aktuellen Zeichenfolge im Datenfluß hinter den Cursor übereinstimmt.
Eine weitere Annahme, die von Lempel und Ziv gemacht wurde, ist daß das Wörterbuch bis auf eine unbegrenzte Größe wachsen kann. Dies ist eindeutig nicht praktikabel. Das von Lempel und Ziv vorgeschlagene Verfahren sieht vor, die Eingabe in derart kleine Blöcke zu unterteilen, daß ihre Wörterbücher gerade eben den verfügbaren Raum auffüllen, um dann jeden Block einzeln zu komprimieren.
Es ist jedoch vorteilhafter, die einzelnen Zeichenfolgen in dem Wörterbuch zu ersetzen. Schritt 3 des erfindungsgemäßen Verfahrens sortiert die Zeichenfolgen aus, welche in irgendeiner Weise am längsten nicht benutzt wurden (vgl. Fig. 4). Eine Zeichenfolge wird definiert als "benutzt", wenn sie angepaßt wurde oder wenn sie ein Vorsatzcode einer Übereinstimmung ist. Die andere Definition weist jeder Zeichenfolge in dem Wörterbuch eine Bezugszahl zu. Die Bezugszahl einer Zeichenfolge S ist die Anzahl der Zeichenfolgen eines Wörterverzeichnisses, welche die Form S//T oder T?/S haben, für einige T (S//S wird zweimal gezählt). Unter den Zeichenfolgen mit der Bezugszahl 0 ist diejenige, deren Bezugszahl am längsten 0 gewesen ist die "am längsten nicht benutzte".
In gewisser Weise sollte das Wörterbuch mit den natürlichen Einheiten der zu komprimierenden Datei gefüllt werden. In Englisch bedeutet dieses, daß die meisten Eintragungen in das Wörterbuch Wörter oder gar Sätze sein würden. Jedoch muß das Verfahren zur Bildung größerer Einheiten Übergänge durchlaufen, welche keine Einheiten sind. So kann es vorkommen, daß eine Einheit sich aus einem Wort plus der ersten Hälfte eines anderen Wortes zusammensetzt. Es ist weniger wahrscheinlich, den letzten Teil eines Wortes in dem Wörterbuch zu haben, als das gesamte Wort selbst. Darüber hinaus können in dem Wörterbuch gespeicherte Teile von Wörtern dieses größer machen als es sein sollte. Wenn z. B. Dreiviertel des Wörterbuches Zeichenfolgen aufweist, welche niemals oder selten benutzt werden, dann werden zwei zusätzliche Bits bei der Übertragung von jedem Bit verwendet, damit auf diese nutzlosen Eintragungen Bezug genommen werden kann. Außerdem dauert es eine lange Zeit, um lange Zeichenfolgen anzupassen. Alle diese Probleme können durch Hinzufügung von Eintragungen in das Wörterbuch eliminiert oder verbessert werden, welche eine Verknüpfung von zwei Übereinstimmungen sind, anstelle der Verknüpfung der ersten Übereinstimmung mit dem ersten Zeichen der zweiten Übereinstimmung.
Durch die Kombination der drei Konstanten wird ein leistungsfähiger Verschlüsseler geschaffen, dessen Ausführungsform als nächstes diskutiert wird.
Die wesentlichen Schwierigkeiten bei der Erzielung einer praktikablen Implementierung sind das Auffinden einer guten Datenstruktur für das Wörterbuch der Zeichenfolgen. Diese Struktur sollte klein sein, um ein schnelles Suchen zu ermöglichen.
Als erstes wird eine Datenstruktur beschrieben, welche für alle Verschlüsselungen ausreichend ist und den zuletzt präsentierten Schlüssel speichert. Die Größe all dieser Strukturen ist proportional zur Anzahl der Zeichenfolgen in dem Wörterbuch und ist nicht abhängig von der Größe der Zeichenfolgen.
In den ersten Verschlüsselungen sind alle Zeichenfolgen S des Wörterbuches entweder ein Zeichen länger als ein Vorsatzcode P von S, wobei P in dem Wörterbuch ist oder S ein Zeichen lang ist. Dabei ähnelt das Wörterbuch einem Baum. Die Wurzel des Baumes ist eine leere Zeichenfolge. Jeder Knotenpunkt (außer für die Wurzel) ist das Kind des Knotens, der die Zeichenfolge repräsentiert, wobei der Knoten nach dem zuletzt weggelassenen Symbol benannt wird. In dem Verschlüsselungsalgorithmus wird durch Erkennung eines Vorsatzcodes und anschließendes Herausfinden, ob er ein Kind hat, welches mit dem nächsten Zeichen übereinstimmt, die Erkennung erreicht. Sei n ein Knoten mit Eltern P, und C sei das letzte Zeichen einer mit n korrespondierenden Zeichenfolge (das Zeichen, welches nicht in der zu P korrespondierenden Zeichenfolge ist). Eine Hash-Tabelle kann durch eine von einer Vielzahl von Hash-Funktionen implementiert und durch das Paar (P, C) indexiert werden, wobei n zurückgegeben wird, wenn es solch ein Kind gibt. Derartige Hash-Tabellen sind aus "Universal Classes of Hash-Functions" von J. Lawrence Carter und Mark N. Wegmann, Journal of Computer and System Sciences Band 18, Nr. 2, April 1979, Seiten 143-154, bekannt. Hash-Techniken sind dem Durchschnittsfachmann gut bekannt und müssen somit hierin nicht näher beschrieben werden. Bei einem gegebenen Knoten kann man schnell feststellen, ob es eine längere Übereinstimmung gibt. Der Entschlüsselungsalgorithmus arbeitet ähnlich, jedoch reicht anstelle einer Hash-Tabelle ein einfacher Zeiger von n auf P aus.
Die am längsten nicht benutzte Verschlüsselung birgt kleine Probleme. Das einzige erwähnenswerte ist, daß in dem Wörterbuch keine Löcher gelassen werden können. Somit kann die Zeichenfolge "abc" nicht in dem Wörterbuch verbleiben, wenn die Zeichenfolge "ab" herausgeworfen worden ist. Die einfachste Strategie ist es, nur Zeichenfolgen auf der LRU (am längsten nicht benutzt) Liste zu plazieren, wenn es Blätter von dem Baum gibt. Somit wird eine neue Zeichenfolge oder eine Zeichenfolge, deren Kinder gelöscht worden sind, ein Löschungskandidat.
Das Verfahren zur Verknüpfung von Zeichenfolgen ist komplizierter. Zwei Datenstrukturen müssen erhalten bleiben. Eine Struktur wird der Entscheidungsbaum genannt und wird zum schnellen Auffinden von Übereinstimmungskandidaten verwendet. Diese Struktur ähnelt dem obigen Wörterbuch und ist vergleichbar mit einem Vorsatzcodebaum. Die andere Datenstruktur wird das Waldpaar genannt und erlaubt es, jemand zwischen den Kandidaten zu wählen. Das Waldpaar stellt knapp alle Zeichenfolgen dar. Ein Knoten ist entweder ein Zeichen oder zwei Zeiger zu anderen Knoten. Somit kann die Verknüpfung von zwei Zeichenfolgen in dem Wörterbuch durch einen Knoten dargestellt werden, welcher auf beide zeigt. Alle Knoten in dem Wald sind in einem Feld angeordnet, dessen I-Element auf die I-te Zeichenfolge in dem Wörterbuch zeigt.
Der Entscheidungsbaum hat die Eigenschaft, daß die Eltern P eines Knoten n mit einem durch n dargestellten Vorsatzcode einer Zeichenfolge korrespondiert. Dieser Vorsatzcode kann jedoch mehr als ein Zeichen kleiner sein. Darüberhinaus müssen nicht alle Knoten in dem Baum notwendigerweise einer Zeichenfolge in dem Wörterbuch entsprechen; sie können auch Vorsatzcodes von Zeichenfolgen in dem Wörterbuch sein.
Alle Zeichenfolgen in dem Wörterbuch, die keine Vorsatzcodes anderer Zeichenfolgen in dem Wörterbuch sind, entsprechen Blättern des Entscheidungsbaumes. Alle anderen Zeichenfolgen des Wörterbuches sind als interne Knoten ebenfalls in dem Baum angeordnet. Wenn S der Vorsatzcode von zwei oder mehreren Zeichenfolgen des Wörterbuches ist, S: sub./1/und S: sub./2/, und S die längste dieser Zeichenfolgen ist, dann ist ein mit S korrespondierender Knoten H in dem Baum, selbst wenn S nicht in dem Wörterbuch ist. Wenn wir S nicht effizient speichern können, dann speichern wir mit n einen Zeiger zu entweder S: sub./1/ oder S: sub./2/ in dem Waldpaar. Mit dieser Information ist es möglich, S wieder zu erzeugen.
Mit jedem Knoten ist die Länge der Zeichenfolge gespeichert, die mit ihr übereinstimmt. Eine oben beschriebene Hash-Tabelle erlaubt es uns, das geeignete Kind von den Eltern zu finden. Wenn wir also versuchen, eine Zeichenfolge zuzuordnen, die ein Blatt in dem Baum ist, dann beginne bei der Wurzel und suche das erste Zeichen um den nächsten Knoten zu finden. Von diesem Knoten finde die Länge der Zeichenfolge mit der er übereinstimmt und das Zeichen jenseits von ihm. Suche den Knoten und dieses Zeichen, um den nächsten Knoten zu erhalten. Dieser Prozeß wird wiederholt, um eine Kandidaten-Übereinstimmung zu finden. Ein Problem taucht auf, wenn die Kandidaten-Übereinstimmung nicht mit dem Text eines Zeichens übereinstimmt, welches nicht in dem Hash-Prozeß verwendet wurde.
An dieser Stelle muß die echte Übereinstimmung in dem Wörterbuch entweder die durch den Entscheidungsbaum gefundene Zeichenfolge oder ein Vorsatzcode davon sein. Das Waldpaar wird verwendet um den längsten Vorsatzcode der Kandidaten-Übereinstimmung zu finden, welcher mit dem zu komprimierenden Text übereinstimmt. Während dieser Prozedur wird der Entscheidungsbaum abgesucht um die längste Zeichenfolge des Wörterbuches zu finden, welche diesem Vorsatzcode entspricht. Diese Zeichenfolge ist die korrekte Übereinstimmung.
Es sollte noch darauf hingewiesen werden, daß in dem Zeichenfolgen-Erweiterungs-Algorithmus die Möglichkeit aufkommt, daß beim Hinzufügen einer Zeichenfolge zu dem Entscheidungsbaum diese dort bereits vorhanden ist. In diesem Falle sollte der Entscheidungsbaum nicht verändert werden.
Das hierin vorgeschlagene Verfahren kann auch dazu verwendet werden, um eine Wahrscheinlichkeitsverteilung für das nächste Zeichen in einer Zeichenfolge von Zeichen (oder Bit in einer Zeichenfolge von Bits) zu erzeugen. Dies kann für Anwendungen zur Erkennung von Daten hilfreich sein. Z.B. können optische Abtastgeräte feststellen, daß ein bestimmtes Zeichen entweder ein "n" oder "h" ist, jedoch haben sie Schwierigkeiten, zwischen diesen Zeichen zu unterscheiden. Wenn in solch einem Falle die Wahrscheinlichkeit, daß ein "h" der gegenwärtigen Zeichenfolge von Zeichen folgt, sehr gering ist, dann kann das Abtastgerät entscheiden, daß das nächste Zeichen ein "n" ist. Ein weiteres Beispiel ist die Erkennung von Phonemen oder Wörtern in der Spracherkennung.
Eine Vielzahl von Autoren hat gezeigt, daß jedwedes Kompressionsverfahren für eine Vorhersage benutzt werden kann. Siehe beispielsweise Thomas M. Cover "Universial Gambling Schemes and the Complexity Measures of Kolmogorov and Chaitin" in Technical Report Nr. 12, 14. Oktober 1974, Dept. of Statistics, Stanford University.

Claims

1. Verfahren zum Komprimieren von Daten in einzelnen Folgen in einem Datenstrom, welches die folgenden Schritte umfaßt:

Initialisieren eines Wörterbuchs, das aus einem Satz von Ketten mit einem Index für jede der Ketten besteht und alle möglichen Ketten mit einer Länge 1 enthält,

Setzen einer aktuellen Eingabeposition an dem Anfang des Datenstroms und Wiederholen der folgenden Schritte solange, bis der Datenstrom ausgeschöpft ist, der komprimiert werden soll,

Bestimmen einer längsten Kette S in dem Wörterbuch, die zu einer aktuellen Kette in dem Datenstrom beginnend von der aktuellen Eingabeposition paßt,

Erzeugen einer Identifizierung I für S, die aus einer Codierung des Index besteht, welcher der längsten angepaßten Kette S zugeordnet ist,

Voranschieben der aktuellen Eingabeposition unmittelbar nach der aktuellen Kette in dem Datenstrom,

Ändern des Wörterbuchs auf der Grundlage der vorangehenden längsten angepaßten Kette S, der unmittelbar nachfolgenden Symbole in der nächsten Kette in dem Datenstrom und der Folge vorangehend angepaßter Ketten,

Übertragen von I zu einer Benutzungseinrichtung und

Decodieren von I bei der Benutzungseinrichtung, um die Kette S wiederherzustellen.

2. Verfahren nach Anspruch 1, bei welchem der Schritt des Änderns die folgenden Schritte umfaßt:

Hinzufügen einer neuen Kette S' zu dem Satz, wo S' eine Verkettung der aktuellen Kettenanpassung und eines unmittelbar nachfolgenden Symbols in dem Datenstrom enthält und

eine Identifizierung I' wird der Kette S' zugewiesen.

3. Verfahren nach Anspruch 2, das ferner den folgenden Schritt umfaßt:

Prüfen eines Wörterbuchs mit fester Speichergröße, welches den Satz von Ketten für einen leeren Schlitz zum Speichern der neuen Kette S' enthält und, falls ein leerer Schlitz nicht gefunden wird, Löschen einer Kette in dem Wörterbuch, um einen leeren Schlitz zu erzeugen.

4. Verfahren nach Anspruch 3, bei welchem der Schritt das Löschen einer LRU-Kette in dem Wörterbuch umfaßt, um einen leeren Schlitz zu erzeugen, falls kein leerer Schlitz gefunden wird.

5. Einrichtung zum Komprimieren von Daten in einzelnen in einem Datenstrom gruppierten Folgen, die folgendes aufweist:

Mittel zum Initialisieren eines Wörterbuchs, das aus einem Satz von Ketten mit einem Index für jede der Ketten besteht und alle möglichen Ketten mit einer Länge 1 enthält,

Mittel zum Setzen einer aktuellen Eingabeposition an den Anfang des Datenstroms,

Mittel zum Bestimmen einer längsten Kette S in dem Wörterbuch, die zu einer aktuellen Kette in dem Datenstrom beginnend von der aktuellen Eingabeposition paßt,

Mittel zum Erzeugen einer Identifizierung I für S, die aus einer Codierung des Index besteht, welcher der längsten angepaßten Kette S zugeordnet ist,

Mittel zum Voranschieben der aktuellen Eingabeposition unmittelbar nach der aktuellen Kette in dem Datenstrom,

ein Mittel zum Ändern des Wörterbuchs auf der Grundlage der vorangehenden längsten angepaßten Kette S, der unmittelbar nachfolgenden Symbole in der nächsten Kette in dem Datenstrom und der folgenden vorangehend angepaßter Ketten,

Mittel zum Übertragen von I zu einer Benutzungseinrichtung und

Mittel zum Decodieren von I bei der Benutzungseinrichtung, um die Kette S wiederherzustellen und

Mittel zum Wiederholen der Schritte des Initialisierens, des Setzens einer aktuellen Eingabeposition, des Bestimmens, Erzeugens, Voranschiebens, Änderns, Übertragens und Decodierens solange, bis der Datenstrom ausgeschöpft ist, der komprimiert werden soll.

6. Einrichtung nach Anspruch 5, bei welcher das Mittel zum Ändern folgendes aufweist:

Mittel zum Hinzufügen einer neuen kette S' zu dem Satz, wo S' eine Verkettung der aktuellen Kettenanpassung und eines unmittelbar nachfolgenden Symbols in dem Datenstrom enthält und

Mittel, um der Kette S' eine Identifizierung I' zuzuweisen.

7. Einrichtung nach Anspruch 6, die ferner folgendes aufweist:

Speicherung eines Wörterbuchs fester Größe, welches den Satz von Ketten enthält,

Mittel zum Prüfen des Wörterbuchs auf einen leeren Schlitz hin, um die neue Kette S' zu speichern und

ein Mittel zum Löschen einer Kette in dem Wörterbuch, um eine solche zu erzeugen, falls ein leerer Schlitz nicht gefunden wird.

8. Einrichtung nach Anspruch 7, bei welcher das Mittel zum Löschen einer Kette Mittel zum Löschen einer LRU-Kette in dem Wörterbuch zum Erzeugen eines leeren Schlitzes aufweist, falls kein leerer Schlitz gefunden wird.