Codereview meines Huffman-Komprimierers

mortified_penguin

Hallo,

ich habe einen Huffman-Komprimierer geschrieben und würde mich über Feedback freuen, insbesondere was das Design der Klassen, aber auch den Code, angeht.

main.cpp
http://pastebin.com/pbZDjVy1

code.hpp, code.cpp ("Hauptklassen" für das Komprimieren / Dekomprimieren)
http://pastebin.com/XR5LC5w4
http://pastebin.com/60UXndGF

tree.hpp, tree.cpp (Huffman-Baum)
http://pastebin.com/QP2B8k8V
http://pastebin.com/7Su0feKY

node.hpp, node.cpp (Datenstruktur für Zweige / Blätter des Baums)
http://pastebin.com/RZHG7dYg
http://pastebin.com/i4rxNdYq

komplette Übersicht: http://pastebin.com/u/mortified_penguin

Also wenn jemand Langeweile hat, kann er es sich ja mal anschauen

Athar

Ich habe mir nicht alles im Detail angesehen, aber wenn du versuchst, eine auf einem Little-Endian-System erzeugte Datei auf einem Big-Endian-System zu lesen (oder umgekehrt), wird das mächtig schief gehen.

Den Baum kannst du sicher weitaus platzsparender ablegen (im Moment speicherst du nur die Häufigkeiten, die dich aber außer für die Konstruktion des Baumes gar nicht interessieren).

Schön wäre es auch, wenn man nicht auf den stark begrenzten Wertebereich von char festgelegt wäre, schließlich erlaubt die Huffman-Codierung ein Alphabet beliebiger Größe (z.B. 257) anstatt auf Zweierpotenzen fixiert zu sein.

Desweiteren ist bei der Benennung der Parameter (infile_) nicht gleich klar, ob der Dateiinhalt oder ein Dateiname gemeint ist. Ich hätte ersteres erwartet bis ich den fstream unter protected gesehen habe. Nicht alle Daten liegen immer schon in Dateien verpackt, es würde also Sinn machen, gleich einen Stream zu übergeben - dann kann ich mir selbst aussuchen, ob es ein stringstream, fstream oder sonstiges sein soll.

Edit: ich sehe gerade, du bastelst beim Komprimieren erst einmal einen String zusammen - der Performanz ist das nicht unbedingt zuträglich. Das Bitgeshifte später kannst du im Prinzip auch gleich machen.

SeppJ

In der Reihenfolge, wie es mir auffällt:

Die Designgrundidee gefällt mir nicht. Wieso sind der Kompressor und Dekompressor beide von einer gemeinsamen Basisklasse abgeleitet? Hat das irgendeine Anwendungsrelevanz? Das sieht eher so aus, als sollten beide Klasse einen Member von der Klasse haben, die den Stream und die map verwaltet.
Mir gefällt auch die Designidee nicht, dass die Kompressoren auf Dateien arbeiten und die Dateiverwaltung auch noch selber durchführen. Hätte man hier nicht einen allgemeinen Stream nehmen können? Oder wenigstens einen String? So wie es jetzt ist, ist der Benutzer dir total ausgeliefert, dass du die Dateien richtig öffnest (das Gefummel mit dem BINARY/PLAIN macht diese Problematik deutlich. Was wäre beispielsweise, wenn er an eine Datei etwas anhängen will?) und kann auch niemals einen eigenen Streamtyp benutzen.
Womit wir beim Stichwort sind: Dies ist doch der optimale Anwendungsfall, um einen Stream zu spezialisieren. Guck mal, wie das hier gemacht wurde:
http://www.cs.unc.edu/Research/compgeom/gzstream/
Das ist, wie ich finde, ein praktisch perfektes Design für diese Anwendung .
Unterscheidet sich dein tree irgendwie von einem set? Warum nimmst du kein set?
Ja, er unterscheidet sich von einem set, da er falsch ist. Wie fast immer, wenn Anfänger manuelle Speicherverwaltung probieren . Du hast mindestens die Regel der großen Drei nicht beachtet. Das heißt, dein Beispielprogramm steht auf total wackeligen Beinen und wird bei der kleinsten Änderung oder Herausforderung versagen.
Nochmal Thema Dateien richtig öffnen: Du wandelst den Dateinamen zu Kleinbuchstaben um . Kein Kommentar. Ok, doch ein Kommentar: Es gibt mehr als NTFS und FAT.
In der main bindest du cstdio ein, aus der du nichts nutzt.
in der main nutzt du Makros aus cstdlib, welche du nicht einbindest.
Nochmal Vererbung: Ein branch ist ein node? Ein leaf ist ein node? Das klingt nach der Wursttheke, die ein Supermarkt ist.
Die vielen reinterpret_cast und dynamic_cast machen mir Sorgen. reinterpret_cast bedeutet, du hast im Design die falschen Datentypen gewählt. dynamic_cast heißt, das Design ist von grundauf total verpfuscht. Letzteres wird mit der komischen Vererbung zusammenhängen.
for (stream = infile.get(); infile.peek() != EOF; stream = infile.get())
Was ist das denn für eine komische Schleifenkonstruktion? peek? Spricht irgendwas dagegen, die Daten auch "normal" einzulesen (z.B. mittels while(leseaktion) ... )? Dann würde dies auch mit allen Arten von Stream funktionieren und verwirrt andere Programmierer nicht, die sich fragen, was dies soll.
Was ist 8? Was ist 0x80? Antwort: Magic numbers!
(Das 8 kann ich mir ja noch herleiten, aber ich habe selbst nach langem Nachdenken keine Ahnung, was das 0x80 soll)
Addier doch einfach einen char zu deinen Strings, anstatt eine fette C-String-Anhängemethode aufzurufen, die dann doch bloß nur ein einzelnes Zeichen anhängt.

