DE10131801A1

DE10131801A1 - Data compression method and navigation system

Info

Publication number: DE10131801A1
Application number: DE2001131801
Authority: DE
Inventors: Arnd Braun
Original assignee: Robert Bosch GmbH
Current assignee: Robert Bosch GmbH
Priority date: 2001-06-30
Filing date: 2001-06-30
Publication date: 2003-01-16
Anticipated expiration: 2021-07-01
Also published as: FR2826804A1; JP2003046392A; DE10131801B4; GB0212613D0; JP4191438B2; GB2378868A; FR2826804B1

Abstract

Verfahren zur Datenkompression und/oder Dekompression nach einem Verfahren des LZSS-Typs, bei dem die folgenden Steuerungscodes verwendet werden: DOLLAR A - ein erster Steuerungscode für Literalsequenzen einer ersten maximalen Länge, DOLLAR A - Steuercodes für einen Zeiger auf eine zu kopierende Literalsequenz, wobei der Zeiger einer zweiten maximalen Länge und die zu kopierende Literalsequenz eine dritte maximale Länge nicht überschreiten.Method for data compression and / or decompression according to a method of the LZSS type, in which the following control codes are used: DOLLAR A - a first control code for literal sequences of a first maximum length, DOLLAR A - control codes for a pointer to a literal sequence to be copied, whereby the pointer of a second maximum length and the literal sequence to be copied do not exceed a third maximum length.

Description

Die Erfindung betrifft ein Verfahren zur Datenkompression und/oder Datendekompression nach einem auf einem Verfahren des LZSS-Typs basierenden Verfahrens, sowie ein entsprechendes elektronisches System, insbesondere ein Navigationssystem. The invention relates to a method for data compression and / or Data decompression based on a method of the LZSS type Procedure, as well as a corresponding electronic system, in particular a Navigation system.

Verfahren des LZSS-Typs sind aus der US-A-487 6541 sowie aus T. C. Beil in "Better OPM/L Text Compression, IEEE Trans. On Communications", Vol. COM- 34, No. 12. Dec., 1986 bekannt. Methods of the LZSS type are known from US-A-487 6541 and from T. C. Beil in "Better OPM / L Text Compression, IEEE Trans. On Communications", Vol. COM- 34, No. Dec. 12, 1986.

Bei dem LZSS-Verfahren handelt es sich um eine Weiterentwicklung des Lempel Ziv Verfahrens. The LZSS process is a further development of the Lempel Civil Procedure.

Bei Anwendung des LZSS-Verfahrens wird in den zuletzt übertragenen Zeichen innerhalb eines Datenfensters einer bestimmten Länge nach einer Zeichenkette gesucht, die mit den nächsten zu übertragenden Zeichen übereinstimmt. Wird eine solche Zeichenkette gefunden, dann wird diese durch einen Rückverweis ersetzt. When using the LZSS procedure, the last transmitted characters are: within a data window of a certain length after a character string searched for that matches the next characters to be transmitted. Becomes such a character string is found, then it is referenced back replaced.

Für die entsprechende Codierung werden zwei unterschiedliche Steuercodes verwendet. Der Steuercode "L" zeigt an, dass als nächstes eine Anzahl "echter" Zeichen, sogenannte Literals, übertragen werden. Dagegen zeigt der Steuercode "C" an, dass aus den schon übertragenen Zeichen eine Zeichenkette kopiert werden soll:
F (s) - Datenfenster, in dem nach gleichen Zeichenketten gesucht wird. Es umfasst eine Anzahl von s Zeichen vor der aktuellen Leseposition im Eingabedatenstrom.
L (n) - Steuerzeichen zur Angabe, dass nachfolgend eine Anzahl von n Literals, das heißt, eine Literalsequenz der Längen übertragen wird.
C (p, n) - Steuerzeichen, zur Identifikation einer zu kopierenden vorausgegangenen Literalsequenz, d. h. gehe p Zeichen zurück und kopiere von dort n Zeichen. Two different control codes are used for the corresponding coding. The control code "L" indicates that a number of "real" characters, so-called literals, are transmitted next. In contrast, the control code "C" indicates that a character string should be copied from the characters already transferred:
F (s) - Data window in which the same character strings are searched. It contains a number of s characters before the current reading position in the input data stream.
L (n) - control character to indicate that a number of n literals, that is to say a literal sequence of lengths, is subsequently transmitted.
C (p, n) - control characters, to identify a previous literal sequence to be copied, ie go back p characters and copy n characters from there.

