DE69701183T2

DE69701183T2 - Datenkompressionsverfahren und -system mit Kontext Baumstruktur Algorithmus

Info

Publication number: DE69701183T2
Application number: DE69701183T
Authority: DE
Inventors: Tjalling Jan Tjalkens; Franciscus Maria Johannes Willems
Original assignee: Koninklijke KPN NV; Eindhoven Technical University
Current assignee: Koninklijke KPN NV; Eindhoven Technical University
Priority date: 1997-01-24
Filing date: 1997-01-24
Publication date: 2000-06-21
Anticipated expiration: 2017-01-25
Also published as: AU727633B2; ES2143829T3; DE69701183D1; AU6294198A; DK0855803T3; ATE189087T1; CA2278605C; CA2278605A1; EP0855803A1; US5986591A; EP0855803B1

Description

A. Technischer Hintergrund der Erfindung

Die Erfindung betrifft ein Verfahren zur Erzeugung eines Baumes für einen Kontextbaumstruktur-Algorithmus zum Kodieren von Symbolen, wobei das Verfahren die Schritte umfasst:
-x- Annehmen eines Wertes von entweder einem ersten Parameter oder von einem zweiten Parameter, deren Werte einem Knoten des besagten Baumes entsprechen, in Abhängigkeit von einem Wert eines zu kodierenden Symbols,
-y- Weiterführen des Schrittes -x- für den vorausgegangenen Knoten im Falle, dass dem besagten Knoten ein vorausgegangener Knoten vorausgegangen ist, in Abhängigkeit von einem Wert eines vorausgegangen Symbols, und
-z- Erzeugen eines anderen vorausgegangen Knotens und Weiterführen des Schrittes -x- für den besagten anderen vorausgegangenen Knoten im Falle, dass dem besagtem Knoten nicht ein vorausgegangener Knoten vorausgegangen ist, in Abhängigkeit von einem Wert eines vorausgegangen Symbols.
Solch ein Verfahren ist aus den IEEE Transactions on INFORMATION THEORY, Mai 1995, Band 41, Nummer 3, insbesondere aus dem Artikel "Das Kontextbaum gewichtete Verfahren: Elementare Eigenschaften" von F. M. J. Willems, Y. M. Shtarkov und T. J. Tjalkens auf den Seiten 653 bis 664, wobei dieser Artikel ein sequentielles universales Datenkompressionsverfahren für binäre Baumquellen beschreibt. Durch den Einsatz von Kontextbäumen gewichtet dieses Verfahren in einer effizienten rekursiven Weise die ko dierenden Verteilungen, die allen gebundenen Speicherbaumquellen entsprechen und schafft eine gewünschte Kodierungsverteilung für Baumquellen mit einem unbekannten Modell und unbekannten Parametern.
Solch ein Verfahren weist Nachteile auf, weil es eine riesige Speicherkapazität erfordert.

B. Zusammenfassung der Erfindung

