Datenkomression

Hallo,

ich suche für folgendes Problem einen passenden Algorithmus:

Daten sollen für einen Microcontroller offline komprimiert werden
und fest in das Rom programmiert werden. Die Daten sollen dann
vom Controller beim Startup in das Ram dekomprimiert werden.

Es geht mir hier nur um den Kompressions- und Dekompressionspart.

Der Algorithmus sollte also bei akzeptabler Kompressionsleistung
besonders die Anforderungen an den Dekompressionsteil
berücksichtigen: Geringstmögliche Codegröße und maximale
Performance. Wird und darf natürlich auf Kosten der Kompresionsrate
gehen, das ist akzeptabel. Bei der Kompressionsroutine selbst gibt
es keine Einschränkungen, hier darf der Code groß und langsam sein.

Wer hat passende Codefragmente oder eine Beschreibung eines
derartigen Algorithmus?

Vielen Dank für die Hilfe.

Michael

Hallo Michael,

ich suche für folgendes Problem einen passenden Algorithmus:

Daten sollen für einen Microcontroller offline komprimiert
werden
und fest in das Rom programmiert werden. Die Daten sollen dann
vom Controller beim Startup in das Ram dekomprimiert werden.

Es geht mir hier nur um den Kompressions- und
Dekompressionspart.

Einerseits solltest du einmal angeben um was für Daten es sich handelt andererseits ist auch noch wichtig was für eine Kompressionsrate du erzielen musst.

MfG Peter(TOO)

Hallo,
spricht irgend etwas gegen eine simple Huffmann-Codierung?
Dabei kommt es natuerlich auf die Daten an…
Grüße,
Moritz

Hallo,
spricht irgend etwas gegen eine simple Huffmann-Codierung?
Dabei kommt es natuerlich auf die Daten an…
Grüße,
Moritz

Dazu müsstest Du wissen, was deine „Symbole“ sind. Huffman-Kodierung erlauubt es dann diese durch andere (Präfixfreie) Symbolkombinationen zu ersetzen. Ein Aufteilung des Strings in zu kodierende sich möglicht häufig wiederholende Symbolketten wäre erst mal zu leisten. Man könnte natürlich Bytes oder Words nehmen, das würde aber längere Widerholungen nicht ausnzuten.

Zur Kompression von einen Bit-Strings wäre wohl das Verfahren,das von zip angewandt wird „klassisch“ (ich weiss allerdings nicht, ob da noch ein Patent drauf ist):
Nehmen wir, wir hätten alles bis zum iten Zeichen kodiert. Dann lesen wir ab i+1
solnge weitere Zeichen, solange der gleiche Substring in den ersten
1 bis i Zeichen irgendwo vorkommt (Stichwort Suffix-Trees). Sobald das nicht mehr geht speichern wir Anfangs und Endposition dieses Substrings und machen mit dem nächsten Zeichen weiter.

MfG

ML

Hallo Peter,

es geht um Tabellen mit z.T. Binärdaten. Zippen läßt sich die Tabelle recht gut.
Die Kompressionsrate ist nicht vorgegeben. Wie gesagt, es kommt nicht
auf die bestmögliche Kompression an. Top-Forderung ist, daß sich der Dekompressionsalgorithmus mit gerigster Codegröße implementieren läßt.

Gruß und vielen Dank für die Antworten

Michael

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

So wird das nix
Hallo Michael,

es geht um Tabellen mit z.T. Binärdaten. Zippen läßt sich die
Tabelle recht gut.
Die Kompressionsrate ist nicht vorgegeben. Wie gesagt, es
kommt nicht
auf die bestmögliche Kompression an. Top-Forderung ist, daß
sich der Dekompressionsalgorithmus mit gerigster Codegröße
implementieren läßt.

Scheinbar hast du von der Problematik keine grosse Ahnung und deshalb frägst du hier. Das ist ja auch der Sinn und Zweck von W-W-W.

Aber Algorithmen gibt es wie Sand am Meer und nicht alle sind für jedes Problem geeignet.
Deshalb stellen wir dir hier Fragen, nicht einfach weil wir nicht mit einer Antwort rausrücken wollen, sondern um die passende Lösung für dein Problem zu finden.

Die funktioniert aber nicht, wenn du die Antworten nicht beantwortest. Hinzu kommt noch, dass ich dich nicht einordnen kann, da du keine Angaben in deiner ViKa machst. Bist du 13 Jahre alt oder ein 25 Jähriger Student ? Wenn ja welche Fachrichtung ? Dies sind Dinge die beim Antworten auch wichtig sind.
Einem 13-Jährigen muss ich etwas auf eine Andere Art erklären, als einem Juristen.

