DE102006028469B4

DE102006028469B4 - Adaptives Quantisiertes Codierungsverfahren

Info

Publication number: DE102006028469B4
Application number: DE200610028469
Authority: DE
Inventors: Iakov Nekritch; Marek Karpinski
Original assignee: Karpinski Marek Prof Dr
Current assignee: Karpinski Marek Prof Dr
Priority date: 2006-06-21
Filing date: 2006-06-21
Publication date: 2010-12-02
Anticipated expiration: 2026-06-22
Also published as: DE102006028469A1

Abstract

Verfahren für die adaptive präfix-freie Codierung eines Datenstroms über einem Alphabet aus n Elementen mit zwei Parameter p und q, wobei p größer als q ist, gekennzeichnet dadurch, dass die Codewortlängen aufgrund von der Länge des bereits codierten Teils des Textes geteilt durch Parameter q und aufgerundet, weiterhin quantisierte Textlänge genannt, sowie der Häufigkeit des Symbols im bereits codierten Teil des Textes geteilt durch Parameter q und abgerundet, weiterhin quantisierte Häufigkeit genannt, bestimmt werden, und weist auf:
– eine Liste R von bereits codierten Symbolen
– ein Verfahren A für die Aktualisierung der Länge des codierten Symbols
– ein Verfahren B, das den Code modifiziert, nachdem die Länge eines Symbols geändert wurde.

Description

Unsere Erfindung ist ein adaptives Verfahren für die präfixfreie Codierung. Die präfixfreie Codierung ist eine der am weitesten verbreiteten Kompressionsmethoden und findet in vielen Kompressionsprogrammen und Dateiformaten (z. B. gzip, JPEG, PNG usw.) ihre Anwendung.
Das Problem der statischen präfixfreien Codierung kann wie folgt formuliert werden: Gegeben ist ein Datenstrom S = s₁...s_m über dem Alphabet a₁, a₂, ..., a_n. Jedem Symbol a_i ∈ A wird ein Codewort c_i zugewiesen, so dass die Gesamtcodierungslänge möglichst klein ist. Man unterscheidet zwischen der statischen und der adaptiven präfixfreien Codierung. Bei der statischen Codierung wird der Datenstrom zweimal gelesen. Beim ersten Durchlauf durch die Daten werden die Häufigkeiten von Symbolen ermittelt. Wenn die Symbolhäufigkeiten bekannt sind, wird ein Code erzeugt. Beim zweiten Durchlauf werden die Symbole codiert. Ein optimaler statischer präfixfreier Code kann mit dem klassischen Huffman-Algorithmus erzeugt werden. Um den statischen Code zu erzeugen, benötigen die statische Verfahren die Häufigkeiten von allen Symbolen. Dies bedeutet, dass der Text S zweimal gelesen werden muss. Außerdem muss die Information über den Code mit dem codierten Datenstrom gespeichert werden.
Bei der adaptiven Codierung benutzt man den (optimalen) Code für den Datenstrom s₁s₂...s_i-1, um das Symbol s_i zu codieren. Der Vorteil von adaptiven Verfahren ist, dass die Datei nur einmal gelesen wird. Die Algorithmen für adaptive Huffman Codierung wurden z. B. von Faller, Gallager und Knuth sowie vom Vitter entwickelt. Die Laufzeit von diesen Algorithmen ist proportional zu M, wobei M die Anzahl der Bits in dem codierten Datenstrom ist.
Dieses Patent beschreibt ein Verfahren mit einer Laufzeit, die linear in m ist, wobei m die Anzahl der Symbole im Datenstrom S ist. Das vorgestellte Verfahren garantiert außerdem eine gute obere Schranke für die Länge des codierten Datenstroms.
Im folgenden Abschnitt beschreiben wir die allgemeine Struktur von adaptiven Kompressionsverfahren. Im Abschnitt 3 beschreiben wir kanonische Codes. Unsere Erfindung wird in den Abschnitten 4 und 5 erklärt.
1 Adaptive Verfahren
Wir bezeichnen mit m die Länge des zu codierenden Datenstroms S = s₁s₂...s_m und M bezeichnet die Codierungslänge, d. h. M ist die Anzahl der Bits, die wir benötigen, um den Datenstrom S zu codieren. Wir bezeichnen mit occ(a, i) die Häufigkeit des Symbol a in s₁s₂...s_i. Wir bezeichnen mit occ(a) = occ(a, m) die Häufigkeit des Symbols a in S. Mit (NYT) bezeichnen wir ein spezielles Symbol, das sich von allen Symbolen in S unterscheidet. Ein adaptives Codierungsverfahren besteht aus folgenden Schritten:

