DE69706439T2

DE69706439T2 - Rechnersortiersystem zur datenkompression

Info

Publication number: DE69706439T2
Application number: DE69706439T
Authority: DE
Inventors: Michael Schindler
Original assignee: Individual
Current assignee: Individual
Priority date: 1996-11-15
Filing date: 1997-11-14
Publication date: 2002-06-06
Anticipated expiration: 2017-11-15
Also published as: US6199064B1; DE69706439D1; EP0951753A1; AU5321998A; WO1998023038A1; CA2270472A1; ATE205029T1; EP0951753B1

Description

Die Erfindung betrifft ein Verfahren zum Sortieren und Komprimieren eines Ursprungsdatenblocks, der aus einer Mehrzahl von Datenwerten besteht, umfassend die Schritte des:
(a) Verwendens eines Kontexts, wobei jeder Datenwert innerhalb des Ursprungsdatenblocks einen Kontext hat, wobei der Kontext der primäre Sortierschlüssel ist;
(b) Sortierens der Datenwerte gemäß dem primären Sortierschlüssel; und
(c) Komprimierens des sortierten Ursprungsdatenblocks zu einem komprimierten Datenblock.
Weiterhin betrifft die Erfindung ein Verfahren des Sortierens, Komprimierens, Dekomprimierens und Wiederherstellens eines Ursprungsdatenblocks, umfassend das vorerwähnte Verfahren des Sortierens und Komprimierens eines Ursprungsdatenblocks und zusätzliche Schritte.
Darüber hinaus betrifft die Erfindung eine Einrichtung zum Sortieren und Komprimieren eines Ursprungsdatenblocks, der aus einer Mehrzahl von Datenwerten besteht, worin
(a) ein Kontext verwendet wird, wobei jeder Datenwert innerhalb des Ursprungsdatenblocks einen Kontext hat, wobei der Kontext der primäre Sortierschlüssel ist; umfassend:
(b) ein Sortiermittel, das die Datenwerte gemäß dem primären Sortierschlüssel sortiert; und
(c) ein Komprimiermittel zum Komprimieren des sortierten Datenblocks zu einem komprimierten Datenblock.
Schließlich betrifft die Erfindung eine Einrichtung für das Sortieren, Komprimieren, Dekomprimieren und Wiederherstellen eines Ursprungsdatenblocks, umfassend die vorerwähnte Einrichtung zum Sortieren und Komprimieren eines Ursprungsdatenblocks und zusätzliche Mittel.

VERBUNDENE ANMELDUNGEN

Diese Anmeldung beansprucht die Priorität der österreichischen Patentanmeldung mit dem Aktenzeichen AT 2001/96, betitelt "Sortierverfahren und System zur Datenkompression" und eingereicht am 15. November 1996 von Dipl.-Ing. Michael Schindler.

HINTERGRUND

Datenkompression ist der Stand der Technik in der permanenten Datenspeicherung (z. B. Festplatte, Band, Diskette) wie auch in der Datenübertragung (z. B. unter Verwendung eines Modems). Es gibt hierfür gut bekannte Verfahren, die entweder in Software (z. B. als Teil eines Betriebssystems) oder in Hardware (z. B. Chips in Magnetband- und Datenübertragungseinrichtungen) ausgeführt sind. Obwohl Daten sequenziell als ein Datenstrom komprimiert werden können, erfordern die besseren Datenkompressionsverfahren ein Suchen oder Sortieren, welches die Ausführung in Hardware kompliziert macht und welches die Verarbeitungszeit in Software unbestimmt macht.
Ein Beispiel eines Sortierverfahrens ist die Burrows-Wheeler-Transformation (BWT), die in Burrows, M; Wheeler, D J: "A block-sorting lossless data compression algorithm", SRC Research Report, 10.05.94, Seiten 1 bis 18, XP646918 offenbart ist, worauf die Oberbegriffe der Ansprüche 1 und 7 basieren. Die Burrows-Wheeler Transformation verarbeitet einen Datenblock als eine einzige Einheit. Eine reversible Transformation wird auf einen Textblock angewandt, um einen neuen Block zu bilden, der die gleichen Zeichen hat. Diese Transformation hat die Tendenz, gleichartige Zeichen miteinander zu gruppieren, um so die Wahrscheinlichkeit des Findens eines Zeichens zu verbessern, das einem anderen Fall des gleichen Zeichens nahe ist. Dieser sortierte Text kann dann mit lokal-adaptiven Algorithmen, wie Move-to-front- Kodierung in Kombination mit Huffman-Kodierung oder arithmetischer Kodierung, komprimiert werden.
Weiter beschreiben Yokoo H. et al. in: "Data compression by context sorting", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Bd. E79-A, Nr. 5, 1. Mai 1996, Seiten 681-686, XP000621206 ein Verfahren der Datenkompression, worin im Gegensatz zu der Burrows-Wheeler-Transformation die Datenwerte durch Kodieren derselben in der Ursprungsfolge, d. h. in jener Reihenfolge, wie sie in den Eingangsdaten sind, komprimiert werden. Das Sortieren wird nur zum Erzeugen von Rängen für die Datenwerte benutzt. In dem von H. Yokoo et al. in dem vorerwähnten Dokument beschriebenen Beispiel wird angenommen, dass die Kontextfolge keine Gleichheit hat. Wenn Gleichheit auftritt, eliminieren H. Yokoo et al. den älteren Kontext mit dem gegenwärtigen Kontext. Demgemäss ist dieses Verfahren ein inhärenter Teil eines Kompressionsverfahrens zum Komprimieren derselben in der alten, ursprünglichen Reihenfolge und nicht ein Verfahren des Sortierens von Daten, um sie dann in einer neuen Reihenfolge, d. h. in der sortierten Reihenfolge, zu komprimieren.

ABRISS DER ERFINDUNG

