Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Info zu Komprimierung (Zip?)
Flamefire - Do 19.08.10 15:15
Titel: Info zu Komprimierung (Zip?)
Ich habe einen Komprimierungsalgorhytmus in einem Programm, von dem ich gerne wüsste, welcher es ist.
Ich hatte erst auf etwas wie zip/ZLib getippt, nur fehlen mir infos dazu.
Woher kann ich möglichst einfache Erklärungen zu den ZIP-Algos finden (gibt da ja auch mehrere), so dass ich das vergleichen kann.
Wichtig wäre insbesondere, wie der komprimierte Block aussieht und wie der dann dekomprimiert wird.
Dekomprimierung: Zur Zeit weiß ich, dass der Block mit 256 Bytes beginnt, die eine Art Tabelle bilden. Genauer: 512 mal 1 Byte
Es wird also wirklich jedes Byte für sich behandelt und in diverse Tabellen kopiert.
Dann wird daraus der Reihe nach das kleinste und 2.kleinste gesucht und vermutlich sortiert.
Rest steht noch in Nachforschung.
BenBE - Do 19.08.10 16:18
Das ist eindeutig n Huffman; wenn ich deine Beschreibung genau lese, würd ich sogar sagen, eine der statischen Varianten.
Bei Huffman gibt's noch eine adaptive Version, die ist von der Art der Speicherung aber etwas anders realisiert. Zusätzlich gibt's noch die Entropie-Kodierung, die sich auf ne Adaptive Huffman-Kodierung zurückführen lässt (ganz grob gesagt).
Flamefire - Do 19.08.10 16:27
Könnte möglich sein. Das würde die 256er Tabelle erklären. Also vermutlich eine Byte-weise kodierung.
Eine solche tabelle sieht so aus:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
| 8C 01 00 00 01 01 01 01 01 01 01 01 01 01 01 01
01 01 05 01 01 01 01 01 05 01 01 01 01 01 01 01
10 01 01 01 01 01 01 01 01 01 01 01 01 02 01 01
01 01 01 01 01 01 01 01 01 01 03 00 01 00 00 00
01 02 02 01 01 01 01 01 01 02 01 01 01 01 01 01
01 01 01 01 01 01 01 01 01 00 01 00 01 00 00 00
01 06 01 02 02 08 01 02 02 05 01 01 04 02 05 04
02 01 06 03 04 03 01 01 01 01 01 00 01 00 00 11
09 00 00 00 01 00 00 00 01 00 00 00 01 00 00 00
01 00 00 00 01 00 00 00 01 00 00 00 01 00 00 00
01 00 00 00 01 00 00 00 01 00 00 00 01 00 00 00
01 00 00 00 01 00 00 00 01 00 00 00 01 00 00 00
01 01 01 01 01 00 00 01 01 00 01 01 01 01 01 01
01 01 01 01 01 01 00 00 01 00 00 00 01 01 00 01
02 01 01 01 01 02 01 01 01 01 01 01 01 02 01 01
0F 02 02 01 01 01 01 01 01 01 01 01 01 01 01 01 |
Aber wie soll man die bitte als Huffman lesen?
Edit: klingt auch ncith schlecht:
http://www.binaryessence.de/dct/de000141.htm
"Die ersten 256 Einträge werden mit den Zeichen vorbesetzt"
Edit2: Könnte tatsächlich stimmen. Zu lesen als:
00: Häufigkeit 8C
01: Häufigkeit 1
usw.
Dann "Baum" aufstellen, in dem die mit den wenigsten Vorkommen zusammengeführt werden. Und dann wird im kodierten Text nach einsen gesucht.
Ok geht klar. Damit ist was anzufangen. Werde mal gucken, ob das rauskommt, was kommen soll
BenBE - Do 19.08.10 23:00
LZW fällt laut deiner Beschreibung (und insbesondere wegen dem Hexdump) raus, weil LZW eine Stream-Kodierung ist, die keine Initialisierung benötigt (Sender und Empfänger synchronisieren sich anhand des Algorithmus, bzw. seiner bekannten Fehler).
AH und EntCod fallen auch raus, weil die auch keine Initialisierung benötigen (EntCod nur, wenn man die Starthäufigkeiten vorgibt, also ungleich Gleichverteilung).
Flamefire - Do 19.08.10 23:49
Jo, es ist eine Huffman Codierung.
Hab gerade geguckt, wie es weiter geht.
Stimmt so ;-)
Ok, will jz keinen neuen Thread dazu aufmachen, will den Baum als flaches Array haben
Also Array of (häufigkeit,parent,left,right)
Die ersten 256 Einträge sind die Blätter.
Frage ist jz: Wenn ich das Array statisch machen will, wie groß muss es werden? Oder anders, wieviele Knoten kann ein Binärbaum mit 256 Blättern haben?
Doch eigendlich nur 255 und zwar genau 255, oder?
BenBE - Fr 20.08.10 01:47
Hab nen adaptiven Huffman mal mit Z80-ASM implementiert.
Der Speicherbedarf ist 2^(n+1)-1 Elemente bei 2^N verschiedenen Werten, wenn man Blätter als Knoten betrachtet und nur den Parent speichert. Man kann dann zeigen, dass man in diesem Fall mit N+1 Bit je Knoten auskommt, wenn man den Parent und die Links/rechts-Info geschickt speichert.
In meinem Fall damals hatte ich in Z80-ASM nen Encoder für adaptives Huffman gebaut; da ist der RAM-Bedarf ETWAS höher (weil man nen Zähler brauch. Die Parent-Info ob links/rechts ergibt sich aber aus dem Zähler und daher reichen dort N Bit + Zähler. Wobei ich nie den zugehörigen Dekoder gebaut hab, weil der RAM auf dem TI einfach extrem doof verteilt war ...
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!