Was wäre eine gute (de) Komprimierungsroutine für dieses Szenario

Question

Ich brauche eine schnelle Dekompression Routine für eingeschränkte Ressource Umgebung optimiert wie eingebettete Systeme auf binäre (Hex-Daten), die Eigenschaften folgende ist:

1. Daten ist 8bit (Byte) orientiert (Datenbus 8 Bit breit).
2. Byte-Wert hat reicht nicht gleichmäßig von 0 - 0xFF, hat aber eine Poisson-Verteilung (Glockenkurve) in jedem Datensatz
.
3. Datensatz in fortgeschrittenen fixiert ist (wird in Flash verbrannt) und jeder Satz ist selten> 1 - 2 MB

Die Kompression kann so viel nehmen, wie Zeit erforderlich, aber Dekompression eines Bytes sollte 23US im schlimmsten Fall mit minimalem Speicherbedarf nehmen, wie es auf einer eingeschränkte Ressourcen Umgebung wie ein eingebettetes System (3 MHz durchgeführt wird - 12MHz Kern, 2k Byte RAM).

Was ist eine gute Dekompression Routine sein würde?

Der Grund Run-Length Encoding scheint zu verschwenderisch - ich kann sofort sehen, dass ein Kopf setion zu den komprimierten Daten hinzugefügt ungenutzt Byte-Werte zu setzen verwendet oft wiederholte Muster darstellen würde phänomenale Leistung

Bei mir, die nur wenige Minuten investiert, doch muss es existieren bereits viel bessere Algorithmen von Menschen, die diese Sachen lieben?

Ich möchte einige "ready to go" haben Beispiele auf einem PC zu testen, so dass ich die Leistung vergleichen kann vis-a-vis ein Grund RLE.

Answer 1

Die beiden Lösungen, die ich verwende, wenn die Leistung die einzige Sorge ist:

• LZO Hat eine GPL-Lizenz.
• liblzf Hat eine BSD-Lizenz.
• miniLZO.tar.gz Dies ist LZO, nur neu verpackt in eine ‚verkleinerte‘ Version, die besser auf die Embedded-Entwicklung geeignet ist.

Beide sind extrem schnell bei der Dekomprimierung. Ich habe festgestellt, dass LZO etwas kleiner komprimierte Daten als liblzf in den meisten Fällen schaffen. Sie müssen Ihre eigene Benchmarks für Geschwindigkeiten tun, aber ich halte sich „im Wesentlichen gleich“ sein. Beide sind Lichtjahre schneller als zlib, obwohl weder Kompressen als auch (wie man erwarten würde).

LZO, insbesondere miniLZO und liblzf sind ausgezeichnet für eingebettete Ziele.

Answer 2

Wenn Sie eine voreingestellte Verteilung von Werten, die die propability jeder Wert bedeutet, wird über alle Datensätze festgelegt, können Sie eine Huffman-Kodierung mit festen Codes erstellen können (der Codebaum hat in den Daten werden nicht eingebettet).

In Abhängigkeit von den Daten, würde ich mit festen Codes oder LZ77 versuchen Huffman (siehe Links von Brian).

Answer 3

Nun, die beiden wichtigsten Algorithmen, die in den Sinn kommen, sind Huffman und LZ .

Der erste im Grunde schafft nur ein Wörterbuch. Wenn Sie das Wörterbuch der Größe ausreichend beschränken, sollte es ziemlich schnell sein ... aber nicht sehr gute Kompression erwarten.

Letzteres funktioniert durch Hinzuverweise auf Teile der Ausgabedatei zu wiederholen. Dies würde wahrscheinlich nehmen sehr wenig Speicher zu laufen, mit der Ausnahme, dass Sie verwenden entweder Datei benötigen würden i / o die Rückverweise oder speichern ein Stück der zuletzt gelesenen Daten im RAM zu lesen.

Ich vermute, LZ ist die beste Wahl, wenn die wiederholten Abschnitte sind in der Regel nahe beieinander sein. Huffman arbeitet mit einem Wörterbuch von oft wiederholten Elementen, wie Sie erwähnt haben.

Answer 4

Da dieses Audio zu sein scheint, würde ich bei jedem Differential PCM oder ADPCM aussehen, oder etwas ähnliches, die es auf 4 Bit / Probe ohne vielen Verlust in der Qualität reduzieren.

Mit der grundlegendsten Differential PCM Implementierung, Sie speichern nur 4 Bit signed Differenz zwischen der aktuellen Probe und einem Akkumulator, und fügen Sie diesen Unterschied zu dem Akkumulator und Umzug in die nächste Probe. Wenn die Differenz es außerhalb von [-8,7], Sie haben den Wert klemmen und es kann mehrere Proben dauern, bis der Akku bis zu fangen. Die Dekodierung erfolgt mit sehr schnell fast kein Gedächtnis, nur jeder Wert in den Akkumulator das Hinzufügen und den Speicher als die nächste Probe ausgibt.

Eine kleine Verbesserung gegenüber Grunde DPCM den Speicher fangen helfen schneller, wenn das Signal lauter wird und höhere Tonlage ist eine Lookup-Tabelle zu verwenden, um die 4-Bit-Werte zu einem größeren nichtlinearen Bereich zu entschlüsseln, wo sie sind immer noch 1 außer in der Nähe von Null, aber in größeren Schritten in Richtung zu den Grenzen erhöhen. Und / oder Sie können einen der Werte behalten einen Multiplikator zu wechseln. Die Entscheidung, wann es zu verwenden, um den Encoder auf. Mit diesen Verbesserungen können Sie entweder eine bessere Qualität erreichen oder mit 3 Bits pro Probe weg statt 4.

Wenn Ihr Gerät ein nicht-linearen μ-law oder A-law ADC hat, können Sie Qualität vergleichbar mit 11-12 Bit mit 8-Bit-Proben erhalten. Oder Sie können es wahrscheinlich tun, um sich in Ihrem Decoder. http://en.wikipedia.org/wiki/M-law_algorithm

Es könnte kostengünstige Chips gibt, die schon alles für Sie tun, je nachdem, was Sie machen. Ich habe nicht in jedem sehe.

Answer 5

Sie sollten verschiedene Komprimierungsalgorithmen versuchen, entweder mit einem Kompressions-Software-Tool mit Kommandozeilenoptionen oder einer Kompressions-Bibliothek, wo Sie können verschiedene Algorithmen ausprobieren. Verwenden Sie typische Daten für Ihre Anwendung. Dann wissen Sie, welcher Algorithmus ist am besten passende für Ihre Bedürfnisse.

Answer 6

Ich habe gebrauchten zlib in Embedded-Systemen für einen Bootloader, den die Anwendung Bild RAM auf Start-up dekomprimiert. Die Lizenz ist schön permissive, kein GPL Unsinn. Es macht einen einzigen malloc Anruf tätigen, aber in meinem Fall habe ich einfach diese mit einem Stummel ersetzt, die einen Zeiger auf einen statischen Block zurückgeführt, und ein entsprechenden free () Stummel. Ich tat dies durch seine Speicherzuordnung Nutzung Überwachung der Größe richtig zu machen. Wenn Ihr System die dynamische Speicherzuordnung unterstützen kann, dann ist es viel einfacher.

http://www.zlib.net/