Es ist unter anderem ein Ziel der vorliegenden Erfindung ein Verfahren der eingangs genannten Art zu schaffen, das weniger Speicherkapazität benötigt.
Dabei ist das Verfahren gemäss der vorliegenden Erfindung dadurch gekennzeichnet, dass in Abhängigkeit von mindestens einem Wert der besagten Parameter der besagte andere vorausgegangene Knoten erzeugt oder nicht erzeugt wird.
Durch das Verhindern der Erzeugung des besagten anderen Knotens in Abhängigkeit von mindestens einem Wert der besagten Parameter im Falle, dass dies nicht notwendig ist, wird ein effizienterer Baum erzeugt, der die Speicherkapazität vermindert.
Die Erfindung basiert unter anderem auf der Einsicht, dass es nicht notwendig ist, jeden möglichen Knoten zu erzeugen.
Das Problem der bekannten Verfahren, die eine riesige Speicherkapazität erfordern, wird dadurch gelöst, dass die Erzeugung eines Knotens von mindestens einem Wert der besagten Parameter abhängig gemacht wird, um die Erzeugung von unnötigen Knoten zu vermeiden.
Das Verfahren gemäss der Erfindung kann eingesetzt werden, um einen Baum für einen Kontextbaumstruktur-Algorithmus zu erzeugen, um Symbole zu kodieren, wobei diese Symbole mindestens zwei Symbolwerte umfassen können.
Ein erstes Ausführungsbeispiel des Verfahrens gemäss der Erfindung ist dadurch gekennzeichnet, dass der erste Parameter a(n) ist und dass der zweite Parameter b(n) ist, wobei die Werte dieser Parameter dem besagten Knoten n zugehören, wobei die anderen vorgehenden Knoten erzeugt worden sind, falls a(n) > 0 und b(n) > 0.
Gemäss diesem ersten Ausführungsbeispiel wird, sofern mindestens einer der Werte a(n) = 0 oder b(n) = 0 wird, der andere vorausgegangene Knoten nicht erzeugt, was Speicherkapazität einspart. Gemäss einem alternativen Ausführungsbeispiel wird der besagte andere vorausgegangene Knoten beispielsweise nicht erzeugt, falls a (n) < 2 und b (n) < 2 ist, oder wird beispielsweise nicht erzeugt, falls a(n)/b(n) < 0,001 oder a(n)/b(n) > 1000 ist.
Ein zweites Ausführungsbeispiel des Verfahrens gemäss der Erfindung ist dadurch gekennzeichnet, dass ein dritter Parameter i(n) den besagten Knoten definiert, wobei dieser Knoten einem vorausgehenden Knoten oder einem vorausgehenden Knoten nicht vorausgegangen ist, wobei die besagte Erzeugung des besagten anderen vorausgegangenen Knotens die Definition eines vierten Parameters j umfasst, der ein Index des anderen vorausgegangenen Knotens ist, wobei a (j) und b (j) initialisiert sind, wobei i (j) den Wert 0 erhält, wobei i(n) den Wert (j) erhält und wobei n den Wert i(n) erhält.
Ein weniger effizienterer aber akkurater Weg, a(j) und b(j) zu initialisieren, könnte darin liegen, dass die gespeicherten Werte von vorausgegangenen Symbolen eingesetzt werden.
Ein drittes Ausführungsbeispiel des Verfahrens gemäss der Erfindung ist dadurch gekennzeichnet, dass bei der Initialisierung a(j) den Wert 0 und b(j) den Wert 0 erhalten.
Ein effizienterer aber weniger akkurater Weg a(j) und b(j) zu initialisieren könnte darin liegen a(j) = b(j) = 0 zu setzen.
Ein viertes Ausführungsbeispiel des Verfahrens gemäss der Erfindung ist dadurch gekennzeichnet, dass das Verfahren einen Schritt umfasst, der zwischen dem Schritt -x- auf der einen Seite und den Schritten -y- und -z- auf der anderen Seite angeordnet ist, wobei dieser Schritt umfasst: -w- einen fünften Parameter d, der für jeden weiteren Knoten angepasst wird und der nach jeder Anpassung mit einem Schwellwert D verglichen wird.
Durch die Einführung des fünften Parameters d und des Vergleichs mit dem Schwellwert D wird das Verfahren zur Erzeugung eines Baumes auf Bäume begrenzt, die eine maximale Tiefe haben, die gleich zu dem Schwellwert D ist.
Die Erfindung betrifft weiterhin ein System zur Erzeugung eines Baumes für einen Kontextbaumstruktur-Algorithmus zum Kodieren von Symbolen, wobei das System Prozessormittel und Speichermittel aufweist, um an ersten Orten, die zu einem Knoten gehören, Werte von Parametern zu speichern und um an zweiten Orten, die zu einem vorausgegangenen Knoten gehören, Werte von Parametern zu speichern und um an dritten Orten, die zu einem anderen vor ausgegangenen Knoten gehören, Werte von Parametern zu speichern, wobei die Prozessormittel umfassen:
- Anpassungsmittel, um in Abhängigkeit von einem Wert eines zu kodierenden Symbols einen Wert von entweder einem ersten Parameter oder von einem zweiten Parameter anzupassen, wobei diese Werte in mindestens zwei der besagten Orte gespeichert sind,
- Vergleichermittel, um in Abhängigkeit von einem Wert eines vorausgegangenen Symbol einen Wert eines dritten Parameters, der an zumindest einer der besagten ersten Orte gespeichert ist, mit einem vorbestimmten Wert zu vergleichen, wobei im Falle eines ersten Vergleichsergebnisses ein Wert von entweder einem ersten Parameter oder von einem zweiten Parameter angepasst wird, wobei diese Werte an mindestens zwei der besagten zweiten Orte gespeichert werden, in Abhängigkeit von einem Wert eines zu kodierenden Symbols, indem die Anpassungsmittel eingesetzt werden, und
- Zuweisungsmittel, um im Falle eines zweiten Vergleichsergebnisses in Abhängigkeit von einem Wert eines vorausgegangenen Symbols einem vierten Parameter einen Wert zuzuweisen, wobei dieser Wert an mindestens einem der besagten dritten Orte gespeichert wird, wobei ein Wert von entweder einem ersten Parameter oder von einem zweiten Parameter angepasst wird, wobei diese Werte in Abhängigkeit von einem Wert eines zu kodierenden Symbols unter Benutzung der Anpassungsmittel an mindestens zwei der besagten dritten Orte gespeichert werden.
Solch ein System ist nachteilhaft, weil es eine riesige Speicherkapazität erfordert.
Es ist daher unter anderem eine weitere Aufgabe der vorliegenden Erfindung, ein System der oben genannten Art zu schaffen, welches eine weniger grosse Speicherkapazität erfordert.
Demgemäss ist ein System gemäss der vorliegenden Erfindung dadurch gekennzeichnet, dass das Prozessormittel umfasst:
- Prüfmittel zum Überprüfen von mindestens einem Wert von zumindest einem der besagten ersten und zweiten Parameter, um im Falle eines ersten Prüfergebnisses die besagten Zuweisungsmittel zu aktivieren und um im Falle eines zweiten Prüfergebnisses die besagten Zuweisungsmittel zu deaktivieren.
Ein erstes Ausführungsbeispiel des Systems gemäss der Erfindung ist dadurch gekennzeichnet, dass der erste Parameter a(n) ist und dass der zweite Parameter b(n) ist, wobei die Werte dieser Parameter an mindestens zwei der besagten ersten Orte gespeichert sind, wobei a (n) > 0 und b (n) > 0 zu dem besagten ersten Prüfergebnis führen und alle anderen Fälle zu dem besagten zweiten Prüfergebnis führen.
Ein zweites Ausführungsbeispiel des Systems gemäss der Erfindung ist dadurch gekennzeichnet, dass der dritte Parameter i(n) ist und der vierte Parameter j ist, wobei a(j) und b(j) initialisiert werden, wobei i (j) den Wert 0 erhält, wobei i (n) den Wert j erhält und wobei n den Wert i(n) erhält.
Ein drittes Ausführungsbeispiel des Systems gemäss der Erfindung ist dadurch gekennzeichnet, dass bei der Initialisierung a(j) den Wert 0 und b(j) den Wert 0 erhalten.
Ein viertes Ausführungsbeispiel des Systems gemäss der Erfindung ist dadurch gekennzeichnet, dass das Prozessormittel umfasst:
- weitere Anpassungsmittel, um einen fünften Parameters d nach jeder Anpassung des besagten Wertes von entweder dem besagten ersten Parameter oder dem besagten zweiten Parameter anzupassen, und
- weitere Vergleichermittel, um den besagten fünften Parameter d mit einem Schwellwert D nach jeder weiteren Anpassung zu vergleichen.