Also ich habe Verstanden, dass du einen µP hast und da irgendwie Platzprobleme hast.
Scheinbar kannst du die Daten einmalig extern komprimieren und dann werden die wohl im ROM abgelegt ?
Irgendwie sollen diese Daten nun zur Laufzeit dekomprimiert werden, ist auch noch klar.
Aber sind das Konfigurations-Parameter, welche nur bei einem Neustart entpackt werden oder musst du immer wieder entpacken ?
Der Platz im ROM ist begrenzt und das RAM auch, soweit klar. Daraus kann man einen vernüftigen, benötigten Komprimierungs-Faktor berechnen. Diese Berechnung kannst aber nur DU vornehmen, da ich keine Angaben zu dem Projekt habe. Je nachdem was da führ ein Wert rauskommt (möglichst viel ist da keine nützliche Angabe) kann man dir Angeben ob das einfach zu realisieren ist oder auch gar nicht !

Aber eben genau mit diesen Werten rückst du nicht raus, und solange kann dir auch nicht richtig geholfen werden !

MfG Peter(TOO)

Hallo,

auch wenn ich mit meiner Antwort meine Chancen reduziere eine
vernünftige Antwort zu bekommen: Vielen Dank für Deine
tiefenpsychologischen Analysen. Ich denke ich
habe in soweit Ahnung von der Materie, als daß ich weiß,
wonach ich suche. Im übrigen gehe davon aus, daß Du mit einem
durchschnittlich begabten Erwachsenen sprichst, der weiß
wie man Informatik schreibt und der auch schon einmal einen
uC gesehen hat.

Falls Du aufhören möchtest Dich zu profilieren und Dich
wieder dem Problem widmen möchtest:

Deine Zusammenfassung ist tatsächlich fast richtig. Die Daten sind
in Tabellen abgelegte Konfiguratuions- und Steuerdaten für einen,
wie gesagt, tabellengesteuerten Algorithmus. Die Daten
sollen einmal, nur beim Startup, dekomprimiert werden. Macht ja
auch keinen Sinn Daten aus einem ROM (werden ja nicht verändert)
mehrfach zur Laufzeit zu dekomprimieren. Bitte gehe davon aus, daß RAM
genügend vorhanden ist, Daten-ROM ist knapp, Programm-ROM noch knapper.
Wenn Du einen Wert für den Wunschkomprimierungsfaktor
brauchst, Faktor 1:1,5 würde schon ausreichen. Da aber die Kompressionsfaktoren
stark datenabhängig sind, wäre mir schon mit dem Angebot zweier (oder mehr)
Alternativen, die ich mit Echtdaten testen könnte, geholfen.

Vielen Dank für Deine Geduld.

Michael

Hallo Michael,

Wenn Du einen Wert für den Wunschkomprimierungsfaktor
brauchst, Faktor 1:1,5 würde schon ausreichen. Da aber die
Kompressionsfaktoren
stark datenabhängig sind, wäre mir schon mit dem Angebot
zweier (oder mehr)
Alternativen, die ich mit Echtdaten testen könnte, geholfen.

1:1,5 ist eigentlich nicht so schwer zu erreichen.

Wenn du grössere Blöcke von z.B. 0x00 hast, könnte schon eine RLE-Codierung reichen:
0x00 0x00 0x00 0x00
wird dann zu
0x00 0x03 // ein 0x00 und noch 3 dranhängen
Damit kannst du Blöcke bis 256 Byte mit 2Byte codieren
Allerdings musst du ein einzelnes 0x00 als 0x00 0x00 ablegen

Sonst kommt noch die normale Huffman-Codierung in Frage:
Da man etwas Zeichnen muss, es zu erklären, nur ein paar Links:
http://www.gym1.at/schulinformatik/aus-fortbildung/f…
http://www.educeth.ch/informatik/interaktiv/kompress…
http://www-i3.informatik.rwth-aachen.de/teaching/02/…
http://www.cs.fhm.edu/~koehler/alg_dat/p3_ws03.pdf
http://www-lehre.informatik.uni-osnabrueck.de/~mm/sk…

Hier noch etwas Source-Code:
http://www.programmersheaven.com/search/LinkDetail.a…
http://www.xcf.berkeley.edu/~ali/K0D/Algorithms/huff/

MfG Peter(TOO)
*derkeineprofilneurosehat*

1 Like

Hallo Peter,

vielen Dank für die Info, werde sicher einiges davon
testen. Krallen sind auch schon wieder eingefahren.

Gruß

Michael

Hallo Michael,

Krallen sind auch schon wieder eingefahren.

*LOL* Kein Problem, ich Übung im Umgang mit Katzen !!

MfG Peter(TOO)