Ok, das soll erst einmal genug sein, wie du siehst bedarf der Code massiver Überarbeitung, da macht es keinen Sinn, jetzt noch mehr Kleinigkeiten zu suchen (z.B. der letzte Punkt ist nur noch Nörgelei). Auf den ersten Blick sieht der Code zwar nach richtig gutem C++ aus (vom Stil her), aber wenn man genauer hinschaut, sehen die Designideen nicht so toll aus.

mortified_penguin

Danke schonmal für die Antwort.

Athar schrieb:

Ich habe mir nicht alles im Detail angesehen, aber wenn du versuchst, eine auf einem Little-Endian-System erzeugte Datei auf einem Big-Endian-System zu lesen (oder umgekehrt), wird das mächtig schief gehen.

Das stimmt, ist im Prinzip aber nicht so wichtig weil es nur eine Übungsaufgabe für mich ist. Kann man eigentlich die Endianness mit einem ifdef abfragen?

Athar schrieb:

Den Baum kannst du sicher weitaus platzsparender ablegen (im Moment speicherst du nur die Häufigkeiten, die dich aber außer für die Konstruktion des Baumes gar nicht interessieren).

Versteh ich nicht so ganz, ich muss die Häufigkeiten in der Binärdatei doch abspeichern um den Baum beim Dekomprimieren entsprechend nach Häufigkeiten konstruieren zu können?

Athar schrieb:

Schön wäre es auch, wenn man nicht auf den stark begrenzten Wertebereich von char festgelegt wäre, schließlich erlaubt die Huffman-Codierung ein Alphabet beliebiger Größe (z.B. 257) anstatt auf Zweierpotenzen fixiert zu sein.

Desweiteren ist bei der Benennung der Parameter (infile_) nicht gleich klar, ob der Dateiinhalt oder ein Dateiname gemeint ist. Ich hätte ersteres erwartet bis ich den fstream unter protected gesehen habe. Nicht alle Daten liegen immer schon in Dateien verpackt, es würde also Sinn machen, gleich einen Stream zu übergeben - dann kann ich mir selbst aussuchen, ob es ein stringstream, fstream oder sonstiges sein soll.

Das sind beides gute Ideen, die ich mir auf jeden Fall mal ansehen werde. Insbesondere das mit dem Wertebereich sollte kein Problem darstellen, kann char ja einfach durch wchar_t ersetzen?

Athar

SeppJ schrieb:

[*]Nochmal Thema Dateien richtig öffnen: Du wandelst den Dateinamen zu Kleinbuchstaben um

Das dachte ich zwar zuerst auch, aber das passiert hier gar nicht.

mortified_penguin

Klasse, danke für deine umfangreiche Antwort!

SeppJ schrieb:

In der Reihenfolge, wie es mir auffällt:

Die Designgrundidee gefällt mir nicht. Wieso sind der Kompressor und Dekompressor beide von einer gemeinsamen Basisklasse abgeleitet? Hat das irgendeine Anwendungsrelevanz? Das sieht eher so aus, als sollten beide Klasse einen Member von der Klasse haben, die den Stream und die map verwaltet.

