Kurzgefasst: Texte für Mikrocontroller – Speicher sparen durch Kompression

Viele Mikrocontroller-Projekte geben Menü- und Hilfetexte, Fehler- oder Diagnosemeldungen über eine grafische Benutzer- oder eine Diagnoseschnittstelle aus. Ein großer Textumfang bedeutet allerdings einen großen Speicherplatzbedarf. Mit einer geeigneten Kompression lässt sich aber so viel Text im Mikrocontrollerspeicher unterbringen, dass externe Datenspeicher meist vermieden werden können. Dieser Artikel zeigt eine mögliche Lösung durch Wörterbuchkompression.
 
Die Voraussetzung jeder erfolgreichen Kompression sind in den zu komprimierenden Daten enthaltene Redundanzen. Bei Texten entstehen Redundanzen durch Zeichen, die häufiger vorkommen als andere Zeichen, oder Zeichenfolgen, die mehrfach auftreten. So könnte man sich einer Entropiekodierung, zum Beispiel der Huffman-Kodierung bedienen, um in einem Text häufiger auftretende Buchstaben mit kürzeren Bitfolgen zu kodieren als weniger häufige Buchstaben. Oder man könnte sich einem Substitutionsverfahren wie dem LZ77-Verfahren, auch Wörterbuchkompression genannt, bedienen, um sich wiederholende Zeichenfolgen in einem Wörterbuch abzuspeichern. Im Text wird die Zeichenfolge dann durch einen Verweis auf den Wörterbucheintrag ersetzt. Beim LZ77-Verfahren ist dafür interessanterweise nicht einmal das Abspeichern eines separaten Wörterbuchs in den komprimierten Daten nötig. Dort bildet ein Ausschnitt aus den dekomprimierten Daten ein Wörterbuch, das mit fortschreitender Dekompression langsam gefüllt und beim Erreichen der maximalen Wörterbuchgröße über ein Sliding-Window-Verfahren verschoben wird. Kompressionsprogramme wie 7z oder Zip verwenden eine Kombination beider Verfahren, Wörterbuchkompression mit nachfolgender Entropiekodierung, um eine bessere Kompression zu erreichen. Für kurze Texte ist die mögliche Einsparung bei beiden Verfahren jedoch gering. Außerdem ist es nicht möglich, einzelne Sätze aus einem komprimierten Text zu extrahieren, ohne den gesamten Text zu dekomprimieren.

Analyse des zu komprimierenden Texts

Wenn man sich die Texte der konkreten Anwendung in Listing 1 anschaut, zeigt sich, dass eine Wörterbuchkompression, die Redundanzen ganzer Wörter und Wortfolgen ausnutzt, erfolgversprechend ist.
 
Das in jedem Text häufig auftretende Leerzeichen wird als Worttrenner verwendet. Für das Leerzeichen erzeugt der Komprimierer entweder einen eigenen Wörterbucheintrag oder der Dekomprimierer fügt die Leerzeichen automatisch zwischen jedem Wort wieder ein. Letzteres funktioniert nur dann sehr einfach, wenn es keine Sonderbehandlungen für Sonderzeichen gibt, die ohne Leerzeichen vor oder hinter einem Wort stehen, also wenn zum Beispiel (Gauge) ein Wörterbucheintrag ist und nicht durch die drei Einträge (, Gauge und ) dargestellt wird.
 

• Der gesamte Text liegt in einem oder mehreren C-String-Arrays vor ⇒ Einzelne Texte können gezielt über Array-Indizes angesprochen werden, was bei den komprimierten Texten ebenfalls möglich sein muss.
• Der Text enthält viele Wörter oder Wortfolgen, die häufig vorkommen ⇒ Redundanzen sind die Voraussetzung jeder Kompression.
• Der Text liegt in englischer Sprache vor ⇒ Der Text verwendet nur 7-Bit-ASCII-Codes (0...127). Die Codes ≥128 bleiben frei. Das vereinfacht später den Schritt 5 des vorgestellten Verfahrens.
• Die meisten Wörter im Text beginnen mit einem Großbuchstaben ⇒ Engine und engine wären zwei verschiedene Einträge im Wörterbuch. Die Kompression kann verbessert werden, wenn alle Wörter mit Großbuchstaben beginnen. Aus Gründen der Lesbarkeit sollten Präpositionen und Artikel klein geschrieben werden.
• Der Text enthält wenige Sonderzeichen, zum Beispiel (  )  #  /  -   , ⇒ Bei der Generierung des Wörterbuchs entstehen deshalb nur wenige Einträge wie (Gauge), die sich von einem möglichen zweiten Eintrag Gauge unterscheiden.
• Der längste Text des gesamten Texts ist mit Stringendezeichen 57 Zeichen lang ⇒ Der Dekomprimierer benötigt einen Puffer von mindestens 57 Bytes RAM.

Wörterbuchkompression

