| Autor |
Beitrag |
Flamefire
 
Beiträge: 1207
Erhaltene Danke: 31
Win 10
Delphi 2009 Pro, C++ (Visual Studio)
|
Verfasst: Do 19.08.10 15:15
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.
Zuletzt bearbeitet von Flamefire am Do 19.08.10 16:25, insgesamt 1-mal bearbeitet
|
|
Ralf Jansen
Beiträge: 4708
Erhaltene Danke: 991
VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
|
Verfasst: Do 19.08.10 15:47
Dein Beschreibung im letzten Absatz hört sich nach Huffman an.
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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).
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Flamefire 
Beiträge: 1207
Erhaltene Danke: 31
Win 10
Delphi 2009 Pro, C++ (Visual Studio)
|
Verfasst: 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: 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
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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).
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Flamefire
Beiträge: 1207
Erhaltene Danke: 31
Win 10
Delphi 2009 Pro, C++ (Visual Studio)
|
Verfasst: 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
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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 ...
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
|