C. Entgegenhaltungen

- IEEE Transactions an INFORMATION THEORY, Mai 1995, Band 41, Nummer 3, insbesondere der Artikel "Das Kontextbaum gewichtete Verfahren: Elementare Eigenschaften" von F. M. J. Willems, Y. M. Shtarkov und T. J. Tjalkens, Seiten 653 bis 664
- EP 96 202 007.9 (Prioritätsdatum/Anmeldetag 15. Juli 1996)
- US 5,534,861
- EP 0 480 115
- US 5,023,611
- US 5,025,258
- US 4,286,256
- US 4,494,108
- US 5,357,250

D. Ausführungsbeispiel

Die Erfindung wird nun an Hand eines in den Figur dargestellten Ausführungsbeispiels beschrieben. Es zeigen:
Fig. 1 ein Flussdiagramm, dass das Verfahren gemäss der Erfindung darstellt, und
Fig. 2 ein Flussdiagramm, dass einen Kontextbaumstruktur- Algorithmus darstellt, der auf dem Verfahren gemäss der Erfindung beruht.
Das in der Fig. 1 dargestellte Flussdiagramm umfasst einzelne Blöcke, die die folgende Bedeutung aufweisen:
Block 1 n: = I
x: = x (t)
d: = 0
Gehe zu Block 2
Block 2 Ist x = 0 ?
Falls ja, Gehe zu Block 3
Falls nein, Gehe zu Block 4
Block 3 a(n): = a(n) + 1
Gehe zu Block 5
Block 4 b(n): = b(n): = b (n) + 1
Gehe zu Block 5
Block 5d: = d + 1
Gehe zu Block 6
Block 6 Ist d > D ?
Falls ja, Gehe zu Block 7
Falls nein, Gehe zu Block 8
Block 7 Beende die weitere Erzeugung des Baumes für x(t)
Block 8 Ist x (t - d) = 0 ?
Falls ja, Gehe zu Block 9
Falls nein, Gehe zu Block 14
Block 9 Ist i&sub0;(n) = 0 ?
Falls ja, Gehe zu Block 10
Falls nein, Gehe zu Block 13
Block 10 Ist a (n) > 0 and b (n) > 0 ?
Falls ja, Gehe zu Block 11
Falls nein, Gehe zu Block 12
Block 11 j: indiziere neuen Knoten
a(j): = 0
b(j): = 0
i&sub0;(j): = 0
i&sub1;(j): = 0
i&sub0;(n): = j
Gehe zu Block 13
Block 12 Beende die weitere Erzeugung des Baumes für x(t)
Block 13 n: = i&sub0;(n)
Gehe zu Block 2
Block 14 Ist i&sub1;(n) = 0 ?
Falls ja, Gehe zu Block 15
Falls nein, Gehe zu Block 18
Block 15 Ist a(n) > 0 and b(n) > 0 ?
Falls ja, Gehe zu Block 16
Falls nein, Gehe zu Block 17
Block 16 j: indiziere neuen Knoten
a(j): = 0
b(j): = 0
i&sub0;(j): = 0
i&sub1;(j): = 0
i&sub1;(n): = j
Gehe zu Block 18
Block 17 Beende die weitere Erzeugung des Baumes für x(t)
Block 18 n: = i&sub1;(n)
Gehe zu Block 2
In den Figur sind die Begriffe "Falls ja" mit dem Buchstaben "Y" und "Falls nein" mit dem Buchstaben "N" bezeichnet.
Das Verfahren gemäss der Erfindung im Hinblick auf das in der Fig. 1 dargestellte Flussdiagramm arbeitet wie folgt. In Antwort auf ein empfangenes Symbol x(t) erhält x den Wert x(t), n erhält den Wert Eins (zeigt die Wurzel des Baumes an) und ein fünfter Parameter d erhält den Wert Null (Block 1). Im Falle eines binären Ausführungsbeispiels wird x(t) entweder den Wert Eins oder den Wert Null aufweisen. Im Falle von x = 0 wird der erste Parameter a(n) mit dem Wert Eins erhöht und im Falle x = 1 wird ein zweiter Parameter b(n) mit dem Wert Eins erhöht (Blöcke 2, 3). Dann wird der fünfte Parameter d mit dem Wert Eins erhöht (Block 5), wonach der erhöhte fünfte Parameter d mit einem Schwellwert D verglichen wird (Block 6). Im dem Fall, dass d > D ist, endet das Verfahren (Block 7), andernfalls wird ein Wert eines vorangegangenen Symbols x(t - d) mit dem Wert Null verglichen (Block 8). Im dem Fall, dass x(t - d) = 0 ist, wird ein dritter Parameter i&sub0;(n) mit dem Wert Null verglichen (Block 9). In dem Fall, dass i&sub0;(n) = 0 ist (anzeigend, dass der besagte Knoten nicht einem vorausgegangenen Knoten vorausgegangen ist), werden die Werte des ersten Parameters a(n) und des zweiten Parameters b(n) mit dem Wert Null verglichen (Block 10). Falls es nicht wahr ist, dass a(n) > 0 und b(n) > 0, endet das Verfahren (Block 12), andernfalls erhält ein vierter Parameter j einen Wert, der ein Index eines anderen vorausgegangenen Knotens (ein neuer Knoten) ist, wobei der erste Parameter a(j) den Wert Null erhält, der zweite Parameter b(j) den Wert Null erhält, der dritte Parameter i&sub0;(j) den Wert Null erhält und der dritte Parameter i&sub1;(j) den Wert Null erhält (anzeigend, dass auf Grund der Erzeugung des anderen vorausgegangenen Knotens dieser andere vorausgegangene Knoten nicht von weiteren Knoten vorausgegangen wird) und der dritte Parameter i&sub0;(n) den Wert des vierten Parameters j erhält (Block 11). Dann erhält n den Wert des dritten Parameters i&sub0;(n) (Block 13). Im Falle, dass 10(n) > 0 ist (anzeigend, dass der besagte Knoten von einem vorausgehenden Knoten vorausgegangen ist) (Block 9) erhält n auch den Wert des dritten Parameters i&sub0;(n) (Block 13) aber ohne die Anpassung des vierten Parameters j etc. . Dann wird dieses Verfahren wiederholt, beginnend mit dem Block 2. Im Fall, dass x(t - d) = 1 ist, wird ein dritter Parameter i&sub1;(n) mit dem Wert Null verglichen (Block 14). Im Fall, dass i&sub1;(n) = 0 ist (anzeigend, dass der besagte Knoten nicht von einem vorausgehenden Knoten vorausgegangen ist), werden die Werte des ersten Parameters a(n) und des zweiten Parameters b(n) mit dem Wert Null verglichen (Block 15). Im Fall, dass es nicht wahr ist, dass a(n) > 0 und b(n) > 0, endet das Verfahren (Block 17), andernfalls erhält ein vierter Parameter j einen Wert, der ein Index eines anderen vorausgegangenen Knotens (ein neuer Knoten) ist, wobei der erste Parameter a(j) den Wert Null erhält, der zweite Parameter b(j) den Wert Null erhält, der dritte Parameter i&sub0;(j) den Wert Null erhält und der dritte Parameter i&sub1;(j) den Wert Null erhält (anzeigend, dass auf Grund der Erzeugung des anderen vorausgehenden Knotens dieser andere vorausgehende Knoten nicht weiteren Knoten vorausgegangen ist), und dass der dritte Parameter i&sub1;(n) den Wert des vierten Parameters j erhält (Block 16).
Dann erhält n den Wert des dritten Parameters i&sub0;(n) (Block 18). Im Falle, dass i&sub1;(n) > 0 ist (anzeigend, dass der besagte Knoten von einem vorausgehenden Knoten vorausgegangen ist) (Block 14) erhält n auch den Wert des dritten Parameters i&sub1;(n) (Block 18) aber ohne die Anpassung des vierten Parameters j etc.. Dann wird dieses Verfahren wiederholt, beginnend mit dem Block 2.
Im Allgemeinen umfasst das Verfahren zur Erzeugung eines Baumes für einen Kontextbaumstruktur-Algorithmus zum Kodieren von Symbolen die Schritte von
-x- Annehmen eines Wertes von entweder einem ersten Parameter a(n) oder von einem zweiten Parameter b(n), deren Werte einem Knoten des besagten Baumes entsprechen (Blöcke 1, 2, 3, 4, 5), in Abhängigkeit von einem Wert eines zu kodierenden Symbols x(t),
-y- Weiterführen des Schrittes -x- für den besagten vorausgegangenen Knoten (Blöcke 8, 9, 13 oder 8, 14, 18) im Falle, dass dem besagten Knoten ein vorausgegangener Knoten vorausgegangen ist, in Abhängigkeit von einem Wert eines vorausgegangen Symbols x(t - d), und
-z- Erzeugen eines anderen vorausgegangen Knotens und Weiterführen des Schrittes -x- für den besagten anderen vorausgegangenen Knoten (Blöcke 8, 9, 11, 13 oder 8, 14, 16, 18) im Falle, dass dem besagtem Knoten nicht ein vorausgegangener Knoten vorausgegangen ist, in Abhängigkeit von einem Wert eines vorausgegangen Symbols
und ist dadurch gekennzeichnet, dass in Abhängigkeit von mindestens einem Wert der besagten Parameter der besagte andere vorausgegangene Knoten erzeugt oder nicht erzeugt wird(Blöcke 10, 11, 12 oder 15, 16, 17), was Speicherkapazität spart.
Gemäss einem ersten Ausführungsbeispiel ist das Verfahren dadurch gekennzeichnet, dass der andere vorausgegangene Knoten dann erzeugt worden ist, wenn a(n) > 0 und b(n) > 0 (Blöcke 10, 11 oder 15, 16). Gemäss einem alternativen Ausführungsbeispiel wird der besagte andere vorausgegangene Knoten beispielsweise nicht erzeugt, falls a(n) < 2 und b(n) < 2 ist, oder wird beispielsweise nicht erzeugt, falls a(n)/b(n) < 0,001 oder a(n)/b(n) > 1000 ist.
Gemäss einem zweiten Ausführungsbeispiel ist das Verfahren dadurch gekennzeichnet, dass ein dritter Parameter i(n) den besagten Knoten definiert, wobei er einem vorausgehenden Knoten oder nicht einem vorausgehenden Knoten vorausgegangen ist, wobei die besagte Erzeugung des besagten anderen vorausgegangenen Knotens die Definition eines vierten Parameters j umfasst, der ein Index des anderen vorausgegangenen Knotens ist, wobei a(j) und b(j) initialisiert sind, wobei i(j) den Wert 0 erhält, wobei i(n) den Wert (j) erhält und wobei n den Wert i(n) erhält (Blöcke 9, 11 oder 14, 16). Ein weniger effizienterer aber akkurater Weg, a(j) und b(j) zu initialisieren, könnte darin liegen, dass die gespeicherten Werte eingesetzt werden, die früher aufgefunden worden sind.
Gemäss einem dritten Ausführungsbeispiel ist das Verfahren dadurch gekennzeichnet, dass bei der Initialisierung a (j) den Wert 0 und b(j) den Wert 0 erhalten (Block 11 oder 16). Dies ist ein effizienterer aber weniger akkurater Weg, a(j) und b(j) zu initialisieren könnte.
Gemäss einem vierten Ausführungsbeispiel ist das Verfahren dadurch gekennzeichnet, dass das Verfahren einen Schritt umfasst, der zwischen dem Schritt -x- auf der einen Seite und den Schritten -y- und -z- auf der anderen Seite angeordnet ist, wobei dieser Schritt umfasst:
-w- einen fünften Parameter d, der für jeden weiteren Knoten angepasst wird und der nach jeder Anpassung mit einem Schwellwert D verglichen wird (Block 6). Durch die Einführung des fünften Parameters d und des Vergleichs mit dem Schwellwert D wird das Verfahren zur Erzeugung eines Baumes auf Bäume begrenzt, die eine maximale Tiefe haben, die gleich zu dem Schwellwert D ist.
Das in der Fig. 2 dargestellte Flussdiagramm umfasst Blöcke mit der folgenden Bedeutung:
Block 20 a(1): = 0
b(1): = 0
i&sub0;(1): = 0
i&sub1;(1): = 0
Gehe zu Block 21
Block 21 t: = 1
Gehe zu Block 22
Block 22 Ist t > T ?
Falls ja, Gehe zu Block 23
Falls nein, Gehe zu Block 24
Block 23 Ende
Block 24 weitere Erzeugung des Baumes für x(t)
Gehe zu 25
Block 25 Statistische Berechnungen und Kodierung für x(t)
Gehe zu 26
Block 26 t: = t + 1
Gehe zu Block 22
Das Verfahren gemäss der Erfindung im Hinblick auf das in der Fig. 2 dargestellte Flussdiagramm arbeitet wie folgt. Der erste Parameter a(1) und der zweite Parameter b(1) erhalten den Wert Null (n = 1 entspricht der Wurzel des Baumes) und der dritte Parameter i&sub0;(1) und der dritte Parameter i&sub1;(1) erhalten den Wert Null (Block 20). Dann erhält ein sechster Parameter t den Wert Eins (Block 21), wonach der Wert des sechsten Parameters t mit einem weiteren Schwellwert T (Block 22) verglichen wird: im Fall, dass t > T ist, gibt es keine weiteren Operationen mehr (Block 23), andernfalls wird für das empfangene Symbol x(t) ein Baum erzeugt, dessen Erzeugung in der Fig. 1 (Block 24) dargestellt ist. Dann werden statistische Berechnungen und die Kodierung von x(t) durchgeführt (Block 25), die beispielsweise in den IEEE Transactions on INFORMATION THEORY, Mai 1995, Band 41, Nummer 3, insbesondere in dem Artikel "Das Kontextbaum gewichtete Verfahren: Elementare Eigenschaften" von F. M. J. Willems, Y. M. Shtarkov und T. J. Tjalkens auf den Seiten 653 bis 664 und in der EP 96 202 007.9 (Prioritätstag/Anmeldetag 15. Juli 1996) beschrieben sind. Schliesslich wird der Wert des sechsten Parameters t mit dem Wert Eins erhöht (Block 26), wonach die besagten Operationen wiederholt werden, beginnend mit dem Block 22.

