DE10131801A1

DE10131801A1 - Verfahren zur Datenkompression und Navigationssystem

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: DE10131801B4; FR2826804A1; GB0212613D0; FR2826804B1; GB2378868A; JP4191438B2; JP2003046392A

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.

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.

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.

Bei dem LZSS-Verfahren handelt es sich um eine Weiterentwicklung des Lempel Ziv Verfahrens.

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.

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.

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.

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.

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.

Der Erfindung liegt die Aufgabe zu Grunde, ein verbessertes Verfahren des LZSS- Typs und ein entsprechendes verbessertes Computerprogrammprodukt sowie elektronisches System zu schaffen.

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.

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.

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.

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.

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.

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.

Im Weiteren wird die Erfindung anhand eines bevorzugten Ausführungsbeispiels mit Bezug auf die Zeichnungen näher erläutert. Es zeigen:
Fig. 1 die Codierung einer Zeichensequenz nach dem Stand der Technik,
Fig. 2 ein Flussdiagramm einer Ausführungsform des erfindungsgemäßen Verfahrens,
Fig. 3 die prozentuale Verteilung von Literalsequenzen und der Länge von Rückverweisen in einem Musterdatensatz,
Fig. 4 eine Ausführungsform für die Bestimmung von Mengen von Steuercodes,
Fig. 5 die Codierung einer Zeichenkette mittels der Steuerungscodes der Fig. 4,
Fig. 6 die Umcodierung der codierten Zeichenkette der Fig. 5 mittels eines weiteren Steuercodes,
Fig. 7 ein Blockdiagramm eines erfindungsgemäßen elektronischen Systems.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Die Tabellen der Fig. 3 zeigen, dass ein hoher Prozentsatz der Daten nur einen kleinen Teil der möglichen Steuerungscodes ausnutzt.
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%.
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%.
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.
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.
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.
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.
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:
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.
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₆.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.

Claims

1. Verfahren zur Datenkompression und/oder Datendekompression nach einem Verfahren des LZSS-Typs,
gekennzeichnet durch die Verwendung von folgenden Steuercodes:

- eines ersten Steuercodes für Literalsequenzen einer ersten maximalen Länge,

- eines zweiten Steuercodes für einen Zeiger für einen Rückverweis auf eine zu komprimierende Literalsequenz, wobei der Rückverweis eine zweite maximale Länge und die zu kopierende Literalsequenz eine dritte maximale Länge haben.

2. Verfahren nach Anspruch 1, bei dem zur Festlegung der ersten maximalen Länge die Häufigkeitsverteilung der Längen der Literalsequenzen in einem mittels Steuercodes ohne Längenbegrenzung durchgeführten LZSS- Verfahren codierten Musterdatensatz verwendet wird.

3. Verfahren nach Anspruch 1 oder 2, bei dem zur Festlegung der zweiten maximalen Länge die Häufigkeitsverteilung der Längen der Zeiger in einem mittels eines LZSS-Verfahrens ohne Längenbeschränkung ermittelten komprimierten Datensatzes verwendet wird.

4. Verfahren nach Anspruch 1, 2 oder 3, bei dem zur Festlegung der dritten maximalen Länge die Häufigkeitsverteilung der Längen von zu kopierenden Literalsequenzen in einem mittels eines LZSS-Verfahren ohne Längenbeschränkung ermittelten komprimierten Datensatzes eines Musterdatensatzes verwendet wird.

5. Verfahren nach einem der vorhergehenden Ansprüche 1 bis 4, bei dem zur Durchführung des LZSS-Verfahrens eine erste Menge erster Steuercodes und eine zweite Menge zweiter Steuercodes verwendet wird.

6. Verfahren nach Anspruch 5, bei dem die erste Menge jeweils einen ersten Steuercode für Literalsequenzen innerhalb eines bestimmten Wertebereichs beinhaltet.

7. Verfahren nach Anspruch 6, bei dem die ersten und die zweiten Steuercodes nach der Auftretentenshäufigkeit der Literalsequenzen bzw. der Häufigkeit des Auftretens von Rückweisen in den betreffenden Wertebereichen nach einem Huffman-Verfahren codiert sind.

8. Verfahren nach einem der vorhergehenden Ansprüche 5, 6 oder 7, bei dem die zweite Menge je einen Steuercode für einen Wertebereich des Zeigers und einen Wertebereich der zu kopierenden Literalsequenz aufweist.

9. Verfahren nach Anspruch 8, wobei die zweiten Steuercodes Huffmanncodiert sind.

10. Verfahren nach Anspruch 8 oder 9, bei dem der Wertebereich des Zeigers byteweise oder in Vielfachen einer Bytelänge aufgeteilt ist.

11. Verfahren nach einem der vorhergehenden Ansprüche 1 bis 10, bei dem die ersten und zweiten Steuercodes und die Literals in zwei voneinander getrennten Abschnitten des Kompressionsergebnisses abgelegt werden und ein dritter Steuercode zur Identifizierung der Trennung dient.

12. Verfahren zur Dekompression einer nach einem Verfahren der vorhergehenden Ansprüche 1 bis 11 komprimierten Zeichenkette mit folgenden Schritten:

- Trennung der Steuercodes von den Literals mittels des dritten Steuercodes,

- Speicherung der Steuercodes in einem ersten Speicherabschnitt,

- Speicherung der Literals in einem zweiten Speicherabschnitt,

- Zugriff auf zu kopierende Literalsequenzen in dem zweiten Speicher und Ablegen der zu kopierenden Literalsequenzen in einem dritten Speicher.

13. Computerprogrammprodukt auf einem computerlesbaren Medium oder einer über ein Computernetzwerk ladbaren Datei mit Programmmitteln zur Durchführung eines Verfahrens nach einem der vorhergehenden Ansprüche 1 bis 12, wenn das Computerprogramm auf einem elektronischem System, vorzugsweise einem Navigationssystem, ausgeführt wird.

14. Elektronisches System, vorzugsweise Navigationssystem, mit Mitteln zur Durchführung der Verfahrensschritte nach einem der vorhergehenden Ansprüche 1 bis 13.

15. Elektronisches System, vorzugsweise Navigationssystem, nach Anspruch 13 mit einem ersten Speicherbereich (10) zum Ablegen von Steuercodes, einem zweiten Speicherbereich (11) zum Ablegen von Literalsequenzen und einem dritten Speicherbereich (12) zum Ablegen von kopierten Literalsequenzen.