1. Wir erzeugen einen präfixfreien Code für (NYT)s₁s₂...s_i-1. Der Code für (NYT)s₁s₂...s_i-1 wird in der Regel dadurch erzeugt, dass man den Code für (NYT)s₁s₂...s_i-2 modifiziert. Dazu kann man z. B. den Algorithmus von Gallager, Faller und Knuth (siehe [1]–[3]) verwenden, oder das hier beschriebene Verfahren.
2. Falls das Symbol s_i bereits in s₁s₂...s_i-1 wenigstens einmal aufgetreten ist, wird das Codewort für s_i verwendet, um das Symbol s_i zu codieren.
3. Falls s_i zum ersten mal in S₁...s_i vorkommt, wird das Codewort für das spezielle Symbol (NYT) ausgegeben, gefolgt von einer Binärdarstellung des Indizes von s_i. Das Symbol (NYT) wird verwendet, um anzugeben, dass das nächste Symbol ein ”neues” Symbol ist.

Die Schritte 2 und 3 sind leicht zu implementieren. Unsere Erfindung beschäftigt sich hauptsächlich mit dem Schritt 1.
2 Vorherige Verfahren
In diesem Abschnitt befassen wir uns mit anderen adaptiven Codierungsverfahren, die vor unserer Arbeit entwickelt wurden. Der so genannte FGK Algorithmus wurde unabhängig von Faller und Gallager entwickelt und von Knuth wesentlich verbessert. Dieser Algorithmus wird in den Arbeiten [1], [2] und [3] beschrieben. Der FGK Algorithmus ermöglicht uns, den optimalen Code für den bereits codierten Teil des Datenstroms (NYT)s₁...s_i-1 aufrechtzuerhalten. Das Verfahren von Vitter [5] basiert ebenfalls darauf, dass man den optimalen Code für den (NYT)s₁...s_i-1 aufrechterhält. Dadurch, dass man einen speziellen optimalen Code verwendet, wird in dem Verfahren von Vitter [5] eine bessere obere Schranke für die Länge des codierten Datenstroms erreicht. Beide Algorithmen ermitteln die Codewortlänge des nächsten zu codierenden Symbols anhand von Häufigkeiten von allen Symbolen in dem bereits codierten Teil des Textes.
Ein weiteres relevantes Verfahren wurde von Turpin und Moffat entwickelt und wird in der Arbeit [4] beschrieben. Das Verfahren basiert darauf dass man den optimalen Code anhand von approximierten Häufigkeiten der Symbole ermittelt. Da in dem Verfahren von Turpin und Moffat ebenfalls ein optimaler Code benutzt wird, wird die Länge des nächsten zu codierenden Symbols anhand von approximierten Häufigkeiten von allen Symbolen ermittelt.
In unserem Verfahren hängt die Länge des nächsten zu codierenden Symbols nur von der approximierten Häufigkeit dieses Symbols in dem bereits codierten Teil des Datenstroms und von der approximierten Länge des bereits codierten Teils des Datenstroms ab. Dies unterscheidet unseren Algorithmus von den Algorithmen, die in [1, 2, 3, 5, 4] beschrieben werden.
Ein weiteres wichtiges Merkmal unseres Verfahrens besteht darin, dass in unserem Verfahren die Codewortlänge des nächsten zu codierenden Symbols anhand approximierten Häufigkeit und approximierten Länge des Textes ermittelt wird. Die Idee, approximierte Häufigkeiten anstatt exakten Häufigkeiten zu verwenden, wurde vorher nur in der Arbeit von Turpin und Moffat [4] verwendet. In ihrem Verfahren wird aber eine andere Approximationsformel verwendet: anstatt Symbolhäufigkeit f wird die größte Zahl f' < f verwendet, so dass f' = 2^r/k für ein Parameter k und r eine beliebige ganze Zahl ist. In unserem Verfahren werden die Häufigkeit des Symbols und die Länge des Textes einfach durch Parameter q geteilt und abgerundet (quantisiert).
3 Kanonische Codes
Kanonische Codes sind eine Klasse von präfix-freien Codes. Ein kanonischer Code hat die sog. numerical sequence property; Codewörter mit der gleichen Länge sind Binärdarstellungen von aufeinanderfolgenden ganzen Zahlen. Ein Beispiel von einem kanonischen Code kann man in der 1 sehen.
Sei l_max die maximale Codewortlänge, und sei n_i, i = 1, ..., l_max, die Anzahl der Codewörter mit Länge i. Mit base[i] bezeichnen wir das erste (kleinste) Codewort der Länge i. Man kann base[i] nach der folgenden rekursiven Formel erzeugen: base[0] = 0, base[i] = (base[i – 1] + n_i-1) × 2. Das j-te Codewort der Länge i ist die Binärdarstellung der Zahl base[i] + j – 1. Daher, falls die Länge l des Codewortes für das Symbol a und der Index von a unter allen Codewörtern der Länge l bekannt sind, kann man das Codewort für das Symbol a in konstante Zeit finden. Z. B. für den Code in 1 ist n₁ = n₂ = 0, n₃ = 2, n₄ = 6, und n₅ = 8. Dann ist base[1] = base[2] = 0, base[3] = 0, base[4] = 4 und base[5] = 20. Das Codewort für das Symbol a₆ ist das 4-te Codewort der Länge 4. Für a₆ ist das Codewort also base[4] + (4 – 1) = 4 + 3 = 7 oder (0111)₂ in Binärdarstellung. Somit ist der kanonische Code durch Parameter n_i, i = 1, ..., l_max, eindeutig definiert.
4 Codierung mit Quantisierung
In unserem Verfahren werden die Codewortlängen (und Parameter n_i) aufgrund der quantisierten Häufigkeiten der Symbole festgestellt. Sei occ_q(a, i) = ⌊occ(a, i)/q⌋ und P_q(i) = ⌈i/q⌉. Das Parameter q > 1 wird im folgenden Quantisierungsparameter genannt. Angenommen, dass der Datenstrom S₁s₂...s_i-1 bereits codiert wurde. Die Codewortlänge
für das nächste Symbol s_i erfüllt die folgende Bedingung:
Betrachten wir den Fall occ(s_i, i – 1 > q. Der Zähler des Bruchs
wird inkrementiert nachdem q neue Symbole codiert wurden. Wenn occ_q(s_i, i – 1) inkrementiert wurde, wird die Codewortlänge für das Symbol s_i eventuell geändert. Wenn dies der Fall ist, wird der Code modifiziert. Man kann das Quantisierungparameter q so wählen, dass der Code in konstanter amortisierter Zeit modifiziert werden kann. Der Nenner des Bruchs
wird inkrementiert, nachdem q beliebige Symbole codiert wurden. Falls aber P_q(i) inkrementiert wurde, können sich die Codewortlängen von mehreren Symbolen ändern. Um die Invariante
zu erhalten, werden alle Symbole s_i in einer Liste R gespeichert. Nachdem q Symbole codiert wurden, werden die ersten q Symbole aus der Liste R entfernt. Für jedes entfernte Symbol a_r wird seine Codewortlänge aktualisiert. Danach werden die q entfernten Symbole am Ende der Liste R eingefügt und der Code C wird entsprechend modifiziert. Man kann das Parameter q so wählen, dass der Code C in Zeit, die linear in q ist, aktualisiert werden kann (also in konstanter amortisierter Zeit).
5 Adaptives Quantisiertes Codierungsverfahren
In diesem Abschnitt geben wir eine detaillierte Beschreibung des Verfahrens, mit dem man den quantisierten Code aktualisieren kann.
Für jedes Symbol a speichern wir die Länge len(a) des Codewortes für a und den Index ind(a) des Codewortes für a unter allen Codewörtern mit der Länge len(a). Alle Symbole a mit occ(a, i) > 0 (alle Symbole, die in dem bereits codierten Teil des Textes wenigstens einmal vorkommen) werden in der Liste R gespeichert. Alle Symbole, deren Codewörter die Länge l haben, werden in einer Liste C[l] gespeichert.
Falls die Codewortlänge von einem Symbol a von l₁ auf l₂ geändert wird, werden die folgenden Operationen durchgeführt. Sei ind(a) = i, sei a' das letzte Codewort der Länge l₁. Der Index von a' wird von
auf i geändert. Wir entfernen a' aus C[l₁] und ersetzen a mit a' in C[l₁],
wird um 1 gesenkt. Somit wird a' zum i-ten Codewort mit der Länge l₁ (d. h. das neue Codewort für a' ist nun das alte Codewort für a). Das neue Codewort für a ist das letzte Codewort mit der Länge l₂. Wir setzen ind(a) auf
inkrementieren
und fügen a am Ende von C[l₂] ein. Alle diese Operationen können schnell implementiert werden. Wenn die Werte von
aktualisiert wurden, kann man das Array base[] aktualisieren. Zum Beispiel, betrachten wir den Code in der 1 und nehmen an, dass die Länge des Codewortes für das Symbol a₆ auf 5 geändert wurde. Wir dekrementieren n₄ und ersetzen a₆ durch a₈. Der Index von a₈ wird auf 4 gesetzt (das neue Codewort für a₈ ist (0111)₂). Das neue Codewort für a₆ ist das letzte Codewort der Länge 5: ind[a₆] = 9, len[a₆] = 5 und n₅ = 9. Das Array base[] wird entsprechend geändert: base[5] = 18 = (10010)₂. Das neue Codewort für a₆ ist also base[5] + ind[a₆] – 1 = (11010)₂.
Der Algorithmus codiert den Datenstrom s₁s₂...s_m. Nachdem das Symbol s_i codiert wurde, wird der Code wie folgt modifiziert:

1. Falls das Symbol s_i zum ersten Mal vorkommt, wird die Länge von s_i auf ⌈log(i + n + 1)⌉ gesetzt und s_i wird am Ende der Liste R eingefügt.
2. Falls occ(s_i, i – 1) > 0 und occ(s_i, i) ≡ 0 (mod q) (falls s_i mehr als einmal im s₁...s_i vorkommt und die Häufigkeit von s_i durch q teilbar ist), wird das Symbol s_i aus der Liste R entfernt und die Länge von s_i auf
gesetzt. Der Code wird wie oben beschrieben aktualisiert.
3. Sei p ein Parameter. Falls i > 0 und i ≡ 0 (mod q), werden die erste p Elemente
aus der Liste R entfernt. Die Codewortlängen für die entfernten Symbole werden aktualisiert. Falls
wird die Länge des Codewortes für das Symbol
auf
gesetzt. Falls
wird die Länge des Codewortes für das Symbol
auf ⌈log(i + n + 1)⌉ gesetzt. Zum Schluss werden die entfernten Symbole am Ende der Liste R eingefügt.

Man kann zeigen, dass die obere Schranke für die Anzahl der Bits, die man braucht, um mit diesem Verfahren einen Datenstrom S zu codieren, (H + 1)m + O(nlog²m) ist, falls der Parameter q = logm ist. In dieser Formel ist
die empirische Entropie.
Der beschriebene Algorithmus kann auch in der Praxis effizient eingesetzt werden.
Literatur