Die Fig. 1 zeigt ein Beispiel für die Codierung einer Zeichenkette 1 nach dem aus dem Stand der Technik bekannten LZSS-Verfahrens. Das Ergebnis der Codierung ist die Zeichenkette 2 der Fig. 1, wobei es sich bei den Zeichen in Fettschrift um Literals handelt. Fig. 1 shows an example of the encoding of a string 1 according to the method known from the prior art LZSS method. The result of the coding is the character string 2 of FIG. 1, the characters in bold letters being literals.

Ferner sind aus dem Stand der Technik verschiedene Varianten des LZSS- Verfahrens bekannt, beispielsweise LZSS mit adaptiver arithmetischer Codierung und LZSS mit adaptiver Hoffman-Codierung. Eine Übersicht hierüber findet sich in dem Proseminar "Redundanz". Vortrag 5, Maximilian Hrabowski (http:/ / qoethe.ira.uka.de/seminare/redundanz/vortrag05/#LZSS). Weitere Darstellungen des LZSS-Verfahrens finden sich unter http: / / ttrp1.fhworms.de/sem/ws95 96/kompressionsalaorithmen/node19.html und http:/ / ttrip1.fhworms.de/sem/ws95 96/kompressionsalgorithmen/node20.html. Furthermore, various variants of the LZSS are from the prior art Method known, for example LZSS with adaptive arithmetic coding and LZSS with adaptive Hoffman coding. An overview of this can be found in the proseminar "Redundancy". Lecture 5, Maximilian Hrabowski (http: / / qoethe.ira.uka.de/seminare/redundanz/vortrag05/#LZSS). Further Representations of the LZSS procedure can be found at http: / / ttrp1.fhworms.de/sem/ws95 96 / kompressionsalaorithmen / node19.html and http: / / ttrip1.fhworms.de/sem/ws95 96 / compression algorithms / node20.html.

Aus der US-A-5 502 439 ist ein Verfahren zur Kompression binärer Daten nach dem LZSS-Verfahren bekannt. Dabei wird ein Puffer in einem Speicher mit wahlfreiem Zugriff für die vorübergehende Speicherung sogenannter Flag-Bits, die bei der Durchführung des LZSS-Verfahrens generiert werden, verwendet. Weitere Verfahren des LZSS-Typs sind aus US-A-5 701 125, US-A-5 673 042 und US-A-5 867 114 bekannt. US-A-5 502 439 describes a method for compressing binary data known as the LZSS process. A buffer is stored in a memory random access for the temporary storage of so-called flag bits, which at the implementation of the LZSS procedure are used. Further LZSS-type processes are disclosed in US-A-5,701,125, US-A-5,673,042 and US-A-5 867 114 known.

Der Erfindung liegt die Aufgabe zu Grunde, ein verbessertes Verfahren des LZSS- Typs und ein entsprechendes verbessertes Computerprogrammprodukt sowie elektronisches System zu schaffen. The invention is based on the object of an improved method of the LZSS Type and a corresponding improved computer program product as well to create electronic system.

Die der Erfindung zu Grunde liegende Aufgabe wird jeweils mit den Merkmalen der unabhängigen Patentansprüche gelöst. Bevorzugte Weiterbildungen der Erfindung sind in den abhängigen Ansprüchen angegeben. The object underlying the invention is in each case with the features of the independent claims. Preferred further developments of Invention are specified in the dependent claims.

Das erfindungsgemäße Verfahren des LZSS-Typs ermöglicht eine besonders schnelle Datendekompression bei gleichzeitiger guter Kompressionsrate. In einer bevorzugten Ausführungsform der Erfindung werden hierzu die Steuercodes für die Durchführung des LZSS-Verfahrens in Abhängigkeit von der Auftretenshäufigkeit unterschiedlicher Längen von Literalsequenzen, Längen von zu kopierenden Literalsequenzen und den Längen von Rückverweisen festgelegt. The method of the LZSS type according to the invention enables a particularly fast data decompression with a good compression rate. In a preferred embodiment of the invention, the control codes for the implementation of the LZSS procedure depending on the Frequency of occurrence of different lengths of literal sequences, lengths of to be copied Literal sequences and the lengths of back references.

Nach einer weiteren bevorzugten Ausführungsform werden jeweils Mengen von Steuercodes gebildet, die zur Erreichung einer weiteren Kompression ihrerseits beispielsweise Hoffman-codiert werden können. According to a further preferred embodiment, amounts of Tax codes are formed which, in turn, achieve further compression for example Hoffman-encoded.

Gemäß einer weiteren Ausführungsform der Erfindung erfolgen die Rückverweise nur in einem Byte-Raster, welches durch die Breite des verwendeten Datenbusses bzw. des verwendeten Prozessors vorgegeben ist. Hierdurch wird die Verarbeitungsgeschwindigkeit bei der Dekompression nochmals gesteigert. Ebenso wird hierdurch auch die Kompressionsrate erhöht. According to a further embodiment of the invention, the back references are made only in a byte grid, which is determined by the width of the data bus used or the processor used is specified. This will make the Processing speed during decompression increased again. Likewise, this also increases the compression rate.

Von besonderem Vorteil ist die Anwendung des erfindungsgemäßen Verfahrens für ein elektronisches System, beispielsweise ein Navigationssystem. Bei bekannten Navigationssystemen werden im Allgemeinen CDs für die Speicherung der Navigationsdatenbanken verwendet. Um möglichst viele Navigationsdaten auf einer CD unterzubringen, ist es vorteilhaft, die Navigationsdaten nach einem erfindungsgemäßen Verfahren zu komprimieren. Die Geschwindigkeit der Datenkompression ist dabei praktisch zweitrangig, da diese nur einmal und nicht im laufenden Betrieb, erfolgt. The use of the method according to the invention is particularly advantageous for an electronic system, for example a navigation system. at Known navigation systems are generally used for storing the CDs Navigation databases used. To get as much navigation data as possible to accommodate a CD, it is advantageous to the navigation data after a Compress method according to the invention. The speed of the Data compression is practically secondary since it is only once and not in the ongoing operation.

Für den praktischen Einsatz des Navigationssystems ist dagegen die Dekompressionsgeschwindigkeit von großer Bedeutung, da ständig beim Betrieb des Navigationssystems Navigationsdaten zu dekomprimieren sind, um die Routenplanung und Positionsbestimmung vorzunehmen. Auch insofern ist das erfindungsgemäße Verfahren besonders vorteilhaft, da es eine besonders schnelle Datendekompression ermöglicht. However, for the practical use of the navigation system Decompression speed is of great importance, since the Navigation system's navigation data is decompressed to route planning and position determination. In this respect, too, is the invention The method is particularly advantageous because it is particularly fast Data decompression enabled.

Im Weiteren wird die Erfindung anhand eines bevorzugten Ausführungsbeispiels mit Bezug auf die Zeichnungen näher erläutert. Es zeigen: Furthermore, the invention is based on a preferred embodiment explained in more detail with reference to the drawings. Show it:

Fig. 1 die Codierung einer Zeichensequenz nach dem Stand der Technik, Fig. 1 shows the encoding of a sequence of characters according to the prior art,

Fig. 2 ein Flussdiagramm einer Ausführungsform des erfindungsgemäßen Verfahrens, Fig. 2 is a flow diagram of an embodiment of the inventive method,

Fig. 3 die prozentuale Verteilung von Literalsequenzen und der Länge von Rückverweisen in einem Musterdatensatz, Fig. 3 shows the percentage distribution of Literalsequenzen and the length of back links in a pattern data set,

Fig. 4 eine Ausführungsform für die Bestimmung von Mengen von Steuercodes, Fig. 4 shows an embodiment for the determination of sets of control codes,

Fig. 5 die Codierung einer Zeichenkette mittels der Steuerungscodes der Fig. 4, Fig. 5 shows the encoding of a string by means of the control codes of FIG. 4,

Fig. 6 die Umcodierung der codierten Zeichenkette der Fig. 5 mittels eines weiteren Steuercodes, Fig. 6 transcoding the encoded string of Fig. 5, by means of a further control codes

Fig. 7 ein Blockdiagramm eines erfindungsgemäßen elektronischen Systems. Fig. 7 is a block diagram of an electronic system according to the invention.

Das Verfahren der Fig. 2 dient zur Ermittlung von Steuercodes für die Anwendung in einer Ausführungsform des erfindungsgemäßen Verfahrens. Dazu wird in dem Schritt 20 zunächst ein Musterdatensatz eingegeben, der in dem Schritt 21 einer Codierung mittels eines an sich aus dem Stand der Technik bekannten LZSS- Verfahrens unterzogen wird. Als Musterdatensatz kann ein typischer Datensatz oder auch ein tatsächlicher Datensatz verwendet werden. The method of FIG. 2 is used to determine control codes for use in one embodiment of the method according to the invention. For this purpose, a sample data set is first entered in step 20 , which is subjected to coding in step 21 by means of an LZSS method known per se from the prior art. A typical data record or an actual data record can be used as the sample data record.

In dem Schritt 22 wird das durch die Ausführung des Schritt 21 erhaltene Kompressionsergebnis einer statistischen Analyse unterzogen. Dazu wird beispielsweise die Häufigkeitsverteilung der unterschiedlichen Längen von in dem Kompressionsergebnis vorkommenden Literalsequenzen festgestellt, sowie auch die Häufigkeitsverteilungen der Längen von Rückverweisen und der Längen von bei der Anwendung des Schritts 21 kopierten Literalsequenzen. In step 22 , the compression result obtained by executing step 21 is subjected to a statistical analysis. For this purpose, for example, the frequency distribution of the different lengths of literal sequences occurring in the compression result is determined, as well as the frequency distributions of the lengths of back references and the lengths of literal sequences copied when step 21 was used .

Zur Optimierung der Dekompressionsgeschwindigkeit werden im Nachfolgenden maximale Längen festgelegt. Hierzu wird zunächst in dem Schritt 23 eine obere Schranke S₁ für die Länge der Literalsequenzen ermittelt, so dass X% der in dem Kompressionsergebnis des Schritt 21 beinhalteten Literale eine Länge ≤ S₁ aufweisen. X% kann beispielsweise als 95% angenommen werden. To optimize the decompression speed, maximum lengths are specified below. For this purpose, an upper bound S ₁ for the length of the literal sequences is first determined in step 23 , so that X% of the literals contained in the compression result of step 21 have a length S S ₁ . For example, X% can be assumed to be 95%.

Entsprechend wird in dem Schritt 24 eine obere Schranke S₂ für die Länge der Rückverweise ermittelt, so dass Y% der Rückverweise eine Länge aufweisen, die ≤ der oberen Schranke S₂ ist. Auch hier kann Y% wieder als 95% gewählt werden. Correspondingly, an upper bound S ₂ for the length of the back references is determined in step 24 , so that Y% of the back references have a length that is der the upper bound S ₂ . Here, too, Y% can again be selected as 95%.

Schließlich wird in dem Schritt 25 noch eine obere Schranke S₃ für die Länge der kopierten Literale in dem Kompressionsergebnis des Schritts 21 ermittelt, so dass Z% der kopierten Literalsequenzen eine Länge ≤ der oberen Schranke S₃ aufweisen. Z% kann wiederum als 95% gewählt werden. Finally, an upper bound S ₃ for the length of the copied literals is determined in step 25 in the compression result of step 21 , so that Z% of the copied literal sequences have a length ≤ of the upper bound S ₃ . Z% can again be selected as 95%.

In dem Schritt 26 werden die für die Codierung der unterschiedlichen Längen jeweils erforderlichen Bitanzahlen ermittelt, das heißt, es werden die Anzahl der Bits B₁ zur Codierung von S₁ unterschiedlichen Längen von Literalsequenzen, die Anzahl von Bits B₂ zur Codierung von S₂ unterschiedlichen Längen von Rückverweisen und die Anzahl von Bits B₃ zur Codierung von S₃ unterschiedlichen Längen zu kopierender Literalsequenzen ermittelt. In step 26 , the number of bits required in each case for the coding of the different lengths are determined, that is to say the number of bits B ₁ for coding S ₁ different lengths of literal sequences and the number of bits B ₂ for coding S _{2 are} different Lengths of back references and the number of bits B ₃ for coding S ₃ different lengths of literal sequences to be copied determined.

Aufgrund der Ergebnisse des Schritts 26 erfolgt in dem Schritt 27 die Festlegung der Steuercodes. Die Unterscheidung zwischen einem L und einem C Steuercode erfolgt durch die erste Bitposition - in dem betrachteten Beispiel 0 für den Steuercode L und 1 für den Steuercode C. Based on the results of step 26 , the control codes are defined in step 27 . The distinction between an L and a C control code is made by the first bit position - in the example considered 0 for the control code L and 1 for the control code C.

In dem Steuercode L folgen danach eine Anzahl von B₁ Bitpositionen X zur Kodierung der Länge n der nachfolgenden Literalsequenz. In dem Steuercode C folgen nach der führenden 1 zunächst eine Anzahl B₂ von Bitpositionen X für die Codierung der unterschiedlichen Längen von Rückverweisen und danach eine Anzahl von B₃ von Bitpositionen Y zur Codierung der unterschiedlichen Zeichenlängen der zu kopierenden Literalsequenzen. The control code L is followed by a number of B ₁ bit positions X for coding the length n of the subsequent literal sequence. In the control code C, the leading 1 is followed by a number B ₂ of bit positions X for coding the different lengths of back-references and then a number B ₃ of bit positions Y for coding the different character lengths of the literal sequences to be copied.

Für einen Musterdatensatz wurden dabei beispielsweise folgende Werte ermittelt:
S₁ = 128, S₂ = 4096 und S₃ = 32. Daraus ergibt sich B₁ = 7, B₂ = 12 und B₃ = 5. For example, the following values were determined for a sample data record:
S ₁ = 128, S ₂ = 4096 and S ₃ = 32.This results in B ₁ = 7, B ₂ = 12 and B ₃ = 5.

Die Tabellen der Fig. 3 zeigen, dass ein hoher Prozentsatz der Daten nur einen kleinen Teil der möglichen Steuerungscodes ausnutzt. The tables of FIG. 3 show that a high percentage of the data uses only a small part of the possible control codes.

Bei dem untersuchten Musterdatensatz hatten Literalsequenzen der Länge 1 einen Anteil von 50% an den vorkommenden Steuerzeichen L; Literalsequenzen einer Länge von 2 bis 8 einen Anteil von 25% und Literalsequenzen von > 8 bis zu der oberen Schranke S₁ einen Anteil von 25%. In the sample data set examined, literal sequences of length 1 had a share of 50% in the control characters L; Literal sequences of a length of 2 to 8 a share of 25% and literal sequences of> 8 up to the upper bound S ₁ a share of 25%.

Entsprechend hatten Rückverweise mit zu kopierenden Literalsequenzen einer Länge von 1 bis 8 einen Anteil von 70% an den Steuerungscodes C. Ferner haben Rückverweise mit einer Länge des Zeigers p zwischen 1 und 32 Positionen einen Anteil von 50% der Steuerungscodes C, Rückverweise einer Länge zwischen 33 und 512 Positionen einen Anteil von 25% und Rückverweise einer Länge von > 512 bis zu der oberen Schranke einen Anteil von 25%. Correspondingly, backlinks with literal sequences to be copied had one Length from 1 to 8 a share of 70% in the control codes C. Furthermore have back references with a length of pointer p between 1 and 32 positions a share of 50% of the control codes C, back references of a length between 33 and 512 positions a share of 25% and back references one Length from> 512 to the upper barrier a share of 25%.

Entsprechend werden gemäß der Darstellung der Fig. 4 zwei unterschiedliche Mengen von Steuerungscodes L und C gebildet. Für die Steuerungscodes L sind dies die Codes L₁, L₂ und L₃ jeweils für einen Längenbereich der Literalsequenzen von 1, 2 bis 9 und 10 bis 265. Die für die Steuerungscodes L₁, L₂ und L₃ jeweils erforderliche Anzahl von Bits B₁ beträgt dabei 0, 3 bzw. 8. In dem hier betrachteten Beispiel wird der Steuerungscode L₁ als 001, der Steuerungscode L₂ als 010 und der Steuerungscodes L₃ als 011 codiert; die jeweilige Länge für die Codierung eines Steuerungscodes beträgt daher in diesem Fall je drei Bit. Accordingly, two different sets of control codes L and C are formed as shown in FIG. 4. For the control codes L, these codes are L _1, L ₂ and L ₃ each represents a length range of Literalsequenzen from 1, 2 to 9 and 10 to 265. The required in each case for the control code L _1, L ₂ and L ₃ Number of bits B ₁ is 0, 3 or 8. In the example considered here, the control code L _{1 is} coded as 001, the control code L ₂ as 010 and the control code L ₃ as 011; the respective length for coding a control code is therefore three bits in each case.

Die Darstellung der Fig. 4 beinhaltet ferner die Codierung für die Steuerungscodes C. In dem betrachteten Beispiel werden sechs Steuerungscodes C₁ bis C₆ entsprechend der Verteilung der Rückverweise der Fig. 3 gebildet. Der Steuerungscode C₁ wird dabei als 1001 codiert, der Steuerungscode C₂ als 1010 usw. The representation of FIG. 4 also includes the coding for the control codes C. In the example under consideration, six control codes C ₁ to C _{6 are formed in} accordance with the distribution of the back references of FIG. 3. The control code C ₁ is coded as 1001, the control code C ₂ as 1010 etc.

Die Anzahl der für die Codierung jedes der Steuerungscodes C verwendeten Bits ist gleichbleibend vier; alternativ kann jedoch die Codierung der Steuerungscodes L und C auch beispielsweise nach einem Huffman-Verfahren erfolgen, wobei die Auftretenswahrscheinlichkeit eines bestimmten Codes gemäß der Tabelle der Fig. 3 berücksichtigt wird. The number of bits used to encode each of the control codes C remains four; alternatively, however, the control codes L and C can also be coded, for example, using a Huffman method, the probability of occurrence of a specific code being taken into account in accordance with the table in FIG. 3.

Nachdem mit der Tabelle 3 die Anzahl der Codes, und ihre Größe, bestimmt wurde, wird die Häufigkeit der einzelnen Codes an der Gesamtheit der auftretenden Codes bestimmt und nach dieser Häufigkeit die Huffman-Codes vergeben. After using table 3 the number of codes, and their size, are determined the frequency of the individual codes is based on the total of the occurring Codes and assign the Huffman codes according to this frequency.

Wenn die Literal-Codes 40% aller Codes ausmachen und die Copy-Codes mit kurzer Zeichenkette 70% aller Copy-Codes, ergibt sich mit Tabelle 3 folgende Verteilung:

If the literal codes make up 40% of all codes and the copy codes with a short string 70% of all copy codes, the following distribution results with table 3:

In diesem Fall ergeben sich unterschiedliche Code-Längen, wobei der Code mit der höchsten Häufigkeit die kürzeste Codierung erhält. In dem betrachteten Beispiel ist dies der Code C1. In this case there are different code lengths, the code with receives the shortest coding with the highest frequency. In the one under consideration Example is code C1.

Der Steuerungscode C₁ kommt für einen Rückverweis mit einem Zeiger in dem Wertebereich 2 bis 33 Zeichen auf eine Literalsequenz einer Länge von 2 bis 5 Zeichen zur Anwendung. Dabei ist zu berücksichtigen, dass ein Rückverweis nur dann stattfindet, wenn die Länge des Rückverweises mindestens zwei Zeichen beträgt und die Länge der zu kopierenden Literalsequenz, auf die rückverwiesen wird, mindestens zwei ist. Entsprechend beträgt die Anzahl von Bits zur Codierung des Wertebereichs des Zeigers ("Pointer") fünf und die Anzahl von Bits für die Codierung des Wertebereichs 2 bis 5 der Länge der zu kopierenden Literalsequenzen zwei Bits. Entsprechende Zuordnungen finden sich in der Tabelle der Fig. 4 auch für die Steuerungscodes C₂ bis C₆. The control code C ₁ is used for a back reference with a pointer in the value range 2 to 33 characters to a literal sequence with a length of 2 to 5 characters. It should be noted that a back reference only takes place if the length of the back reference is at least two characters and the length of the literal sequence to be copied to which reference is made is at least two. Accordingly, the number of bits for coding the range of values of the pointer ("pointer") is five and the number of bits for coding the range of values 2 to 5 of the length of the literal sequences to be copied is two bits. Corresponding assignments can also be found in the table in FIG. 4 for the control codes C ₂ to C ₆ .

Wenn die Zeichen in der zu komprimierenden Sequenz in einem Byteraster angeordnet sind, beispielsweise einer Breite von zwei oder vier Bytes, kann die Datenkompression weiter optimiert werden, in dem nur die tatsächlich vorkommenden Zeigerlängen in den Steuercodes C abgebildet werden. Beispielsweise lässt sich die Bitanzahl für die Codierung der Zeigerlänge in dem Steuercode C₁ für Daten in einem Zweibyteraster von fünf auf vier Bit reduzieren, da ungeradzahlige Rückverweise per Definition nicht vorkommen können. Bei einem Raster von Vierbytelänge lässt sich entsprechend eine Reduktion um ein weiteres Bit erzielen. Das Vorliegen von Daten in einem Byteraster wird auch als Alignment bezeichnet. Das Alignment der Daten überträgt sich entsprechend auf die Rückverweise. If the characters in the sequence to be compressed are arranged in a byte raster, for example a width of two or four bytes, the data compression can be further optimized by only mapping the actually occurring pointer lengths in the control codes C. For example, the number of bits for coding the pointer length in the control code C ₁ for data in a two-byte grid can be reduced from five to four bits, since by definition, odd-numbered references cannot occur. With a grid of four byte length, a reduction by another bit can be achieved accordingly. The existence of data in a byte grid is also referred to as alignment. The alignment of the data is transferred accordingly to the back references.

Die Fig. 5 zeigt die Codierung der Sequenz 1 (vgl. Fig. 1) nach einem erfindungsgemäßen Verfahren mittels der Steuerungscodes der Fig. 4. Es resultiert dabei das Kompressionsergebnis 3. FIG. 5 shows the coding of sequence 1 (cf. FIG. 1) according to a method according to the invention by means of the control codes of FIG. 4. The result of compression 3 results.

Ein Nachteil bei dem Kompressionsergebnis 3 ist, dass die in dem Kompressionsergebnis 3 beinhalteten Literalsequenzen wegen der bitorientierten Codierung der Befehle nicht mehr an Bytegrenzen ausgerichtet sind und deshalb entsprechend geshiftet werden müssen. A disadvantage of the compression result 3 is that the literal sequences contained in the compression result 3 are no longer aligned with byte boundaries due to the bit-oriented coding of the commands and must therefore be shifted accordingly.

Um diesen Nachteil zu beheben, werden die Steuerungsbefehle und die Literalsequenzen bei der Codierung zunächst in zwei Datenströme getrennt. Der Datenstrom der Literalsequenzen ist dabei byteorientiert. Der Datenstrom der Steuerungscodes ist bitorientiert. To overcome this disadvantage, the control commands and the Literal sequences are initially separated into two data streams during coding. The The data stream of the literal sequences is byte-oriented. The data stream of the Control codes are bit-oriented.

Nachdem die beiden Datenströme vollständig vorliegen, können sie wieder in einen einzigen Datenstrom zusammengeführt werden, in dem die beiden Datenströme beispielsweise aneinandergehängt werden. Die Trennung der beiden Datenströme wird in dem durch Aneinanderhängen entstandenen Datenstrom durch einen weiteren Steuercode gekennzeichnet. Dieser kann etwa an den Anfang des resultierenden Datenstroms gestellt werden, um von dort die Trennung zwischen den Datenströmen zu referenzieren. After the two data streams are complete, they can be in again a single data stream are merged in which the two For example, data streams can be linked together. The separation of the two Data streams are carried through in the data stream created by connecting them marked another tax code. This can be at the beginning of the resulting data stream to be made from there the separation between to reference the data streams.

Die Fig. 6 zeigt ein entsprechendes Beispiel, in dem das Kompressionsergebnis 3 der Fig. 5 umcodiert wird. Zunächst erfolgt eine Aufteilung des Kompressionsergebnisses 3 in einen Datenstrom 4 von Steuerungscodes und in einen Datenstrom 5 von Literalsequenzen. FIG. 6 shows a corresponding example in which the compression result 3 of FIG. 5 is recoded. First, the compression result 3 is divided into a data stream 4 of control codes and a data stream 5 of literal sequences.

Durch Aneinanderhängen der Datenströme 4 und 5 entsteht der resultierende Datenstrom 6. Diesem ist ein Zeiger Z(n) vorangestellt, der auf das erste Zeichen des Datenstroms 5 zeigt. The resulting data stream 6 is created by connecting the data streams 4 and 5 . This is preceded by a pointer Z (n) which points to the first character of the data stream 5 .

Die Fig. 7 zeigt ein Blockdiagramm eines Navigationssystems 7, welches einen CD-ROM Abspieler 8 beinhaltet. Das Navigationssystem 7 hat ferner einen Mikroprozessor 9 sowie Speicherbereiche 10, 11 und 12. Auf einer CD-ROM des CD- ROM Abspielers 8 befinden sich nach einem erfindungsgemäßen Verfahren komprimierte Navigationsdaten. FIG. 7 shows a block diagram of a navigation system 7 which contains a CD-ROM player 8 . The navigation system 7 also has a microprocessor 9 and memory areas 10 , 11 and 12 . Compressed navigation data are stored on a CD-ROM of the CD-ROM player 8 using a method according to the invention.

Sequenzen solcher Navigationsdaten werden von dem Navigationssystem von dem CD-ROM Abspieler 8 abgefragt und zu dem Navigationssystem 7 übertragen. Bei Empfang eines Datenstroms entsprechend dem Datenstrom 6 der Fig. 6 teilt der Mikroprozessor 9 den empfangenen Datenstrom in einem ersten Datenstrom von Steuercodes und in einem zweiten Datenstrom von Literalsequenzen auf, wobei dies unter Verwendung des vorangestellten Zeigers Z(n) erfolgt. Sequences of such navigation data are queried by the navigation system from the CD-ROM player 8 and transmitted to the navigation system 7 . Upon receipt of a data stream corresponding to data stream 6 of FIG. 6, microprocessor 9 divides the received data stream into a first data stream of control codes and a second data stream of literal sequences, this being done using the preceding pointer Z (n).

Die Steuercodedatensequenz wird in dem Speicherbereich 10 abgelegt, die Literalsequenzen in dem Speicherbereich 11. Zur Decodierung muss der Mikroprozessor 9 dann lediglich die Steuercodes in dem Speicherbereich 10 abarbeiten und dabei auf die Literalsequenzen in dem Speicherbereich 11 zugreifen. Nach Ausführung eines Steuercodes ermittelte Dekompressionsergebnisse werden dann nacheinander in dem Speicherbereich 12 abgelegt, ohne dass Shift- Operationen notwendig sind. Aufgrund dessen lässt sich eine sehr schnelle Decodierung in dem Navigationssystem 7 erreichen, so dass während der Fahrt beispielsweise auf Routenänderungen und dergleichen sehr schnell reagiert werden kann. The control code data sequence is stored in the memory area 10 , the literal sequences in the memory area 11 . For decoding, the microprocessor 9 then only has to process the control codes in the memory area 10 and access the literal sequences in the memory area 11 . Decompression results determined after execution of a control code are then stored one after the other in the memory area 12 without shift operations being necessary. As a result, very fast decoding can be achieved in the navigation system 7 , so that, for example, route changes and the like can be reacted to very quickly while driving.

Eine weitere Beschleunigung der Dekompression lässt sich erreichen, wenn bei der Kompression nur Rückverweise einer Zeigerlänge, die größer als die Länge der zu kopierenden Literalsequenz ist, zugelassen werden. Beispielsweise wird ein Rückverweis C4 (17, 20) dann aufgespalten in C4 (17, 17) C4 (17, 3). Dies führt zu einer Einsparung von Prozessorleistung. A further acceleration of the decompression can be achieved if the compression only allows back references of a pointer length that is greater than the length of the literal sequence to be copied. For example, a back reference C4 ( 17 , 20 ) is then split into C4 ( 17 , 17 ) C4 ( 17 , 3 ). This leads to a saving in processor performance.

Wenn die zu komprimierenden Daten besondere Strukturen beinhalten, kann durch weitere ergänzende Methoden und ggf. weitere Steuercodes eine nochmalige Verbesserung der Kompressionsrate bzw. der Dekompressionszeit erzielt werden:

- Einige Datenstrukturen haben Bereiche, in denen eine lange Folge gleicher Zeichen auftritt; diese Sequenzen können zusätzlich vorab mit einem RUN-LENGTH-ENCODING Verfahren codiert werden.
- Wenn sich zeigt, dass Steuerungscodesequenzen mehrfach hintereinander wiederholt auftreten, können diese mit einem Wiederholungskommando codiert werden. Der Vorteil ist, dass die entsprechende Steuerungscodesequenz nur einmal decodiert werden muss.

If the data to be compressed contains special structures, the compression rate or decompression time can be improved again by using additional methods and, if necessary, additional control codes:

- Some data structures have areas in which a long sequence of the same characters occurs; these sequences can additionally be coded beforehand using a RUN-LENGTH-ENCODING method.
- If it appears that control code sequences occur repeatedly several times in succession, they can be coded with a repeat command. The advantage is that the corresponding control code sequence only has to be decoded once.

Claims

1. Method for data compression and / or data decompression according to a method of the LZSS type,
characterized by the use of the following tax codes:

a first control code for literal sequences of a first maximum length,

a second control code for a pointer for a back reference to a literal sequence to be compressed, the back reference having a second maximum length and the literal sequence to be copied a third maximum length.

2. The method according to claim 1, in which to determine the first maximum Length the frequency distribution of the lengths of the literal sequences in one LZSS- carried out using control codes without length limitation Procedure encoded pattern data set is used.

3. The method according to claim 1 or 2, in which to determine the second maximum length the frequency distribution of the lengths of the pointers in one determined using an LZSS method without length restriction compressed data set is used.

4. The method of claim 1, 2 or 3, in which to determine the third maximum length the frequency distribution of the lengths of to be copied Literal sequences in one using an LZSS procedure without Length restriction determined compressed data record of a Sample data set is used.

5. The method according to any one of the preceding claims 1 to 4, in which Execution of the LZSS procedure a first set of first control codes and a second set of second control codes is used.

6. The method of claim 5, wherein the first set each has a first Control code for literal sequences within a certain Value range includes.

7. The method of claim 6, wherein the first and second Control codes according to the frequency of occurrence of the literal sequences or the Frequency of rejections in the relevant value ranges are encoded according to a Huffman method.

8. The method according to any one of the preceding claims 5, 6 or 7, in which the second set each a control code for a range of values of the pointer and has a range of values of the literal sequence to be copied.

9. The method of claim 8, wherein the second control codes Huffmann coded.

10. The method of claim 8 or 9, wherein the range of values of the pointer divided byte or in multiples of a byte length.

11. The method according to any one of the preceding claims 1 to 10, in which the first and second control codes and the literals in two from each other separate sections of the compression result are stored and a third control code is used to identify the separation.

12. Method for decompression according to a method of preceding claims 1 to 11 compressed character string with the following steps:

Separation of the tax codes from the literals by means of the third control code,

Storage of the control codes in a first storage section,

Storage of the literals in a second storage section,

- Access to literal sequences to be copied in the second memory and storage of the literal sequences to be copied in a third memory.

13. Computer program product on a computer readable medium or a file which can be loaded via a computer network with program means for Carrying out a method according to one of the preceding Claims 1 to 12 if the computer program on an electronic System, preferably a navigation system, is executed.

14. Electronic system, preferably navigation system, with means for Execution of the process steps according to one of the preceding Claims 1 to 13.

15. Electronic system, preferably navigation system, according to claim 13 with a first memory area ( 10 ) for storing control codes, a second memory area ( 11 ) for storing literal sequences and a third memory area ( 12 ) for storing copied literal sequences.