Claims

1. Verfahren zur Erzeugung eines Baumes für einen Kontextbaumstruktur-Algorithmus zum Kodieren von Symbolen, wobei das Verfahren die Schritte umfasst:

-x- Annehmen eines Wertes von entweder einem ersten Parameter oder von einem zweiten Parameter, deren Werte einem Knoten des besagten Baumes entsprechen, in Abhängigkeit von einem Wert eines zu kodierenden Symbols,

-y- Weiterführen des Schrittes -x- für den vorausgegangenen Knoten im Falle, dass dem besagten Knoten ein vorausgegangener Knoten vorausgegangen ist, in Abhängigkeit von einem Wert eines vorausgegangen Symbols, und

-z- Erzeugen eines anderen vorausgegangen Knotens und Weiterführen des Schrittes -x- für den besagten anderen vorausgegangenen Knoten im Falle, dass dem besagtem Knoten nicht ein vorausgegangener Knoten vorausgegangen ist, in Abhängigkeit von einem Wert eines vorausgegangen Symbols, dadurch gekennzeichnet, dass in Abhängigkeit von mindestens einem Wert der besagten Parameter der besagte andere vorausgegangene Knoten erzeugt oder nicht erzeugt wird.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass der erste Parameter a(n) ist und dass der zweite Parameter b(n) ist, wobei die Werte dieser Parameter dem besagten Knoten n zugehören, wobei die anderen vorgehenden Knoten erzeugt worden sind, falls a (n) > 0 und b (n) > 0.