Ein Ziel von bevorzugten Ausführungsformen der Erfindung ist es, ein Computersortiersystem zu schaffen, das sehr einfach, schnell, deterministisch in der Zeit und gut geeignet für Hardwareausführung ist. Das langsame Sortieren eines Datenblocks und das empfohlene Lauflängenkodieren des Standes der Technik wird durch ein neues Verfahren ersetzt. Der Output dieses Verfahrens wird dann durch irgendein Kodierverfahren des Standes der Technik, das für diese Aufgabe geeignet ist, komprimiert.
Dieses Ziel wird gemäß der Erfindung durch ein Verfahren des Sortierens und Komprimierens eines Ursprungsdatenblocks, wie eingangs erwähnt, erreicht, welches dadurch gekennzeichnet ist, dass
(d) der primäre Sortierschlüssel von fester, vorbestimmter Länge ist;
(e) ein sekundärer Sortierschlüssel aus der Position der Daten innerhalb des Ursprungsdatenblocks entwickelt wird; und
(f) für Datenwerte, deren primärer Sortierschlüssel der gleiche ist, die Daten gemäß dem sekundären Sortierschlüssel, vorzugsweise unter impliziter Verwendung des sekundären Sortierschlüssels, sortiert werden.
Demgemäss wird im Fall der Gleichheit nach einer vorbestimmten Anzahl von Schritten die Position der Daten innerhalb des Datenblocks anstelle von weiteren Vergleichen als Sortierschlüssel benutzt. Diese Position wird immer unterschiedlich für unterschiedliche Datenposten sein und wird daher immer zu einem eindeutigen Ergebnis führen. Unter Verwendung der Position als dem sekundären Sortierschlüssel wird nur eine vorbestimmte begrenzte Anzahl von Zeichen für das Sortieren benutzt (beschränkter Kontext). Eine Kontextgröße von 4-6 Zeichen ist für die meisten Fälle genügend.
Der Hauptvorteil ist nicht dieser frühe Ausgang, sondern, dass in den meisten Fällen, in denen die Anzahl von verglichenen Symbolen nicht viel größer ist als die Logarithmen zur Basis Zwei der Größe des zu sortierenden Datenblocks, ein Radixsortieralgorithmus, der ursprünglich für das mechanische Sortieren entwickelt wurde, verwendet werden kann. Dieses Sortierverfahren hat alle in der ursprünglichen Problembeschreibung geforderten Charakteristika: seine Hardwareausführung ist einfach, und seine Verarbeitungszeit ist schnell und fest. Ein zweiter Vorteil besteht darin, dass, wenn eine Radixsortierung benutzt wird, der Durchsatz nicht durch die Blockgröße beeinflusst wird. Dieses ermöglicht die Verwendung von großen Datenblöcken, was die Kompression verbessert. In Abhängigkeit von den Umständen mag eine Bucket- bzw. Speicherbereichssortierung oder eine Variante einer Mehrschlüssel-Schnellsortierung besser für die Sortieraufgabe geeignet sein.
Ein anderer Vorteil des beschränkten Kontexts besteht darin, dass irgendetwas als Kontext verwendet werden kann, z. B. das entsprechende Gebiet des letzten gleichartigen Datensatzes. Dieses ermöglicht eine verbesserte Kompression bei vielen Anwendungen.
In bevorzugten Ausführungsformen des obigen Verfahrens nach der Erfindung
(i) ist der Kontext ein interner Kontext, der von dem Ursprungsdatenblock ableitbar ist,
(ii) ist der Kontext ein externer Kontext, der unabhängig von dem Ursprungsdatenblock vorgesehen wird,
(iii) umfasst der Schritt (b) das Anwenden einer Radixsortierung.
Weiterhin stellt die Erfindung, wie eingangs erwähnt, ein Verfahren des Sortierens, Komprimierens, Dekomprimierens und Wiederherstellens eines Ursprungsdatenblocks zur Verfügung, umfassend die Schritte:
- (a) bis (f) gemäß Anspruch 1,
(g) - Dekomprimieren des komprimierten Datenblocks zu dem sortierten Ursprungsdatenblock,
(h) - Wiederherstellen des Ursprungsdatenblocks aus dem dekomprimierten sortierten Ursprungsdatenblock.
Gemäß einer bevorzugten Ausführungsform dieses Verfahrens umfasst der Schritt (h) des Wiederherstellens das Berechnen eines Transpositionsvektors, welcher aus der Burrows- Wheeler-Transformation abgeleitet wird.
Demgemäss kann das oben beschriebene Sortieren umgekehrt werden, was für die Dekompression wesentlich ist. Für die Umkehr müssen die Ausgangs- bzw. Startpunkte für jeden Sortierschlüssel (Kontext) bekannt sein. Im Fall von internen Kontexten zeigt Beispiel Eins einen Weg, alle Kontexte zu zählen und demgemäss Ausgangs- bzw. Startpunkte für jeden zu berechnen. Weiterhin kann eine Modifizierung der Verfahren des Standes der Technik dazu benutzt werden, Kontexte zu zählen. Im Fall von externen Kontexten ist alle Kontextinformation beim Dekodierer bekannt.
Im Gegensatz zu Sortierungen des Standes der Technik, welche eine eindeutige Reihenfolge durch fortlaufende Vergleiche herstellen, wird gemäß bevorzugten Ausführungsformen der Erfindung im Zweifel eine eindeutige Reihenfolge durch Betrachten der Ursprungsposition hergestellt.
Darüber hinaus stellt die Erfindung eine Einrichtung zum Sortieren und Komprimieren eines Ursprungsdatenblocks der eingangs genannten Art zur Verfügung, welcher dadurch gekennzeichnet ist, dass
(d) der primäre Sortierschlüssel von fester, vorbestimmter Länge ist;
(e) ein sekundärer Sortierschlüssel aus der Position der Daten innerhalb des Ursprungsdatenblocks abgeleitet wird; und
(f) für Datenwerte, deren primärer Sortierschlüssel der gleiche ist, das Sortiermittel die Daten gemäß dem sekundären Sortierschlüssel, vorzugsweise unter impliziter Verwendung des sekundären Sortierschlüssels sortiert.
Bevorzugte Ausführungsformen dieser Einrichtung sind jene, wie sie oben unten (i) und (ii) erwähnt sind, wie auch eine Ausführungsform, gemäß deren das Sortiermittel eine Radixsortierung anwendet.
Schließlich stellt die Erfindung, wie eingangs angegeben, eine Einrichtung zum Sortieren, Komprimieren, Dekomprimieren und Wiederherstellen eines Ursprungsdatenblocks zur Verfügung, umfassend:
- die Einrichtung gemäß Anspruch 7, weiter umfassend:
(g) - ein Dekomprimiermittel zum Dekomprimieren des komprimierten Datenblocks zu dem sortierten Ursprungsdatenblock; und
(h) - ein Wiederherstellungsmittel zum Wiederherstellen des Ursprungsdatenblocks aus dem dekomprimierten sortierten Ursprungsdatenblock.
Gemäß einer bevorzugten Ausführungsform dieser Einrichtung berechnet das Wiederherstellungsmittel einen Transpositionsvektor, welcher aus der Burrows-Wheeler-Transformation abgeleitet ist.
Die obigen und andere Merkmale der Erfindung, einschließlich verschiedener neuartiger Details des Aufbaus und der Kombination von Teilen, werden nun mehr im besonderen unter Bezugnahme auf die beigefügten Zeichnungen beschrieben und in den Ansprüchen aufgezeigt. Es versteht sich, dass das spezielle Computer-Sortiersystem für Daten-Kompression, welches die Erfindung verwirklicht, nur als Beispiel und nicht als eine Beschränkung der Erfindung gezeigt wird. Die Prinzipien und Merkmale dieser Erfindung können in variierten und zahlreichen Ausführungsformen verwirklicht werden, ohne den Bereich der Erfindung zu verlassen.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

