DE68927331T2 - Suchbaumdatenstrukturkodierung für Kettensubstitutionsdatenverdichtungssysteme - Google Patents

Suchbaumdatenstrukturkodierung für Kettensubstitutionsdatenverdichtungssysteme

Info

Publication number
DE68927331T2
DE68927331T2 DE1989627331 DE68927331T DE68927331T2 DE 68927331 T2 DE68927331 T2 DE 68927331T2 DE 1989627331 DE1989627331 DE 1989627331 DE 68927331 T DE68927331 T DE 68927331T DE 68927331 T2 DE68927331 T2 DE 68927331T2
Authority
DE
Germany
Prior art keywords
symbol
tree
symbols
copy
length
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
DE1989627331
Other languages
English (en)
Other versions
DE68927331D1 (de
Inventor
Edward R Fiala
Daniel H Greene
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Xerox Corp
Original Assignee
Xerox Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Xerox Corp filed Critical Xerox Corp
Application granted granted Critical
Publication of DE68927331D1 publication Critical patent/DE68927331D1/de
Publication of DE68927331T2 publication Critical patent/DE68927331T2/de
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00—Image coding
    • G06T9/40—Tree coding, e.g. quadtree, octree

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Multimedia (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Description

  • Diese Erfindung bezieht sich auf digitale Datenkompressionssysteme und insbesondere auf adaptive und invertierbare oder verlustlose digitale Datenkompressionssysteme.
  • Es wird Bezug auf unsere parallel angemeldete EP-Patentanmeldung 0 340 041 mit dem Titel "Start, Step, Stop Unary Coding for Data Compression" genommen. Eine gemeinsame, detaillierte Beschreibung ist verwendet worden, da die Erfindungen, die durch die unterschiedlichen Anmeldungen abgedeckt werden, in verschiedenen Arten und Weisen kombiniert werden können.
  • Eine digitale Datenkompression ist ein wichtiges Werkzeug, da sie zum Beispiel dazu verwendet werden kann, die Speichererfordernisse für Files bzw. Dateien zu reduzieren, um die Rate zu erhöhen, unter der Daten über in der Bandbreite begrenzte Kommunikationskanäle übertragen werden können, und um die interne Redundanz von Daten vor deren Verschlüsselung zu reduzieren, um eine erhöhte Sicherheit zu schaffen.
  • Es existieren Datenkompressionssysteme für spezielle Zwecke und allgemeine Zwecke. Systeme für spezielle Zwecke sind oftmals zufriedenstellend, wenn sie dazu verwendet werden, Quellendaten zu komprimieren, für die sie optimiert worden sind. Allerdings werden Systeme für allgemeine Zwecke kundenorientiert ausgebaut, um die Quellendaten anzupassen, so daß sie gewöhnlich besser zum Komprimieren unbekannter oder diverser Quellendaten-Typen geeignet sind. Idealerweise sind diese Systeme für allgemeine Zwecke nicht in der Lage unmittelbar fundamentale Änderungen in der zusammensetzungsmäßigen Struktur der Quellendaten anzupassen, wie dies erforderlich sein kann um eine signifikante Kompression für kleine Files bzw. Dateien und für Quellen mit intern inkonsistenten statistischen Charakteristika zu liefern, sondern auch in der Lage sind eine nahezu optimale Kompression für große Files mit stabilen, statistischen Charaktertstika zu liefern. Designer haben verschiedene Versuche unternommen, um diese in Konkurrenz stehenden Design-Ziele zu erfüllen, allerdings sind die Ergebnisse der Bemühungen nicht vollständig zufriedenstellend. Die Kommunikations-Theorie von Shannon (C.E. Shannon, "A Mathematical Theory of Communication", The Bell System Technical Journal, Vol XXVII, No. 3,1948, Seiten 379-423, und No. 4,1948, Seiten 623-656), gibt an, daß die ideale Codierung eines vorgegebenen Quellensymbols Raum gleich zu - log&sub2; der Wahrscheinlichkeit, P, des Auftretens des Symbols verwendet. Wenn die Codierung dieses speicherlose Modell bestätigt, ist der durchschnittliche Raum. der benötigt wird, um irgendein Symbol darzustellen, die Entropie der Quelle:
  • wobei: x ein zufällig ausgewähltes Symbol von einer Quelle ist, das n einzigartige Symbole enthält; und
  • cl über alle möglichen Quellen-Symbole reicht.
  • D.A. Huffman schlägt in "A Method for the Construction of Minimum Redundancy Codes", Proceedings of the I.R.E., Vol 40, 1952, Seiten 1098-1110, eine Auflistung von variablen Längencoden auf die Quellen-Symbole gemäß der statistischen Frequenzverteilung der Symbole vor, um eine diskrete Annäherung einer solchen idealen Codierung zu liefern. Danach wurden arithmetische Codier-Techniken entwickelt, um weiterhin die Codierung durch eine arithmetische Modifizierung der letzten paar Bits in den zuvor codierten Symbolen zu optimieren, um dadurch die Verschwendung von fraktionalen Bits zu vermeiden. Siehe zum Beispiel R.C. Pasco, "Source Coding Algorithmus for Fast Data Compression", pH. D. Dissertation, Stanford University, 1976; G. G. Langdon, Jr. et al., "Compression of Black-White Images with Arithmetic Coding", IEEE Transactions on Communications, Com-29, No. 6, 1981, Seiten 858-867; G. G. Langdon, Jr. et al., "A Double Adaptive File Compression Algorithmus", IEEE Transactions on Communications Com-31, No. 11,1983, Seiten 1253-1255; und J. Rissanen et al., "Universal Modeling and Coding", IEEE Transactions on Information Theory, 11-27, No. 1, 1981, Seiten 12-23.
  • Aus einem praktischen Grund schlägt allerdings das Entropie-Modell der nullten Ordnung der Gleichung (1) fehl, einen signifikanten Teil der Redundanz vieler herkömmlicher Quellen zu erfassen. Zum Beispiel zeigt ein englischsprachiger Text normalerweise einen wesentlichen Abfall in der Entropie der ersten Ordnung:
  • wobei: xy ein zufällig ausgewähltes Paar benachbarter Quellenzeichen ist.
  • Demzufolge haben verschiedene der vorstehend angegebenen Referenzen Huffman und arithmetische Codiertechniken durch Begründen der Codierung auf Statistiken erweitert, die durch die Frequenz konditioniert werden, unter der irgendeinem vorgegebenen Symbol mindestens ein und gewöhnlich zwei oder mehr andere Symbole vorangegangen ist bzw. sind. Unglücklicherweise erfordert allerdings die erhöhte Kompression, die auf diese Art und Weise erreicht wird, charakteristisch im wesentlichen mehr Speicher und Verarbeitungszeit, um den Kompressionsprozeß auszuführen.
  • Andere haben sogenannte "textorientierte Substitutions-" Daten-Kompressionsprozesse zum Erfassen der Kohärenz höherer Ordnung eines Textes und ähnlicher Quellen-Daten vorgeschlagen, und zwar ohne eine Vorkonditionierung des Erfassungsmechanismus auf statistischen Wahrscheinlichkeiten. J. Ziv und A. Lempel schlugen ein algorithmisches Modell für einen textorientierten Substitutionsprozeß basierend auf der Notation vor, daß ein Wiederauftauchen eines Strings bzw. einer Zeichenfolge zuvor codierter Symbole durch Einleiten des Symbols unmittelbar einem solchen Wiederauftreten folgend (d.h. das Suffix-Zeichen der auftretenden Zeichenfolge) mit einem Kopie-Codewort dargestellt werden kann, das (1) auf ein Ende (z.B. das voranführende Ende) des früheren Auftretens der Zeichenfolge hinweist und (2) die Länge der wiederauftretenden Zeichenfolge identifiziert. Sie erkannten, daß ein solches Kopie-Codewort vollständig und komplett die wiederauftretende Symbol-Zeichenfolge definieren würde, so daß sie ein "Substituieren" des Codewortes für die Symbole der wiederauftretenden Symbol-Zeichenfolge ins Auge faßten, um eine komprimierte Darstellung davon zu lieferen. Siehe J. Ziv et al., "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, IT-23, No. 3, 1977, Seiten 337-343.
  • Bedauerlicherweise tendieren Kompressionssysteme, die auf dem Original Ziv-Lempel- Algorithmus begründet sind, dazu, nicht akzeptierbar langsam zu sein und haben keine besonders hohe Kompression erzielt. Um die Geschwindigkeit zu verbessern haben sie und andere Fachleute auf dem Gebiet verschiedene Alternativen entwickelt. Einige dieser Alternativen paßten künstlich steife Parsing-Mechanismen an, um die Erzeugung der Kopie-Codeworte zu vereinfachen und die Größe der Datenstrukturen zu begrenzen, die benötigt werden, um die Kompression auszuführen. Siehe zum Beispiel J. Ziv et al., supra; J. Ziv, "Coding Theorems for Individual Sequences", IEEE Transactions on Information Theory, IT-24, No. 4, 1978, Seiten 405-412; J. Ziv et al, "Compression of Individual Sequences Via Variable-Rate Coding", IEEE Transactions on Information Theory, IT-24, No. 5, 1978, Seiten 530-536; und W.L. Eastman et al., US-Patent 4,464,650, das am 7. August 1984 herausgegeben ist, "Apparatus and Method for Compressing Data Signals and Restoring the Compressed Data". Allerdings sind diese modifizierten Daten-Kompressions-Systeme im Stil von Ziv-Lempel nicht vollständig zufriedenstellend, da deren Leistung typischerweise gemessen durch die Geschwindigkeit, unter der sie sich anpassen, und/oder die Kompression, die sie liefern, enttäuschend ist.
  • Ein etwas unterschiedlicher Versuch, der zur Verwendung einer textorientierten Substitution für eine Daten-Kompression vorgeschlagen worden ist, basiert auf dem Aufbau adaptiver Listen oder Wörterbücher bzw. Terminologien individueller Symbole oder Symbol-Zeichen-Folgen. Siehe zum Beispiel V.S. Miller et al., "Variations on a Theme by Ziv and Lempel", IBM Research Report RC, 10630, #47798, 1984, Combinational Algorithms on Words, NATO, ASI Series F, Vol 12, 1985, Seiten 131-140; T. A. Welch, "A Technique for High Performance Data Compression", IEEE Computer, Vol 17, No 6, 1984, Seiten 8-19; und J. L. Bonkley, "A Locally Adaptive Data Compression Scheme", Communications of the ACM, Vol. 29, No. 4, 1984, Seiten 320-330. Allerdings sind diese Systeme langsam und führen zu einer niedrigen Kompression.
  • Als noch weiterer technischer Hintergrund in Bezug auf eine textorientierte Substitution einer digitalen Datenkompression wird zum Beispiel auf M. Rodeh et al., "Linear Algorithm for Data Compression Via String Matching", Journal of the Association for Computing Machinery, Vol 28, No. 1, 1981, Seiten 16-24; J. A. Storer, "Data Compression Via Textual Substitution", Journal of Association for Computing Machinery, Vol 29, No. 4, 1982, Seiten 928-951; G. Guoan et al., "Using String Matching to Compress Chinese Characters", Stanford Technical Report, STAN-CS-82-914, 1982; and G. G. Langdon Jr. "A Note on the Ziv-Lempel Mode tor Compressing Individual Sequences", IEEE Transactions on Information Iheory, IT-29, No. 2,1983, Seiten 284-287, verwiesen.
  • In Anbetracht der Nachteile des Stands der Technik wird ersichtlich werden, daß dennoch ein Erfordernis für adaptive und invertierbare (d.h. verlustlose) Datenkompressionssysteme für praktische, allgemeine Zwecke für eine zuverlässige und effiziente Komprimierung großer Quellen, die stabile statistische Charakteristika besitzen, ebenso wie für kostengünstige Quellen und Quellen, die variable, statistische Charakteristika besitzen, vorhanden ist. Textorientierte Substitutions-Techniken würden ebensogut für diese Aufgabe geeignet sein, allerdings werden verbesserte Verfahren und Einrichtungen zum Ausführen eines solchen Datenkompressionsprozesses in der Praxis benötigt, um vollständiger dessen Potential zu realisieren.
  • Die folgende Erfindung schafft ein textorientiertes Substitutions-Datenkompressionssystem gemäß den beigefügten Ansprüchen. Der Suchbaum, der durch den Kompressor des Systems konstruiert und beibehalten wird, liefert einen einzelnen Suchpfad für irgendeine gegebene Symbol-Zeichenfolge, so daß keine Redundanz beim Codieren der komprimierten Daten vorhanden ist.
  • Diese und andere Merkmale und Vorteile der vorliegenden Erfindung werden ersichtlich werden wenn die nachfolgende, detallierte Beschreibung in Verbindung mit den beigefügten Zeichnungen gelesen wird, in denen:
  • Figur 1 zeigt ein vereinfachtes Blockdiagramm eines Datenkompressionssystems;
  • Figur 2 zeigt ein Diagramm, das die Codierung eines Strings bzw. einer Zeichenfolge eines Abtasttextes gemäß einer Basisausführungsform der vorliegenden Erfindung darstellt;
  • Figur 3 zeigt ein detaillierteres Blockdiagramm eines Datenkompressors, der so aufgebaut ist, um die Codierung, die in Figur 2 dargestellt ist, durchzuführen;
  • Figur 4 zeigt ein Blockdiag ramm eines Expanders zur Dekomprimierung von Daten, die durch den Kompressor, der in Figur 3 dargestellt ist, komprimiert sind;
  • Figur 5 stellt das Parsing-Symbol einer Abtastsymbolzeichenfolge dar;
  • Figuren 6A-6E stellen schematisch den Aufbau einer in einem Trie-Suchbaum organisierten Datenstruktur dar;
  • Figuren 7A-7E stellen schematisch den Aufbau einer in einem PATRICIA-Baum organisierten Datenstruktur dar;
  • Figur 8 stellt schematisch eine Suffix-Baumorganisation der Datenstruktur, die in Figur 7E gezeigt ist, dar;
  • Figur 9 ist eine verallgemeinerte Darstellung eines Suffix-Baums;
  • Figur 10 zeigt ein schematisches Blockdiagramm eines Kompressors, der einen monadischen Codierer besitzt;
  • Figur 11 zeigt ein finites Zustandsdiagramm zur Darstellung der Betriebsweise des monadischen Codierers, der in Figur 10 dargestellt ist;
  • Figur 12 zeigt ein vereinfachtes Flußdiagramm für einen textorientierten Substitutionskompressor, der komprimierte Verschiebungen verwendet oder einen Baumstruktur-Codierer besitzt;
  • Figur 13 zeigt ein vereinfachtes Flußdiagramm eines Baumstruktur-Codierers und des Kompressors, der in Figur 12 dargestellt ist;
  • Figur 14 zeigt ein vereinfachtes Flußdiagramm eines Flush- und Pad-Unterprogramms für eine Wortausrichtung des komprimierten Ausgangs und des Kompressors, der in Figur 12 dargestellt ist; und
  • Figuren 15A-15B verbinden sich miteinander, um ein vereinfachtes Flußdiagramm eines Expanders für den Kompressor zu bilden, der in den Figuren 12-14 dargestellt ist.
  • Während die Erfindung in einem gewissen Detail nachfolgend unter Bezugnahme auf bestimmte dargestellte Ausführungsformen beschrieben ist, sollte verständlich werden, daß nicht die Absicht besteht, sie auf diese Ausführungsformen zu beschränken. Im Gegensatz dazu ist das Ziel dasjenige, alle Modifikationen, Alternativen und Äquivalente, die innerhalb des Schutzumfangs der Erfindung, wie sie dumh die beigefügten Ansprüche definiert ist, fallen, einzuschließen.
    • A. Übersicht
  • Wie nun die Figuren zeigen, und an dieser Stelle insbesondere Figur 1, ist ein Datenkompressionssystem 61 gezeigt, das einen Kompressor 62 zum Komprimieren serieller digital codierter Quellendaten und einen Expander 63 zum seriellen Dekomprimieren der Daten besitzt. Verschiedene Ausführungsformen der vorliegenden Erfindung werden beschrieben und andere werden sich selbst anbieten, allerdings liefert jede davon ein invertierbares oder verlustloses Datenkompressionssystem, wodurch sichergestellt wird, daß die expandierten oder dekomprimierten Daten im wesentlichen identisch zu den Originalquellendaten sind. Weiterhin sind alle Ausführungsformen dieser Erfindung anpaßbar, so daß die Quellendaten zum Beispiel aus einem alphanumerischen Text, abgetasteten oder synthetischen Bildern, personen- oder maschinenlesbaren Computer-Coden oder unterschiedlichen Kombinationen von diesen und/oder anderen Quellentypen zusammengesetzt sein können.
  • Es sollte zu Anfang verstanden werden, daß der Kompressor 62 und der Expander 63 mittels einer geeignet konfigurierten Hardware oder durch die Verwendung geeignet programmierter digitaler Computer für allgemeine Zwecke ausgeführt werden kann. Weiterhin können der Kompressor 62 und der Expander 63 an derselben Stelle angeordnet werden, wenn erwünscht ist, sie zu lokalisieren, wie beispielsweise zum Einladen von komprimierten Quellendaten in einen oder ein Suchen von dekomprimierten Quellendaten von einem File-Surfer (nicht dargestellt). Tatsächlich kann eine Software-Implementierung des Kompressors 62 und des Expanders 63 an einer Stelle denselben Computer zum Ausführen der Kompressor- und Expanderprogramme auf Befehl hin verwenden. Alternativ können der Kompressor 62 und der Expander 63 an unterschiedlichen Stellen angeordnet werden, falls erwünscht ist, deren Funktionen zu verteilen, wie beispielsweise zum Übertragen und zum Empfangen von Daten über ein Kommunikationsmedium mit einer begrenzten Bandbreite (auch nicht dargestellt). File- und Datenstrom-Kompressoren und -Expander werden diskutiert werden, so daß verständlich sein sollte, daß sich die primären Unterscheidungen zwischen diesen auf die Flußsteuerung deren Eingabedaten und auf das Auffüllen der komprimierten Daten mit Pad-Codeworten beziehen, um deren Byte-Ausrichtung wiederherzustellen. Daten werden in Datenfluß-Kompressoren "gedrückt" und aus Datenstrom-Expandern durch den "Client" (ein Kompressor- "Client" ist eine Datenquelle und ein Expander- "Client" ist eine Datensenke) herausgezogen, während Daten in File-Kompressoren und -Expandern unter deren interner Steuerung "gezogen" werden. Einige Anmerkungen werden auf das Auffüllen der komprimierten Daten mit Pad- bzw. Füll-Codeworten gemacht, allerdings liegt dieser Gegenstand im wesentlichen jenseits des Schutzumfangs der vorliegenden Erfindung und liegt innerhalb des Fachwissens von Fachleuten auf dem betreffenden Fachgebiet.
  • Um die vorliegende Erfindung auszuführen, stellt der Kompressor 62 eine vollständige und momentane Aufzeichnung aller vor kurzem komprimierten Quellensymbolen zusammen und behält sie bei, die gemäß der Reihenfolge deren Auftretens miteinander verknüpft sind. Diese Aufzeichnung wird in einem geeigneten Speicher aufrechterhalten, um ein "Suchfenster" auf der Basis first in/first out ("FIFO") bzw. zuerst eingegangen/zuerst ausgegangen beibehalten, das alle der früher komprimierten Symbole in dem Quellendatenstrom zwischen der Position i des zuletzt komprimierten Symbols in einer Position i - w eines früher komprimierten Symbols überspannt, wobei w die Symbollänge des Suchfensters ist.
  • Im Betrieb werden die Quellensymbole get stet, bevor sie in das Suchfenster eingesetzt werden, um zu bestimmen, ob das Suchfen ter Anpassungen für irgendeine der erweiterten Symbol-Zeichen-Folgen enthält, die urch Ergänzen eines Testsymbols an einer Symbol-Position i + 1 mit einem oder mehr ren der Symbol(e), die im folgenden gebildet werden, und wenn dies so ist, die Symbollänge der längsten dieser Anpassungen bestimmen. Falls keine Anpassung gefunden wird oder falls die längste, bestehende Anpassung zu kurz ist, um ein vorbestimmtes "minimales, bedeutungsvolles Kopierlängen-" Kriterium zufriedenzustellen, setzt der Kompressor 62 das Testsymbol in den komprimierten Datenstrom hinter einem Literal-Co ewort einer festgelegten oder variablen Länge ein, das die allgemeine Form "Literal xl" esitzt. Der Expander 63 wiederum interpretiert dieses Codewort als eine Anweisung, um ihn zu instruieren, die nächsten "xl"-Symbole direkt zu seinem Ausgang hin durchzulassen. Falls andererseits das Suchfenster eine ausreichend lange Anpassung für ein solche erweiterte Testsymbol-Zeichenfolge besitzt, sieht der Kompressor 62 noch weiter Symbol für Symbol in der nicht komprimierten Datenfolge nach vorne, bis entweder (1 auf ein Symbol, das die längste existierende Anpassung beendet (d.h. ein Symbol, das ahingehend fehlschlägt, weiter die Länge dieser Anpassung zu erweitern), stößt, ode (2) er bestimmt, daß eine maximal zulässige Anpassungslänge gefunden worden ist. In Abhängigkeit jedes dieser Ereignisses setzt der Kompressor 62 ein Kopie-Codeworte einer festgelegten oder variablen Länge der allgemeinen Form "Kopie xc - y" in den komprimierten Datenstrom anstatt der angepaßten Symbol-Zeichenfolge ein Dieses Codewort instruiert den Expander 63, zurück über "y" zuvor dekomprimierter Quellensymbole zu springen, wobei y < w gilt, und um dann "xc" aufeinanderfolgender Symbole einer progessiv neueren Verarbeitung in seinen Ausgang zu kopieren, beginnend mit dem Kopieprozeß mit dem Symbol an der Sprungeintrittsposition.
    • B. Eine elementare Ausführungsform
  • Wie ersichtlich werden wird, hängt die Kompression, die erreicht wird, von dem Raum ab, der für die Kopie- und Literal-Codeworte erforderlich ist. Figur 2 stellt eine Einzeldurchgangskompression eines üblichen Durchgangs eines Textes, der eine festgelegte Länge, 8 und 16 Bit-Literal- und Kopie-Codeworte jeweils, verwendet. Während die Längen dieser Codeworte kein fundamentales Merkmal der vorliegenden Erfindung sind, wird verständlich werden, daß diese besonderen Codeworte für eine praktische Ausführung dieser Erfindung ausreichend sind und den Vorteil einer Byte-Ausrichtung mit Quellendaten besitzen, die aus ordinären 8 Bit pro Zeichentext und/oder Computer-Quellencode zusammengesetzt sind.
  • Um sich für einen Moment auf die Layouts der Codeworte zu konzentrieren, wird gesehen werden, daß die ersten vier Bit-Positionen eines acht Bit-Literal-Codeworts typischerweise einem Literal-Zeichen oder Identifikationsfeld, LF, zugeordnet sind, um eine umgekehrte Einleitung-Bit-Sequenz anzupassen, wie beispielsweise "0000", und zwar für eine einzigartige Identifizierung des Literal-Codeworts. In diesem Fall bestehen die anderen oder letzten vier Bits eines solchen Codeworts in einem Literal-Längenfeld, LL, zum Codieren einer Literal-Länge, xl in dem Bereich [1....16], wodurch bis zu 16 Literal- Symbole an einem solchen Codeworte abgehängt sein können (d.h. die "maximal zulässige Literal-Länge"). Ein Kopie-Codewort andererseits enthält sowohl eine Kopie-Länge als auch einen Verschiebungs- oder Stellenwert. Hier werden zum Beispiel die ersten vier Bit-Positionen jedes Kopie-Codeworts einem Kopielängenfeld, CL, zum Codieren einer Kopie-Länge, xc, in dem Bereich von [2 ...... 16] zugeordnet, während seine verbleibenden oder 12 End-Bit-Positionen ein Kopieverschiebungsfeld, CD, zum Codieren einer Verschiebung y in dem Bereich [1 .... 4096] liefern. Deshalb können bis zu 16 Symbole durch ein einzelnes Kopie-Codewort dargestellt werden, um dadurch die "maximal zulässige Kopie-Länge" (dies ist einer einer Anzahl von Fällen, bei denen Code geeignet nach unten um 1 verschoben werden, so daß ein Code, der einen binären Wert von 1 besitzt, eine Kopie-Länge von 2 bedeutet, ein Code, der einen binären Wert von 2 besitzt, eine Kopie-Länge von 3 bedeutet, usw.) zu definieren. Weiterhin wird die effektive Länge des Suchfensters bestimmt, da der Ursprung einer Anpassungssymbol-Zeichenfolge einzigartig identifizierbar nur ist, wenn er eine von 4096 zuallerletzt verarbeiteter Symbol-Positionen ist.
  • Um das Beispiel, das in Figur 2 dargestellt ist, zu vereinfachen, ist angenommen worden, daß das Suchfenster des Kompressors 62 anfänglich leer ist und von einer ausreichenden Länge ist, um alle alphanumerischen Zeichen, Punktuationen und Zwischenräume des Abtasttextes zu speichern (d.h. alle seiner "Quellen-Symbole"). Ein vereinfachtes Computerprogramm zum Komprimieren und Expandieren von Qullendaten gemäß einer Ausführungsform dieser Erfindung ist in Appendix A angegeben (wobei einige der gebräuchlicheren Prozeduren nur funktionell beschrieben sind), der hier unter Bezug darauf eingeschlossen wird.
  • Wie gesehen werden wird, legt die Ausführungsform der Erfindung gemäß Appendix A die nachfolgenden, logischen Regeln der Operation des Kompressors 62 auf. (1) wenn der Kompressor 62 leer läuft und wenn die längste Anpassung, die innerhalb des Suchfensters für ein gegebenes Testsymbol gefunden wird, wenn es um eines oder mehrere der Symbole, die ihm folgen, erweitert wird, (d.h. eine erweiterte Testsymbol-Zeichenfolge) geringer als zwei Symbole lang ist, wird ein "Literal" initiiert; (2) wenn es einmal initiiert ist, wird ein Literal nicht unterbrochen, bevor es seine maximal mögliche Länge erreicht, ohne daß eine Anpassung, die mindestens drei Symbole überspannt, gefunden ist; (3) eine "Kopie" wird initiiert (i) in dem Fall einer solchen Unterbrechung oder (ii) wenn der Kompressor 62 leer läuft und eine Anpassung, die mindestens zwei Symbole überspannt, gefunden ist; (4) ein Literal-Codewort und das Literal-Quellensymbol, das an ihm anhängt, werden in die komprimierte Datenfolge eingesetzt, immer wenn (i) ein Literal unterbrochen wird oder (ii) ein Literal einer maximal zulässigen Länge verfügbar ist; und (5) ein Kopie-Codewort wird in den komprimierten Datenstrom eingesetzt immer wenn es dahingehend bestimmt wird, daß der angepaßte Eingang oder die Testsymbol- Zeichenfolge (i) durch ein Symbol bestimmt wird, das nicht weiter die Länge der längsten verfügbaren Anpassung erweitert, oder (ii) eine maximal zulässige Kopie-Länge überspannt. Die Kommentare, die im Appendix erscheinen, werden dabei helfen, die vorstehenden Regeln mit dem Code zu korrelieren. Weiterhin bezieht sich das Vorwort des Appendix A auf verschiedene Techniken, die zum Erhöhen der Ausführgeschwindigkeit des Kompressionsprogramms und zum Reduzieren der Menge des Speichers, der benötigt wird, um es auszuführen, verwendet werden kann.
  • In Anbetracht der vereinfachten Annahme, daß das Suchfenster des Kompressors 62 anfänglich leer ist, wird ersichtlich werden, daß die vorstehend zusammengefaßten Kompressionsregeln bewirken, daß der Kompressor 62 die ersten paar Symbole des Abtasttextes, der in Figur 2 dargestellt ist, einem Literal-Codeworte anhängt. Tatsächlich erfordern in diesem Fall die Kompressionsregeln eine Literal-Codierung von Symbolen 1-26, so daß dort mehr Literals in dieser ersten Symbol-Zeichenfolge als in irgendeinem Literal-Codeworte einer maximal zulässigen Literal-Länge vorhanden sind, die effektiv mit dem Expander 63 kommunizieren können. Eine solche Situation ist dahingehend wahrscheinlich, daß sie von Zeit zu Zeit auftritt, insbesondere während des Hochfahrens und während der Kompressor 62 von einem Typ von Quellendaten zu einem anderen übergeht, so daß es wichtig ist, zu verstehen, daß der Kompressor 62 immer dann zurückläuft, wenn er eine Literal-Symbol-Zeichenlänge einer maximal zulässigen Literal- Länge zusammenstellt. Als Folge dieses Zurücklaufens unterteilt der Kompressor 62 längere Literal-Symbol-Zeichen-Folgen in zwei oder mehr Unter-Zeichen-Folgen einer zulässigen Länge und hängt diese Unter-Zeichen-Folgen separaten Literal-Codeworten an um sie zu dem Expander 63 zu befördern. Zum Beispiel werden Symbole 1 - 16 des Textes, der in Figur 2 angegeben ist, an ein erstes Literal-Codewort angehängt, das einen Längenwert von sechzehn besitzt, und dann werden Symbole 17 - 26 an ein zweites Literal-Codewort angehängt, das einen Längenwert von zehn besitzt. Wie ersichtlich werden wird, ist ein Vorteil dieser längeren Literals derjenige, daß sie effektiv die Anzahl der Literal-Codeworte reduzieren, die in den komprimierten Datenstrom eingesetzt werden, während sich der Kompressor einem neuen Quellen-Daten-Typ anpaßt.
  • Während sich die Symbole 27 des Textes der Figur 2 in einer Symbol-Position i + 1 befinden, wird eine Längenanpassung von drei Symbolen gefunden, da sich Symbole 27-29 zu zuvor auftretenden Symbolen 1-3 anpassen. Demzufolge wird das "Literal", das dann in Arbeit ist, unterbrochen, und eine "Kopie" wird initiiert. Diese Ereignisse sind der erste Fall einer "Kopie" in diesem bestimmten Beispiel, gerade obwohl eine kurze Durchsicht des Abtasttextes einige frühere, zwei Symbole lange Anpassungen aufdekken wird. Es sollte deshalb verständlich werden, daß diese früheren Anpassungen beim Beibehalten der Kompressionsregeln des Appendix A ignoriert wurden, da jede davon nur zwei Symbole lang war und gerade ein Literal erzeugt wurde.
  • Wenn er eine "Kopie" in Abhängigkeit der Anpassung, die für Symbole 27-29 gefunden ist, initiiert hat, erweitert der Kompressor 62 weiter die angepaßte Symbol-Zeichenfolge mit einem nach dem anderen der nachfolgenden Quellen-Symbole, bis er ein Quellensymbol findet, das die Anpassung beendet (d.h. ein Symbol, das dahingehend fehlschlägt, daß es weiter die Länge der längsten Anpassung erweitert), wie an dem Symbol 38, oder bis er eine Anpassung einer maximal zulässigen Kopie-Länge findet. Wenn irgendeines dieser Ereignisse auftritt, gibt der Kompressor 62 ein Kopie-Codewort in den komprimierten Datenstrom anstelle der angepaßten Symbol-Zeichenfolge ab. Das Kopie-Codewort zeigt die Länge dieser Symbol-Zeichenfolge an und liefert einen Hinweiszeiger zur Lokalisierung des Führungs-Symbols dieses früheren Ereignisses, um dadurch dem Expander 63 zu ermöglichen, diese Symbole, die durch das Codewort dargestellt sind, mittels des zuvor beschriebenen "Zurückspring-" und "Kopie-Vorwärts-" Verfahrens zurückzugewinnen.
  • Wie die Figur 3 zeigt, weist die Ausführungsform des Appendix A des Kompressors 62 einen Eingangs-Puffer 71 auf der Basis first in/first out (FIFO) zum Speichern (1) von Symbolen von einem etwa zu komprimierten Bereich der Quelle in Symbol-Positionen, die bis zu einer Symbol-Position i + 1 führen und diese umfassen, vorausgegangen durch (2) die am kürzesten davor komprimierten Symbole in den Suchfenster-Smybol- Positionen i bis i - w, auf. In einer Software-Ausführung ist der Puffer 71 in geeigneter Weise ein zirkularer Puffer, der in Quadranten unterteilt ist, so daß eine Batch-Transaktion für eine reguläre Zurückladung von Quellensymbolen in Quadrant für Quadrant hinein eingesetzt werden kann, bis die Quelle, die komprimiert werden soll, erschöpft ist (z.B. bis das Ende des momentanen Quellen-Files erreicht ist). Dies reduziert die Anzahl der I/O-Transaktion, die zum Beibehalten eines zeitlichen Flusses von Quellensymbolen für den Kompressor 62 erforderlich ist. In einer solchen Ausführung werden die Quadranten ausgewählt, so daß sie ausreichend groß sind, um effektiv die Kompression zu isolierern, die durch den Kompressor 62 von der Neubeladung eines Eingangs-Puffers 71 an durchgeführt ist. Eine Such- und Aktualisierungs-Logik 72 tastet einen Suchbaum einer organisierten Datenstruktur 73 ab und hält ihn bei, der die Symbole innerhalb Symbol- Position i bis i - w des Puffers 71 (d.h. das Suchfenster) zueinander gemäß der Ordnung eines Auftretens verknüpft und der das letzte Auftreten dieser Symbol-Zeichen-Folgen als aufeinanderfolgende Symbole in das, durch das und aus dem Suchfenster verschiebt. Die Schnitt-Tiefe dieser Verknüpfungen, die durch die Suchbaumdatenstruktur 73 geliefert wird, wird geeignet so ausgewählt, daß sie gleich der maximal zulässigen Kopie-Länge ist, um dadurch die Menge an Speicher, die erforderlich ist, um sie zu speichern, und die Verarbeitungszeit, die erforderlich ist, um sie beizubehalten, zu begrenzen. Verschiedene andere Techniken, die für eine weitere Reduzierung der Größe des Suchbaums 73 verwendet werden können, und die Zeit, die zum Aktualisieren davon erforderlich ist, werden in weiterem Detail nachfolgend beschrieben werden.
  • Im Betrieb setzt die Such- und Aktualisierungs-Logik 72 den Suchbaum 73 zum Bestimmen ein, ob eine Anpassung irgendwo der Symbol-Positionen i bis i - w des Puffers 71 für das Test-Symbol vorhanden ist, das an der Symbol-Position i + 1 auftritt. Falls eine Anpassung gefunden wird, verlängert die Logik 72 die Test-Zeichenfolge durch Anhängen des Symbols an die Smybol-Position i + 2 daran und bestimmt dann, ob dort auch eine Anpassung innerhalb des Suchfensters für diese verlängerte Eingangs-Symbol-Zeichenfolge vorhanden ist. Dies ist ein reiterativer Prozeß, wodurch die Such- und Aktualiierungs-Logik 72 progessiv die Testsymbol-Zeichenfolge durch Verlängerung davon mit einem nach dem anderen der nicht komprimierten Symbole ergänzt, bis ein Symbol, das fehlschlägt, die Länge der längsten existierenden Anpassung zu verlängern (d.h. ein Anpassungs-Beendigungssymbol) erfaßt wird, oder bis die Existenz einer Anpassung einer maximal zulässigen Kopie-Länge identifiziert wird. Wenn irgendeines dieser Ereignisse auftriff, gibt die Such- und Aktualisierungs-Logik 72 einen Report zu einem Diskriminator 74 ab, der gemäß den vorstehend zusammengefaßten Codier-Regeln arbeitet, um zu bestimmen, ob das Symbol oder die Symbole, die getestet sind, als ein Kopie-Codewort durch den Kopie-Codierer 75 codiert werden sollen oder an ein Literal- Codewort durch einen Literal-Codierer 76 angehängt werden sollen. Hierbei identifiziert der Report, der durch die Such- und Aktualisierungs-Logik 72 geliefert wird, die Länge der längsten Anpassung, die aufgefunden worden ist, und die Suchfenster-Position des früheren Auftretens der angepaßten Symbole (die positionsmäßige Information muß nicht berichtet werden, wenn die Länge der Anpassung geringer als die minimale Anpassungslänge ist, die für eine Kopie erforderlich ist). in diesem Fall wird die Stelle des Führungs- oder ersten Symbols der Anpassungs-Symbol-Zeichenfolge an den Kopie-Codierer 75 als eine Verschiebung von einer Symbol-Position i + 1 berichtet, allerdings wird ersichtlich werden, daß diese Stelle eindeutig auf andere Art und Weise identifiziert werden könnte.
  • Ein Kopie-Codewort wird in einen Ausgangs-Puffer 77 durch den Kopie-Codierer 75 in Abhängigkeit eines Reports von der Such- und Aktuaiisierungs-Logik 72 eingesetzt, die den Diskriminator 74 veranlaßt, darauf zu schließen, daß eine Anpassung einer ausreichenden Länge, die codiert werden soll, durch ein solches Codewort identifiziert worden ist. Das Kopie-Codewort wird für die Symbole der angepaßten Symbol-Zeichenfolge substituiert, so daß alle Symbole der angepaßten Symbol-Zeichenfolge in den Suchfenster-Quadranten oder -Sektor des Puffers 71 verschoben werden, bevor der Diskriminator 74 auf irgendwelche weiteren Reporte von der Such- und Aktualisierungs-Logik 72 anspricht. Hierbei wird eine Zählung entsprechend der Länge jeder Kopie in einen Zeichen-Spring-Zähler eines mittels Zähler gesteuerten Gatters 78 für eine temporäre Sperrung der Codier-Logik 74-76 gegen ein Produzieren weiterer Codeworte eingeladen, während die Symbole, die durch die Kopie dargestellt sind, in den Suchfenster-Sektor des Eingangs-Puffers 71 eingeladen werden. Die Zählung wird schrittweise erniedrigt, wenn jedes der aufeinanderfolgenden Symbole der angepaßten Symbol-Zeichenfolge in das Suchfenster eingeladen wird, so daß die Codierung mit dem Symbol fortfährt, das der angepaßten Zeichenfolge folgt.
  • Ein Literal wird andererseits durch den Diskriminator 74 eingeleitet, wenn die Such- und Aktualisierungs-Logik 72 dahingehend fehlschlägt, eine Anpassung einer ausreichenden Länge zu finden, die als eine Kopie codiert werden soll, gerade obwohl die Länge des Literals noch unbekannt ist. Wenn einmal eine Literal initiiert ist, testet die Such- und Aktualisierungs-Logik 72 die Verlängerungen aufeinanderfolgender der nicht komprimierten Symbole, wenn sie in eine Symbol-Position i + 1 verschoben werden, bis sie eine Anpassung für eine verlängerte Testsymbol-Zeichenfolge einer ausreichenden Länge findet, um eine Unterbrechung des Literals (z.B. mindestens einer Länge von drei Symbolen) zu garantieren oder bis die Zahl der Symbole, die getestet worden ist, die maximal zulässige Literal-Länge erreicht. Immer wenn irgendeines dieser Ereignisse auftritt, setzt der Literal-Codierer 76 ein Literal-Codewort, das die Länge des Literal identifiziert, in den Ausgangspuffer 77 ein und kopiert dann die akkumulierten Symbole des Literals in dem Puffer 77 in einer seriellen Reihenfolge, um sie dadurch an das Literal-Codewort anzuhängen. Das Literal-Codewort und dessen angehängte Literal-Symbole können in den Ausgangspuffer 77 eingeladen werden, sobald eine Anpassung einer ausreichenden Länge für eine Kopie gefunden ist, oder, wie in den dargestellten Ausführungsformen nachdem die Anpassung die Kopie bis zu ihrer allerletzten Länge erweitert worden ist, so daß der Kopie-Codierer 75 bereit ist, ein Kopie-Codewort abzugeben.
  • Wie in Figur 4 dargestellt ist, weist für eine Dekomprimierung der komprimierten Quellen-Daten der Expander 63 einen Eingangs-Puffer 81 zum Zuführen der komprimierten Daten zu einem Decodierer 82 unter einer geeigneten Rate, oder wie es gefordert ist, auf. Der Decodierer 82 wiederum decodiert die Literal- und Kopie-Codeworte für eine Literal-Logik 83 und eine Kopie-Logik 84 jeweils. Wenn ein Literal-Codewort durch den Decodierer 82 decodiert ist, spricht die Literal-Logik 83 auf die decodierte Länge des Literal xl an, um seriell die nächsten xl-Symbole direkt in den FIFO-Ausgangs-Puffer 85 einzuladen. Andererseits spricht, wenn ein Kopie-Codewort decodiert wird, die Kopie-Logik 84 auf deren Verschiebung, y, und Länge, XC, für ein serielles Kopieren in den Ausgangs-Puffer 85 einer Zeichenfolge zuvor dekomprimierter Symbole an, beginnend mit dem y-ten zuvor dekomprimierten Symbol in dem Puffer 85, und erweitert die Kopie von dort über eine Zeichenfolge von XC progressiv der noch kürzer zuvor dekomprimierten Symbole.
    • C. Mehr über die Suchbäume
  • Vorteilhafterweise verzweigt sich der Suchbaum 73 gemäß den "einstelligen Ziffern" seiner Schlüssel zu seinen "Blättern", die durch die Quellen-Symbole definiert sind, die innerhalb der Suchfenster-Symbol-Position i bis i - w des Eingangs-Puffers 71 in irgendeiner vorgegebenen Zeit sind. Um sich zum Beispiel auf den höchst redundanten englischsprachigen Text, der in Figur 5 dargestellt ist, zu konzentrieren, wird ersichtlich werden, daß ein Suchbaum 73, der sich gemäß den individuellen Zeichen irgendeines Bereichs des Textes verzweigt, der innerhalb der Suchfenster-Symbol-Positionen des Eingangs-Puffers 71 liegt, ebenso gut zum Liefern der Hinweiszeiger geeignet ist, die zum Lokalisieren früherer Erscheinungen wiederauftretender Symbole und Symbol-Zeichen- Folgen benötigt wird, vorausgesetzt, daß die Hinweiszeiger während eines Betriebs aktualisiert sind, um der FIFO-Verschiebung der komprimierten Quellen-Symbole in dem durch das und aus dem Suchtenster gerecht zu werden. Symbole werden in das Fenster über eine Symbol-Position i verschoben, unmittelbar nachdem sie dahingehend bestimmt ist, ob sie einem Literal- oder Kopie-Codewort, wie zuvor beschrieben, zugeordnet sind während ältere Symbole aus dem Fenster über eine Symbol-Position i - w verschoben werden, wenn Raum, der durch sie belegt ist, zum Speichern neuerer aufgetretener Symbole und Symbol-Zeichen-Folgen benötigt wird. Obwohl die relative Bewegung zwischen den Quellen-Symbolen und dem Suchfenster mit festgelegter Länge sehr leicht als eine physikalische Verschiebung der Symbole in Bezug auf das Suchfenster visualisiert wird, wird verständlich werden, daß sie in einer Software durch Einsetzen von Hinweiszeigern ausgeführt werden kann, die in Bezug auf die Quellen-Symbole unter einer Software-Steuerung verschoben werden.
  • Unter Bezugnahme auf die Figuren 6A-6E wird ersichtlich werden, daß eine Trie-Baum- Datenstruktur (siehe D.E. Knuth, The Art of Computer Programming Vol. 3 : Sorting and Searching, Addison-Wesley, Second Printing, 1975, S. 481) die basismäßigen, funktionalen Erfordernisse für den Suchbaum 73 erfüllen. Wie bekannt ist, wird eine Symbol- Zeichenfolge in einen Trie-Baum durch Herabsteigen von der Wurzel des Baums ein zusätzliches Niveau für jedes darauffolgende Symbol in der Zeichenfolge eingesetzt. Demzufolge verzweigt sich das j-te Niveau des Baums gemäß dem j-ten Symbol in irgendeiner vorgegebenen Symbol-Zeichenfolge mit der Folge, daß der Baum ihm eigen alle notwendigen Hinweiszeiger zum Lokalisieren aller Symbole und Symbol-Zeichen-Folgen innerhalb des Suchfensters enthält. Allerdings ist eine wesentliche Menge an Verarbeitungszeit erforderlich, um Symbol-Zeichen-Folgen in einen Trie-Baum einzusetzen (d.h. die Einsetzzeit für den ungünstigsten Fall für einen File, der aus n-Symbolen zusammengesetzt ist, beträgt O(d n), wobei d die maximal zulässige Kopie-Länge ist). Weiterhin wächst die Größe einer solchen Datenstruktur auf O(d w) an, wobei w die Suchfenstergröße ist, so daß eine einfache Trie-Baum-Datenstruktur dahingehend wahrscheinlich ist, daß sie zu groß für die meisten praktischen Anwendungen dieser Erfindung ist.
  • Wie nun die Figuren 7A-7E zeigen, ist ein PATRICIA-Baum (siehe D.R. Morrison, "PATRICIA-Practical Algorithm to Retrieve Information Coded in Alhpanumeric", Journal of the Association for Computing Machinery, Vol 15, No. 4, 1968, Seiten 513-534) eine relativ kompakte Alternative zu dem Trie-Baum. Wie bekannt ist, umfassen die inneren Knoten eines PATRICIA-Baums Hinweiszeiger zu dem File, den er indiziert, so daß die Datenstruktur eines solchen Baums nur eine einzelne "einstellige Zahl" oder ein Symbol für jede Suchpfadverzweigung haben muß, um dadurch die unnötigen inneren Knoten eines Trie-Baums (d.h. solche mit nur einem Deszendenten) zu eliminieren. Zum Beispiel müssen, wenn der Suchbaum 73 (Figur 3) ein PATRICIA-Baum ist, die Symbole, auf die eingeklammert auf seinen Bogen in den Figuren 7B-7E Bezug genommen wird, nicht explizit in der Datenstruktur enthalten sein, da sie nicht die Verzweigung des Baumes beeinflussen. Diese Symbole können allerdings durch Abtasten der Symbole innerhalb der Suchfenster-Symbol-Positionen zurückgewonnen werden, die durch die Positions- und Niveau-Hinweiszeiger-Paare der Knoten für die Bogen identifiziert sind, auf denen sie vorhanden sind, so daß sie effektiv durch diese Bogen dargestellt werden.
  • Ein klassischer PATRICIA-Baum erfordert nur einen einzelnen File-Zugriff und einen Vergleich an dem Ende jeder Suche. Allerdings ist es, wenn ein Suchbaum 73 im PATRICIA-Stil verwendet wird, um die vorliegende Erfindung auszuführen, allgemein bevorzugt, die Symbole abzutasten, die durch die Bogen dargestellt werden, die während des Einsetzens der Symbol-Zeichenfolge in den Baum überquert werden, so daß die Positions-Hinweis-Adressen innerhalb der Knoten, zu denen solche Bogen führen, aktualisiert werden können, während nach unten in den Baum abgestiegen wird. Typischerweise sind die "einstelligen Ziffern", die in den Suchbaum 73 eingesetzt werden, Bytes, z.B. Zeichen mit acht Bit, so daß ein Verzweigungsfaktor bis zu 256 geliefert werden kann. Als allgemeine Regel allerdings müssen die Knoten nicht diese vielen Deszendenten haben, so daß die Menge an Raum, die innerhalb der Knoten des Baums 73 reserviert werden muß, um die Verzweigung seiner Suchpfade zu definieren, durch Kontrollsummieren seiner Bogen reduziert werden kann.
  • Ein PATRICIA-Baum ist eine akzeptierbare Wahl für den Suchbaum 73, wenn eine ausreichende Kompression erreicht werden kann, während ein Suchbaum mit einer relativ flachen Abschnittstiefe eingesetzt wird. Wie zuvor ausgeführt ist, wird ein solcher Baum durch eine annehmbar kompakte Datenstruktur definiert, er beruht allerdings auf im wesentlichen denselben Einsetzprozessen (d.h. Rückkehr zu der Wurzel und dann Absteigen in den Baum) wie der Trie-Baum. Demzufolge tendiert die Zeit, die zum Einsetzen längerer Symbol-Zeichen-Folgen in einen PATRICIA-Baum erforderlich ist, dazu, die praktische Anwendung dieses Typs eines Baums auf Ausführungsformen zu begrenzen, bei denen die maximal zulässige Kopie-Länge relativ kurz ist (wiederum ist die Einsetzzeit für den ungünstigsten Fall für einen File von n Symbolen O(d n), wobei die Tiefe d, die für den Baum erforderlich ist, gleich der maximal zulässigen Kopie-Länge ist.
  • Glücklicherweise kann ein leicht modifizierter Suffix-Baum, wie dies in Figur 8 dargestellt ist, für Ausführungsformen verwendet werden, in denen es notwendig oder erwünscht ist, in der Lage zu sein, Symbol-Zeichen-Folgen in den Suchbaum 73 (Figur 3) in einer Zeit 0 (n) einzusetzen. Wie durch E.M. McCreight, "A Sapce-Economical Suffix Tree Algorithm", Journal of the Association for Computing Machinery, Vol 28, No. 1,1976, Seten 262-272, beschrieben ist, ist ein Suffix-Baum ähnlich einem PATRICIA-Baum mit der Ausnahme, daß die inneren Knoten eines Suffix-Baums Hinweiszeiger umfassen, die sie mit den Knoten für deren Suffix verknüpfen, wie dies durch die unterbrochene Linie 8 dargestellt ist. Genauer gesagt wird, wie der verallgemeinerte Suffix-Baum, der in Figur 9 dargestellt ist, zeigt, gesehen werden, daß die inneren Knoten im Suffix erweiterter Symbol-Zeichen-Folgen, wie beispielsweise die Zeichen-Folgen aX, Hinweiszeiger zu den Knoten umfassen, die deren Suffix-Erweiterungen, beispielsweise X, darstellen. Demzufolge kann, wenn eine in ihrem Suffix erweiterte Symbol-Zeichenfolge, die an einer Position p in dem Suchfenster beginnt, gerade bei dem Niveau 1 eines Suchbaums 73 vom Suffix-Stil eingesetzt worden ist, die Zeichenfolge, die an einer Position p + 1 startet, in den Suchbaum eingesetzt werden, und zwar ohne zurückkehren zu dessen Wurzel, da dort immer eine naheliegende Suffix-Hinweisanzeige vorhanden ist, die von dem Knoten, der eine im Suffix erweiterte Symbol-Zeichenfolge darstellt (z.B. die Zeichenfolge, die an einer Position p startet), zu dem Knoten für deren Suffix-Erweiterung (z.B. die Zeichenfolge, die an einer Position p + 1 startet) vorhanden ist.
  • Unter Betrachtung der Figur 9 in zusätzlichem Detail wird ersichtlich werden, daß sie eine Situation darstellt, in der eine Anpassung auf der früheren Iteration für eine Zeichenfolge, die aus aXY zusammengesetzt ist, gefunden worden ist, wobei a ein Einzelsymbol ist, X und Y Zeichen-Folgen sind, die aus einem oder mehreren Symbol(en) zusammengesetzt sind, und b das erste, nicht angepaßte Symbol, das Y folgt, ist. Um eine weitere Komplikation darzustellen, die von Zeit zu Zeit auftritt, ist angenommen worden, daß &alpha; ein neuer, innerer Knoten ist, der gerade zu dem Baum hinzugefügt worden ist, um zwischen dem Suchpfad für die Zeichenfolge aXYb und dem Suchpfad für die Zeichen-Folgen aXYZ zu diskriminieren, wobei Z nicht mit b beginnt. Unter Berücksichtigung dieser Annahme wird ersichtlich werden, daß es noch notwendig ist, die Suffix-Verknüpfung für den Knoten &alpha; zu berechnen.
  • Gemäß den vorstehend angegebenen Lehren von Mccreight kann die nächste Zeichenfolge, XYb, in den Baum durch anfängliches Bewegen hoch in dem Baum (d.h. zu seiner Wurzel hin) von dem Knoten &alpha; (der bis jetzt noch keine Suffix-Verknüpfung besitzt) zu dem nächst höheren Knoten &beta;, um dadurch Y von der Zeichenfolge aXY abzustreifen, eingesetzt werden. Der Knoten &beta; stellt notwendigerweise die Zeichenfolge aX dar, so daß sein Suffix-Hinweiszeiger dem Knoten &gamma; folgt, der durch Definition den Suffix X der Zeichenfolge aX darstellt. Nachdem der Knoten, der X darstellt, gefunden ist, kann die um den Suffix erweiterte Symbol-Zeichenfolge XYb nun durch Absteigen in dem Baum eingesetzt werden, zuerst um die Zeichenfolge Y wieder "einzutasten" und um dann weiter nach unten in den Baum "zu tasten", um die längste, existierende Anpassung für die Symbol-Zeichenfolge aufzufinden, die mit der Unter-Zeichenfolge XY beginnt. Wenn eine existierende Anpassung für deren Suffix-Erweiterung XYb vorhanden ist, wird die "erneute Abtastung" auf dem Knoten 6 entsprechend der Unter-Zeichenfolge XY enden. Andererseits wird, wenn keine Anpassung für die um den Suffix erweiterte Zeichenfolge XYb vorhanden ist, der Knoten 6 durch Schlagen eines Bogens, der eine Zeichenfolge darstellt, die mit Y beginnt, um den neuen Knoten 6 mit Y durch seinen ankommenden Bogen dargestellt einzusetzen, erzeugt werden. In jedem Fall verzweigt sich der Knoten &delta; zu dem Symbol b und stellt den Suffix XY für die frühere Symbol-Zeichenfolge aXY dar. Demzufolge wird ein Hinweiszeiger dazu in das Suffix-Verknüpfungsfeld des Knotens &alpha; eingegeben, um dadurch die Unveränderlichkeit jedes internen Knotens innerhalb des Suffix-Baums wiederherzustellen bzw. zurückzuführen, mit der möglichen Ausnahme, daß einer der zu allerletzt Erzeugten eine Suffix-Verknüpfung besitzt.
  • Glücklicherweise müssen die Smybol-Zeichen-Folgen, die durch die Bogen dargestellt sind, die "wieder abgetastet" während des vorstehend beschriebenen Prozesses sind (z.B. die Zeichenfolge Y), nicht gegen die entsprechenden Symbole der Zeichenfolge verglichen werden, die in den Baum eingesetzt werden sollen, da die Identität solcher zwei Symbol-Sätze während der früheren Iteration eingerichtet wurde (d.h. während das Suffix XY der Symbol-Zeichenfolge aXY in den Baum eingesetzt wurde). Diese frühere Kenntnis ermöglicht, daß Symbol-Zeichen-Folgen in einen Baum 73 vom Suffix-Stil in einer im wesentlichen linearen Zeit eingesetzt werden können, da nur die allerletzten Suffix-Erweiterungen gegenüber den Inhalten des Suchbaums verglichen werden müssen.
  • Gemäß einem der Merkmale dieser Erfindung werden verschiedene wichtige Modifikationen in Bezug auf die Datenstruktur des Suchbaums vom Suffix-Stil vorgenommen, der durch McCreight, supra, beschrieben ist, um seine Größe zu begrenzen und die Zeit zu reduzieren, die zum Aufrechterhalten von diesem erforderlich ist Wie zuvor hervorgehoben ist, werden die Blätter des Baums seriell in die, durch die und aus den Suchfenster- Symbolpositionen i bis i-w des Puffers 71 (Fig. 3) auf einer FIFO-Basis verschoben um dadurch ein geordnetes Verfahren zum Beibehalten des am kürzesten vorher komprimierten Bereichs der Quellendaten innerhalb des Suchfensters mit festgelegter Länge aufrechtzuerhalten. Weiterhin sind "Sohn-Zähl-" Felder in den inneren Knoten des Baums zum Identifizieren von Knoten, die ausgelassen bzw. gelöscht werden sollen, umfaßt. Wie ersichtlich werden wird, werden innere Knoten zu dem Baum nur dann hinzugefügt, wenn sie zwischen alternativen Suchpfaden diskriminiert werden müssen. Ein "Eltern-Knoten", der nur einen verbleibenden "Sohn" besitzt, liefert nicht irgendeine Suchpfaddiskriminierung. Demzufolge wird, immer wenn der Wert in dem Sohn-Such- Feld irgendeines Knotens auf 1 abfällt, der Knoten ausgelassen und das Symbol oder die Symbol-Zeichen, die durch ihren allein verbleibenden oder "verwaisten" Sohn dargestellt werden, mit dem Symbol oder der Symbol-Zeichenfolge, die durch den Bogen von dem nächst höheren Niveau oder "Großeltern" -Knoten dargestellt ist, kombiniert.
  • Ein noch anderer Weg gegenüber dem bekannten Suchbaum vom Suffix-Stil ist derjenige, daß eine Vorsehung zum Aktualisieren der Positions-Hinweiszeiger in den internen Knoten des Suffix-Baums vorgenommen wird, ohne daß notwendigerweise erforderlich ist, daß eine Rückkehr zu der Wurzel des Baums vorgenommen wird, um dies durchzuführen. Insbesondere kann, um eines der mehreren, detaillierten Merkmale der vorliegenden Erfindung beizubehalten, eine "Perkulations-Aktualisierung" zum Aktualisieren der Hinweiszeiger in den inneren Knoten eines Suffix-Baums eingesetzt werden, um dadurch diese Hinweiszeiger auf den Suffix-Blättern des Baums beizubehalten, wenn die Blätter (d.h. die kürzlich komprimierten Quellen-Symbole) durch das Suchfenster verschoben werden. Hierbei umfaßt jeder innere Knoten des Baums ein einzelnes "Aktualisierungs-" Bit zusätzlich zu seinen vorstehend erwähnten Positions- und Niveau-Hinweiszeigern, Suffix-Hinweiszeigern und Sohn-Zähl-Feld. Weiterhin wird, immer wenn eine neue Symbol-Zeichenfolge in den Baum eingesetzt wird, die momentane Position in dem Abtastfenster des Anfangs- oder Führungs-Symbols der Zeichenfolge nach oben zu dem Eltern-Knoten für das neue Blatt der gerade eingesetzten Symbol- Zeichenfolge propagiert, wodurch 1) die momentane Position des Blatt-Symbols des am kürzesten vorherigen Auftretens der gegebenen Symbol-Reihenfolge in das Positionsfeld seines Blatt-Eltern-Knotens eingeschrieben wird, um dieses Auftreten von irgendwelchen früheren Auftretungen derselben Symbol-Zeichenfolge zu unterscheiden, die noch innerhalb des Suchfensters sein können, und 2) der Zustand des Aktualisierungs- Bits für den Eltern-Knoten des neuen Blatts umgekehrt wird. Wenn das Aktualisierungs- Bit des Eltern-Knotens von einem "falschen" Zustand zu einem "wahren" Zustand umgeschaltet wird, ist keine weitere Ausbreitung zu der Positions-Aktualisierung vorhanden. Allerdings breitet sich, wenn das Aktualisierungs-Bit des Eltern-Knotens des neuen Blatts von einem "wahren" Zustand zu einem "falschen" Zustand umgeschaltet wird, die momentane Suchfensterposition des Blatt-Symbols der neu eingesetzten Symbol-Zeichenfolge nach oben in den Baum aus (zurück zu seiner Wurzel hin), um die Positionsfelder aller Knoten auf dem Suchpfad für die Symbol-Zeichenfolge zu aktualisieren, bis die Aktualisierung einen Knoten mit einem höheren Niveau erreicht, der ein "falsches" Aktualisierungs-Bit besitzt. Dieser Aktualisierungs-Prozeß wird als "Perkulations-Aktualisierung" bezeichnet, da die Ausbreitung der Aktualisierung an dem ersten Knoten (der Knoten mit dem niedrigsten Niveau) bestimmt wird, der eine Aktualisierung empfängt, während sich sein Aktualisierungs-Bit in einem "falschen" Zustand befindet. Das Positionsfeld eines solchen Aktualisierungs-Bestimmungsknotens wird aktualisiert, um auf das Blatt-Symbol der neu eingesetzten Symbol-Zeichenfolge zu zeigen, und das Aktualisierungs-Bit des Knotens wird auf einen "wahren" Zustand umgeschaltet, um dadurch den Knoten zum Ausbreiten der nächsten Aktualisierung, die sie empfängt, zu ihrem Eltern- Knoten zu konditionieren. Zuletzt wird das letzte Symbol der neu eingesetzten Symbol Zeichenfolge in das Suchfenster verschoben, um dadurch zu bewirken, daß das älteste Blatt des Suchbaums 73 (Fig. 3) gelöscht wird (d.h. aus dem Suchfenster heraus verschoben wird), wenn das Suchfenster voll ist.
  • Wie zuvor hervorgehoben ist, triggert die Löschung von Blättern von dem Suchbaum 73 vom Suffix-Stil in erwünschter Weise die Löschung bzw. Auslassung irgendwelcher Eltern-Knoten, die mit gerade einem Sohn verbleiben. Aus diesem Grund wird die Position eines Eltern-Knotens, der von einem solchen Baum gelöscht ist, nach oben zu der Wurzel des Baums mehr oder weniger gemäß dem vorstehend beschriebenen Prozeß perkuliert (d.h. der Positions-Hinweiszeiger des Knotens, der gelöscht werden soll wird immer in das Positionsfeld des nächst höheren Niveau-Knotens eingeschrieben, wird allerdings nur konditionell nach oben von dort in Abhängigkeit von dem Zustand der Aktualisierungs-Bits der Knoten mit höherem Niveau ausgebreitet). Der Basisunterschied ist derjenige, daß während einer Perkulations-Aktualisierung von einem gelöschten Knoten der existierende Positions-Hinweiszeiger für jeden der Knoten mit höherem Niveau, der eine solche Aktualisierung empfängt, gegenüber dem Positions-Hinweiszeiger der vorgeschlagenen Aktualisierung verglichen wird, um dadurch zu ermöglichen, daß der am kürzestens vorher liegende dieser zwei Hinweiszeiger ausgewählt wird, (1) der Positions-Hinweiszeiger für den Knoten, der die Aktualisierung empfängt, und (2) als die vorgeschlagene Aktualisierung für den Knoten mit dem nächst höheren Niveau, wenn der Aktualisierung ermöglicht wird, sich zu ihm auszubreiten.
  • In dem ungünstigsten Fall müssen alle Knoten auf dem Pfad von dem Eltern-Knoten für das Suffix-Blatt oder Endsymbol einer neu eingesetzten Symbol-Zeichenfolge zu der Wurzel des Baums "wahre" Aktualisierungs-Bits haben, um dadurch zu bewirken, daß eine Aktualisierung alle Wege hoch zu der Wurzel des Baums perkuliert. Allerdings kann gezeigt werden, daß der vorstehend beschriebene Perkulations-Aktualisierungs-Prozeß in einem konstanten Zeitbetrag pro Symbol oder Zeichen durchgeführt werden kann, wenn die Zeit, die erforderlich ist, um sie so durchzuführen, über alle Blätter des Suchbaums 73 amortisiert ist. Noch wichtiger kann auch gezeigt werden, daß der Prozeß effektiv beim Beibehalten gültiger Positions-Hinweiszeiger in allen der inneren Knoten des Suchbaums 73 effektiv ist, so daß die Knoten akkurat zu den Suchfenster-Symbol-Positionen in Bezug gesetzt werden können, die die Symbole enthalten, die sie darstellen.
  • Noch andere Ausführungsanwendungen des Suchbaums 73 werden sich selbst vorschlagen. Zum Beispiel wird aus der vorstehenden Diskussion der Trie-Bäume und der PATRICIA-Bäume ersichtlich werden, daß die Perkulations-Aktualisierung, die für den Suffix-Baum geliefert wird, durch einfaches Zurückkehren zu der Wurzel des Baums für die Einsetzung jeder Symbol-Zeichenfolge vermieden werden könnte. In diesem Fall würden die inneren Knoten des Baums nicht irgendwelche Aktualisierungs-Bits erfordern und es würde unnötig sein, Aktualisierungen durchzuführen, wenn Knoten gelöscht werden. In ähnlicher Weise sind Suffix-Verknüpfungen nicht zur Lokalisierung der Suffix- Knoten während der Einsetzung von Symbol-Zeichen-Folgen in einen solchen Suchbaum erforderlich, obwohl sie wesentlich die durchschnittliche Zeit. die zum Durchführen dieser Aufgabe erforderlich ist, reduzieren. Bei deren Nichtvorhandensein würde es möglich sein, an einem Suffix-Blatt für eine gegebene Zeichenfolge zu starten und dann den Eltern-Hinweiszeigern zurück zu der Wurzel des Baums hin zu folgen, bis der Suffix- Knoten erreicht ist. Wie ersichtlich werden wird, wird das Suffix-Blatt für eine gegebene Symbol-Zeichenfolge einfach lokalisiert, da es das erste, unangepaßte Symbol ist, das einer Zeichenfolge folgt, wie beispielsweise die Zeichenfolge aXY (Fig. 8), die dahingehend bekannt ist, daß sie eine Anpassung besitzt, die an einer vorbestimmten Symbol- Position, p, in dem Suchfenster ihren Ursprung hat. Weiterhin kann der Suffix-Knoten für eine solche Symbol-Zeichenfolge unter Verwendung der Eltern-Hinweiszeiger identifiziert werden, um nach oben von dem Suffix-Blatt zu der Wurzel des Baums eine geeignete Anzahl von Niveaus zu bewegen, wie dies durch die Länge der Zeichenfolge bestimmt wird, die eingesetzt werden soll, um dadurch den Vorteil zu bewahren, keine Rückführung zu der Wurzel des Baums zum Einsetzen jeder Symbol-Zeichenfolge zu haben (wie ersichtlich werden wird, sind die Kosten zum Bewegen durch den Suchbaum nicht gleichförmig, da Kontroll- bzw. Zwischentafel-Durchsichten normalerweise erforderlich sind, um sich nach unten von Niveau zu Niveau zu den Suffix-Blättern zu bewegen). Immer wenn die maximal zulässige Kopie-Länge lang ist, ist dieser alternative, auf einem Zeichen-Folgen-Einsetzprozeß basierende Suffix-Knoten unerwünscht langsam in dem ungünstigsten Fall. Ähnlich ist, wenn manche Teile des Suchbaums 73 tief sind, eine übermäßig lange, durchschnittliche Aktualisierungszeit erforderlich, wenn sich alle Aktualisierungen zu der Wurzel des Baums ausbreiten müssen. Deshalb sind die Suffix- Verknüpfungen und die Perkulations-Aktualiserung gewöhnlich bevorzugt.
    • D. Erweiterte Ausführungsformen 1. Statistisch empfindliche Codierung
  • Wie ersichtlich werden wird, erfordert eine effektive Verwendung eines Literals mit festgelegter Länge und von Kopie-Codeworten eine sorgfältige Ausbalancierung der Länge solcher Codeworte gegenüber den durchschnittlichen Längen der Literals und Kopien in die die Quellen-Daten tendieren, sich zu zerlegen. Eine Erhöhung der Größe des Suchfensters tendiert dazu, die durchschnittliche Länge der Anpassungs-Symbol-Zeichen- Folgen zu erhöhen, die gefunden werden können, allerdings erhöht sich ebenfalls die Größe der Positions-Hinweiszeiger, die zum Spezifizieren der individuellen Symbol-Positionen innerhalb des Suchfensters erforderlich sind. Diese längeren Hinweiszeiger körnen die Kompression reduzieren, die erreicht wird, wenn sie ungeordnet eingesetzt werden, da die Hinweiszeiger, die auf die neueren Symbol-Positionen hinweisen, wahrscheinlicher sind, daß sie verwendet werden. Weiterhin sind kürzere Literals und Kopien wahrscheinlicher als längere Literals und Kopien. Demgemäß werden Literal- und Kopie- Worte mit statistisch sensitiver, variabler Länge vorteilhaft dazu verwendet, die vorliegende Erfindung auszuführen, wenn eine erhöhte Kompression erwünscht ist.
  • Verschiedene Techniken können zum Liefern solcher Codeworte mit statistisch sensitiver, variabler Länge eingesetzt werden. Zum Beispiel könnte eine adaptive Huffman-Codierung oder eine arithmetische Codierung der Literal-Längen und der Kopie-Längen und der Verschiebungen, die zu der Codier-Logik 74 (Fig. 3) hin berichtet werden verwendet werden. Allerdings ist eine solche Codierung allgemein langsam und es würde bloß zu einem sekundären, adaptiven Vorteil führen, da das Suchfenster mit festgelegter Länge des Kompressors 12 (Fig. 3) schon bewirkt, sich an die Quelle anzupassen. Eine noch andere Annäherung ist diejenige, eine erweiterte Familie einzigartiger Codeworte unterschiedlicher Bit-Längen zu der Codierung der Literals verschiedener Längen ebenso wie zu der Codierung der Kopien verschiedener Längen und Verschiebungen vorab zuzuordnen. In diesem Fall werden kurze Literals und kurze, naheliegende Kopien typischerweise durch Zuordnen relativ kurzer Codeworte zu diesen codiert, während längere Literals und längere und/oder weiter entfernt verschobene Kopien durch Zuordnen längerer Codeworte zu diesen codiert werden, um dadurch die Längen der Codeworte, die für ein vorbestimmtes Modell der Frequenzverteilung der Literal- und Kopie-Komponenten, in die sich eine durchschnittliche Quelle verlegt, zuzuschneiden. Eine repräsentative Familie gegenseitig unterscheidbarer Codeworte (siehe deren Einführungs-Indiktor-Bit- Sequenzen), die in der Länge von vier bis dreißig Bit-Längen reichen (siehe deren Größen), sind nachfolgend zusammen mit den Codier-Aufgaben, denen sie zugeordnet sind (siehe deren Namen- und Zeichen-Folgen-Länge, die durch sie innerhalb unterschiechcher Verschiebungsbereiche von einem Suchfenster mit 16k Länge abgedeckt sind), ebenso wie die Layouts, die diesen Codeworten ermöglichen, einzigartig die Literals und Kopien, zu denen sie zugeordnet sind (siehe die Codewort-Layouts, zu codieren angegeben:
  • Allerdings ist, um sich mit einem der wichtigeren Merkmale dieser Erfindung zu befassen, herausgefunden worden, daß eine von mehreren gerade ausgericheten und effektiven Techniken zur Erzeugung von Literal- und Kopie-Codeworten mit statistisch empfindlicher, variabler Länge diejenige ist, einen monadischen Codierer vorzusehen, wie beispielsweise ein solcher, der bei 91 in Fig. 10 dargestellt ist, zum Zuführen linearer Vorwärtsbewegungen von monadischen < Start, Schritt, Stop> Coden zum Darstellen der Längen der Literals und der Längen und Verschiebungen der Kopie. Wie gesehen werden wird, werden die Codier-Regeln oder Verfahrensweise durch eine Codier-Logik 92 die vor dem monadischen Codierer 91 angeordnet ist, erzwungen, allerdings ist ansonsten der Kompressor, der in Fig. 10 dargestellt ist, ausreichend ähnlich zu dem Kompressor, der in Fig. 3 dargestellt ist, um die Verwendung ähnlicher Bezugszeichen zu erlauben, um entsprechende Teile zu identifizieren.
  • Zu Zwecken der Definition weist ein monadischer (Start, Schritt, Stop) Code einen monadischen Code zum Spezifizieren der Bit-Länge des Felds auf, in dem die Länge des Literals oder die Länge oder Verschiebung der Kopie digital aufgezeichnet werden, gefolgt durch das Wert-Feld selbst. Das Wert-Feld wird wiederum so eingeschränkt, daß es keine wenigeren Bits enthält als die spezifizierte "Start" -Zahl und nicht mehr Bits als die spezifizierte "Stop" -Zahl enthält. Weiterhin variiert sich die Bit-Länge des Wert-Felds aufsteigend als lineare Funktion des spezifizierten "Schritt" -Parameters, um eine lineare Progression von Coden variabler Länge zu definieren. Deshalb weist das n-te Codewort eines solchen Codes n-1 "1", beendet durch eine einzelne "0", auf (d.h. der monadische Feldlängen-Indikator), gefolgt durch ein Wert-Feld einer Größe (Start + (n-1) Schritt). Ganze Zahlen werden sequentiell durch diese Differenzgrößen-Codeworte ausgelegt. Zum Beispiel sind die Codeworte der vier bestimmten Längen einer monadischen Code- Auflistung < 3,2,9> auf den ganzzahligen Zählnummern wie folgt:
  • Wie gesehen werden wird, kann der einzelne "0" Terminator für den monadischen Feldlängen-Indikator weggelassen werden, wenn die Bit-Länge des Wert-Felds gleich zu einer vorgegebenen "Stop" -Größe ist. Ein vereinfachtes berechnungsmäßiges Pseudo- Code-Verfahren zum Erzeugen monadischer Code ist in Appendix B angegeben, der hier unter Bezug darauf eingeschlossen wird, obwohl verständlich werden sollte, daß ein Tabellendurchsichtsverfahren eine lebensfähige Alternative zum Codieren monadischer Code ist. Weiterhin wird auch Appendix C unter Bezug darauf eingeschlossen, da er ein Cedar-Quellencode ist, der ein textorientiertes Substitutionsdatenkompressions-System auflistet, das eine monadische Codierung auf Literals und Kopien anwendet, die durch Zerlegung der Quellendaten gemäß den logischen Regeln, die vorstehend ausgeführt sind, identifiziert werden. Es sollte allerdings auch verständlich werden, daß eine monadische Codierung für verschiedene Typen von Lauf-Längen oder Zeichen-Folgen-Längen in Abhängigkeit einer Datenkompression zum Erfassen der Länge verwendet werden, über die die kompressible Kohärenz existiert (und/oder die Länge, über die die nicht kompressible Inkohärenz existiert) und in dem Fall eines textorientierten Datenkompressions-Systems vom Substitutions-Stil, und für die Stelle, an der die Redundanz gefunden werden kann. Allgemeiner gesagt kann eine monadische Codierung in einem digitalen Datenkompressions-System verwendet werden, um eine Codierung numerischer Werte variabler Länge, einschließlich Lauf-Längen, Kopie-Längen, Kopie-Verschiebungen, Literal-Längen, usw., zu liefern.
  • Wie ersichtlich werden wird, können verschiedene Faktoren die Auswahl der monadischen < Start, Schritt, Stop> Code zum Codieren der Literal-Längen und der Kopie-Längen und Verschiebungen der Daten, die komprimiert sind, gemäß den vorstehend beschriebenen Codier-Regeln beeinflussen. Zum Beispiel können, wie durch die vereinfachte, finite Zustands-Maschine (FSM), die in Fig. 11 dargestellt ist, ein monadischer Code < 2,1,10> zum Codieren einer Kopie-Länge eingesetzt werden, um dadurch die maximal zulässige Kopie-Länge auf 2044 Symbole zu begrenzen. Eine Kopie-Länge von Null signalisiert ein Literal; die Länge davon wird dann unter Verwendung eines monadischen Codes < 0, 1, 5> codiert, so daß die maximal zulässige Literal-Länge 63 Symbole beträgt. Wenn andererseits die Kopie-Länge nicht Null ist, kann die Kopie-Verschiebung mit einem monadischen Code < 10, 2, 14> codiert werden, um auf Kopien zu zeigen, die irgendwo innerhalb eines Suchfensters mit einer Breite von 21.504 Symbol-Positioner ihren Ursprung hat. In der Praxis werden die maximale Kopie- und Literal-Längen typischerweise so ausgewählt, um verschwendete Zustände in den monadischen Progressionen zu vermeiden. Eine ähnliche Technik wird manchmal auch zum Vermeiden verschwendeter Zustände in der monadischen Codierung von Kopie-Verschiebungen verwendet.
  • Die monadischen Code, die eingesetzt werden, können auch verfeinert werden (nicht dargestellt), um verschwendete Zustände zu vermeiden. Zum Beispiel stellen die früher beschriebenen Regeln zum Zerlegen von Quellen-Daten in Literals und Kopien sicher daß ein Literal geringer als eine maximal zulässige Literal-Länge niemals unmittelbar von entweder einem anderen Literal oder einer Kopie einer Länge von zwei gefolgt wird. Demzufolge kann, immer wenn ein solches Literal mit einer nicht maximalen Länge codiert wird, der Code < 2, 1, 10> nach unten um zwei für die Codierung der Kopie verschoben werden, die einem solchen Literal folgt, mit dem Ergebnis, daß ein Code-Wert von Null dann eine Kopie-Länge von drei bedeutet, ein Code-Wert von eins eine Kople-Länge von vier bedeutet, usw..
  • Eine andere Verfeinerung des Werts während des Startens ist diejenige, in der Kopie- Verschiebungs-Codierung abzustimmen, wenn das Suchfenster gefüllt wird. Zum Beispiel kann eine solche Abstimmung bzw. Synchronisierung unter Verwendung eines monadischen Codes < 10-x, 2, 1-x> für Kopie-Verschiebungen realisiert werden, wobei x anfänglich gleich zehn gesetzt wird und dann auf Null erniedrigt wird, um, und wie es erforden ich ist, den Verschiebungs-Zeiger freizugeben, um alle Fensterpositionen zu identitizieren, die zuvor komprimierte Symbole enthalten.
  • Eine noch weitere Technik, die verwendet werden kann, um verschwendete Zustände in der Kopie-Verschiebungs-Codierung zu vermeiden, ist diejenige, das größte Feld in seiner monadischen Progression zu schrumpfen, bis es gerade groß genug eingestellt ist um eine Familie von "sparsamen" bzw. "dünnen" Codeworten für eine einzigartige Identifizierung jedes der unterschiedlichen Verschiebungs-Werte, für die von dem Feld gefordert wird, sie darzustellen, zu liefern. Demzufolge bewirkt, wenn dort insgesamt v-Werte vorhanden sind, die in dem größten oder "Stop"-Größenfeld eines monadischen Codes von < 10-x, 2, 14-x> codiert werden sollen, eine "sparsame Codierung" dieses Felds, das die kleineren dieser v-Werte mit log&sub2; v Bits codiert werden sollen und die größeren davon mit log&sub2; v Bits codiert werden sollen. Wie ersichtlich werden wird, vermeidet eine solche sparsame Codierung das Erfordernis zur Verwendung von 14-x Bits zum Codieren jedes der v-Werte, um dadurch die Bit-Größe der Kopie-Codeworte mit den Größenverschiebungs-Werten zu reduzieren.
  • Um weiterhin diese sparsame Codier-Technik darzustellen, wird die Codierung eines von sechs Werten betrachtet. Wenn ein 3-Bit-Feld zum Codieren des Werts verwendet wird werden zwei der acht möglichen Zustände 2 verschwendete Zustände sein. Allerdings sind dort keine verschwendeten Zustände vorhanden, wenn die Werte 0 und 1 in 2 Bits und die Werte (2..5) in 3 Bits wie folgt codiert werden:
  • Typische sparsame Codier- und Decodier-Verfahren sind nachfolgend angegeben:
  • Codieren: PROC [value, nFeeValues, nBits: CARDINAL] = { IF value < nFreeValues THEN Output[value, nBits - 1] ELSE Output[value + nFreeValues, nBits];
  • Decodieren: PROC [nFreeValues, nBits: CARDINAL] RETURNS [value: CARDINAL] = {
  • IF nFreeValues = 0 THEN valueE Input[nbits) ELSE { valueEInput[nBits - 1]; IF value > = nFreeValues THEN valueEvalue + value - nFreeValues + Input[1]; };
    • 2. Schnellere Kompressoren
  • Die vorstehenden Kompressoren formatieren die komprimierten Daten so, daß sie relativ schnell mittels Expander expandiert werden können, die eine begrenzte Speicherkapazität besitzen, wie beispielsweise der Expander 63 (Fig. 5). Deshalb sind sie besonders gut für Anwendungen geeignet, wo die Kompressionsgeschwindigkeit weniger wichtig als eine Vereinfachung des Designs und eine Optimierung der Funktion des Expanders ist, wie beispielsweise dann, wenn es erwünscht ist, eine Massenfreigabe von Software in einer komprimierten Form auf Floppy-Disks zur Verteilung zu und zum Expandierer durch die Endbenutzer zu erzeugen. Zusätzlich eignen sich die vorstehenden Kompressoren selbst für eine natürliche und annehmbare, richtungsbetriebene Hardware-Umsetzung. Zum Beispiel wird in einer VLSI-Hardware-Ausführungsform der Suchbaum eliminiert und durch eine Anzahl von Kom paratoren ersetzt, die simultan auf vielen Zeichen in dem Suchfenster arbeiten, um die längste Anpassung zu bestimmen. In geeigneter Weise werden die Symbole, die durch das Suchfenster enthalten sind, auf einem Halbleiterspeicherchip gespeichert, so daß keine externen Speicherreferenzen erforderlich sind, während die längste Anpassung bestimmt wird. Teilweise dadurch, daß keine externen Speicherreferenzen erforderlich sind, kann diese Art eines Kompressors extrem schnell laufen und eine exzellente Kompression bei einer breiten Vielfalt von Daten erreichen. Zusätzlich hat sie, da sie auf einen einzelnen Chip paßt Vorteile bei Anwendungen, wo eine "alleinstehende" Daten-Kompressionsfunktion erwünscht ist, ohne irgendein Erfordernis für Berechnungsfunktionen für allgemeine Zwecke.
  • Allerdings sind andere Situationen vorhanden, in denen schnellere Software-Kompressoren bevorzugt sein können, wie beispielsweise dann, wenn Files in einer komprimierten Form archiviert werden sollen. Demzufolge können mit einer noch anderen Ausführungsform der vorliegenden Erfindung die Kompressionsgeschwindigkeiten des vorstehend beschriebenen Codeworts mit festgelegter Länge und Ausführungsformen mit monadisch codiertem Codewort mit variabler Länge der vorliegenden Erfindung wesentlich durch Begrenzung von Kopien erhöht werden, um an einer Grenze zu beginnen, die durch das Anfangssymbol einer früheren Kopie oder durch ein Symbol, das zuvor in dem komprimierten Datenstrom als ein Literal eingesetzt wurde, definiert ist. Im Gegensatz dazu, daß man ein Blatt in einem Such-Baum 73 (Fig. 3) für jedes Symbol in dem Suchfenster, wie bei den zuvor beschriebenen Kompressionen, besitzt, besitzen diese schnelleren Ausführungsformen der Erfindung nur ein Blatt in dem Suchbaum 73 für jedes Kopie-Codewort und für jedes Literal. Dies reduziert die Berechnung, die erforderlich ist, um den Baum 73 zu durchsuchen und zu aktualisieren, um dadurch wesentlich die Kompressionsgeschwindigkeit für durchschnittliche Daten zu erhöhen. Anpassungen, die an den zweiten oder darauffolgenden Symbolen einer früheren Kopie entspringen, werden ignoriert, so daß die "längste, variable Anpassung" die längste Anpassung irgendwo innerhalb des Suchfensters sein kann oder nicht sein kann. Es wird deshalb ersichtlich werden, daß die erhöhte Kompressionsgeschwindigkeit, die durch diese Maßnahme erzielt wird, auf Kosten der Verlangsamung der Rate erzielt wird, unter der sich das System auf Änderungen in den Quellen-Daten anpaßt. Zusätzlich wird aus Gründen, die noch ersichtlich werden, der Komplementär-Expander für diese schnelleren Kompressoren etwas verlangsamt und erfordert mehr Speicher.
  • Einer der Vorteile einer Begrenzung aller Kopien, um von einer früheren Kopie oder einem Literal auszugehen, ist derjenige, daß die Positions-Hinweiszeiger zum Lokalisieren der früheren Erscheinungen oder Wiedererscheinungen von Symbol-Zeichen-Folgen komprimiert werden können, da sie nur in der Lage sein müssen, den Beginn des y-ten früheren Codeworts oder Literal-Zeichens, das abgegeben ist, zu identifizieren. Zum Beispiel können "komprimierte Verschiebungen" wie folgt ausgeführt werden: Erstens wird ein Feld aus Speicherelementen einer Länge gleich der Fenstergröße zum Speichern von Hinweiszeigern in dem Kompressor-Eingangspuffer vorgesehen. Jedes Element dieses Felds zeigt auf ein unterschiedliches der Kopie-Codeworte oder Literal-Zeichen, die durch den Kompressor ausgegeben werden, so daß dort eine Übereinstimmung eins zu eins zwischen Blättern in dem Suchbaum 73 und Elementen in diesem Feld vorhander ist, und jeder innere Knoten in dem Baum identifiziert das Feldelement, das einem der absteigenden Blätter entspricht. Als nächstes werden Kopie-Verschiebungen in Einheiten der Anzahl der Feldelemente zwischen dem einen, das dem Blatt der angepaßten Symbol-Zeichenfolge entspricht (d.h. die Symbol-Zeichenfolge, für die die Kopie substituiert werden soll), und einem Feldelement, das dem Blatt oder dem inneren Bogen, auf dem die längste Anpassung gefunden wurde, entspricht, gemessen. Anders ausgedrückt werden Kopie-Verschiebungen in einem "Fenster mit festgelegter Länge", wie irden früheren Ausführungsformen, gemessen, allerdings wird die Position in dem Zeichenpuffer des Blatt-Symbols eines früheren Auftretens einer wieder auftretenden Symbol-Zeichenfolge durch "indirektes" Gehen durch dieses Feld der Hinweiszeiger im Gegensatz zu einem direkten Adressieren der "Suchfenster" -Symbol-Positionen bestimmt. Demzufolge ist die Größe des Referenz-Hinweiszeiger-Felds festgelegt, allerdings kann die Länge des Suchfensters in Abhängigkeit von der Zusammensetzung der zuvor komprimierten Daten erweitert oder zusammengezogen werden. Kopie-Längen werden noch in Symbolen gemessen, so daß die vorangegangene Beschreibung der Messung und Codierung der Kopie-Längen bei diesen modifizierten Ausführungsformen anwendbar ist. Appendix D, der hier unter Bezug darauf eingeschlossen wird, ist ein Cedar-Quellen- Code, der ein Kompressions-System basierend auf den vorstehend beschriebenen Kompressions-Regeln in Kombination mit komprimierten Verschiebungen und einer monadischen Codierung auflistet.
  • Symbol-Zeichen-Folgen werden in die Such-Bäume 73 (Fig. 3) dieser schnelleren Kompressoren durch Starten an der Wurzel des Baums bei jeder iteration eingesetzt. Die Zeichen-Folgen können in einer linearen Zeit eingesetzt werden, da sie nur an bestehenden Codeworten/Literal-Zeichen-Grenzen eingesetzt werden. Suffix-Hinweiszeiger und sich ausbreitende Aktualisierungen sind nicht notwendig, so daß der Suchbaum 73 (Fig. 3) für diese Ausführungsformen ein relativ einfacher PATRICIA-Baum (siehe Fig. 7A-7E) ist. Es sollte allerdings angemerkt werden, daß es nützlich ist, ein Feld aus permanenten Knoten für alle Symbole bei einer Tiefe von 1 eines Suchbaums 73 eines PATRICIA-Stils für diese Ausführungsformen zu kreieren. Dies kann vorgenommen werden, gerade obwohl das Suchfenster nicht ein Symbol entsprechend jedem dieser permanenten Knoten zu allen Zeitpunkten enthält, da eine Kopie einer Länge von 1 niemals ausgegeben wird. Wenn ein solches permanentes Feld aus Knoten für den Suchbaum 73 vorgesehen wird, können Symbol-Zeichen-Folgen in den Baum durch irdizieren in das permanente Knoten-Feld basierend auf dem ersten Symbol der Zeichenfolge, die eingesetzt werden soll, eingesetzt werden. Danach beruht der Einsetzprozeß typischerweise auf unerwünschten Tafel-Durchsichten und Bogen-Vergleichen, um tiefer in den Baum abzusteigen, wie dies zuvor in Verbindung mit der Verwendung der Suchbäume vom PATRICIA-Stil allgemein beschrieben ist. insoweit als alle Knoten auf den Suchpfad für irgendeine Symbol-Zeichenfolge, die in dem Baum eingesetzt ist, hindurchgeführt werden, während die Zeichenfolge eingesetzt wird, können die aktualisierten Suchfenster-Symbol-Positionen für die Symbole, die durch diese Knoten dargestellt werden, in die Positions-Felder dieser Knoten eingeschrieben werden, während tiefer in den Baum während des Einsetz-Prozesses abgestiegen wird.
  • Ein Zwang für Kopien, daß sie mit Symbolen im Ursprung beginnen, die vor Kopie-Codeworten beginnen, oder mit Symbolen, die durch frühere Literals enthalten sind, reduziert die Fähigkeit dieser modifizierten Kompressoren, die lokale Kohärenz der Quellen-Daten zu erfassen, allerdings ermöglicht die Verwendung von komprimierten Hinweiszeigern einer relativ anspruchslosen Bit-Größe zum Zurückreichen relativ weit in die zuvor komprimierten Quellen-Daten, um es dadurch durchführbar zu gestalten, größere Suchfenster zu verwenden, um längere Anpassungen zu erzielen. Dies ist vorteilhaft für Quellen- Daten, die eine natürliche Wortstruktur, wie beispielsweise einen Text, besitzen. Allerdings kann in Bezug auf die vorstehende Einschränkung bzw. den Zwang befunden werden, daß er für die Kompression von Quellen-Daten unerwünscht ist, die einen wesentlichen Umfang einer höchst lokalisierten Kohärenz, wie sie gewöhnlicherweise existiert, zum Beispiel dann, wenn die Quelle eine abgetastete Abbildung darstellt, haben.
    • 3. Zusätzliche Variation
  • Verschiedene Variationen in Bezug auf diese Schemata können zur Aktualisierung des Suchbaums 73 (Fig. 3) häufiger als auf jeder früheren Kopielliteral-Grenze eingesetzt werden. Zum Beispiel könnte ein Blatt zu dem Suchbaum 73 zwischen den Symbolen hinzugefügt werden, die durch jedes Kopie-Codewort der Länge 2 dargestellt werden, und/oder ein Blatt könnte in den Suchbaum dem End-Symbol jeder Symbol-Zeichenfolge folgen, die durch ein Kopie-Codewort einer Länge 3 dargestellt ist. Anstelle irgendeiner Variation eines Einsetzens von Blättern in den Baum zwischen den Extremen, die durch die vorangehenden Kompressoren (in einem davon wird ein Blatt in den Baum für jedes Symbol eingegeben und in dem anderen davon wird ein Blatt einmal pro Kopie- Codewort und einmal pro Literal-Zeichen eingegeben) dargestellt sind, innerhalb des allgemeinen Netzwerks dieses Verfahrens durchführbar. Eine gewisse erhöhte Kompression ist dahingehend wahrscheinlich, daß sie unter Verwendung dieser und anderer Techniken zur Erhöhung der Fähigkeit dieser schnelleren Kompressions-Systeme erreicht wird, die lokale Kohärenz der Quellen-Daten zu erfassen, allerdings würde deren Kompressions- und Expansions-Geschwindigkeit reduziert werden. Es sind auch Variationen vorhanden, bei denen der Baum an einem gewissen Punkt eingefroren und nicht aktualisiert wird, so daß zusätzliche Quellen-Symbole danach als Kopien und Literals auf der Basis der statischen Datenstruktur des Suchbaums codiert werden, allerdings wird der Baum nicht für die Zeichenfolge, die gerade codiert ist, aktualisiert. In diesem Fall fällt die Kompression aus, und zwar aufgrund nicht stationärer Statistiken der Quellen-Daten, allerdings kann ein zyklisches Durchlaufen des Baums fortgesetzt werden, falls dies benötigt wird. Diese Maßnahme könnte in Anwendungen verwendet werden, wo die höchste Geschwindigkeit erforderlich ist, obwohl sie dahingehend wahrscheinlich ist, daß sie zu einer geringeren Kompression führt.
  • Dabei sind auch Variationen bei jedem der zwei vorstehenden Verfahren vorhanden, bei denen das Fenster mit nützlichen Symbolen vorgebildet oder initialisiert wird, so daß die Kompression des frühesten Teils der Quelle verbessert werden kann Während dies dahingehend wahrscheinlich ist, die Kompression zu verbessern, wenn die Quellen-Daten die vorgebildeten Daten abgleichen, sind sie leicht komplexer und werden eine Kompression verschlechtern, wenn die Quellen-Daten nicht die vorgebildeten Daten abgleichen.
  • Zusätzlich zu Variationen dann, wenn Zeichen-Folgen zu dem Suchbaum hinzugefügt oder davon entfernt werden, sind Variationen in Bezug auf Daten-Strukturen vorhanden, die in einer Software-Ausführungsform verwendet werden. In Appendix C hat man einen Suffix-Baum verwendet, in dem die Bögen in einer verketteten, zirkularen Kontrollsummen-Tabelle eingesetzt sind. Es wird ersichtlich werden, daß in einer Hardware-Ausführungsform kein Baum erforderlich ist und nur das Fenster selbst zentral in Bezug auf das Kompressionsverfahren ist. Es wird auch ersichtlich werden, daß in einer Software-Ausführungsform viele andere Arten von Störtabellen, Listen oder anderen Daten-Strukturen verwendet werden können, um einen Suffix-Baum auszuführen. Weiterhin wird ersichtlich werden, daß der Suffix-Baum durch den einfacheren PATRICIA-Baum ersetzt werden könnte, obwohl man glaubt, daß diese Ausführungsform nicht so gut ist; oder er könnte durch einen binären Baum, eine sortierte Liste oder eine andere Daten-Struktur ersetzt werden. Solche Variationen sind auch für Appendix C möglich. Alle diese Variationen liegen innerhalb der Fähigkeiten eines Fachmanns auf dem Fachgebiet des Programmierens.
  • Zusätzlich wird ersichtlich werden, daß, während die Ausführungen in den Appendizes A, C und D Symbole oder Zeichen mit 8 Bit einsetzen, es möglich ist, äquivalente Kompressoren einzusetzen, die andere Symbol-Größen verwenden.
  • Darüberhinaus wird auch verständlich werden, daß, während die Ausführungsformen in den Appendizes A, C und D "mächtig" in dem Sinne sind, daß sich deren Kopie-Codeworte immer auf die längste Anpassung bezieht, die in dem Fenster gefunden ist, es innerhalb der Fähigkeiten eines Fachmanns auf dem betreffenden Fachgebiet liegt, eine Variation vorzunehmen, bei der eine Anpassung kürzer als die längste Anpassung manchmal codiert wird, falls sie durch ein kürzeres Codewort als die längste Anpassung dargestellt werden kann. Eine solche Variation ist dahingehend wahrscheinlich, daß sie langsamer als die "mächtigen" Gegenstück-Verfahren sind, allerdings kann sie eine gering höhere Kompression im Durchschnitt erreichen (und in dem ungünstigsten Fall kann sie eine viel höhere Kompression erreichen).
  • Weiterhin setzen die zwei vorstehenden Kompressoren bestimmte Taktiken zum Auswählen zwischen Kopie- und Literal-Codeworten und zum Entscheiden, an welchem Punkt ein Literal-Codewort zugunsten einer Kopie enden soll, ein. Es wird ersichtlich werden, daß viele andere Taktiken möglich sind und der Einsatz irgendwelcher von diesen innerhalb der Fähigkeiten eines Fachmanns auf dem betreffenden Fachgebiet liegt.
  • Schließlich ist es, während die Ausführungsform des Appendix C eine Kopie-Länge und Verschiebung, die unabhängig monadische < Start, Schritt, Stop> Code einsetzt, möglich, Variationen zu verwenden, wo die monadische oder eine andere Codierung einer Kopie-Länge abhängig von der schon codierten Kopie-Verschiebung ist oder wo die monadische oder eine andere Codierung der Kopie-Verschiebung von der bereits codierten Kopie-Länge abhängig ist. Tatsächlich werden sich noch andere Variationen selbst ergeben, einschließlich der Verwendung eines einzelnen Präfix-Codes zum Bestimmen der Codierung sowohl einer Kopie-Länge als auch einer Kopie-Verschiebung (siehe die Codierung mit festgelegter Länge, die vorstehend besprochen ist). Alle diese Variationen liegen innerhalb der Fähigkeiten eines Fachmanns auf dem Fachgebiet der Programmierung und besondere Auswahlen würden durch die Einfachheit der Ausführung und die statistischen Charakteristika der jeweiligen Quellen-Daten-Abtastungen geleitet.
    • 4. Verbesserung des Kompressions-Verhältnisse
  • Die Codierung der komprimierten Daten durch die vorstehend beschriebenen Kompressoren ist weniger optimal, da die komprimierten Daten mehrfach kopierte Fälle identischer Symbol-Zeichen-Folgen innerhalb der adressierbaren Spannweite des Suchfensters enthalten können, gerade obwohl nur ein Fall jeder Symbol-Zeichenfolge erforderlich ist, um zu ermöglichen, daß alle notwendigen Kopien hergestellt werden. Die Suchbaum-Daten-Strukturen verschwenden allerdings keinen Raum, da ein Wiederauftreten von Symbol-Zeichen-Folgen gemeinsame Suchpfade innerhalb davon gemeinsam teilen.
  • Deshalb kann, um das Kompressions-Verhältnis zu verbessern, die Codierung unter Verwendung von Kopie-Codeworten durchgeführt werden, die direkt auf der Suchbaum- Daten-Struktur begründet sind, wie beispielsweise die Struktur eines PATRICIA-Baums (Fig. 7A-7E). Zum Beispiel kann ein Präfix mit einem einzelnen Bit ("0" oder "1") zum Unterscheiden zwischen Kopie-Codeworten die Anpassungen, die auf irgendeinem der Blätter eines solchen Baums (eine LeafCopy) enden, und Anpassungen, die auf inneren Bögen des Baums (eine NodeCopy) enden, darstellen. Identische Suchbäume werden in dem Kompressor und in dem Expander konstruiert, wobei der Expander die Codeworte verwendet, die er von dem Kompressor empfängt, um den Baum, der durch den Kompressor konstruiert ist, nachzubilden. Wie gesehen werden wird, enthält jedes LeafCopy- und NodeCopy-Codewort zwei Elemente einer Information zum Spezifizieren der Symbol-Zeichenfolge, die es darstellt: einen Knoten oder ein Blatt und eine Bogen-Verschiebung (die Verschiebung, die erforderlich ist, da der Bogen eines PATRICIA-Baums mehr als ein Symbol darstellt). Es sollte verständlich werden, daß die Zeichen-Folgen, die zwei oder mehrere Male innerhalb der Spannweite des Suchfensters erscheinen, als ein einzelner Knoten-Bogen erscheinen, so daß sie als NodeCopy mit keiner Redundanz in deren Codierung komprimiert sind.
  • Insbesondere folgt, wenn eine NodeCopy aufgerufen wird, deren identifizierender Präfix durch eine Knoten-Nummer, die sich auf den nächsten, freien Knoten innerhalb eines Bereichs [0... maxNodeNo) bezieht, wobei maxNodeNo die größte Knotennummer ist, die seit einer Initialisierung des Kompressions-Systems verwendet ist. Dann wird die Bogen-Verschiebung basierend auf der Zahl der Symbole auf dem ankommenden Bogen codiert. Wenn, wie dies oftmals der Fall ist, nur ein einzelnes Symbol auf dem ankommenden Bogen vorhanden ist, kann die Verschiebung daraus gefolgert durch Unterdrükken des Längen-Felds codiert werden. Allerdings wird, wenn der ankommende Bogen eine Vielzahl von Symbolen darstellt, ein Längenfeld an die Knoten-Nummer zum Wiederaufzeichnen eines Werts angehängt, der die Stelle entlang des Bogens angibt, an dem die Anpassung aufgetreten ist. Typischerweise ist der aufgezeichnete Wert 0 für eine Anpassung, die exakt an dem neuen Knoten auftritt, 1 für eine Anpassung, die an einer Verschiebung eines Symbols nach unten von seinem Eltern-Knoten auftritt, 2 für eine Anpasssung, die zwei Symbole nach unten von dem Eltern-Knoten auftritt, usw.. In geeigneter Weise wird ein spärlicher Code zum Codieren der NodeCopy-Bogen-Verschiebungen eingesetzt, so daß die Längen-Felder dieser Codeworte gewöhnlich aus nur einem oder zwei Bits zusammengesetzt sind.
  • Andererseits wird, wenn eine LeafCopy für ihren identifizierenden Präfix aufgerufen wird, durch ein monadisch codiertes Längen-Feld (1,1,11) (eine solche monadische Progression kann Bogen-Längen bis zu 4094 Symbolen lang codieren) zum Spezifizieren des Abstands nach unten des Blatt-Bogens von dem Eltern-Knoten, bei dem die Anpassung beendet ist (mit einer Bogen-Verschiebung von 0, die ein Literal bezeichnet), gefolgt. Dem Längen-Feld einer LeafCopy folgen die, die einen Bogen-Verschiebungs- Wert von nicht 0 besitzen (d.h. eine solche, die nicht ein Literal bezeichnet) wird die Suchfenster-Symbol-Position des voranführenden Symbols der Anpassungs-Symbol- Zeichenfolge codieren; vorzugsweise durch graduelle Phasenanpassung in einer anderen, geeigneten monadischen Progression, wie beispielsweise die Progression < 10-x, 2, 14-x> , die vorstehend beschrieben ist.
  • Literals, die geeignet sind, werden einzigartig durch Einsetzen einer LeafCopy identifiziert, die eine Bogen-Verschiebung von 0 als deren Einführungs-Bit-Sequenz oder "Zeichen" bzw. "Flag" besitzen. Solchen Einführungs-Zeichen-Bits folgt ein Längen-Feld, in das die Länge des Literals codiert wird, und zwar unter Verwendung noch einer anderen monadischen Progression < Start, Schritt, Stop> , wie beispielsweise ein Code < 0, 1, 5> . Die Codier-Regeln verhindern ein Literal geringer als eine maximal zulässige Länge, daß ihm unmittelbar ein anderes Literal folgt, so daß die monadischen Code für die Bogen- Verschiebung einer LeafCopy, die unmittelbar nach einem solchen Literal kopiert ist, nach unten um 1 verschoben werden kann, so daß eine Bogen-Verschiebung von 1 dann als 0 codiert wird, eine Verschiebung von 2 als 1 codiert wird, usw..
  • Knoten-Nummern für NodeCopies werden unter Verwendung einer spärlichen Codierung für die Werte < 0... maxNodeNo> codiert, gerade obwohl es erwünscht sein könnte, sie gemäß einem kurz zuvor verwendeten (LRU) Auswahl-Algorithmus zu managen und eine Codierung einzusetzen, die die Anzahl von Bits reduziert, die erforderlich ist, um noch kürzer vorher verwendete Knoten zu identifizieren. Wie ersichtlich werden wird, könnte ein solches Knoten-Handhabungs- und Codierschema unter der Diskretion des Designers ausgeführt werden.
  • Wie zuvor hervorgehoben ist, muß, um die Daten zu dekomprimieren, der Expander für diese Ausführungsform einen Suchbaum rekonstruieren und aufrechterhalten, der identische Suchpfade zu denjenigen des Kompressor-Suchbaums während der Kompression/Expansion der entsprechenden Bereiche der Quellen-Daten enthält. Im Gegensatz zu dem Kompressor allerdings ermöglichen die Codeworte, die zu dem Expander zugeführt werden, ihm die Länge jeder Kopie zu bestimmen und unmittelbar die Eltern irgendwelcher neuen Knoten zu lokalisieren, die zu dem Baum hinzugefügt werden. Demzufolge sind keine Kontrollsummen-Tabellen zum Einsetzen von Symbol-Zeichen- Folgen in den Baum an dem Expander erforderlich, vorausgesetzt, daß die Codier-Taktik so begrenzt ist, daß eine Kopie immer ausgewählt wird, wenn sich die längste Anpassung zwei oder mehr Symbole weit spannt. Mit dieser Einschränkung auf die Codier- Taktik kann der Expander den Baum rekonstruieren, indem jedes neue Blatt von dem Knoten oder dem Bogen, der durch das bestimmte NodeCopy- oder LeafCopy-Codewort angegeben wird, das er decodiert hat angehängt wird. Weiterhin kann in dem Fall eines decodierten Literals der Expander das Blatt von der permanenten Tiefe oder dem Knoten des Niveaus 1 für das Literal-Symbol anhängen (falls es wieder aufgerufen wird, wird ein Knoten einer permanenten Tiefe 1 vorteilhaft jedes Quellen-Symbol vorgesehen).
    • E. Repräsentative, funktionale Flußdiagramme
  • Um die vorstehende Beschreibung zu stützen, werden nachfolgend repräsentative, funktionale Flußdiagramme beschrieben werden. Während diese Diagramme vereinfacht sind und für bestimmte Ausführungsformen spezifisch sind, werden sie ein allgemeines Gerüst für Personen liefern, die in Bezug auf das Ausführen der Erfindung der verschiedenen Formen interessiert sind. In einem inverfierbaren oder verlustfreien Kompresssions-System ergänzt der Expander notwendigerweise den Kompressor, so daß die funktionalen Funktions-Charakteristika des Kompressors stark die Funktions-Erfordernisse des Expanders vorgeben. Einige der vorstehend beschriebenen Kompressoren ermöglichen eine direkte Adressierung aller Symbole innerhalb des Suchfensters zum Lokalisieren früherer Auftretungen wieder auftretender Symbol-Zeichen-Folgen, während andere solche früheren Auftretungen durch indirekte Adressierung bestimmter Symbole innerhalb des Suchfensters lokalisieren (d.h. solche, die vor Codeworten beginnen, oder die zuvor als Literals ausgegeben sind) durch die Verwendung eines Felds von Hinweiszeigern oder durch Codierung der Baum-Struktur. Die Codierung und Decodierung der Baum-Struktur für die Kompression und Expansion der Quellen-Daten wird geringfügig stärker eingesetzt als die direkte oder indirekte Adressierung der Suchfenster-Inhalte, so daß eine Baum-Struktur-Codierung und -Decodierung in den nachfolgenden Flußdiagrammen ausgeführt wird.
    • 1. Lokalisieren und Erweitern einer Anpassungs-Symbol-Zeichenfolge
  • Wie die Fig. 12 zeigt, verwenden alle Strom-Kompressoren im wesentlichen denselben Prozeß zum Beibehalten deren Suchbäume 73 (Fig. 3) und zum identifizieren früherer Auftretungen wieder auftretender Symbol-Zeichen-Folgen. Wenn sie wieder aufgerufer werden. "ziehen" File-Kompressoren Quellen-Symbole von einem File im Gegensatz dazu, daß sie die Quellen-Symbole an ihnen "hineingeschoben" besitzen, allerdings setzen sie ansonsten Symbol-Zeichen-Folgen in deren Suchbäume ein und halten deren Suchbäume im wesentlichen in derselben Art und Weise wie deren Strom-Kompressor-Gegenstücke aufrecht. Die "Strom" -Ausführungen der vorliegenden Erfindung sind so aufgebaut, daß sie eine standardmäßige "Strom" -I/O-Interface-Spezifikation erfüllen, so daß sie leicht mit anderen Strom-Prozeduren verknüpft werden können, wie beispielsweise Daten-Verschlüsselungs- und -Entschlüsselungs-Programme und Daten-Kommunikations-Protokolle.
  • Appendix E, der hier unter Bezug darauf eingeschlossen wird, gibt Prozeduren an, die dazu erforderlich sind, Strom-Kompressions- und -Expansions-Funktionen zu liefern, die mit den vorstehend erwähnten I/O-Spezifikationen konsistent sind (die über den Schutzumfang der Erfindung hinausgehen). Wenn ein Kompressions-Software-Package durch das Betriebssystem eingeladen wird, richtet es sich selbst mit einer Kompressions-Verfahrens-Ausrichtung (nicht dargestellt) aus, so daß die Prozeduren durch das Verfahren geliefert werden, auf die durch Clients zugegriffen werden kann (d.h. Daten Quellen und -Senken, die für Serviceleistungen des Kompressions-Systems erforderlich sind). Um eine Kompression auszuführen, initialisiert ein Client zuerst die Daten-Strukturen, die durch den Kompressor benötigt werden, mittels einer "CreateEncodingStream" -Prozedur; ein Argument bzw. ein Parameter zu dem Createencodingstream ist eine Ausgangs-Strom-Prozedur, zu der Codeworte, die die Quelle darstellen, geschickt werden. Darauffolgend liefert der Client Blöcke aus Zeichen für eine Kompression unter Verwendung einer "CSUnsafePutBlock" -Prozedur oder liefert einzelne Zeichen unter Verwendung einer "CSPutChar" -Prozedur. Während des Ablaufs einer Komprimierung einer Sequenz von Quellen-Symbolen akkumuliert der Kompressor Codeworte in seinem Ausgangspuffer, allerdings wird er andere Symbole haben, die in seinen inneren Daten- Strukturen dargestellt sind, für die er bis jetzt noch nicht Codeworte erzeugt hat.
  • Demzufolge ruft er, wenn zu irgendeinem Zeitpunkt der Client wünscht, eine Codierung aller Symbole, die bis jetzt noch nicht durch Codeworte dargestellt sind, zu erzwingen, und um alle diese Codeworte so zwangszuführen, so daß sie zu dem Ausgangs-Strom geschickt werden, eine "CSFlush" -Prozedur auf. CSUnsafePutBlock, CSPutChar und CSFlush können wiederholt in irgendeiner Reihenfolge aufgerufen werden. Schließlich kann, wenn der Client unter Verwendung des Kompressors beendet hat und ein abschließendes Csflush abgegeben hat, er den Speicher freigeben, der durch den Kompressor verwendet wurde, und zwar unter Aufrufen einer "CSClose" -Prozedur.
  • Analog besitzt der Expander eine "CreateDecodingStream" -Prozedur, für die ein Argument der Eingangs-Strom ist, von dem Codeworte erhalten werden sollen. Er besitzt auch eine "ESUnsafeGetBlock" -Prozedur, die aufgerufen werden kann, um Blöcke hicht komprimierter oder decodierter Quellen-Symbole zu erhalten, und eine "ESGetChar" -Prozedur, die aufgerufen werden kann, um einzelne, nicht komprimierte Quellen-Symbole zu erhalten. Weiterhin besitzt der Expander eine "ESClose" -Prozedur, die den Speicher freigibt, den er verwendet hat.
  • Wenn das Strom-Kompressions-System verwendet wird, um einen File zu komprimieren wird CSFlush nur einmal an dem Ende des Files verwendet. Csflush produziert normalerweise entweder eine PadCopy oder ein PadLiteral-Codewort, wie dies nachfolgend besprochen wird. Diese Codeworte sind der prinzipielle Unterschied zwischen dem Strom- und dem File-Kompressor. Da diese Codeworte einer sehr niedrigen Wahrscheinlichkeit zugeordnet sind, ist die Codierung, die durch den Strom-Kompressor verwendet wird, fast identisch zu derjenigen, die durch einen äquivalenten File-Kompressor verwendet werden würde, und die Kompression wird fast identisch ausgeführt. Es wird verständlich werden, daß der prinzipielle Vorteil eines Strom-Kompressors derjenige ist, daß er in anderen Anwendungen neben einer File-Kompression verwendet werden kann, wie dies zuvor diskutiert wurde.
  • Um sich nun der CSUunsafeputblock-Prozedur des Kompressors zuzuwenden, die diagrammartig in Fig. 12 dargestellt ist, besteht der Suchbaum anfänglich aus Knoten einer permanenten Tiefe 1, einem leeren Fenster und einem leeren Eingangs-Zeichen-Puffer; die Tiefe der momentanen Anpassung ist 0. Wenn Zeichen zur Kompression durch CSUnsafePutBlock oder CSPutChar geliefert werden, wächst der Baum an und das Fenster füllt sich, bis einer von seinen drei Resourcen erschöpft ist; diese Resourcen sind durch Größen-Parameter maxCopyDisp (die Anzahl der Blätter- oder Fenster-Positionen in dem Baum), maxNodes (die maximale Anzahl von Knoten, die in dem Baum zugelassen sind) und oBufsize (die maximale Größe des Eingangs-Zeichen-Puffers) definiert sind. Die Werte für maxNodes und obufsize werden normalerweise so ausgewählt, daß die meisten Quellen-Daten die maxCopyDisp-Blätter erschöpfen werden, bevor der Knoten- oder der Zeichen-Puffer erschöpft ist. In diesem Fall wird der Kompressor eventuell einen "Bereitschafts-Zustand" -Betriebszustand erreichen, in dem bei jedem Kopie-Codewort oder Literal-Zeichen ein Blatt freigemacht wird und ein Blatt zugeordnet wird. Für einen Text und einige andere Arten von Daten wird sich der Grad eine Kompression, der auf großen Quellen erreicht wird, erhöhen, wenn sich maxCopyDisp erhöht. Die beispielhafte Ausführung in Appendix E verwendet eine Fenstergröße von maxCopyDisp = 16.384 Positionen, allerdings wird verständlich werden, daß diese Ausführung vollständig funktional für Werte von maxCopyDisp zwischen etwa 1000 und 63000 ist.
  • Bei der Initialisierung des Kompressors und nach einem Csflush ist die längste Anpassungstiefe 0. Allerdings ist, der Ausführung von CSUnsafeputblock oder CSPutChar folgend, die Tiefe der längsten Anpassung immer größer als oder gleich 1. Wenn das nächste Zeichen zur Kompression geschickt wird, wie bei ein 101, versucht der Kompressor zuerst, die derzeit längste Anpassung zu erweitern, um dieses Zeichen zu umfassen, wobei die erweiterte Symbol-Zeichenfolge in den Baum eingesetzt wird, wie dies bei 102, 103, 104, 111, 113, 110 und 112 angezeigt ist. Der Suchpfad, dem während dem Einsetzen der erweiterten Symbol-Zeichenfolge gefolgt ist, wird durch die Position der momentanen Anpassung in dem Baum bestimmt. insbesondere wird, (1) wenn die momentane Anpassung auf einem Blatt-Bogen liegt, der Such pfad für die erweiterte Zeichenfolge so definiert, daß sie bei 102, 111, 113 und 112 ist, (2) wenn die momentane Anpassung exakt an einem Knoten ist, dann wird der Suchpfad so bestimmt, daß er bei 102, 103, 110 und 112 ist, oder (3) wenn die momentane Anpassung auf einem inneren Bogen des Baums ist, dann wird der Suchpfad so identifiziert, daß er bei 102, 103, 104 und 112 ist.
  • Wenn eine Anpassung nicht weiter auf einem inneren Bogen des Suchbaums erweitert werden kann, wie bei 104, oder auf einem Blatt-Bogen des Baums, wie bei 111, wird ein Knoten von der freien Liste herangezogen und in den Baum an dem Punkt eingespleißt an dem die Anpassung bestimmt ist, wie bei 105. Das neue Blatt wird dann von diesen neuen Knoten, wie bei 106, herabgehängt. Oder wenn eine Anpassung nicht über einen bestehenden Knoten hinaus erstreckt werden kann, wie bei 110, wird das neue Blatt von dem existierenden Knoten, wie bei 106, herabhängt. Eine Anpassung wird auch immer dann beendet, wenn sie die maximal zulässige Kopie-Länge oder -Tiefe auf einem Blatt- Bogen, wie bei 113, erreicht. Unter diesen Umständen ist allerdings keine nützliche Differenz zwischen der neuen Zeichenfolge und dem früheren Auftreten, die in der Anpassung resultiert, vorhanden, mit Ausnahme einer temporären Bestimmung und der sich ergebenden Differenz in deren Position relativ zu dem Suchfenster. Demzufolge wird ein altes, abgeschnittenes Blatt für die Zeichenfolge entfernt, wie bei 114, und das neue Blatt an diese Stelle, wie bei 106, eingesetzt. In diesen Fällen, wo ein Knoten von der freien Liste erhalten wird, wird eine Prüfung für die freie Liste, daß sie leer ist, vorgenommen, was anzeigt, daß alle Knoten in Verwendung sind. Wenn dies auftritt, wird ein neuer Knoten erzeugt und auf die freie Liste gesetzt, vorausgesetzt, daß die maximale Knoten-Zuordnung, die durch den "maxNodes" -Parameter bestimmt ist, noch nicht erreicht worden ist.
  • Abschließend werden Baum-Positionen aktualisiert, wie bei 107, beginnend mit den Eltern-Knoten für das neue Blatt und abwärts in dem Baum gehend, bis der Knoten mit der permanenten Tiefe 1 erreicht ist. In dieser Ausführungsform werden alle Knoten bis zu der Wurzel aktulisiert, allerdings wird verständlich werden, daß eine Perkulations-Aktualisierung, wie dies vorstehend beschrieben ist, eingesetzt werden kann. Auch könnten einige Ausführungsformen Knoten während des Absteigens in dem Baum aktualisieren.
  • An diesem Punkt ist der Baum aktualisiert worden und stellt korrekt die neue Symbol- Zeichenfolge dar. Die nächsten Schritte sind der Codierung der Zeichenfolge, die gerade in dem Baum dargestellt ist, und einer Vorbereitung, um die nächste Anpassung zu bestimmen, zugeordnet. Wenn das Fenster voll ist, wird das älteste Blatt von dem Baum entfernt, wie bei 108, so daß sein Speicher für das Blatt wieder verwendet werden kann das zum nächsten Zeitpunkt erzeugt werden wird (dieser Schritt ist unnötig, wenn der Kompressor bis jetzt noch nicht sein Fenster gefüllt hat, oder wenn dieses Blatt schon aufgrund eines Erreichens einer Abschneidtiefe, wie bei 114, erreicht worden ist, oder wenn es schon entfernt worden ist, um Raum in dem Puffer zu schaffen, wie bei 117, oder wenn es schon entfernt worden ist, da die Anzahl der Knoten, die für diesen Baum zugeordnet sind, schon erschöpft war, wie bei 121). Als nächstes wird eine Codierung ausgeführt, wie bei 115; dies wird vollständiger nachfolgend in Fig. 13 erläutert.
  • Nach einer Codierung prüft der Kompressor seinen Ausgangs-Puffer, wie bei 116, um zu bestimmen, ob der Puffer einen ausreichend freien Raum besitzt, um eine Kopie einer maximal zulässigen Kopie-Länge zu speichern (ein ungünstigster Fall für das nächste Codewort). Falls dies nicht der Fall ist, werden die ältesten Blätter von dem Baum entfernt, wie bei 117, um ausreichenden Speicherraum in dem Puffer für eine solche Kopie plus einem zusätzlichen Betrag eines Speichers freizumachen, "oBufReserve" (siehe Appendix E). Insoweit als jedes Blatt eines oder mehrere Symbole in dem Puffer darstellt, macht ein Freigeben eines Blatts auch Pufferraum frei. Nach einem Prüfen des Ausgangspuffers prüft der Kompressor, wie bei 122, um zu bestimmen, ob die Liste für Frei-Knoten leer ist, was impliziert, daß maxNodes Knoten derzeit in dem Baum verwendet werden. Falls dies der Fall ist, entfernt er die ältesten Blätter von dem Baum durch einen Batch-Entfernungs-Prozeß ("ToFree leaves") (was einen Parameterwert von 100 hat). Ein Entfernen eines Blatts bewirkt oftmals, daß ein Eltern-Knoten nur einen verbleibenden Sohn besitzt, so daß der vorstehend beschriebene Knoten-Lösch- oder Reklamations-Prozeß dann eingesetzt werden kann, um diesen Eltern-Knoten wieder zu beanspruchen und ihn auf die freie Liste zu setzen, allerdings sollte angemerkt werden, daß dieser Schritt wiederholt wird, bis die Liste mit freien Knoten einen oder mehrere freie Knoten enthält. Wie ersichtlich werden wird, könnte eine etwas einfachere Variation des Kompressors die Schritte 121 und 122 der Fig. 2 durch Zuordnung einer Zahl von Knoten größer als oder gleich zu dem Erfordernis des ungünstigsten Falls für maxCopyDisp-Blätter eliminieren. Tatsächlich wird diese Alternative als ein Kommentar in Appendix E besprochen und wird bei den Ausführungen der Appendizes C und D eingesetzt. Allerdings ist der Nachteil dieser alternativen Maßnahme derjenige, daß sie die Speichererfordernisse für den Kompressor erhöht.
  • Schließlich wird das Zeichen, das gerade zu dem Kompressor zugeführt ist, das nicht die längste Anpassung erweiterte, das erste Zeichen einer neuen Anpassung, wie bei 123. Die Baum-Position wird so eingestellt, daß sie der Knoten der permanenten Tiefe 1 für dieses Zeichen ist, und der Kompressor nimmt dann eine Schleife vor, um ein anderes Zeichen zu akzeptieren.
  • Es wird verständlich werden, daß Fig. 12 entweder den Kompressor in Appendix E oder denjenigen in Appendix D angibt; diese zwei Kompressoren unterscheiden sich in den Codier-Details, die in einer Codier-Funktion 115 verborgen sind, die nachfolgend erläutert werden. Zusätzlich verwendet der Kompressor in Appendix D die einfachere Variation, die nachfolgend besprochen wird. in der die Knoten-Management-Schritte 121 und 122 durch Vorsehen einer Anzahl von Knoten eliminiert wird, die für das Erfordernis des ungünstigsten Falls von "maxCopyDisp"-Blättern ausreichend ist.
    • 2. Ein Baum-Struktur-Codierer
  • Schritt 105 in Fig. 12 stellt den Codierabschnitt des Kompressors dar; der in Baumform strukturierte Codierer des Appendix E ist vollständiger in Fig. 13 diagrammartig dargestellt. Die Aufgabe des Codier-Abschnitts ist diejenige, die Quelle kompakt mittels Node-Copy-, LeafCopy-, Literal., PadLiteral. und PadCopy-Codeworte darzustellen. Die Art der Codeworte, die verwendet wird, sind vorteilhafterweise Präfix-Code, was bedeutet, daß kein Codewort ein Präfix irgendeines anderen ist, so daß der Expander unzweideutig einen Strom aus Codeworten decodieren kann.
  • Für die Ausführungsform in Appendix C wird der Codier-Abschnitt einmal pro Zeichen unabhängig davon, ob das Zeichen schon durch ein Kopie-Codewort dargestellt worden ist oder nicht, eingegeben, so daß eine Zeichen-Auslassungs-Zählung eingesetzt wird wie in Fig. 3 im Schritt 78. Dies wird dazu verwendet, um durch die Zeichen nach oben zu zählen, die schon durch ein Kopie-Codewort dargestellt sind, bis es Zeit ist, ein anderes Codewort zu produzieren. Allerdings erfordern die Ausführungsformen in den Appendizes D und E nicht diese Auslassungs-Zählung, da in den Codierer für diese niemals wieder für Zeichen, die schon codiert sind, eingetreten wird.
  • Der Codierer entscheidet zuerst, wenn das nächste Zeichen ansteht, daß es in einem Literal dargestellt wird, und wenn es ansteht, in einer Kopie dargestellt zu werden. Wenn die längste Anpassung von einer Länge list, dann muß das Zeichen in einem Literal dargestellt werden, wenn allerdings die längste Anpassung von der Länge 2 oder länger ist, dann kann die Taktik auswählen, es entweder in einem Literal oder in einer Kopie darzustellen. Die Ausführungsformen in den Appendizes C und D basieren nicht auf dieser Taktik-Entscheidung bloß auf der Länge der längsten Anpassung; der Grund hierfür ist, daß die Codierung eines Literals einer Länge 1 4 Bits (plus dem Zeichen) erfordern, während ein Literal von einer Länge 2 oder 3 6 Bits (plus die Zeichen) erfordert; anders ausgedrückt sind die "Kosten" einer Initiierung eines Literals 4 Bits, während die Verlängerung von einer Länge 1 zu der Länge 2 nur 2 Bits kostet und die Verlängerung von einer Länge 2 zu einer Länge 3 0 Bits kostet. Da sich diese Kosten unterscheiden ist der Codierer vorteilhafterweise reluktant, um ein Literal zu initiieren, allerdings wenn er einmal eines begonnen hat, ist er reluktant, es zugunsten einer Kopie zu beenden; anders ausgedrückt ist dort vorteilhafterweise eine "Hysterese" in der Taktik-Entscheidung vorhanden. Diese Betrachtungen führen zu der einfachen Taktik, die vorstehend beschrieben ist, bei der eine Kopie einer Länge 2 gegenüber einem Literal bevorzugt ist, wenn allerdings einmal das Literal gestartet worden ist, kann nur eine Kopie einer Länge 3 (oder ein Erreichen einer maximalen Literal-Länge) es stoppen. Man kann andere Taktiken ins Auge fassen, die eine leicht höhere Kompression auf Kosten einer geringfügig höheren Komplexität erreichen.
  • In dem Fall des Baum-Struktur-Codierers des Appendix E allerdings kommt eine andere Betrachtung ins Spiel; es ist nämlich für den Expander erwünscht, daß er in der Lage ist, den Baum wieder aus den Codeworten, die er decodiert, ohne Wiedersortieren zu unerwünschten Tabellen oder anderen Daten-Strukturen, ähnlich denjenigen des Kompressors, wieder zu erzeugen. Hierbei ist es vorteilhaft, die Taktik darauf zu beschränken, immer eine Kopie auszuwählen, wenn die längste Anpassung von einer Länge 2 oder länger ist, und ein Literal nur dann zu initiieren oder zu erweitern, wenn die längste Anpassung kürzer ist. Als Folge dieser Einschränkung wird der Expander immer in der Lage sein, das Blatt für ein Literal-Zeichen von einem Knoten der permanenten Tiefe 1 anzuhängen, und zwar entsprechend diesem Literal-Zeichen. Als Folge dieser Taktik-Beschränkung wird der Expander einfacher, läuft schneller und fordert weniger Speicher, obwohl er typischerweise eine geringfügig niedrigere Kompression erreicht, als dies der Fall sein würde, wenn eine komplexere Taktik verfolgt werden würde.
  • Anhand nun der Fig. 13 wird ersichtlich werden, daß die Codierung von dem Kompressions-Algorithmus, der eingesetzt wird, abhängig ist. Allerdings wird, unter Beibehalten einer gemeinsamen Charakteristik aller bevorzugter Kompressions-Algorithmen zuerst bestimmt, wie bei 127, ob ein Literal codiert werden soll oder nicht. Für die Codierung eines Literals wird die Länge des Literals verlängert, wie bei 128, und zwar während jeder Iteration des vorstehend beschriebenen Einsetz-Prozesses, bis dort eine Kopie, die codiert werden soll, vorhanden ist, oder bis ein Literal einer maximal zulässigen Literal- Länge abgetastet ist, wie bei 129. Immer wenn ein Literal seine maximal zulässige Länge erreicht, wird ein Literal-Codewort, wie bei 131, in den Ausgangs-Puffer unmittelbar vor den Literal-Symbolen, die akkumuliert worden sind, eingeladen. In ähnlicher Weise wird, wenn dort eine Kopie, die codiert werden soll, vorhanden ist, die akkumulierte Literal-Längen-Zählung geprüft, wie bei 134, um zu bestimmen, ob ein Literal akkumuliert werden soll. Falls dies der Fall ist, werden ein Literal-Codewort, wie bei 135, und die akkumulierten Literal-Symbole in den Ausgangs-Puffer vor dem Kopie-Codewort eingeladen (wenn es wieder aufgerufen wird, können das Literal-Codewort und seine angehängten Literal-Quellen-Symbole in den Kompressor-Ausgangs-Puffer zu jedem Zeitpunkt eingeladen werden, nachdem die Existenz der Kopie bestätigt worden ist und bevor das Codewort für die Kopie eingeladen wird). Immer wenn ein Literal ausgegeben wird, wird die akkumulierte Literal-Symbol-Zählung bei 134 auf Null zurückgesetzt, so daß ein anderes Literal akkumuliert werden kann.
  • In diesem Fall werden Kopien unter Verwendung einer LeafCopy 136 oder einer NodeCopy 137 in Abhängigkeit davon, ob die Kopie an einem Blatt-Bogen endet oder nicht, wie dies bei 138 bestimmt ist, codiert. Der Ausgangs-Puffer wird geprüft, wie bei 139, nachdem jedes Literal und jede Kopie in ihn eingeladen ist, und wird zwischengespeichert, wie bei 140, wenn er im wesentlichen voll ist. Die verschiedenen Details der baumartig strukturierten Codierung werden durch Kommentare in Appendix E beschrieben. Eine zusätzliche Beschreibung der Codierung erscheint in der Diskussion des Expanders nachfolgend.
    • 3. Byte-Ausrichtung des Codierers
  • Wie die Fig. 14 zeigt, wird ein Flush-Prozeß zum Ausgeben von Codeworten für irgendwelche Teil-Literals oder -Kopien, die in dem Kompressor verbleiben, wenn ein Flush- Befehl abgegeben wird, eingesetzt. In einem File-Kompressor, wird ein solcher Befehl nur an dem Ende des Files ausgegeben, wobei es zu dieser Zeit gewöhnlich notwendig ist, die letzten paar Symbole des Files aus dem Kompressor herauszunehmen, gerade obwohl der Kompressor nicht vorbereitet werden muß, um ein gewöhnliches Kopie- oder Literal-Codewort auszugeben, und wobei es notwendig sein kann, die vorhergehende Zeichenfolge aus Bits zu beenden, so daß sie nicht dahingehend fehl interpretiert werden könnte, daß sie ein Codewort ist. Für einen Strom-Kompressor kann der Flush-Prozeß auch verwendet werden, um einige zusätzliche komprimierte Daten für einen Empfänger zu liefern, während die Quellen-Daten für den Kompressor temporär entleert werden. In irgendeinem Typ eines Kompressors setzt ein Flush die Byte- oder Wort-Ausrichtung der komprimierten Daten zurück (die Ausführungsform des Appendix E setzt die Ausrichtung auf eine 16 Bit Grenze zurück).
  • Wenn ein Flush initiiert wird, ist die normale Operation des Kompressors zeitweilig schwebend und die Tiefe, an der sich sein Suchbaum 73 (Fig. 3) befindet, wird so vorbereitet, um das nächste Symbol oder Zeichen, das geprüft ist, wie bei 141, einzusetzen. Wenn der Baum schon auf seine Wurzel gesetzt ist, wird der Flush vorzeitig abgebrochen, wie bei 142, und der Kompressor wird unmittelbar auf einen normalen Betrieb zurückgesetzt. Ansonsten wird die akkumulierte Literal-Zählung geprüft, wie bei 143, und ein Literal-Codewort wird ausgegeben, wie bei 144, um die akkumulierten Symbole durch irgendein Literal, das durch den Flush unterbrochen ist, zu begleiten. Nach einem Ausgeben irgendeines akkumulierten Literals wird das älteste Blatt von dem Baum, wie bei 144, entfernt, wenn es noch nicht gelöscht worden ist. Allerdings wird der Baum nicht für die Symbole, die durch das PadCopy-Codewort codiert sind, aktualisiert, da sie nicht einen eindeutigen Suchpfad definieren. Als nächstes wird der Flush codiert, wie bei 145, und zwar unter Verwendung eines PadLiteral-Codeworts, um das eine Quellen-Symbol zu begleiten, das sich noch in dem Suchbaum des Kompressors befindet, wenn sich der Baum bei einem Knoten mit der Tiefe 1 befindet, wenn das Flush initiiert wird, oder eines PadCopy-Codeworts, um die Suchfenster-Symbol-Position und -Länge der unterbrochenen Kopie zu identifizieren, wenn dort zwei oder mehr Quellen-Symbole noch in dem Baum sind. Das PadLiteral- oder PadCopy-Codewort wird in den Kompressor-Ausgangs- Puffer eingeladen und zusätzliche Bits werden zu ihm hinzugefügt, um den Ausgang des Puffers an einer bequemen Grenze auszurichten, wie beispielsweise die nächste 16 Bit Grenze, wie in diesem besonderen Beispiel. Schließlich wird der Puffer zwischengespeichert, wie bei 146, und der Suchbaum 73 (Fig. 3) wird dann zu seiner Wurzel zurückgesetzt, wie bei 147, um den Kompressor so vorzubereiten, um mehr Zeichen zu empfangen.
    • 4. Ein Baum-Struktur-Expander
  • Gemäß der Ausführungsform des Appendix E der Erfindung initialisiert ein Client den Expander durch Aufrufen einer "CreateDecodingStream" -Prozedur die ein Argument eines Eingangs-Stroms (oder einer Daten-Quelle) besitzt, von dem Codeworte erhalten werden. Nach einer Intitialisierung nimmt der Client wiederholte Prozedur-Aufrufe für "ESUnsafeGetBlock" vor, das einen Block von Zeichen liest, und zu "ESGetChar", was Einzel-Zeichen liest, um nicht komprimierte oder erweiterte Symbole durch Aufeinanderfolgen des Decodierens von Codeworten von dem Eingangsstrom, wie er durch den Client gerichtet wird, zu extrahieren. "ESEndOf" kann dazu verwendet werden, die Unfähigkeit des Expansionsstroms zu prüfen, um mehr Symbole zu liefern. Da die Ausführung eines "ESGetChar" einfach "ESUnsafeGetBlock" mit einer Symbol-Zählung von 1 aufruft, wird die Beschreibung hier auf die "ESUnsafeGetBlock" -Prozedur beschränkt obwohl verständlich werden wird, daß eine einfache Beschreibung bei der "ESGetChar" -Prozedur anwendbar sein würde.
  • Anhand nun der Fig. 15A und 15B wird ersichtlich werden, daß der Expander den Kompressor komplettiert, um getreu die Original-Quellen-Daten zurückzugewinnen. Hierbei werden, wie vorstehend hervorgehoben wurde, die Daten-Strukturen des Expanders exakt ähnlich jedes Kompressors initialisiert. Weiterhin sind, immer wenn ein Codewort decodiert wird, der Expander-Baum und das Suchfenster zu dem Kompressor-Baum an entsprechenden Schritten des Kompressions-Prozesses identisch. Wie verständlich werden wird, werden die Schritte, die durch den Expander vorgenommen werden, um Codeworte zu decodieren, vollständig durch die Codierung diktiert.
  • Der Expander des Appendix E besitzt ein Eingangs-Unterprogramm zum Erhalten von Bits aus dem Eingangs-Strom. immer wenn mehr Bits für ein anderes Codewort- oder Literal-Zeichen benötigt werden, wie bei 156, 159 und 160, dann wird dieses Unterprogramm aufgerufen, um die Bits zu erhalten. Wenn der Eingangs-Strom vollständig erschöpft ist, wird ein "EndOfStream" -Fehler-Zeichen erhoben, um dadurch zu bewirken, daß die "ESUnsafeGetBlock" -Prozedur zu ihrem Client mit einer Zeichen-Zählung kleiner als diejenige, die angefordert ist, zurückzukehren. Dies bewirkt, daß der Client die Expansion beendet.
  • Der Expander besitzt Zustands-Variablen, die die Puffer-Position und die restliche Länge der momentanen Kopie, die erweitert werden soll, sind, falls welche vorhanden sind, oder die restliche Länge des momentanen Literals, das expandiert ist, falls ein solche vorhanden ist. Wenn ein anderes Zeichen gefordert wird, wie bei 151, prüft "ESUnsafe-GetBlock" zuerst diese Variablen, um zu sehen, ob er das nächste Symbol ohne Decodieren eines anderen Codeworts liefern kann. Wenn ein NodeCopy-, ein LeafCopy- das eine Bogen-Verschiebung von nicht Null besitzt, oder ein PadCopy-Codewort in der Bearbeitung, damit sie erweitert wird, ist, verwendet der Expander die Schritte, die bei 152, 153 und 154 angegeben sind, um das nächste Zeichen durch Kopieren von diesem von einer anderen Stelle in den Zeichen-Puffer zu liefern. Andererseits verwendet, wenn ein Literal-Codewort (d.h. eine LeafCopy mit einer Bogen-Verschiebung von Null) in dem Prozeß ist, damit es erweitert wird, der Expander die Schritte, die bei 152, 155, 156, 157 und 158 angezeigt sind, um das nächste Literal-Zeichen zu erweitern.
  • Wie ersichtlich werden wird, wird der Baum bei jedem Literal-Zeichen und bei jedem Kopie-Codewort aktualisiert. Schritte 108', 116', 117', 122' und 121' sind zum Liefern von Blättern, Knoten und Puffer-Raum in exakt derselben Art und Weise, wie vorstehend in Verbindung mit dem Kompressor beschrieben ist, zugeordnet. In ähnlicher Weise bewirken Schritte 108', 116', 117', 122' und 121', daß ein Blatt befestigt wird, wie bei 157, zu seinem Knoten der permanenten Tiefe 1 des Expander-Baums, exakt so, wie dies durch den Kompressor vorgenommen wurde. Deshalb entsprechen die gestrichenen Bezugszeichen denjenigen, die zur Beschreibung des Kompressors eingesetzt wurden, um entsprechende Schritte des Expansions-Prozesses zu identifizieren.
  • Wenn die momentane Kopie oder das Literal ausgegeben wird, ist es geeignet, das nächste Codewort, wie bei 159, zu decodieren. Dies wird dazu führen, daß ein neues Blatt zu dem Baum hinzugefügt wird, wenn das Codewort eine NodeCopy oder eine LeafCopy ist. Zusätzlich wird ein Blatt auch zu dem Expander-Baum für das erste Zeichen jedes Literals hinzugefügt werden. Um diese möglichen Codeworte vorzubereiten werden wiederum Schritte 108', 116', 117', 122' und 121' verwendet, um sicherzustellen, daß die Ressourcen, die für das Blatt erforderlich sind, verfügbar sind, und um sicherzustellen, daß der Expander-Baum dieselbe Konfiguration während einer Decodierung, wie diejenige besitzt, die der Kompressor-Baum während einer Codierung hatte.
  • Der Decodierer, wie bei 159, kann leicht ein Codewort von einem anderen unterscheiden, da die Codierung eine Familie von Coden, die als "Präfix" -Code bekannt ist, einsetzt, was bedeutet, kein Codewort ist ein Präfix irgendeines anderen. Demzufolge ist nur eine mögliche Interpretation irgendeiner Sequenz von Bits vorhanden. Genauer gesagt unterscheidet bei der Codierung, die durch Appendix E verwendet wird, das erste Bit der Codeworte NodeCopy-Codeworte von LeafCopy-, LiteralCopy- und PadLiteral- Codeworten. Wenn dieses Bit eine NodeCopy signalisiert, dann bestimmt die maximale Knotenzahl, die in Verwendung ist, die Anzahl der Bits, die als eine Knoten-Zahl gelesen und decodiert werden wird, und zwar unter Verwendung der "sparsamen Codier" -Technik, die vorstehend diskutiert ist. Die Knoten-Zahl wiederum wird dazu verwendet, um auf den Baum Bezug zu nehmen, und um die Länge des ankommenden Bogens zu diesem bestimmten Knoten zu bestimmen. Weiterhin bestimmt, wenn der ankommende Bogen zu dem spezifizierten Knoten länger als ein Symbol lang ist, seine Symbol-Länge die Anzahl der Bits, die als eine Bogen-Verschiebung decodiert sind, und zwar wiederum basierend auf einer sparsamen Code- "Darstellung" der Bogen-Länge. Es ist auch anzumerken, daß die Decodierung der Knoten-Zahl erfordert, daß der Expander denselben Wert für die maximale Knoten-Zahl verwendet wie der Kompressor, und daß er einen Baum besitzt, in dem die Knoten numeriert sind, und in exakt derselben Art und Weise wie der Kompressor verwendet werden.
  • Immer wenn das erste Bit, das durch den Decodierer bearbeitet wird, wie bei 159, anzeigt, daß das Codewort, das decodiert werden soll, nicht eine NodeCopy ist, wird ein monadischer Code < 1, 1, 12> decodiert, mit Ausnahme, daß das größte oder Stop-Größen-Feld des Codes (d.h. ein monadisches Codewort, das einen "Indikator" von 11 binären 1 (d.h. 11111111111) besitzt), zum "Austreten" aus dem monadischen Code reserviert wird, um ein PadCopy- oder PadLiteral-Codewort auszugeben. Wenn der decodierte Wert des monadischen Codes < 1, 1, 12> eine 0 ist, was ein Literal anzeigt, decodiert der Decoder als nächstes einen monadischen Code < 0, 1, 5> als die Literal-Länge, um die Anzahl der Literal-Quellen-Symbole, die an das Literal angehängt sind, zu bestimmen.
  • Wenn der decodierte Wert des monadischen Codes < 1, 1, 12> in dem Bereich von [1..4094] liegt, wird er als eine Bogen-Verschiebung nach unten einen Blatt-Bogen von den Bogen-Eltern dieses Blatt-Bogens interpretiert. Demzufolge wird die komprimierte Verschiebung basierend in diesem Fall auf einen monadischen Code von < 10-x, 2, 14-x> und basierend auf der "sparsamen Codierung" seines größten oder "Stop" -Felds, wie dies vorstehend für den Codierer besprochen ist, decodiert.
  • In dem Fall, daß die Bogen-Verschiebung eine PadCopy oder ein PadLiteral bezeichnet, wird das PadCopy-Längenfeld codiert, und zwar unter Verwendung eines monadischen Codes < 1, 1, 12> . Falls der decodierte Wert dieses Felds Null ist, bedeutet dies, daß das Codewort ein PadLiteral ist, dem ein einzelnes Literal-Zeichen folgen wird. Ansonsten wird, nachdem die PadCopy-Länge decodiert ist, die relative Verschiebung zu der Suchfenster-Position des ersten oder voranführenden Symbols der längsten Anpassung decodiert, und zwar unter Verwendung eines monadischen Codes von < 10-x, 2, 14-x> mit der sparsamen Feld-Verbesserung für das größte oder "Stop" -Feld. Alle diese Details bestätigen die Codier-Operationen, die durch den Kompressor, der vorstehend beschrieben ist, durchgeführt sind.
  • Wenn der Decodierer, wie bei 159, eine LeafCopy oder PadCopy decodiert, erzeugt er eine komprimierte Verschiebung, die die Anzahl der komprimierten Positionen (d.h. die Anzahl der Kopie-Codeworte oder Literal-Zeichen) zwischen der momentanen Fenster- Position und der einen, bei der die längste Anpassung gefunden wurde, ist. Die komprimierte Verschiebung wird in eine komprimierte Fenster-Position, oder äquivalent dazu, in eine Blatt-Nummer durch Subtrahieren der komprimierten Verschiebung von dem momentanen Fenster-Position-Modub der Fenster-Größe translatiert. Wenn der Decodierer eine NodeCopy decodiert, wird die komprimierte Fenster-Position für den spezifizierten Knoten von dem Knoten in dem Baum erhalten. In allen diesen Fällen wird die komprimierte Fenster-Position in eine Zeichen-Puffer-Position durch Lesen des "cWindow" -Feldeintritts für die komprimierte Fenster-Position (siehe Appendix E) translatiert; diese Translationen sind schematisch in Fig. 158 bei 162 und 170 dargestellt.
  • Kein Blatt wird zu dem Expander-Baum in Abhängigkeit der Codierung eines PadLiteral- oder PadCopy-Codeworts hinzugefügt. Die Gründe dafür, warum ein Blatt nicht zu dem Baum hinzugefügt wird, sind für diese besondere Ausführungsform des Kompressionssystems spezifisch und werden in einem langen Kommentar, der der "CSFlush" -Prozedur in Appendix E vorangeht, erläutert. Sie sind allerdings nicht ausreichend für das Ziel der Erfindung relevant, um eine weitere Diskussion zu rechtfertigen. Tatsächlich werden Fachleute mit Erfahrung in der Programmiertechnik erkennen, daß eine Vielfalt von Arten und Weisen zum Ausführen der Pad-Funktion vorhanden sind. Nichtsdestotrotz ist die Funktion wichtig, so daß anzumerken ist, daß der Expander, der das Einzel-Symbol von einem PadLiteral-Codewort in den Zeichen-Puffer, wie beispielsweise an dem Kasten 160, plaziert und dann den Eingangs-Strom an einer 16 Bit Wort- Grenze, wie bei 161, durch Auslassen von Bits von dem Eingangs-Strom bis zu der nächsten in 16 Bit ausgerichteten Position ausrichtet. In ähnlicher Weise translatiert der Expander, und zwar in Abhängigkeit einer PadCopy, die in der PadCopy komprimierte Verschiebung in einer Zeichen-Puffer-Position (wie vorstehend diskutiert ist) und spart die PadCopy-Länge ein, wie bei 162. Er richtet dann eine 16 Bit Grenze aus, gerade wie für ein PadLiteral, bevor der Prozeß durch Kopieren der Symbole, die durch die Padcopy dargestellt sind, in den Puffer, wie bei 153 und 154, abgeschlossen ist.
  • Wenn der Decodierer, wie bei 159, eine LeafCopy codiert hat, translatiert er als nächstes die komprimierte Verschiebung in eine Blatt-Zahl- oder Fenster-Position, wie dies vorstehend besprochen ist. Dann folgt er dem Eltern-Hinweiszeiger von dem angezeigten Blatt in dem Baum zu den Knoten-Eltern dieses Blatts (wie verständlich werden wird, ist die Tiefe dieses Knotens plus die Bogen-Verschiebung die Anzahl der Zeichen, die kopiert werden sollen). Wenn bestimmt ist, wie bei 113, daß die berechnete Kopie-Länge gleich der maximal zulässigen Kopie-Länge ist, wird das abgeschnittene Blatt für die wiederauftretende Symbol-Zeichenfolge von dem Baum entfernt, wie bei 114', so daß es durch das neue Blatt ersetzt wird, wie bei 106'. Wiederum wird ersichtlich werden, daß diese Aktionen exakt äquivalenten Aktionen innerhalb des Kompressors entsprechen. Wenn, wie dies normalerweise der Fall ist, die maximal zulässige Kopie-Länge nicht erreicht wurde, dann wird ein Blatt und ein Knoten zu dem Baum, wie bei 164, hinzugefügt. Schritte 165,166 und 167 sind einem graduellen Ansteigen der Anzahl der Knoten, die in Verwendung sind, zugeordnet, bis die maximal zulässige Zahl von Knoten, "maxNodes", in Bearbeitung ist (sie liefern eine etwas detailliertere Zählung der Funktion des Schritts 105 in dem Kompressor). Nach diesen Prüfungen der Liste für freie Knoten die sicherstellt, daß die Liste der freien Knoten nicht leer ist, ohne daß maxNodes-Knoten Verwendung sind, werden Baum-Positionen aktualisiert, wie bei 107', exakt wie in dem Kompressor bei 107, und die Fenster-Position wird in eine Zeichen-Puffer-Positior, wie bei 170, durch Lesen des "cWindow" -Felds, wie dies vorstehend besprochen ist, translatiert. Abschließend wird das erste Zeichen der LeafCopy kopiert wie bei 153 und 154.
  • Wenn der Decodierer eine NodeCopy decodiert hat, werden die Tiefe und die Fenster- Position des angezeigten Knotens aus dem Baum, wie bei 169, erhalten. Wenn die Bogen-Verschiebung Null ist, wie in 168 getestet, endet die längste Anpassung exakt an einem Knoten; in diesem Fall wird das neue Blatt von dem angezeigten Knoten aus, wie bei 106', angehängt. Ansonsten wird ein neuer Knoten aus dieser freien Liste erhalten und in den Baum an der angezeigten Bogen-Verschiebung von den Eltern des angezeigten Knotens eingesetzt und das neue Blatt wird von dem neuen Knoten aus, wie bei 164, angehängt. Die anderen Aktionen sind dieselben wie für eine LeafCopy, wie bei 165, 166, 167, 107', 170, 153, 154 angezeigt.
  • Nachdem ein Zeichen zugeführt worden ist, geht der Expander zurück zu Schritt 151 und fährt fort.
    • Zusammenfassung
  • Unter Berücksichtigung des Vorstehenden wird verständlich werden, daß eine nicht redundante Codierung für textorientierte Subtitutions-Daten-Kompressions-Systeme durch Codieren der Struktur eines Suchbaums, der durch den Kompressor für die Kompression der Quellen-Daten konstruiert und beibehalten wird, um dadurch einen Codierer in die Lage zu versetzen, einen identischen Suchbaum zum Erweitern der Daten zu rekonstruieren, geschaffen.

Claims (3)

1. Textorientiertes Substitutions-Daten-Kompressionssystem, das einen Kompresssor und einen Expander umfaßt, wobei der Kompressor aufweist:
eine Puffer-Speicher-Einrichtung (71) zum seriellen Empfangen von Quellen-Symbolen und zum Schaffen eines Speichers auf der Basis zuerst eingegangen/zuerst ausgegeben für eine finite Zahl der Quellen-Symbole, wobei ein Bereich der Puffer- Speichereinrichtung ein Suchfenster einer finiten Länge definiert;
eine Logik-Einrichtung (72, 78, 74), die mit der Puffer-Speicher-Einrichtung zum Konstruieren und Beibehalten einer mittels Suchbaum organisierten Daten-Struktur (73) verbunden ist, die die Quellen-Symbole innerhalb jedes Suchfensters gemäß deren Reihenfolge eines Auftretens verknüpft, um Symbol-Zeichenfolgen zu produzieren und zum Spuren von Verschiebungen der Symbol-Zeichenfolgen innerhalb des Suchfensters gemäß dem Kriterium eines am kürzesten vorherigen Auftretens; wobei die Logik-Einrichtung einen Test-Modus zum Testen von Quellen-Symbolen unmittelbar vor deren Eintritt in das Suchfenster gegenüber der Daten-Struktur, um zu bestimmen, ob das Suchfenster irgendwelche Anpassungs-Symbole enthält, und einen Erweiterungs-Modus zum Abschätzen der Verschiebung und der Länge der längsten Symbol-Zeichenfolge innerhalb des Suchfensters besitzt, das irgendein angepaßtes Symbol oder die Symbole, die ihm folgen, anpaßt; und
eine Codier-Einrichtung (75, 76), die mit der Logik-Einrichtung zum Codieren angepaßter Symbol-Zeichenfolgen gekoppelt ist, die aus mindestens einer minimalen Vielzahl von Quellen-Symbolen als Kopie-Codeworte zusammengesetzt sind, die die Verschiebung und die Länge der passenden Symbol-Zeichenfolgen spezifizieren, und zum Codieren aller anderen Symbole als Literal-Codeworte, die die Symbole spezifizieren, um dadurch den Expander so freizugeben, um eine aktualisierte Replika der mittels Suchbaum origanisierten Daten-Struktur beizubehalten, wobei sich die minimale Anzahl der Quellen-Symbole als eine Funktion des vorbestimmten Zustands der Codier-Einrichtung variiert.
2. System nach Anspruch 1, wobei die Daten-Struktur nur ein Symbol für jede Verzweigung des Suchbaums enthält.
3. System nach Anspruch 2, wobei der Suchbaum innere Knoten besitzt, die jeweilige Symbol-Zeichenfolgen darstellen, wobei sich die Daten-Struktur von den inneren Knoten verzweigt, und wobei im wesentlichen alle der Knoten Hinweiszeiger zu Knoten für die Suffixe der Symbol-Zeichenfolgen, die sie darstellen, haben, wodurch neue Symbole zu der Daten-Struktur hinzugefügt werden können, um alle existierenden Symbol-Zeichenfolgen durch Nachfolgen der Hinweiszeiger von den Knoten von den existierenden Symbol-Zeichenfolgen zu den Knoten für deren Suffixe zu erweitern.
DE1989627331 1988-04-29 1989-04-28 Suchbaumdatenstrukturkodierung für Kettensubstitutionsdatenverdichtungssysteme Expired - Fee Related DE68927331T2 (de)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
US18769988A 1988-04-29 1988-04-29

Publications (2)

Publication Number Publication Date
DE68927331D1 DE68927331D1 (de) 1996-11-21
DE68927331T2 true DE68927331T2 (de) 1997-03-20

Family

ID=22690091

Family Applications (1)

Application Number Title Priority Date Filing Date
DE1989627331 Expired - Fee Related DE68927331T2 (de) 1988-04-29 1989-04-28 Suchbaumdatenstrukturkodierung für Kettensubstitutionsdatenverdichtungssysteme

Country Status (2)

Country Link
EP (1) EP0340039B1 (de)
DE (1) DE68927331T2 (de)

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5455577A (en) * 1993-03-12 1995-10-03 Microsoft Corporation Method and system for data compression
US6470347B1 (en) 1999-09-01 2002-10-22 International Business Machines Corporation Method, system, program, and data structure for a dense array storing character strings
US6360221B1 (en) 1999-09-21 2002-03-19 Neostar, Inc. Method and apparatus for the production, delivery, and receipt of enhanced e-mail
US7840639B1 (en) 1999-09-21 2010-11-23 G&H Nevada-Tek Method and article of manufacture for an automatically executed application program associated with an electronic message
US6687740B1 (en) 1999-09-21 2004-02-03 Neostar, Inc. System, method and article of manufacture for preventing the proliferation of unwanted electronic messages
US6704771B1 (en) 1999-09-21 2004-03-09 Neostar, Inc. Electronic message payload for interfacing with text contained in the message
US8219551B2 (en) 2007-10-31 2012-07-10 General Instrument Corporation Decoding a hierarchical multi-layer data package
CN112200465B (zh) * 2020-10-14 2024-04-19 安徽继远软件有限公司 基于多媒体信息智能分析的电力ai方法及系统

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4677649A (en) * 1983-04-26 1987-06-30 Canon Kabushiki Kaisha Data receiving apparatus

Also Published As

Publication number Publication date
DE68927331D1 (de) 1996-11-21
EP0340039B1 (de) 1996-10-16
EP0340039A3 (de) 1992-09-23
EP0340039A2 (de) 1989-11-02

Similar Documents

Publication Publication Date Title
DE68925798T2 (de) Datenverdichtung
DE69318064T2 (de) Verfahren und Vorrichtung zur Verwaltung von mehreren Wörterbüchern zur Datenkomprimierung mit Inhaltsadressierung
DE19606178C2 (de) Verfahren zum Komprimieren einer Anordnung von Pixelwerten und zum Dekomprimieren einer Anordnung von Pixelwerten aus einem komprimierten Datensatz
DE69527679T2 (de) Verfahren zur Datenkomprimierung und -Dekomprimierung
DE4340591C2 (de) Datenkompressionsverfahren unter Verwendung kleiner Wörterbücher zur Anwendung auf Netzwerkpakete
DE69633730T2 (de) Verfahren zur kompression/dekompression von bilddateien
US5058144A (en) Search tree data structure encoding for textual substitution data compression systems
DE69027606T2 (de) Vorrichtung zur datenkompression
DE19622045C2 (de) Datenkomprimierungs- und Datendekomprimierungsschema unter Verwendung eines Suchbaums, bei dem jeder Eintrag mit einer Zeichenkette unendlicher Länge gespeichert ist
DE69413347T2 (de) Auf die Bytegrenze ausgerichtete Datenkomprimierung
DE69518022T2 (de) Vorrichtung und Verfahren für Lempel Ziv Datenkompression mit Verwaltung von mehreren Wörterbüchern in Assoziativspeichern
DE4437790B4 (de) Verfahren und Vorrichtung zur Verwendung von endlichen Automaten zur Durchführung einer Kanalmodulation und einer Fehlerkorrektur und einer Entropie-Kodierung
DE19506164C2 (de) Verfahren zum Komprimieren eingegebener Symbole in Codeworte
DE69510662T2 (de) Kompakte Quellencodierungstabellen für Codierungs-/Decodierungssystem
DE10301362B4 (de) Blockdatenkompressionssystem, bestehend aus einer Kompressionseinrichtung und einer Dekompressionseinrichtung, und Verfahren zur schnellen Blockdatenkompression mit Multi-Byte-Suche
DE69429482T2 (de) Methode und Einrichtung zur Datenkompression
DE68907812T2 (de) Verfahren und Vorrichtung zur Kodierung, Dekodierung und Übertragung von Daten in komprimierter Form.
DE69023329T2 (de) Vorrichtung zur adaptiven datenkompression für ein bandantriebssystem.
DE69802520T2 (de) Verfahren und vorrichtung zur verlustfreien datenkompression
DE69905343T2 (de) Blockweiser adaptiver statistischer datenkompressor
EP1467491B1 (de) Arithmetische Codierung von Transformationskoeffizienten
DE3852341T2 (de) Zeichenverarbeitungssystem mit Funktion zur Prüfung von Rechtschreibung.
DE69522497T2 (de) System und Verfahren zur Datenkompression
DE10196890B4 (de) Verfahren zum Ausführen einer Huffman-Decodierung
DE69834695T2 (de) Verfahren und Vorrichtung zur Datenkompression

Legal Events

Date Code Title Description
8364 No opposition during term of opposition
8339 Ceased/non-payment of the annual fee