Schritt 1: Erzeugen des Wörterbuchs
Dieser Schritt zerlegt den zu komprimierenden Text in seine einzelnen Wörter. Als Trennzeichen wird das Leerzeichen verwendet, was später vom Dekomprimierer automatisch wieder eingefügt wird. Nebenbei wird die Häufigkeit und der Speicherplatzbedarf (Stringlänge plus Stringendezeichen) jedes Wortes berechnet. Am Ende wird das erzeugte Wörterbuch nach absteigenden Häufigkeiten sortiert. Bei gleicher Häufigkeit entscheidet die größere Länge. Listing 2 zeigt bereits das im Schritt 2 optimierte Wörterbuch. Häufigkeit und Länge sind dort als Kommentar angegeben.
 
 
Schritt 2: Optimierung des Wörterbuchs
Falls im Text Wörter gleicher Häufigkeit vorkommen, die für jedes Auftreten benachbart sind, zum Beispiel Exhaust und Gas, können diese Wörterbucheinträge zu einem Eintrag Exhaust Gas zusammengefasst werden. Dazu muss im neuen Eintrag zwar das Leerzeichen zwischen den Wörtern wieder eingefügt werden, aber dafür entfällt eines von zwei Stringendezeichen.
Da nach der Zusammenfassung zweier Einträge der zusammengefasste Eintrag wieder die obigen Bedingungen mit einem weiteren benachbarten Eintrag erfüllen kann, können bei wiederholter Anwendung Einträge entstehen, die mehr als zwei Wörter enthalten.
Da jeder Eintrag im Wörterbuch (C-String-Array) zusätzlich zum Speicherplatz für den String auch Speicher für einen Pointer auf diesen String erfordert, wird pro zusammengefasstem Eintrag ein Pointer eingespart. Die tatsächliche Einsparung hängt vom Speicherplatzbedarf eines Pointers auf dem Zielsystem ab. Zusätzlich wird das im Schritt 3 erzeugte Array dictIndex[] um die Häufigkeit des zusammengefassten Eintrags * sizeof(dict_index_t) kleiner.
 
Schritt 3: Kodierung des Originaltexts
Wenn das Wörterbuch erstellt ist, kann der Text mit Hilfe der Array-Indizes der Wörterbucheinträge kodiert werden.
Hier eine beispielhafte Kodierung des ersten Texts aus Listing 1:
 
text[0] = Fuel System 1 Status

• Fuel = Wörterbucheintrag dictionary[5]. Ersetze Fuel durch Index 5.
• System = Wörterbucheintrag dictionary[45]. Ersetze System durch Index 45.
• 1 = Wörterbucheintrag dictionary[4]. Ersetze 1 durch Index 4 (keine Kompression).
• Status = Wörterbucheintrag dictionary[30]. Ersetze Status durch Index 30.

 
Die Leerzeichen entfallen. Dann ergibt sich daraus folgendes Array:
   
Da die Anzahl der Indizes pro komprimiertem Text variabel ist, wird eine zweite Tabelle benötigt, die für jeden Text aus Listing 1 einen Verweis auf seinen ersten Index enthält. So kann jeder Text unabhängig von vorhergehenden Texten dekomprimiert werden.
   
Der letzte Eintrag im Array startIndex[] führt dazu, dass der Dekomprimierer für alle Texte, auch den letzten, die Anzahl der Indizes einfach berechnen kann. Die Anzahl der Indizes für text[n] ist startIndex[n+1] – startIndex[n].
 
Schritt 4: Erweiterung des Wörterbuchs um Indexpaare
Dieser Schritt komprimiert häufiger auftretende Wortpaare (Indexpaare) und Wortfolgen (Indexfolgen) effektiver. Zuerst wird die am häufigsten auftretende Indexfolge bestehend aus zwei Indizes gesucht. Diese wird am bisherigen Ende des Wörterbuchs als neuer logischer Eintrag eingetragen. Tatsächlich wird bei der Implementierung in Listing 3 ein neues zweidimensionales Array pair[][2] angelegt und um einen aus zwei Indizes bestehenden Eintrag erweitert.
 

Wenn der bisher größte Index des Wörterbuchs 126 war, so nimmt das erste Indexpaar in pair[0] den logischen Index 127 an. Dann müssen im Array dictIndex[] alle Indexpaare aus pair[0][0] und pair[0][1] (in Listing 3 Index 2 und Index 0) durch einen einzigen Index 127 ersetzt werden. Das Array dictIndex[] wird also um die Häufigkeit des Indexpaars kleiner, während im Array pair[][2] genau ein Eintrag, der dieses Indexpaar enthält, dazu kommt. Da dieser Schritt so oft auf das Array dictIndex[] angewendet wird, wie Paare mit einer minimalen Auftrittshäufigkeit gefunden werden, werden nicht nur zwei benachbarte Wörter, sondern auch längere Wortfolgen gefunden. Ein Indexpaar kann dann wieder Indizes von einem oder zwei Indexpaaren enthalten (Eintrag 3, Index 67 oder Index 68 in Listing 3).
Die Auftrittshäufigkeit eines Paares muss folgende Bedingung erfüllen, damit tatsächlich eine Kompression erreicht wird und ein neues Paar im Array pair[][2] eingetragen wird: Häufigkeit Indexpaar > 2 * sizeof(dict_index_t).
 
