Huffman abspeichern

Vertex

Hi!
Wie kann man am geeignetsten den Binärbaum(also das Alphabet) unterbringen, so das es am wenigsten speicher verschlingt.

Also zum Beispiel bei "MISSISSIPPI" wird folgendes erstellt:

Alphabet:
I: 00
P: 010
M: 011
S: 1

Kodiert:
M: 011
I: 00
S: 1
S: 1
I: 00
S: 1
S: 1
I: 00
P: 010
P: 010
I: 00

Ich stehe z. Z. voll aufm Schlauch. Eine Idee wäre doch

I: 00
P: 010
M: 011
S: 1

So zu Ordnen, das die Astlänge(sprich Anzahl von Nullen und Einsen) von oben nach unten ist. Die Binärfolgen von Zeichen mit gleicher Astlänge könnte man doch beliebig ausstauschen(natürlich müsste man dies auch beim Kodieren der Zeichen berücksichtigen) ?oder

So könnte man die Zeichen mit selber Astlänge nochmals dem ASCII-Codes nach Ordnen. Am besten so, das das erste Zeichen dann bei z. B. eine Binärlänge von 4 Bit bei 0000 beginnt, das zweite 0001, das dritte 0010, das vierte 0011 usw. bekommt.

Der Astlänge nach sortiert:

S: 1
I: 00
P: 010
M: 011

P und M haben die selbe Astlänge, man kann hier bei P an beginnen zu zählen:

S: 1
I: 00
P: 000
M: 001

Die große Frage ist, verlieren dann die Zeichen ihre Eindeutigkeit die beim Dekodieren wichtig ist?

Darf man das bei 000 beginnen zu Zählen nicht durchführen?

mfg olli

Korbinian

naja, P = 000 klappt ja schon mal nicht, weils dann nicht mehr präfixfrei ist. du wirst nicht drumrum kommen, die schlüsseltabelle unkomprimiert zu speichern, und zwar jeweils wortlänge und wort"inhalt" (also bei 010 z.b. 3 und 2)

volkard

Vertex schrieb:

So zu Ordnen, das die Astlänge(sprich Anzahl von Nullen und Einsen) von oben nach unten ist. Die Binärfolgen von Zeichen mit gleicher Astlänge könnte man doch beliebig ausstauschen(natürlich müsste man dies auch beim Kodieren der Zeichen berücksichtigen) ?oder

jo, kann man.

So könnte man die Zeichen mit selber Astlänge nochmals dem ASCII-Codes nach Ordnen. Am besten so, das das erste Zeichen dann bei z. B. eine Binärlänge von 4 Bit bei 0000 beginnt, das zweite 0001, das dritte 0010, das vierte 0011 usw. bekommt.

jo, mach das. ich bin zu dem gleichen ergebnis gekommen.

Der Astlänge nach sortiert:

S: 1
I: 00
P: 010
M: 011

P und M haben die selbe Astlänge, man kann hier bei P an beginnen zu zählen:

S: 1
I: 00
P: 000
M: 001

ich würde anders sortieren:

S: 1
I: 00
P: 000
M: 001

und da den code auch ändern darf, indem ich an alen codewörter die gleiche stelle invertiere, mache ich draus

S: 0
I: 10
P: 100
M: 101

und

S: 0
I: 10
M: 110
P: 111

nu ist der baum sortiert nach wirtlängen und innerhalb der wortlängen auch alphabetisch.
als darstellung reicht "S,I,MP" aber wichtiger finde ich die andere sache: es reicht, die wortlängen zu wissen. bei einer dicken datei, wo jedes zeichen mal vorkommt, brauchst nur noch die wortlängen abzuspeichern. die rehenfolge ist dann definiert. und die wortlängen kann man vermutlich auch nochmal gut packen. zum beispiel
0: 0000
1: 0001
2: 0010
...
14: 1110
15: 1111 00000000
16: 1111 00000001
17: 1111 00000010
ka, ob das sinn ergibt, so zu packen. wäre halt einfach.

Die große Frage ist, verlieren dann die Zeichen ihre Eindeutigkeit die beim Dekodieren wichtig ist?

ich sehe kein problem. wenigstens nicht bei meinem code.

Darf man das bei 000 beginnen zu Zählen nicht durchführen?

P und M haben die selbe Astlänge, man kann hier bei P an beginnen zu zählen:

S: 1
I: 00
P: 000
M: 001

wenn du den baum so sortiert hast, daß zuerst kurze wörter kommen und bei gleich langen wörtern die lexikographisch kleineren, und du dann mir die liste S,i,PM gibst, dann hab ich doch folgende garantien:
S ist ...
keine ahnung. kann 0 oder 1 sein.
ich nehm doch meinen code.

S: 0
I: 10
M: 110
P: 111
und du schickst S,I,MP

ich erzeuge alle möglichen wörter der länge 1:
freie wörter: 0 1
S hat länge 1. die wörter 0 und 1 sind noch frei, ich nehme das kleinere. S: 0
freie wörter: 1
dann lese ich ein "," und gehe deswegen zur wortlänge 2. dazu verlängere ich jedes freie wort mit 0 und 1
freie wörter: 10 11
I weise ich das nächste freie wort zu. I: 01
freie wörter: 11
dann gehe ich zu wortlänge 3
freie wörter: 110 111
und weise M die 110 zu und weise P die 111 zu.

Vertex

Hi!
Danke für die Antworten!

volkard: Hmm wie Korbinian schon sagte, kann man leider doch nicht die Codes beliebig austauschen. (Auch wenn sie gleicher Länge sind, und nur einmal vorkommen)

