deflate Algorithmus, Huffman codes

meiru

Kann mir jemand den Sinn der Bit-Umdrehung erklären in der DEFLATE-Kompression? Damit ist doch am Ende der Bitstrom schwerer lesbar, weil ich nichts präfixfreies mehr vorliegen habe, oder sehe ich das falsch?

Beispiel: ... codes 0, 10, 110, 111 werden verdreht geschrieben... also 0, 01, 011, 111... (so sehe ich das zumindest)... dann habe ich was ... z.B. 01011111 ... gibt? 0 -> na ja... muss noch auf 01 prüfen... dann kommt 011 ... könnte 0, 01 und 011 sein... ist das nicht viel mühsamer als es in der korrekten Reihenfolge zu belassen?

also hätten wir 10110111 .... und meine "codetabelle" ist

0000 -> 0
1000 -> 10
1100 -> 110
1110 -> 111

binäre Suche nach 1011 -> gibt 1000 als "Treffer" somit decodier ich 10, lass den Rest bleiben... neue Suche 1101 -> "Treffer" bei 1100 -> decodiert 110, bleibt 111 ... und so weiter... ich finde das viel einfacher... wozu also diesen Dreher?

... der verwirrt mich so dermassen, dass ich die Decodierung einfach nicht hinbekomme.

Worin liegt der Sinn eines präfixfreien Codes, wenn man ihn umdreht und dann genau seine tolle Eigenschaft verliert? ... aber gut, vielleicht habe ich etwas sehr wichtiges und geniales nicht verstanden. ... oder drehen die den Bitstrom gar nicht so um?

Finnegan

@meiru sagte in deflate Algorithmus, Huffman codes:

Worin liegt der Sinn eines präfixfreien Codes, wenn man ihn umdreht und dann genau seine tolle Eigenschaft verliert? ... aber gut, vielleicht habe ich etwas sehr wichtiges und geniales nicht verstanden. ... oder drehen die den Bitstrom gar nicht so um?

Die Eigenschaft geht ja nicht unbedingt verloren. Wenn man die Bits rückwärts liest, sind sie ja immer noch Präfixfrei. Ich kenne die genaue Motivation auch nicht, aber ich kann mir vorstellen, dass man die Codes rückwärts vielleicht etwas simpler "bitweise abschreiten" kann:

code >>= 1;
next_bit = code & 0x1;

Das nächste Bit ist so immer das Niedrigstwertige. Wollte ich "vorwärts" abschreiten, müsste ich eventuell noch einen Zähler für die Bitposition mitführen, die ich als nächstes extrahieren will.... ist aber nur Spekulation - letztendlich ist es IMHO relativ egal, ob die vorwärts oder rückwärts gespeichert sind, solange mein Algorithmus die in der korrekten Reihenfolge abarbeitet. Es gibt ja auch Sprachen, in denen von rechts nach links geschrieben und gelesen wird. Das ist letztendlich auch nur eine Konvention, welche den Inhalt nicht verändert, solange man in der korrekten Richtung liest.

(-: tnhowegnu run tlah tsI .nebierhcs os hcstueD hcua nnak naM

meiru

Irgendwie glaube ich, dass die ursprüngliche Implementierung auf einer big-endian Maschine stattfand. Und dann wollten sie präfixfrei lesen, kamen aber von der falschen Seite. Daher haben sie's umgedreht. (Ist jetzt mal meine Spekulation.) Und... ich habe gesehen, sie drehen eigentlich alles um. Und dann die Codes nochmal. Das scheint also eine Doppelte-Verneinung zu sein.

Na ja, muss ich mal überlegen, wie ich den Bitreader umbaue, damit das einfacher läuft. Ich habe den von einem anderen Programm übernommen, aber das macht keine solchen Dreher. Und alles doppelt drehen... irgendwie sträubt sich da mein Effizienz-Überwacher dagegen.

... irgendwie wird's nie langweilig (oder einfacher... oder weniger mühsam )

Finnegan

@meiru sagte in deflate Algorithmus, Huffman codes:

Irgendwie glaube ich, dass die ursprüngliche Implementierung auf einer big-endian Maschine stattfand.

Endianess von CPUs bezieht sich auf die Byte-Reihenfolge, nicht auf die der Bits.

Und dann wollten sie präfixfrei lesen, kamen aber von der falschen Seite. Daher haben sie's umgedreht. (Ist jetzt mal meine Spekulation.) Und... ich habe gesehen, sie drehen eigentlich alles um. Und dann die Codes nochmal. Das scheint also eine Doppelte-Verneinung zu sein.

Vorwärts, rückwärts und in Knoten Denken muss man ständig als Programmierer/Informatiker. Da muss man durch. Auf jeden Fall immer sorgfältig und systematisch arbeiten, sonst verzweifelt man irgendwann an seinen eigenen Programmen

Na ja, muss ich mal überlegen, wie ich den Bitreader umbaue, damit das einfacher läuft. Ich habe den von einem anderen Programm übernommen, aber das macht keine solchen Dreher. Und alles doppelt drehen... irgendwie sträubt sich da mein Effizienz-Überwacher dagegen.

Ich glaube in diesem speziellen Fall ist es wirklich einerlei - spätestens wenn der Optimizer des Compilers damit fertig ist. Es sind aber oft tatsächlich Effizienzgründe, wenn Algorithmen etwas auf den ersten Blick so unintuitiv arbeiten. Manchmal liegen diese Gründe aber auch schon 40 Jahre zurück und sind heute nicht mehr wirklich relevant - oder nur noch, wenn man es per Hand in Assembler implementiert.

Gerade so ein Standard-Algo wie deflate soll natürlich auch weiterhin kompatibel bleiben, daher behält man das natürlich bei.

... irgendwie wird's nie langweilig (oder einfacher... oder weniger mühsam )

Ne, das sind Standard-Ärgernisse, mit denen man auf jedem Niveau konfrontiert wird. Es ist gut, wenn man sich frühzeitig daran gewöhnt