3. Verfahren nach Anspruch 2, dadurch gekennzeichnet, dass ein dritter Parameter i(n) den besagten Knoten definiert, wobei dieser Knoten einem vorausgehenden Knoten oder einem vorausgehenden Knoten nicht vorausgegangen ist, wobei die besagte Erzeugung des besagten anderen vorausgegangenen Knotens die Definition eines vierten Parameters j umfasst, der ein Index des anderen vorausgegangenen Knotens ist, wobei a(j) und b(j) initialisiert sind, wobei i(j) den Wert 0 erhält, wobei i(n) den Wert (j) erhält und wobei n den Wert i(n) erhält.

4. Verfahren nach Anspruch 3, dadurch gekennzeichnet, dass bei der Initialisierung a(j) den Wert 0 und b(j) den Wert 0 erhalten.

5. Verfahren nach einem der Ansprüche 1, 2, 3 oder 4, dadurch gekennzeichnet, dass das Verfahren einen Schritt umfasst, der zwischen dem Schritt -x- auf der einen Seite und den Schritten - y- und -z- auf der anderen Seite angeordnet ist, wobei dieser Schritt umfasst: -w- einen fünften Parameter d, der für jeden weiteren Knoten angepasst wird und der nach jeder Anpassung mit einem Schwellwert D verglichen wird.