[1] N. Faller, ”An adaptive system for data compression”, in Record of the 7th Asilomar. Conference on Circuits, Systems, and Computers (1973), 593–597.
[2] R. G. Gallager, ”Variations on a Theme by Huffman”, IEEE Trans. on Information Theory 24(1978), 668–674.
[3] D. E. Knuth, ”Dynamic Huffman Coding”, J. Algorithms 6(1985), 163–180.
[4] A. Turpin, A. Moffat, ”On-line Adaptive Canonical Prefix Coding with Bounded Compression Loss”, IEEE Trans. on Information Theory, 47(2001), 88–98.
[5] J. S. Vitter, ”Design and Analysis of Dynamic Huffman Codes”, J. ACM 34(1987), 825–845.

Claims

Verfahren für die adaptive präfix-freie Codierung eines Datenstroms über einem Alphabet aus n Elementen mit zwei Parameter p und q, wobei p größer als q ist, gekennzeichnet dadurch, dass die Codewortlängen aufgrund von der Länge des bereits codierten Teils des Textes geteilt durch Parameter q und aufgerundet, weiterhin quantisierte Textlänge genannt, sowie der Häufigkeit des Symbols im bereits codierten Teil des Textes geteilt durch Parameter q und abgerundet, weiterhin quantisierte Häufigkeit genannt, bestimmt werden, und weist auf: – eine Liste R von bereits codierten Symbolen – ein Verfahren A für die Aktualisierung der Länge des codierten Symbols – ein Verfahren B, das den Code modifiziert, nachdem die Länge eines Symbols geändert wurde.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass für jedes mindestens einmal codiertes Element des Eingabealphabets seine Codewortlänge und sein Index unter allen Codewörtern mit der gleichen Länge bekannt sind, wobei die Indizes der Symbole mit der gleichen Codewortlänge eine mit Eins anfangende Folge von aufeinanderfolgenden ganzen Zahlen bilden.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass jedes neues Codewort mit der Länge l, das in den Code eingefügt wird, zum letzten Codewort mit der Länge l wird, d. h. das neue Codewort hat den größten Index unter allen Codewörtern mit der Länge l.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass das erste Codewort mit der Länge 1 den Wert 0 hat und das erste Codewort mit der Länge l als das Doppelte der Summe von dem ersten Codewort mit der Länge l – 1 und der Anzahl der Codewörter mit der Länge l – 1 bestimmt wird.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass die Liste R von bereits codierten Elementen des Eingabealphabets wie folgt regelmäßig aktualisiert wird: nachdem eine Folge von q Eingabesymbolen codiert wurde, werden die erste p Elementen aus der Liste R entfernt und die Codewortlängen der entfernten Symbole werden aktualisiert; die Codewortlänge eines jeden entfernten Symbols a wird wie folgt geändert: – Falls die Häufigkeit von a kleiner oder gleich q ist und i Eingabesymbolen bereits codiert wurden, wird die Codewortlänge von a auf die kleinste ganze Zahl k gesetzt, so dass die k-te Zweierpotenz mindestens so groß wie die Summe von i und n um eins inkrementiert ist. – Falls die Häufigkeit von a größer als q ist, wird die Codewortlänge von a auf die kleinste ganze Zahl k gesetzt, so dass die k-te Zweierpotenz mindestens so groß wie das Verhältnis von der Summe der quantisierten Textlänge und n zur quantisierten Häufigkeit ist. Abschließend werden die Symbole am Ende der Liste R wieder eingefügt.
Verfahren B entsprechend Anspruch 1, dadurch gekennzeichnet, dass bei Veränderung der Länge des Codewortes für ein Symbol a von l₁ auf l₂ die folgende Operationen durchführt werden: – dem Symbol mit dem größten Codewort der Länge l₁ wird der Index des alten Codewortes für a zugewiesen – das neue Codewort des Symbols a wird zum letzten Codewort mit der Länge l₂ – die Anzahl der Codewörter mit Längen l₁ und l₂ wird entsprechend geändert.
Verfahren A entsprechend Anspruch 1, gekennzeichnet dadurch, dass nach der Codierung des i-ten Symbols in dem Datenstrom, weiterhin s genannt, die folgende Operationen durchführt werden: – falls s zum ersten Mal in dem Datenstrom vorkommt, wird die Codewortlänge für s auf die kleinste ganze Zahl k gesetzt, so dass die k-te Zweierpotenz mindestens so groß wie die Summe von i und n um eins inkrementiert ist. – falls die Häufigkeit von s ein mehrfaches von q ist, wird die Codewortlänge von s auf die kleinste ganze Zahl k gesetzt, so dass die k-te Zweierpotenz mindestens so groß wie das Verhältnis von der Summe der quantisierten Textlänge und n zur quantisierten Häufigkeit ist.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass der Code vor dem Anfang der Codierung leer ist und keine Codewörter enthält.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass ein neues Codewort mit der Länge l, das in den Code hingefügt wird, zum letzten Codewort mit der Länge l wird.
Verfahren nach Anspruch 1, wobei das allererste Symbol in dem Datenstrom als eine Binärdarstellung des Indexes von diesem Symbol im Eingabealphabet codiert wird.
Verfahren nach Anspruch 10, wobei nachdem das allererste Symbol s codiert wurde, werden die Codewörter für Symbole (NYT) und das Symbol s in den Code eingefügt.
Verfahren nach Anspruch 1, bei dem ein Symbol a das zum ersten mal codiert wird, aber nicht das allererste Symbol in dem Datenstrom ist, als ein spezielles Symbol (NYT) gefolgt von dem Index von a in dem Eingabealphabet codiert wird.
Verfahren entsprechend Anspruch 1, bei dem ein nächstes zu codierendes Symbol a, das im bereits codierten Teil des Datenstroms wenigstens einmal vorkam, mit dem Codewort, das dem Symbol a entspricht, codiert wird.
Verfahren nach Anspruch 13, bei dem das Codewort für ein Symbol mit der Länge l und dem Index i als die Binärdarstellung der Summe von dem ersten Codewort mit der Länge l und des Indexes i um 1 decrementiert bestimmt wird.