Mir gefällt auch die Designidee nicht, dass die Kompressoren auf Dateien arbeiten und die Dateiverwaltung auch noch selber durchführen. Hätte man hier nicht einen allgemeinen Stream nehmen können? Oder wenigstens einen String? So wie es jetzt ist, ist der Benutzer dir total ausgeliefert, dass du die Dateien richtig öffnest (das Gefummel mit dem BINARY/PLAIN macht diese Problematik deutlich. Was wäre beispielsweise, wenn er an eine Datei etwas anhängen will?) und kann auch niemals einen eigenen Streamtyp benutzen.

Womit wir beim Stichwort sind: Dies ist doch der optimale Anwendungsfall, um einen Stream zu spezialisieren. Guck mal, wie das hier gemacht wurde:
http://www.cs.unc.edu/Research/compgeom/gzstream/
Das ist, wie ich finde, ein praktisch perfektes Design für diese Anwendung .

Unterscheidet sich dein tree irgendwie von einem set? Warum nimmst du kein set?

Ja, er unterscheidet sich von einem set, da er falsch ist. Wie fast immer, wenn Anfänger manuelle Speicherverwaltung probieren . Du hast mindestens die Regel der großen Drei nicht beachtet. Das heißt, dein Beispielprogramm steht auf total wackeligen Beinen und wird bei der kleinsten Änderung oder Herausforderung versagen.

Nochmal Thema Dateien richtig öffnen: Du wandelst den Dateinamen zu Kleinbuchstaben um . Kein Kommentar. Ok, doch ein Kommentar: Es gibt mehr als NTFS und FAT.

In der main bindest du cstdio ein, aus der du nichts nutzt.

in der main nutzt du Makros aus cstdlib, welche du nicht einbindest.

Nochmal Vererbung: Ein branch ist ein node? Ein leaf ist ein node? Das klingt nach der Wursttheke, die ein Supermarkt ist.

Die vielen reinterpret_cast und dynamic_cast machen mir Sorgen. reinterpret_cast bedeutet, du hast im Design die falschen Datentypen gewählt. dynamic_cast heißt, das Design ist von grundauf total verpfuscht. Letzteres wird mit der komischen Vererbung zusammenhängen.

for (stream = infile.get(); infile.peek() != EOF; stream = infile.get())
Was ist das denn für eine komische Schleifenkonstruktion? peek? Spricht irgendwas dagegen, die Daten auch "normal" einzulesen (z.B. mittels while(leseaktion) ... )? Dann würde dies auch mit allen Arten von Stream funktionieren und verwirrt andere Programmierer nicht, die sich fragen, was dies soll.

Was ist 8? Was ist 0x80? Antwort: Magic numbers!
(Das 8 kann ich mir ja noch herleiten, aber ich habe selbst nach langem Nachdenken keine Ahnung, was das 0x80 soll)

Addier doch einfach einen char zu deinen Strings, anstatt eine fette C-String-Anhängemethode aufzurufen, die dann doch bloß nur ein einzelnes Zeichen anhängt.

Ok, das soll erst einmal genug sein, wie du siehst bedarf der Code massiver Überarbeitung, da macht es keinen Sinn, jetzt noch mehr Kleinigkeiten zu suchen (z.B. der letzte Punkt ist nur noch Nörgelei). Auf den ersten Blick sieht der Code zwar nach richtig gutem C++ aus (vom Stil her), aber wenn man genauer hinschaut, sehen die Designideen nicht so toll aus.

Das ist eine gute Frage, hatte es anfangs auch erst getrennt.
Akzeptiert.
Danke für den Link!
set kannte ich bis jetzt gar nicht bzw. hatte es eher als Menge nach mathematischer Definition interpretiert.
Naja valgrind sagt mir dass ich keine Leaks habe... Kopierkonstruktor und Zuweisungsoperator fehlen halt, das stimmt
Nein, ich wandele den Parameter um. Dass es mehr als NTFS und FAT gibt ist mir bewusst; ich arbeite unter Linux/ btrfs.
Stimmt.
tolower? Habe gedacht das wär in cstdio
Also für mich ist eine Verzweigung / Blatt ein Knoten.
Wenn ich einen node habe, von dem ich weiß dass er ein leaf ist, muss ich doch irgendwie casten, oder?
Stimmt, ich habe eine Zwangsneurose alles in for-Schleifen umzuwandeln
0x80 ist das MSB in einem Byte, für mich ist das eindeutig; aber eine Konstante mit Namen wäre wirklich besser
Akzeptiert.

mortified_penguin schrieb:

[*] 0x80 ist das MSB in einem Byte, für mich ist das eindeutig; aber eine Konstante mit Namen wäre wirklich besser

Nein, bloß nicht.

Hab mir den Code jetzt nich komplett angesehen, kann mir aber nicht vorstellen, dass Sepp das meinte. In der Tat ist es offensichtlich, dass 0x80 bei einem Byte ein gesetztes MSB darstellen soll. Es geht eher darum, welchen Hintergrund das ganze hat. Warum überprüfst du, ob das MSB gesetzt ist? Wieso ist das wichtig?

Außerdem wäre es noch schön, wenn dein Programm bei nichtangegebenen Dateiparametern entsprechend die Standardeingabe/-ausgabe verwenden würde, sodass es auch als Filter nutzbar ist. Das ist allerdings nur noch eine Kleinigkeit nachdem du deine Klassen auf Streams anstatt Dateinamen umgestellt hast.

mortified_penguin schrieb:

Das stimmt, ist im Prinzip aber nicht so wichtig weil es nur eine Übungsaufgabe für mich ist. Kann man eigentlich die Endianness mit einem ifdef abfragen?

Kannst du wahrscheinlich, solltest du aber nicht.

Netter Link:
http://commandcenter.blogspot.de/2012/04/byte-order-fallacy.html

mortified_penguin

sahnemann schrieb:

mortified_penguin schrieb:

[*] 0x80 ist das MSB in einem Byte, für mich ist das eindeutig; aber eine Konstante mit Namen wäre wirklich besser

Nein, bloß nicht.

Hab mir den Code jetzt nich komplett angesehen, kann mir aber nicht vorstellen, dass Sepp das meinte. In der Tat ist es offensichtlich, dass 0x80 bei einem Byte ein gesetztes MSB darstellen soll. Es geht eher darum, welchen Hintergrund das ganze hat. Warum überprüfst du, ob das MSB gesetzt ist? Wieso ist das wichtig?

[...]

Naja ich muss ja wissen ob das MSB 1 oder 0 ist um entsprechend im Baum zu "manövrieren".

Athar

mortified_penguin schrieb:

Das stimmt, ist im Prinzip aber nicht so wichtig weil es nur eine Übungsaufgabe für mich ist.

Sicher, aber du könntest die Übungsaufgabe auch dazu nutzen, dir zu überlegen, wie du das Thema für dieses und alle deine zukünftigen Programme möglichst einfach abhaken kannst.

mortified_penguin schrieb:

Versteh ich nicht so ganz, ich muss die Häufigkeiten in der Binärdatei doch abspeichern um den Baum beim Dekomprimieren entsprechend nach Häufigkeiten konstruieren zu können?

Nö, du konstruierst nämlich daraus keine Häufigkeiten, sondern den Huffman-Baum - entsprechend reicht es auch, die Struktur des Baums zu speichern. Die Häufigkeiten sind unwichtig, kosten aber viel.

mortified_penguin schrieb:

Insbesondere das mit dem Wertebereich sollte kein Problem darstellen, kann char ja einfach durch wchar_t ersetzen?

Oder gleich (u)int32_t.

mortified_penguin schrieb:

Naja ich muss ja wissen ob das MSB 1 oder 0 ist um entsprechend im Baum zu "manövrieren".

Du musst wissen, ob das "nächste" Bit im Eingabestrom gesetzt ist. Das wäre für mich das LSB von meinem aktuellen Byte (es soll ein Bit gelöscht werden und es kommt dabei <<= zum Einsatz? Nanu? Das ist nicht intuitiv).

mortified_penguin

Athar schrieb:

[...]

mortified_penguin schrieb:

Naja ich muss ja wissen ob das MSB 1 oder 0 ist um entsprechend im Baum zu "manövrieren".

Du musst wissen, ob das "nächste" Bit im Eingabestrom gesetzt ist. Das wäre für mich das LSB von meinem aktuellen Byte (es soll ein Bit gelöscht werden und es kommt dabei <<= zum Einsatz? Nanu? Das ist nicht intuitiv).

Ich glaube ich steh gerade ein bisschen auf dem Schlauch - was würdest du stattdessen vorschlagen?

Athar

mortified_penguin schrieb:

Ich glaube ich steh gerade ein bisschen auf dem Schlauch - was würdest du stattdessen vorschlagen?

Na, die Bitreihenfolge innerhalb eines Bytes beim Schreiben umzudrehen, so dass das LSB das erste geschriebene Bit darstellt und das MSB das letzte (innerhalb eines Bytes, versteht sich).