6. System zur Erzeugung eines Baumes für einen Kontextbaumstruktur-Algorithmus zum Kodieren von Symbolen, wobei das System Prozessormittel und Speichermittel aufweist, um an ersten Orten, die zu einem Knoten gehören, Werte von Parametern zu speichern und um an zweiten Orten, die zu einem vorausgegangenen Knoten gehören, Werte von Parametern zu speichern und um an dritten Orten, die zu einem anderen vorausgegangenen Knoten gehören, Werte von Parametern zu speichern, wobei die Prozessormittel umfassen:

- Anpassungsmittel, um in Abhängigkeit von einem Wert eines zu kodierenden Symbols einen Wert von entweder einem ersten Parameter oder von einem zweiten Parameter anzupassen, wobei diese Werte in mindestens zwei der besagten Orte gespeichert sind,

- Vergleichermittel, um in Abhängigkeit von einem Wert eines vorausgegangenen Symbol einen Wert eines dritten Parameters, der an zumindest einer der besagten ersten Orte gespeichert ist, mit einem vorbestimmten Wert zu vergleichen, wobei im Falle eines ersten Vergleichsergebnisses ein Wert von entweder einem ersten Parameter oder von einem zweiten Parameter angepasst wird, wobei diese Werte an mindestens zwei der besagten zweiten Orte gespeichert werden, in Abhängigkeit von einem Wert eines zu kodierenden Symbols, indem die Anpassungsmittel eingesetzt werden, und