Eben bei:
S: 1
I: 00
P: 000
M: 001

Es geht praktisch ein Ast zum I und am I selber hängen P und M. Somit könnte man das "M" = 001 leider auch als "IS" = 00 1 interpretieren.

volkard schrieb:

ich würde anders sortieren:
S: 1
I: 00
P: 000
M: 001
und da den code auch ändern darf, indem ich an alen codewörter die gleiche stelle invertiere, mache ich draus
S: 0
I: 10
P: 100
M: 101
und
S: 0
I: 10
M: 110
P: 111
nu ist der baum sortiert nach wirtlängen und innerhalb der wortlängen auch alphabetisch.

Ja, der letzte Baum ist eindeutig. Jedoch verstehe ich nicht, wo du festlegst, was invertiert werden darf.

Was sich sehr gut anhört:

volkard schrieb:

ber wichtiger finde ich die andere sache: es reicht, die wortlängen zu wissen. bei einer dicken datei, wo jedes zeichen mal vorkommt, brauchst nur noch die wortlängen abzuspeichern. die rehenfolge ist dann definiert. und die wortlängen kann man vermutlich auch nochmal gut packen

Das man halt eine Art "Wo ist was frei?"-Suche macht, ist eine gute Idee, wozu ich mir nochmal Gedanken zur Umsetzung machen muss.

Müsste es nochmal ausprobieren, aber wenn der Binärbaum IMMER Perfekt ist, dürfte doch ein Ast niemals länger als 8 Bit sein. Ein Ast mit der Länge 0 gibt es halt nicht, deswegen reichen 3 Bit(2^3 = 8 Kombinationen aus Nullen und Einsen) völlig aus, um die Länge der Zeichen zu speichern.

Und da die Zeichen noch nach ihrer Länge sortiert sind, kann man event. auch nur die Differenz in weniger Bit unterbringen.

Also nochmals vielen Dank!

mfg olli

Vielleicht bringt es dir auch was, den RFC von Deflate anzusehen. Weiß jetzt aber nicht, ob das vielleicht nicht zu kompliziert wird, weil da nicht nur die Huffman-Kodierung verwendet wird. Aber für ne richtig geile Kompression reicht das alleine eben auch noch nicht.
Ich habe den Thread erst so aufgefasst, als würde es nur um Huffman gehen, aber jetzt scheint ihr ja schon mit jedem Bit zu geizen, daher ist es evtl. ratsam, noch ein bisschen weiter zu schauen.

volkard

Vertex schrieb:

volkard: Hmm wie Korbinian schon sagte, kann man leider doch nicht die Codes beliebig austauschen. (Auch wenn sie gleicher Länge sind, und nur einmal vorkommen)

Eben bei:
S: 1
I: 00
P: 000
M: 001

Es geht praktisch ein Ast zum I und am I selber hängen P und M. Somit könnte man das "M" = 001 leider auch als "IS" = 00 1 interpretieren.

ok. wie vertauschen gar nix.

I: 00
P: 010
M: 011
S: 1

ich sortiere nach anzahl und bei gleicher anzahl nach alphabet.

S: 1
I: 00
M: 011
P: 010

wenn ich jetzt nur das erste bit angucke, sehe ich, daß die wörter falschrum sortiert sind. deswegen invertiere ich überall das erste bit.

S: 0
I: 10
M: 111
P: 110

das zweite bit ist gut.

das dritte wird auch invertiert.

S: 0
I: 10
M: 110
P: 111

aber geht das immer?

mal testen

A: 110
B: 111
C: 010
011
E: 100
F: 101
G: 001
H: 000

naja, das erste mal invertieren.

A: 010
B: 011
C: 110
111
E: 000
F: 001
G: 101
H: 100

nee, nur invertieren kann nicht gehen. es muss auch getauscht werden.

wie kamst du nochmal durch tauschen auf einen uneindeutigen code? das kann ich gar nicht verstehen, daß man nicht wild wörter der gleichen länge tauschen darf.

Vertex

Jup, die Sache mit dem freien Platz hat sich als funktionstüchtig herausgestellt.

wie kamst du nochmal durch tauschen auf einen uneindeutigen code? das kann ich gar nicht verstehen, daß man nicht wild wörter der gleichen länge tauschen darf.

In dem Sinne hatte ich nicht den Code zweier Zeichen getauscht, sondern selber einen generiert.

Was ich mich jetzt Frage:
Wenn es ein Zeichen mit der kleinsten Astlänge n und ein Zeichen mit der größten Astlänge m gibt, muss doch zwischen n und m alle Längen vorhanden sein. Also meinetwegn n = 2 und m = 6, dann kann man doch davon ausgehen, dass es Zeichen mit der Astlänge 3, 4 und 5 mind. einmal gibt. ?oder

Das wäre somit eine Fehlerprüfung. Event. sogar eine ungenutzte Information.

Weiterhin kann man doch auch anhand des Dekodierten Textes prüfen, ob die Häufigkeit der Zeichen korrekt war. Ist event. auch noch eine ungenutzte Information.

Zumindest bräuchte man dann in WinRAR oder so keine CRC Fehlererkennung

Jedenfalls wenn das mit m und n so hinhaut, dann bräuchte man wirklich immer nur das Zeichen+Astlänge abzuspeichern, und niemals den Code selber.

mfg olli

Brutus

Hmm, meinst du wirklich, dass Zeichenhäufigkeiten überprüfen sicherer ist als CRC?