Fig. 1 ist ein schematisches Blockdiagramm eines Rechensystems gemäß einer bevorzugten Ausführungsform der Erfindung.
Fig. 2 ist ein Blockdiagramm eines Kodierers, in dem interne Kontexte gemäß einer bevorzugten Ausführungsform der Erfindung verwendet werden.
Fig. 3 ist ein Blockdiagramm eines Dekodierers, in dem interne Kontexte gemäß einer bevorzugten Ausführungsform der Erfindung verwendet werden.
Fig. 4A-4B veranschaulichen ein Verfahren des Sortierens für die Kompression unter Verwendung von internen Kontexten.
Fig. 5A-5B veranschaulichen ein Verfahren des Entsortierens des sortierten Texts der Fig. 4B für die Dekompression unter Verwendung von internen Kontexten.
Fig. 6 ist ein Blockschaltbild eines externe Kontexte verwendenden Kodierers gemäß einer bevorzugten Ausführungsform der Erfindung.
Fig. 7 ist ein Blockschaltbild eines externe Kontexte verwendenden Dekodierers gemäß einer bevorzugten Ausführungsform der Erfindung.
Fig. 8A-8D veranschaulichen ein Verfahren, das in Situationen verwendet wird, in denen die Kontexte für jeden Datenposten, der zu kodieren ist, als Eingangsdaten zugeführt werden, welche sowohl dem Kodierer als auch dem Dekodierer bekannt sind.
Fig. 9 ist ein Ablaufdiagramm eines bevorzugten Verfahrens für das Ausführen einer Transformationsfunktion.
Fig. 10 ist ein Ablaufdiagramm eines bevorzugten Verfahrens einer inversen Transformationsfunktion.
Fig. 11 ist ein Ablaufdiagramm eines bevorzugten Verfahrens von einer anderen inversen Transformationsfunktion.
Fig. 12 ist ein Ablaufdiagramm eines Verfahrens hoher Ordnung für eine Transformationsfunktion.

DETAILLIERTE BESCHREIBUNG VON BEVORZUGTEN AUSFÜHRUNGSFORMEN DER ERFINDUNG