Schritt 5: Einführung von ASCII-Indizes
In der tatsächlichen Implementierung folgt noch ein weiterer Schritt, der aufgrund seiner vielen Sonderfälle und Bedingungen hier nicht umfassend dargestellt werden kann. Durch die Einführung von ASCII-Indizes für Wörter im Wörterbuch, die mit Häufigkeit 1 auftreten oder für kurze Wörter mit geringer Häufigkeit, die nicht in pair[][2] verwendet werden, lassen sich Wörter, die nicht zur Komprimierung beitragen, aus dem Wörterbuch entfernen. Diese Wörter werden direkt mit den ASCII-Codes ihrer Zeichen im Array dictIndex[] eingetragen und im Wörterbuch entfernt. Zuvor müssen alle anderen Indizes entsprechend zu Werten ungleich der Werte der ASCII-Codes verschoben worden sein, bei 7-Bit-ASCII-Codes zum Beispiel zu Werten ≥ 128. Details dazu finden sich im veröffentlichten Sourcecode des Komprimierers und Dekomprimierers beim Arduino-Projekt.

Nachbetrachtung

Bei der Ausführung der einzelnen Schritte zeigt sich eine generelle Problematik der Kompression. Der Speicherplatzbedarf für einen einzelnen Index sizeof(dict_index_t) ist vor der Kompression noch nicht bekannt, wird aber im Verfahren benötigt, um bei niedrigen Auftrittshäufigkeiten und kurzen Wörtern entscheiden zu können, ob überhaupt ein Wörterbucheintrag oder Indexpaar erzeugt werden soll. Im vorgestellten Fall der Textkompression der PID-Texte sind 8-Bit-Indizes ausreichend, was das Verfahren und die Dekompression vereinfacht. Die Textkompression der Fehlertexte kommt nicht mehr mit nur 256 8-Bit-Indizes aus. Dort wird mit einer Entropiekodierung der Indizes, die die häufigsten Wörter mit 8-Bit-Indizes und alle anderen Wörter mit 16-Bit-Indizes kodiert, der Vergrößerung des dictIndex[]-Arrays entgegengewirkt.
Wenn die mit Schritt 3 oder Schritt 4 erzielte Textkompression ausreichend ist, kann das Verfahren vorzeitig beendet werden. Die Dekomprimierroutine benötigt dann weniger Speicherplatz und weist eine kürzere Laufzeit auf, als wenn man weitere Schritte unternehmen würde.

Wie alles begann...

Der Auslöser für die Entwicklung einer verlustlosen Textkompression waren meine Elektor OBD2-Fahrzeugdiagnose-Projekte [OBD2-Analyser NG] [OBD2 for Raspberry Pi] [OBD2 for Arduino]. Wie bei professionellen Diagnosetestern sollten für den Benutzer mehrere tausend Beschreibungen für Diagnosefehlercodes (Diagnostic Trouble Codes, DTC) bereitgestellt werden. Der Gesamtumfang dieser Texte beträgt etwa 211 KB, der durch das hier vorgestellte Kompressionsverfahren auf rund 35 KB reduziert werden konnte. Dadurch passen die Texte in den im Projekt [1] verwendeten 8-Bit-AVR-Mikrocontroller AT90CAN128 mit 128 KB Flash-Speicher.
Im Arduino Projekt [3] sollte auch der kleine Arduino Uno R3 und der Elektor Uno R4 mit nur 32 KB Flash-Speicher unterstützt werden. Natürlich ist dieser Speicherplatz auch für die komprimierten Fehlertexte zu klein, aber allein die etwa 7 KB umfassenden Beschreibungen für die bisher in den Projekten unterstützten OBD2-Parameter-Identifier (PID), meistens Beschreibungen der Sensordaten, konnten auf rund 2 KB komprimiert werden. Das von mir entwickelte Kompressionsverfahren soll am Beispiel der aktuell 190 kurzen PID-Texte in Listing 1 vorgestellt werden.
Für einen 8-bit-AVR-Mikrocontroller AT90CAN128 und den avr-gcc-Compiler 4.9.2 (Optimierung -Os eingeschaltet) wurden die folgenden Werte für den Speicherplatzbedarf der Dekomprimierroutine ermittelt (die restlichen Werte sind berechnet):
 

	Ursprungstext [Bytes]	Komprimierter Text [Bytes]	Dekomprimierer [Bytes]	RAM-Puffer für Dekompression [Bytes]
DTC-Texte	216311	35340	566	106
PID-Texte	7273	1820	314	57

 
(180278​)

---

➔ Wollen Sie weitere ElektorLabs-Artikel lesen? Jetzt Elektor-Mitglied werden!

---