- Zuweisungsmittel, um im Falle eines zweiten Vergleichsergebnisses in Abhängigkeit von einem Wert eines vorausgegangenen Symbols einem vierten Parameter einen Wert zuzuweisen, wobei dieser Wert an mindestens einem der besagten dritten Orte gespeichert wird, wobei ein Wert von entweder einem ersten Parameter oder von einem zweiten Parameter angepasst wird, wobei diese Werte in Abhängigkeit von einem Wert eines zu kodierenden Symbols unter Benutzung der Anpassungsmittel an mindestens zwei der besagten dritten Orte gespeichert werden,

dadurch gekennzeichnet, dass die Prozessormittel umfassen

- Prüfmittel zum Überprüfen von mindestens einem Wert von zumindest einem der besagten ersten und zweiten Parameter, um im Falle eines ersten Prüfergebnisses die besagten Zuweisungsmittel zu aktivieren und um im Falle eines zweiten Prüfergebnisses die besagten Zuweisungsmittel zu deaktivieren.

7. System nach Anspruch 6, dadurch gekennzeichnet, dass der erste Parameter a(n) ist und dass der zweite Parameter b(n) ist, wobei die Werte dieser Parameter an mindestens zwei der besagten ersten Orte gespeichert sind, wobei a(n) > 0 und b(n) > 0 zu dem besagten ersten Prüfergebnis führen und alle anderen Fälle zu dem besagten zweiten Prüfergebnis führen.

8. System nach Anspruch 7, dadurch gekennzeichnet, dass der dritte Parameter i(n) ist und der vierte Parameter j ist, wobei a(j) und b(j) initialisiert werden, wobei i(j) den Wert 0 erhält, wobei i (n) den Wert j erhält und wobei n den Wert i (n) erhält.

9. System nach Anspruch 8, dadurch gekennzeichnet, dass bei der Initialisierung a(j) den Wert 0 und b(j) den Wert 0 erhalten.

10. System nach einem der Ansprüche 6, 7, 8 oder 9, dadurch gekennzeichnet, dass das Prozessormittel umfasst:

- weitere Anpassungsmittel, um einen fünften Parameters d nach jeder Anpassung des besagten Wertes von entweder dem besagten ersten Parameter oder dem besagten zweiten Parameter anzupassen, und

- weitere Vergleichermittel, um den besagten fünften Parameter d mit einem Schwellwert D nach jeder weiteren Anpassung zu vergleichen.