Fig. 1 ist ein schematisches Blockschaltbild eines Rechensystems gemäß einer bevorzugten Ausführungsform der Erfindung. Es sind zwei Computer 10, 20 veranschaulicht, die über ein Verbindungsglied 30 durch jeweilige Modems 18, 28 kommunizieren. Jeder Computer 10, 20 wird durch einen jeweiligen Benutzer 2, 2' betrieben. Daten werden auf jeweiligen Platten 15, 25 gespeichert.
Gemäß einer bevorzugten Ausführungsform der Erfindung lässt jeder Computer 10, 20 einen jeweiligen Datenzuordner bzw. -kodierer 50, 50' ablaufen. Jeder Datenzuordner bzw. -kodierer 50, 50' umfasst einen jeweiligen Encoder 52, 52' für das Komprimieren von Daten und einen jeweiligen Dekodierer 54, 54' für das Dekomprimieren von Daten. Der Datenzuordner bzw. -kodierer 50, 50' kommuniziert mit dem Modem 18, 28, um Daten für die Übertragung über das Verbindungsglied 30 zu kodieren und um von dem Verbindungsglied 30 empfangene Daten zu dekodieren. Der Datenzuordner bzw. -kodierer 50, 50' kann auch Daten für das Speichern auf der Platte 15, 25 kodieren und die von der Platte 15, 25 gelesenen gespeicherten Daten- dekodieren.
In einer bevorzugten Ausführungsform der Erfindung ist der Zuordner bzw. Kodierer 50 innerhalb eines Rechensystems integriert bzw. eingebaut. Der Zuordner bzw. Kodierer 50 kann ein ausführbares Softwareprogramm oder ein Hardwaremodul sein. In jedem Fall ist der Zuordner bzw. Kodierer 50 in einem maschinenlesbaren Medium ausgeführt, wie magnetische oder optische Speicherung, oder direkt in eine bzw. einer Schaltungseinrichtung hergestellt. Ein bevorzugte Ausführungsformen der Erfindung verkörperndes Computerprogramm wird vorzugsweise auf einem magnetischen Speichermedium (z. B. Festplatte, Floppydisk oder Band) oder auf einem optischen Speichermedium (z. B. CD-ROM) vertrieben.
Insbesondere umfassen bevorzugte Ausführungsformen der Erfindung ein Verfahren zum Sortieren von Daten, welches Datenposten zusammenbringt, die in einer ähnlichen bzw. gleichartigen Umgebung (dem "Kontext") auftreten. Dieses Aufzeichnen ("Transformation") des Datenblocks ermöglicht es, ihn effizienter unter Verwendung von bekannten Kompressionsalgorithmen zu komprimieren. Die Kontexte können "intern" sein, was bedeutet, dass sie durch die anderen Bytes in dem Datenblock, der kodiert wird, hergestellt sein können. Die Kontexte können auch "extern" sein, was bedeutet, dass sie als Daten vorgesehen sein können, die sowohl dem Kodierer bzw. Encoder 52 als auch dem Dekodierer 54 bekannt sind.
Fig. 2 ist ein Blockschaltbild eines interne Kontexte nutzenden Kodierers bzw. Encoders 52 gemäß einer bevorzugten Ausführungsform der Erfindung. Ein Ursprungsdatenblock 105 wird mittels einer Transformationsfunktion 110 entweder unter Verwendung der Burrows- Wheeler-Transformation (BWT) des Standes der Technik oder einer unten beschriebenen Transformation verarbeitet. Es wird ein Start- bzw. Beginnindex 115 gespeichert, weicher zum Umkehren der Transformation benötigt wird. Die transformierten Daten werden dann durch eine Kompressionstransformationsdatenfunktion 120 unter Verwendung von irgendeinem geeigneten Kompressionsverfahren komprimiert. Zwei- oder mehrstufiges arithmetisches Kodieren unter Verwendung eines Caches und zweier Spezialsymbole für die binäre Repräsentation einer Wiederholungszählung waren brauchbar. Die kodierten Daten 125 umfassen die komprimierten Transformationsdaten und den Startindex 115.
Fig. 3 ist ein Blockschaltbild eines interne Kontexte benutzenden Dekodierers 54 gemäß einer bevorzugten Ausführungsform der Erfindung. Um den Ursprungsdatenblock 105 wieder zu gewinnen, wird der Kompressionsalgorithmus 120 (Fig. 2) umgekehrt. Der Startindex 115 wird von den kodierten Daten 125 abgetrennt. Die übrigen Daten werden dann durch einen Dekomprimierer 150 dekomprimiert. Die resultierenden dekodierten Daten und der Startindex 115 werden dann mittels einer inversen Transformationsfunktion 155 verarbeitet, welches das Dekodieren vollendet und einen dekodierten Datenblock 105' hervorbringt, der identisch mit dem Ursprungsdatenblock 105 ist.
Die Differenz zwischen bevorzugten Ausführungsformen der Erfindung und der BWT ist die Transformation 110 (Fig. 2) und die inverse Transformation 155 (Fig. 3). Die Transformation gemäß der vorliegenden Erfindung und die Differenzen gegenüber der BWT werden vollständiger in dem folgenden Beispiel beschrieben.
Die Fig. 4A-4B veranschaulichen ein Verfahren des Sortierens für die Kompression unter Verwendung von internen Kontexten. Wie in Fig. 4A veranschaulicht ist, verwendet das Beispiel Rang 2, Text "abracadabra", Alphabet {"a", "b", "c", "d", "r"}. Der Ursprungsdatenblock 105 sind daher die geordneten Buchstaben:
a b r a c a d a b r a
Von jedem Buchstaben in dem Ursprungsdatenblock 105 wird bestimmt, dass die vorherigen beiden Buchstaben 107 sind:
ra aa ab br ra ac ca ad da ab br
Jeder Buchstabe in dem Ursprungsdatenblock 105 wird auch einer jeweiligen Textposition oder einem Index 109 in dem Ursprungsdatenblock 105 zugeordnet. Weil elf Buchstaben vorhanden sind, gibt es elf Textpositionen 107 (1-11), wie dargestellt.
Die Buchstaben werden dann durch die vorherigen Buchstaben sortiert, wie in Fig. 4B veranschaulicht ist. Der Sortierer schaut zunächst nach dem unmittelbar vorhergehenden Buchstaben, und wenn sie gleich sind, vergleicht er den nächsten vorherigen Buchstaben.
Wenn zwei Buchstaben den gleichen Kontext haben, werden sie in der Reihenfolge aufgelistet, in der sie in dem Ursprungsdatenblock erscheinen.
Die resultierenden sortierten Buchstaben 112 sind:
b d b a c r r a a a a
Für jeden Buchstaben werden die vorherigen Buchstaben 107' und die Textposition 109' von dem Ursprungsdatenblock 105 festgehalten. Der sortierte Text "bdbacrraaaa" kann nun durch die Kompressionstransformationsdatenfunktion 120 (Fig. 2) komprimiert werden.
Bei größeren Blöcken und höherem Rang (für Text angenähert 4 bis 6) erscheinen Blöcke wie jene bei der Vollsortierung der BWT. Zum Beispiel werden die Buchstaben "sor" oft durch den Buchstaben "t" auf dieser Seite gefolgt.
Wenn man die BWT verwendet, wäre es notwendig, die Kontexte "dabra" und "aabra" zu betrachten, um die Sortierordnung von a(1) und c(5) zu bestimmen. In einigen Fällen (z. B. 1000 Null-Bytes) kann der Kontext sehr groß werden, bevor eine Sortierordnung bzw. -reihenfolge hergestellt werden kann. Der Nachteil wird vermieden, indem man bevorzugte Kompressionsverfahren, wie unten beschrieben, verwendet.
Die Fig. 5A-5B veranschaulichen ein Verfahren des Entsortierens des sortierten Textes der Fig. 4B für die Dekompression unter Verwendung von internen Kontexten. Nach der Dekodierung ist die Sequenz des dekodierten Textes 112' bekannt. Es ist außerdem bekannt, dass die denselben vorhergehenden Buchstaben in einer Reihenfolge sortiert waren, und diese Sequenz 151 kann aus dem dekodierten Text unter Verwendung eines Sortier- oder Zählverfahrens, gleichartig bzw. ähnlich der inversen BWT, erzeugt werden, welches zu der Sequenz "aaaaabbcdrr" zurückkehrt. Diese Buchstaben 151 sind die Vorgänger von jedem der Buchstaben in dem dekodierten Text 112'.
Da die Prozessorsortiersequenz 151 das Kontextbyte unmittelbar vordem sortierten Textposten ist, können sie mit dem dekodierten Text 112' kombiniert werden, um Paare von Buchstaben 152 zu erfahren.
Jedes dieser Paare von Buchstaben ist außerdem der Kontext für einen der Buchstaben in dem dekodierten Text. Diese Paare 152 werden dann zunächst durch das letzte Zeichen sortiert, wie es beim Kodieren getan wurde, was eine Sortierordnung bzw. -reihenfolge 153 in der gleichen Ordnung bzw. Reihenfolge wie der dekodierte Text 107' (Fig. 4B) hervorbringt. Ein Sequenzindex 154 wird dann den sortierten Paaren 153 zugeordnet.
Die Ordnung bzw. Reihenfolge des Ursprungsdatenblocks kann nun, wie in Fig. 5B veranschaulicht, rekonstruiert werden. Wie bei der BWT wird die Position des ursprünglich letzten (oder ersten) Zeichens - Index 11 in diesem Fall, welcher dem Kontext "br" aus den sortieren Paaren 153 zugeordnet ist und welcher selbst der Kontext für ein "a" aus dem dekodierten Text 112 ist - sortiert. Alternativ kann der Kontext des ersten Zeichens gespeichert werden.
Auf die eine oder die andere Art erhält man "bra" als Kontext für das erste Zeichen. Nun sucht man den ersten Kontext "ra" (Index 4) und erhält ein weiteres "a" als nächsten Buchstaben. Kontext "aa"-> b(1), Kontext "ab"-> r(6), weil der erste erscheinende Buchstabe im Fall von nichteindeutigen Kontexten zuerst in der sortierten Datei kommt, "br"-> a(10, "ra"- > c(5, da der Index 4 bereits verwendet wird), "ac"-> a(8), "ca"-> d(2), "ad"-> a(9), "da"-> b(3) und "ab"-> r(7). Auf diese Weise kann der Ursprungstext "abracadabra" 105' vollständig wiedergewonnen werden.
In einer praktischen Ausführung wird ein Zeiger bzw. eine Marke zum Beginn von jedem Kontext in einer Hash-Tabelle gespeichert. Wenn dieser Kontext erscheint, folgt man dem Zeiger bzw. der Marke und findet die korrekte Fortsetzung. Dann wird der Zeiger bzw. die Marke um eins inkrementiert.
Für höhere Ordnung kann die Ordnung auf diese Weise erhöht werden: die bekannten n-Buchstaben-Kombinationen werden durch den ihnen folgenden Buchstaben verlängert, wie hier die bekannten 1-Buchstaben-Kontexte, die durch Sortieren oder Zählen hergestellt worden sind, zu Zwei-Buchstaben-Kontexten verlängert wurden. Dieses führt zum Wissen von allen n+1-Buchstaben-Kombinationen des Ursprungstexts. Dieser Prozess kann wiederholt werden, bis die Kontextgröße groß genug ist.
Es ist auch möglich, eine inverse BWT auf den sortierten Text anzuwenden - alle langen Buchstaben-Kombinationen von der Ordnung +1 werden korrekt zurückgeführt und geben demgemäss alle Kontexte des Ursprungstexts. Es könnte sein, dass die inverse BWT frühzeitig zum Ursprung zurückkehrt; wenn dieses der Fall ist, muss die inverse BWT wieder erneut mit einem neuen Index begonnen werden, bis alle Indices verwendet sind.
Fig. 6 ist ein Blockdiagramm eines Encoders bzw. Kodierers 52 unter Verwendung von externen Kontexten gemäß einer bevorzugten Ausführungsform der Erfindung. Für jeden Posten in einem Ursprungsdatenblock 205, der kodiert werden soll, wird ein entsprechender Kontext 210 vorgesehen. Eine Transformation 215 gemäß der vorliegenden Erfindung wird dann ausgeführt, und der transformierte Datenblock wird dann durch eine Funktion zum Komprimieren der transformierten Daten 220 unter Verwendung von irgendeinem geeigneten Verfahren zu kodierten Daten 225 kodiert.
Fig. 7 ist ein Blockschaltbild eines Dekodierers 54 unter Verwendung von externen Kontexten gemäß einer bevorzugten Ausführungsform der Erfindung. Um den Ursprungsdatenblock 205 wiederherzustellen, werden die kodierten Daten 225 zuerst durch eine Dekodiererfunktion 250 dekodiert, welche das Inverse des Algorithmus benutzt, der in der Funktion zum Komprimieren der transformierten Daten 225 benutzt wurde (Fig. 6). Um eine inverse Transformation 255 auszuführen, werden die gleichen Kontextdaten 210, die dem Encoder bzw. Kodierer 52 dargeboten wurden, als Eingangsdaten zugeführt. Dieses befähigt dazu, den Ursprungsdatenblock durch die inverse Transformation 255 als einen dekodierten Datenblock 205' wiederherzustellen, der identisch mit dem Ursprungsdatenblock 205 ist. Weitere Einzelheiten einer bevorzugten Ausführungsform der Erfindung, die externe Kontexte benutzt, werden in dem folgenden Beispiel beschrieben.
Die Fig. 8A-8D veranschaulichen ein Verfahren, das in Situationen verwendet wird, in denen die Kontexte für jeden zu kodierenden Datenposten als Eingangsdaten zugeführt werden, die sowohl dem Encoder bzw. Kodierer als auch dem Dekodierer bekannt sind. Wie in dem obigen Beispiel sortiert das Verfahren die Datenposten gemäß den Kontexten, und wenn die Kontexte gleich sind, wird die Position in dem Ursprungsdatenblock als ein sekundärer Sortierschlüssel verwendet. Ein Beispiel dieser Art von Anwendung ist das für das Kodieren von Bilddaten unter Verwendung einer Binärpyramide.
Wie in Fig. 8A veranschaulicht ist, wird jedem Pixel 300 eine Kennzeichnung zugeordnet, hier "A", "b", "c", "d" und "e". Wie in Fig. 8B veranschaulicht ist, wird das zu kodierende Bild in kleine Quadrate 305 unterteilt (hier sind die Kanten vier Pixellängen lang), und die Ecken werden mit "A" gekennzeichnet und zuerst verarbeitet. Dann werden die Zentren dieser kleinen Quadrate (mit "b" gekennzeichnet) verarbeitet. Wie in Fig. 8C veranschaulicht ist, ergeben die mit "A" und "b" gekennzeichneten Pixel zusammen kleinere Quadrate 310, die so gedreht sind, dass sie auf einer Ecke stehen. Die Mittelpunkte dieser kleineren Quadrate (mit "c" gekennzeichnet) sind als nächstes zu verarbeiten. Wie in Fig. 8D veranschaulicht ist, bilden die mit "A", "b" und "c" gekennzeichneten Pixel zusammen noch kleinere Quadrate 315 mit einer Kantengröße von zwei Pixellängen. Die Mittelpunkte jener Quadrate (mit "d" gekennzeichnet) kommen als nächstes. Dieses wird fortgesetzt, bis alle Pixel verarbeitet sind. Die anfängliche Quadratgröße kann größer als die in diesem Beispiel verwendeten vier Pixel sein, und die Verarbeitung wäre die gleiche, ausgenommen die Zunahme in der Anzahl von Niveaus (f, g, h, ...) gegenüber den fünf (A ... e), die hier benutzt wurden.
Das Kodieren des Bilds kann als fünf separate Blöcke ausgeführt werden. Der erste enthält alle die mit "A" gekennzeichneten Pixel, der zweite enthält die mit "b" gekennzeichneten Pixel, gefolgt von den mit "c", "d" und "e" gekennzeichneten Pixeln. Wenn der Block der mit "A" gekennzeichneten Pixel kodiert wird, sind keine anderen Kontextdaten bekannt, so dass die mit "A" gekennzeichneten Pixel unter Verwendung eines Verfahrens kodiert werden müssen, das keine externen Kontexte erfordert. Es könnte das durch die Fig. 4A-4B veranschaulichte Verfahren oder irgendein anderes Verfahren benutzt werden. Das Verfahren gemäß einer bevorzugten Ausführungsform der Erfindung wird zum Verarbeiten der mit "b" gekennzeichneten Pixel und der nachfolgenden Niveaus verwendet.
Jedes mit "b" gekennzeichnete Pixel hat einen Kontext, der durch die vier mit "A" gekennzeichneten Pixel an seinen Ecken bestimmt wird. Da die mit "A" gekennzeichneten Pixel vorher kodiert wurden, sind sie dem Dekodierer bekannt, wenn er die mit "b" gekennzeichneten Pixel dekodiert. Die mit "b" gekennzeichneten Pixel sind der Ursprungsdatenblock 205 (Fig. 6), und die Kontexte, welche durch die mit "A" gekennzeichneten Pixel für jedes mit "b" gekennzeichnete Pixel gebildet sind, sind die Kontextdaten 210. Wenn jeder Kontext aus vier Bytes besteht, wie wenn vier mit "A" gekennzeichnete Acht-Bit-Pixel zu einem 32-Bit-Wort verkettet werden, ist die Transformation 215 eine Sortierung vierter Ordnung, wie in der zweiten Ausführung unten gezeigt ist. Wenn die Transformation einmal geschehen ist, kann der gleiche Kodieralgorithmus für die Kodiertransformationsdatenfunktion 225, wie er oben benutzt wurde, benutzt werden. Nachdem die mit "b" gekennzeichneten Pixel kodiert worden sind, können die mit "A" und "b" gekennzeichneten Pixel als die Kontexte zum Transformieren der mit "c" gekennzeichneten Pixel verwendet werden. Dieser Prozess wird fortgesetzt, bis alle Niveaus verarbeitet worden sind.
Es sind viele Abwandlungen möglich. Anstelle der Verwendung der Pixelwerte als der Ursprungsdatenblock 205 können die Daten Fehler gegenüber vorhergesagten Werten enthalten. In diesem Fall würden die Kontexte nicht direkt durch Verketten der mit "A" gekennzeichneten Roheckenpixel gebildet werden, sondern sie würden vielmehr aus einer von jenen mit "A" gekennzeichneten Pixeln synthetisierten Fehlerschätzfunktion bestehen. Derartige Abwandlungen beeinträchtigen nicht bevorzugte Verfahren der vorliegenden Erfindung, da die Sortierung der Daten gemäß den Kontexten noch in der gleichen Art und Weise ausgeführt würde.
Dieses Beispiel demonstriert, wie die Kombination einer Sortierung mit endlichem Kontext, gefolgt von einer Sortierung-durch-Position, als eine Lösung für einen weiten Bereich von Anwendungen in der Datenkompression benutzt werden kann, um gleichartige bzw. ähnliche Kontexte zusammenzubringen. Es sei beachtet, dass das Aufnehmen einer eindeutigen Position in einem Sortierschlüssel äquivalent dem hier beschriebenen Verfahren ist - er wird gerade Teil des primären Schlüssels anstatt dass er ein sekundärer Schlüssel ist oder implizit als solcher gehandhabt wird, wie in der folgenden ersten Ausführung. Dieses gilt, selbst wenn der so konstruierte Schlüssel einen unendlichen Kontext benutzt, weil jeder Vergleich an der eindeutigen Position stoppen wird.
Vier beispielhafte Ausführungen werden unten angegeben. Die ersten drei Ausführungen benutzen einen Rang 2 (zwei Byte)-Kontext, welcher es ermöglicht, die in dem Verfahren benutzten Zähler unter Verwendung von einfachen Anordnungen bzw. Gruppierungen zu handhaben, und welcher dann die Benutzung der Blockposition als sekundärer Sortierschlüssel ermöglicht, die bzw. der äußerst einfach zu verstehen ist. Die erste Ausführung beschreibt einen Encoder bzw. Kodierer, der sowohl für interne als auch externe Kontexte verwendet werden kann. Die zweite Ausführung beschreibt einen Dekodierer für externe Kontexte. Die dritte Ausführung beschreibt einen Dekodierer für interne Kontexte. Die vierte Ausführung beschreibt einen Encoder bzw. Kodierer, der interne Kontexte benutzt, welcher höhere Ordnungen handhaben kann und welcher die Radixsortierung benutzt.
Bevorzugte Ausführungsformen der Erfindung benutzen Zähler zum Bestimmen der Frequenz von jedem Kontext und dann zum Bestimmen seiner Position in dem sortierten Datenblock. Dieses wird mit Bezug auf eine erste, zweite und dritte Ausführung unten beschrieben. Diese bevorzugte Ausführung sieht drei Zählerfunktionen vor:
InitCounters - setzt den Zählerwert auf Null
GetAndIncrement - gewinnt den Zählerwert, der einem Kontext zugeordnet ist, zurück und nachinkrementiert denselben
AddCounters - ersetzt jeden Zählerwert durch eine Summe von vorherigen Zählerwerten
Die erste, zweite und dritte Ausführung führen diese Funktionen für Rang 2 (Zwei- Byte-Kontext) aus, welche die Benutzung einer einfachen Gruppierung bzw. Anordnung ermöglicht, die einen Zähler [i]-Wert für jeden möglichen Kontext i vorsieht. Bei höheren Ordnungen mag eine Anordnung bzw. Gruppierung, die alle möglichen Kontexte repräsentiert, nicht praktisch sein, und die einfache Anordnung bzw. Gruppierung kann durch einen Trie, einen Baum, eine Hash-Tabelle oder eine andere Möglichkeit ersetzt sein. Beachte, dass Bäume und Tries in der Reihenfolge durchlaufen werden können, die für AddCounters benötigt wird, wohingegen die Kontexte sortiert werden, wenn eine Hash-Tabelle benutzt wird. Ein Prototyp-Pseudo-Code-Fragment zur Implementierung von Zählern gemäß einer bevorzugten Ausführungsform der Erfindung für Ordnung 2 ist wie folgt:
Fig. 9 ist ein Ablaufdiagramm eines bevorzugten Verfahrens für das Ausführen einer Transformationsfunktion. Das Verfahren 400 wird für die Transformationsfunktionen 110 (Fig. 2), 215 (Fig. 6) für interne und externe Kontexte verwendet, die bei Kompression benutzt werden. Im Schritt 405 werden Datenvariable initialisiert. Im Schritt 410 wird der Ursprungsdatenblock gelesen. Im Schritt 415 wird die Häufigkeit des Auftretens von jedem Kontext in dem Datenblock berechnet. Im Schritt 420 wird die Position des ersten Falls von jedem Kontext in dem Datenblock berechnet. Im Schritt 425 werden die Daten von dem Datenblock durch Kontext sortiert.
Im Schritt 430 wird eine Prüfung durchgeführt, um zu bestimmen, ob interne Kontexte verwendet werden. Wenn das so ist, dann wird der Index des letzten Elements in den sortierten Daten im Schritt 435 gespeichert.
Eine Prototyp-Pseudo-Code-Fragment-Implementierung des Ablaufdiagramms der Fig. 9 wird unten gegeben. Es wird angenommen, dass eine Funktion context(i) existiert, die den Kontext von jedem Symbol in dem zu verarbeitenden Block gibt. Für interne Kontexte gibt diese Funktion die vorherigen vier Bytes im Block zurück. Dieses Beispiel benutzt eine Bucket- bzw. Speicherbereichssortierung, um die Relation zu dem Dekodierer besser zu zeigen. Die Posten werden durch den Wert bzw. mittels des Werts ihres Kontexts sortiert.
Fig. 10 ist ein Ablaufdiagramm eines bevorzugten Verfahrens einer inversen Transformationsfunktion. Das Verfahren 500 ist auf die inverse Transformation 250 (Fig. 7) anwendbar, die für externe Kontexte bei der Dekompression benutzt wird. Im Schritt 505 werden Datenvariable initialisiert. Im Schritt 510 wird der dekomprimierte Datenblock gelesen. Im Schritt 515 wird die Häufigkeit des Auftretens von jedem Kontext in dem Datenblock berechnet. Im Schritt 520 wird die Position des ersten Falls von jedem Kontext in dem Datenblock berechnet. Im Schritt 525 werden die Daten entsortiert.
Eine Prototyp-Pseudo-Code-Fragment-Implementierung des Ablaufdiagramms der Fig. 10 wird unten gegeben. Es wird angenommen, dass eine Funktion context(i) existiert, die den Kontext von jedem Symbol in dem zu verarbeitenden Block gibt. Beachte, dass bei externen Kontexten alle Kontexte 210 (Fig. 6-7) bereits bekannt sind, so dass diese Funktion definiert ist.
Fig. 11 ist ein Ablaufdiagramm eines bevorzugten Verfahrens einer anderen inversen Transformationsfunktion. Das Verfahren 600 ist auf die inverse Transformation 155 (Fig. 3) für interne Kontexte, die bei der Dekompression benutzt werden, anwendbar. Im Schritt 605 werden Datenvariable initialisiert. Im Schritt 610 werden Zeichenzähler von einer Eingangsanordnung bzw. -gruppierung berechnet, die den dekodierten Datenblock hat. Im Schritt 615 wird ein Transpositionsvektor aus den Zeichenanzahlen berechnet. Im Schritt 620 werden Ordnung 2-Kontextanzahlen aus der Eingangsanordnung bzw. -gruppierung und dem Transpositionsvektor berechnet. Im Schritt 625 werden Datenwerte, die jedem Kontext zugeordnet sind, in eine Outputanordnung bzw. -gruppierung geschrieben, welche die entsortierte Eingangsanordnung bzw. -gruppierung ist. Ein Prototyp-Pseudo-Code-Fragment für die Implementierung des Verfahrens der Fig. 11 ist wie folgt:
Fig. 12 ist ein Ablaufdiagramm eines Verfahrens höheren Rangs für eine Transformationsfunktion. Das Verfahren 700 kann als eine Transformation 110 (Fig. 2) höheren Rangs für interne Kontexte angewandt werden. Eine speziell bevorzugte Ausführung der Transformation unterstützt 6-Byte-Kontexte und benutzt eine Radixsortierung, um schnelle Kodiergeschwindigkeiten zu erreichen. Sie sortiert die Daten in drei Durchgängen unter Verwendung von zwei Bytes von dem Kontext in jedem Durchgang.
Im Schritt 705 werden, wie oben, Datenvariable initialisiert. Im Schritt 710 wird jeder Kontext, wie oben, gezählt. Im Schritt 715 werden, wie oben, alle kleineren Kontexte unabhängig von dem Systemende summiert.
Im Schritt 720 beginnt eine Schleife, um mehrere Durchläufe des Sortierens zu verarbeiten. Im Schritt 720 wird ein Schleifenindex inkrementiert. Im Schritt 725 wird die Sortierung für den gegenwärtigen Durchlauf durchgeführt. Im Schritt 730 kann die Schleife zum Schritt 720 für einen anderen Durchlauf oder eine andere Verarbeitung zurückzukehren.
Bevorzugte Ausführungsformen der Erfindung können leicht in Hardware implementiert werden, indem Variable durch Speicherung, Schleifen durch Zähler und Indices durch Speicherauslesungen, wo der Index zu den Adressenverbindern geschickt wird, ersetzt werden.
Es gibt Optimierungen, die durch Hardwareimplementierungen ausgenutzt werden können. Zum Beispiel macht es Sinn, einige Bytes in einem schnellen statischen Ram zu sammeln und sie dann als ein Block zu einem langsamen dynamischen Ram zu übertragen. Es ist auch möglich, Überlappung bzw. Pipelining leicht einzuführen; ein Block wird nachverarbeitet, einige andere sind in anderen bzw. unterschiedlichen Sortierstadien oder werden vorverarbeitet/gezählt. Da irgendein Zwischenstadium möglich ist (CPU + ROM-Programm - Hardware oder Software), versteht es sich, dass alle solche Kombinationen innerhalb des Bereichs der Erfindung sind. Ein Prototyp-Pseudo-Code-Fragment ist wie folgt:

ÄQUIVALENTE

Obwohl die Erfindung speziell unter Bezugnahme auf bevorzugte Ausführungsformen derselben gezeigt und beschrieben worden ist, versteht es sich für den Fachmann, dass verschiedene Änderungen in der Form und in den Einzelheiten durchgeführt werden können, ohne den Bereich der Erfindung zu verlassen, wie er durch die beigefügten Ansprüche definiert ist. Obwohl z. B. die Erfindung unter Bezugnahme auf spezielle Hardware- und Softwareausführungsformen beschrieben worden ist, versteht es sich, dass verschiedene Aspekte der Erfindung entweder in Hardware, Software oder Firmware ausgeführt werden können.
Es ist beabsichtigt, dass diese und alle anderen Äquivalente von den folgenden Ansprüchen umfasst sind.

Claims

1. Verfahren zum Sortieren und Komprimieren eines Ursprungsdatenblocks (105), bestehend aus einer Mehrzahl von Datenwerten, umfassend die Schritte des:

(a) Verwendens eines Kontexts, wobei jeder Datenwert innerhalb des Ursprungsdatenblocks (105) einen Kontext hat, wobei der Kontext der primäre Sortiertschlüssel ist;

(b) Sortierens der Datenwerte gemäß dem primären Sortierschlüssel (107); und

(c) Komprimierens des sortierten Ursprungsdatenblocks zu einem komprimierten Datenblock,

dadurch gekennzeichnet, dass

(d) der primäre Sortierschlüssel von fester, vorbestimmter Länge ist;

(e) ein sekundärer Sortierschlüssel aus der Position der Daten innerhalb des Ursprungsdatenblocks (105) abgeleitet wird; und

(f) für Datenwerte, deren primärer Sortierschlüssel (107) der gleiche ist, die Daten gemäß dem sekundären Sortierschlüssel, vorzugsweise unter impliziter Verwendung des sekundären Sortierschlüssels, sortiert werden.

2. Verfahren nach Anspruch 1, worin der Kontext ein interner Kontext ist, welcher aus dem Ursprungsdatenblock (105) ableitbar ist.

3. Verfahren nach Anspruch 1, worin der Kontext ein externer Kontext ist, welcher unabhängig von dem Ursprungsdatenblock vorgesehen wird.

4. Verfahren nach Anspruch 1, 2 oder 3, worin der Schritt (b) das Anwenden einer Radix- bzw. Digitalsortierung umfasst.

5. Verfahren zum Sortieren, Komprimieren, Dekomprimieren und Wiederherstellen eines Ursprungsdatenblocks (105), umfassend die Schritte:

- (a) bis (f) gemäß Anspruch 1,

(g) - Dekomprimieren des komprimierten Datenblocks (125) zu dem sortierten Ursprungsdatenblock,

(h) - Wiederherstellen des Ursprungsdatenblocks (105') aus dem dekomprimierten sortierten Ursprungsdatenblock.

6. Verfahren nach Anspruch 5, worin der Schritt (h) des Wiederherstellens das Berechnen eines Transpositionsvektors (615) umfasst, welcher aus der Burrows-Wheeler-Transformation abgeleitet ist.

7. Einrichtung zum Sortieren und Komprimieren eines Ursprungsdatenblocks (105), bestehend aus einer Mehrzahl von Datenwerten, worin

(a) ein Kontext verwendet wird, wobei jeder Datenwert innerhalb des Ursprungsdatenblocks (105) einen Kontext hat, wobei der Kontext der primäre Sortierschlüssel ist; umfassend:

(b) ein Sortiermittel, welches die Datenwerte gemäß dem primären Sortierschlüssel (107) sortiert; und

(c) ein Komprimiermittel zum Komprimieren des sortierten Ursprungsdatenblocks zu einem komprimierten Datenblock,

dadurch gekennzeichnet, dass

(d) der primäre Sortierschlüssel von fester, vorbestimmter Länge ist;

(f) für Datenwerte, deren primärer Sortierschlüssel (107) der gleiche ist, das Sortiermittel die Daten gemäß dem sekundären Sortierschlüssel, vorzugsweise unter impliziter Verwendung des sekundären Sortierschlüssels, sortiert.

8. Einrichtung nach Anspruch 7, worin der Kontext ein interner Kontext ist, welcher aus dem Ursprungsdatenblock(105) ableitbar ist.

9. Einrichtung nach Anspruch 7, worin der Kontext ein externer Kontext ist, welcher unabhängig von dem Ursprungsdatenblock (105) vorgesehen ist.

10. Einrichtung nach Anspruch 7, 8 oder 9, worin das Sortiermittel eine Radix- bzw. Digitalsortierung anwendet.

11. Einrichtung zum Sortieren, Komprimieren, Dekomprimieren und Wiederherstellen eines Ursprungsdatenblocks (105), umfassend:

- die Einrichtung gemäß Anspruch 7, weiter umfassend:

(g) - ein Dekomprimiermittel zum Dekomprimieren des komprimierten Datenblocks (125) zu dem sortierten Ursprungsdatenblock; und

(h) - ein Wiederherstellungsmittel zum Wiederherstellen des Ursprungsdatenblocks (105') aus dem dekomprimierten sortierten Ursprungsdatenblock.

12. Einrichtung nach Anspruch 11, worin das Wiederherstellungsmittel einen Transpositionsvektor (615) berechnet, welcher aus der Burrows-Wheeler-Transformation abgeleitet ist.