huffman code

[icarus2]

Klar kannst du. Du erzeugst ein Blatt, indem du die Zeige left = NULL und right = NULL setzt. So ist es ja in einem normalen Baum auch.

Und wenn du dann einen Vater erzeugst, so fügst du als left und right einfach bereits erzeugte Knoten hinzu. Du kannst also problemlos einen Baum von unten nach oben aufbauen.

Oder verstehe ich dein Problem nicht richtig?

[kleiner Troll]

struct node
{
   int data;
   node* left;
   node* right;
}

Das erstellt ja an sich noch keinen node - das sagt ja erstmal wie ein node aussieht.

Um einen node zu erstellen machst einfach

node* initialNode = new node;

Dann hast du mit initialNode auch deinen zeiger.

Wenn du dich fragst WO du denn so ne Zeile schreiben sollst, z.B. hier:

class HuffmanCode {
node* initialNode; //oder gleich "node initialNode;"

public:
HuffmanCode() 
{
initialNode = new node; //falls du das oben ohne pointer gemacht hast, kannst dir die Zeile sparen
//hier den node mit sinnvollen Werten füllen
}
~HuffmanCode()
{
delete initialNode; //angeforderten Speicher natürlich wieder freigeben!
}

//operator= und kopierkonstruktor solltest du auch noch selbst schreiben oder private machen - oder aber du nimmst einfach keinen pointer sondern den wert selbst, is imho eh die bessere Lösung

[YouAreTrolling]

kleiner Troll schrieb:

~HuffmanCode()
{
delete initialNode; 
}

Kann das jemand an failblog.org schicken?
Wenn man schon deleted, dann richtig.
Du musst den Huffman schön waschen (jeden Knoten einzeln löschen), sonst bleibt er dreckig und stinkt.

[EOutOfResources]

YouAreTrolling schrieb:

Wenn man schon deleted, dann richtig.

Wenn er den delete -Operator von node korrekt überladen hat, enthält der Code keine Memory-Leaks.

[CStoll]

EOutOfResources schrieb:

YouAreTrolling schrieb:

Wenn man schon deleted, dann richtig.

Wenn er den delete -Operator von node korrekt überladen hat, enthält der Code keine Memory-Leaks.

Nicht den operator delete, sondern den Destruktor

[EOutOfResources]

CStoll schrieb:

Nicht den operator delete, sondern den Destruktor

Sollte nicht beides gehen? Der delete -Operator callt einfach die delete -Operatoren der Member falls die ungleich nullptr sind.

[CStoll]

Nein, der delete-Operator ist etwas anderes. Wenn du in deinem Programm delete p; schreibst, passieren zwei Sachen:

• Der Destruktor des Objekts, auf das p verweist, wird ausgeführt
• operator delete(...) wird aufgerufen, um den Speicherbereich freizugeben den dein Objekt belegt hat

(letzterer arbeitet nicht mehr mit Objekten, sondern mit blanken Speicherbereichen)

[EOutOfResources]

CStoll schrieb:

letzterer arbeitet nicht mehr mit Objekten, sondern mit blanken Speicherbereichen

Ups.

[Gucky]

wenn ich das wort 'c++Forum' habe, würde ich das so machen

................................./ \ <-Man erstellt erstellt den ersten node
Buchstabe: c + f o r u m
Anzahl :.... 1 2 1 1 1 1 1

jetzt muss man sich doch irgendwo "merken", dass man diesen ersten node erstellt hat, damit man später, wenn man weitere erstellt hat, an diesen wieder ein node hängen kann, oder sehe ich das falsch?

[CStoll]

Du kannst dir einen STL-Container (z.B. vector<>) verwenden und alle Blatt-Knoten (für die verwendeten Buchstaben) dort reinpacken. Beim Aufbau des Codes nimmst du jeweils zwei Knoten aus dem Container, hängst sie in einen neu erzeugten Knoten ein und packst diesen wieder in den Container.

[kleiner Troll]

Kann das jemand an failblog.org schicken?

Wenn du dich lächerlich machen willst, kannst das gerne machen.

Wenn man schon deleted, dann richtig.

Ist richtig. Ich delete genau das, was ich angelegt habe, nicht mehr und nicht weniger.

Du musst den Huffman schön waschen (jeden Knoten einzeln löschen), sonst bleibt er dreckig und stinkt.

Die einzelnen Knoten soll derjenige löschen, der sie angelegt hat. Wer immer das auch sein mag. Ich wars auf jedenfall nicht.
Weißt, wenn ich den lieben Huffman selbst bestückt hätte hättest du sogar recht. Hab ich aber nicht.

[icarus2]

Das Prinzip beim effizienten Aufbau des Hummmancodes ist es ja, dass man kleine Teilbäume baut und diese dann zu grösseren Bäumen zusammenfügt.

Man beginnt also am Anfang mit einem Wald, der n Bäume hat (wenn es n verschiedene Zeichen hat). Dann baut man grosse aus kleinen Bäumen, bis man keinen Wald mehr sondern nur noch einen Baum hat. Du musst dir also jeweils nur die Wurzeln der Bäume, die noch im Wald sind, merken.

(Hoffe, das war jetzt nicht allzu wirr ^^)

*Edit
Und ja, wie schon gesagt wäre ein std::vector wohl sinnvoll.

[volkard]

icarus2 schrieb:

bis man keinen Wald mehr sondern nur noch einen Baum hat.

bis man nur noch einem Baum hat (einen zusammenhängenden Wald).

[icarus2]

volkard schrieb:

icarus2 schrieb:

bis man keinen Wald mehr sondern nur noch einen Baum hat.

bis man nur noch einem Baum hat (einen zusammenhängenden Wald).

Von mir aus. An dem solls nicht scheitern

[DrakoXP]

hi,

da ich mich im mom für ein Proseminar auch mit dem Huffman-Code auseinandersetzen muss, hab ich heute aus langer Weile mal den Algorithmus implementiert.

Ich kam zu dem Schluss, dass es wohl sinnvoll wäre, zwei Knotentypen zu haben, die von einem Basisknoten erben.

also hier Node.hxx:

#ifndef __HUFFMAN_NODE_HXX__
#define __HUFFMAN_NODE_HXX__

namespace Huffman
{
	enum NodeType
	{
		NT_Fork,
		NT_Leaf
	};

	class BasicNode
	{
	public:
		virtual ~BasicNode(void) {}
		virtual double value(void) const = 0;
		virtual NodeType type(void) const = 0;
	};

        // Repräsentiert eine Gabelung...
        // Der Wert der Gabelung ergibt sich aus der Summe der Werte ihrer Kinder
	class Fork : public BasicNode
	{
	private:
		BasicNode *left_;
		BasicNode *right_;

		double value_;

	public:
		Fork(BasicNode *l, BasicNode *r)
                : left_(l)
                , right_(r)
                , value_(l->value() + r->value())
                {
                }

		virtual ~Fork(void)
                {
                }

		virtual double value(void) const { return value_; }
		virtual NodeType type(void) const { return NT_Fork; }

		BasicNode* left(void) { return left_; }
		BasicNode* right(void) { return right_; }
	};

        // Ein Endzweig
        // Hier wird die prozentuale Häufigkeit eines Byte-Wertes und der Wert selbst gespeichtert
	class Leaf : public BasicNode
	{
	private:
		unsigned char byte_;
		double value_;

	public:
		Leaf(unsigned char b, double v)
                : byte_(b)
                , value_(v)
                {
                }

		virtual ~Leaf(void)
                {
                }

		virtual double value(void) const { return value_; }
		virtual NodeType type(void) const { return NT_Leaf; }

		unsigned char byte(void) const { return byte_; }
	};
}

#endif // __HUFFMAN_NODE_HXX__

Dann noch ein kleines Programm, was zu jedem Bytewert in einer Datei die prozentuale Häufigkeit und den zugehörigen Huffmancode ausgibt:

#include <iostream>
#include <fstream>
#include <map>
#include <list>
#include <algorithm>

#include "Node.hxx"

// für std::min_element
// so finden wir das Element mit dem kleinsten prozentualen Anteil in der Menge
struct NodeCompare
{
	bool operator () (Huffman::BasicNode *p1, Huffman::BasicNode *p2)
	{
		return (p1->value() < p2->value());
	}
};

// Eine kleine Komfort-Funktion um den Knoten mit dem kleinsten Wert aus der Menge zu extrahieren
// -> der Knoten wird aus der Menge entfernt und dann zurückgegeben.
Huffman::BasicNode* extract_min(std::list<Huffman::BasicNode*> &freq)
{
	if (freq.empty())
		return NULL;

	std::list<Huffman::BasicNode*>::iterator it = std::min_element(freq.begin(), freq.end(), NodeCompare());
	Huffman::BasicNode *node = *it;
	freq.erase(it);

	return node;
}

// Diese Funktion gibt rekursiv ausgehend vom Wurzelknoten den ganzen Baum aus.
void dump_node(Huffman::BasicNode *node, const std::string &code = "")
{
	if (node->type() == Huffman::NT_Leaf)
	{
		Huffman::Leaf *leaf = reinterpret_cast<Huffman::Leaf*>(node);
		std::cout << static_cast<int>(leaf->byte()) << " (" << (leaf->byte() >= 10 && leaf->byte() <= 13 ? ' ' : static_cast<char>(leaf->byte())) << ") : " << leaf->value() << "% -> " << code << std::endl;
	}
	else
	{
		Huffman::Fork *fork = reinterpret_cast<Huffman::Fork*>(node);
		dump_node(fork->left(), code + "0");
		dump_node(fork->right(), code + "1");
	}
}

// Aufruf: ./Huffman [datei]
// auf Fehlermeldungen habe ich auf die Schnelle verzichtet :p
// Rückgabewert überprüfen, um herauszufinden, was schief ging ;-)
int main(int argc, char **argv)
{
	if (argc != 2)
		return (-1);

        // EIngabedatei einlesen -> Dateiname aus argv[1]
	std::ifstream in(argv[1], std::ios::binary);
	if (!in.is_open())
		return (-2);

	in.seekg(0, std::ios::end);
	int size = static_cast<int>(in.tellg());
	in.seekg(0);

	unsigned char *buffer = new unsigned char [size];
	in.read(reinterpret_cast<char*>(buffer), size);

	in.close();

        // Häufogkeiten untersuchen
	int counts[256] = { 0 };

	for (unsigned char *ptr = buffer; ptr != buffer + size; ++ptr)
		++(counts[*ptr]);

	delete[] buffer;

        // prozentuale anteile heraussuchen
	std::map<unsigned char, double> percentages;
	for (int n = 0; n < 256; ++n)
	{
		if (counts[n])
			percentages[static_cast<unsigned char>(n)] = static_cast<double>(counts[n] * 100) / static_cast<double>(size);
	}

        // Das ist nun unsere Menge
	std::list<Huffman::BasicNode *> frequency;
        // Hier erstmal nur mit Blättern füllen
	for (std::map<unsigned char, double>::iterator it = percentages.begin(); it != percentages.end(); ++it)
		frequency.push_back(new Huffman::Leaf(it->first, it->second));

        // Hier führen wir den Huffman-Algorithmus aus (kA ob das so heißt xD)
	while (frequency.size() > 1)
	{
		Huffman::BasicNode *left = extract_min(frequency);
		Huffman::BasicNode *right = extract_min(frequency);
		frequency.push_back(new Huffman::Fork(left, right));
	}

        // hier holen wir uns aus der Menge den Wurzelknoten
        // Die Liste sollte danach leer sein...
	Huffman::BasicNode *root = extract_min(frequency);
        // Ergebnisse ausgeben
	dump_node(root);

	return 0;
}

ja, es geht effizienter, wie gesagt, hab das nur eben so hingepatscht,
aber zur Veranschaulichung sollte es genügen

mir ist ebenfalls bewusst, dass ich den alloziierten Speicher für den Baum nicht freigebe...
hierbei verlasse ich mich einfach auf das Betriebssystem, da sieses Programm im Normalfall nach wenigen Millisekunden abgeschlossen ist...

ich hoffe mein Beispiel ist anschaulich geworden und du kannst was damit anfangen

MfG DrakoXP

[CStoll]

Nettest Design, aber trotzdem ein paar Anmerkungen:
- reinterpret_cast<> solltest du nur verwenden, wenn du gar nichts anderes zur Verfügung hast. Für die dump-Funktion wäre dynamic_cast<> angebrachter (oder noch besser wäre es, sie gleich als Methode der node-Klasse zu implementieren)
- das Zwischenspeichern der kompletten Datei könnte etwas ineffizient sein, da wäre ich lieber mit in.get() einmal über die Datei gerannt.
- und die Gleitkomma-Arithmetik kannst du dir auch sparen, wenn du mit den Zeichen-Anzahlen arbeitest statt mit relativen Anteilen.

PS: Und sich bei der Speicherfreigabe auf das Betriebssystem zu verlassen ist auch nicht gerade guter Stil - wer sagt denn, daß du das nicht irgendwann in eine Funktion packen willst, die regelmäßig aufgerufen werden muß?

[DrakoXP]

CStoll schrieb:

Für die dump-Funktion wäre dynamic_cast<> angebrachter (oder noch besser wäre es, sie gleich als Methode der node-Klasse zu implementieren)

Stimmt, daran hatte ich gar nicht gedacht... (also das mit der Methode)
das werde ich wohl noch umsetzen.
Was die Meinungen zu dynamic_cast, static_cast und reinterpret_cast in Verbindung mit Pointer-Conversions angeht, so schenke ich dem wenig Beachtung, da ich weiß, was ein reinterpret_cast tut, und in dieser Situation definitiv das geschieht, was ich beabsichtige.

CStoll schrieb:

das Zwischenspeichern der kompletten Datei könnte etwas ineffizient sein, da wäre ich lieber mit in.get() einmal über die Datei gerannt.

Wie gesagt, hatte ich mir keine großen Gedanken weiter gemacht,
aber das sollte noch ohne größeren Aufwand einzubauen sein

CStoll schrieb:

und die Gleitkomma-Arithmetik kannst du dir auch sparen, wenn du mit den Zeichen-Anzahlen arbeitest statt mit relativen Anteilen.

weiß ich aber ich wollte es eben prozentual haben.

CStoll schrieb:

wer sagt denn, daß du das nicht irgendwann in eine Funktion packen willst, die regelmäßig aufgerufen werden muß?

-> ich
ich war hier einfach zu faul extra noch eine Funktion/Methode zum Aufräumen des Baums zuschreiben, zumal sowohl Windows als auch Linux mit Freuden den Speicher meines Programmes nach dessen Beendigung aufräumen
Ist ja nicht so, als würde das Programm über Jahre hinweg ununterbrochen laufen.
Selbst wenn, so wäre es in dem Fall auch nicht wirklich schwer, noch so eine kleine Funktion hinzuzufügen

MfG DrakoXP

[CStoll]

DrakoXP schrieb:

CStoll schrieb:

Für die dump-Funktion wäre dynamic_cast<> angebrachter (oder noch besser wäre es, sie gleich als Methode der node-Klasse zu implementieren)

Stimmt, daran hatte ich gar nicht gedacht... (also das mit der Methode)
das werde ich wohl noch umsetzen.
Was die Meinungen zu dynamic_cast, static_cast und reinterpret_cast in Verbindung mit Pointer-Conversions angeht, so schenke ich dem wenig Beachtung, da ich weiß, was ein reinterpret_cast tut, und in dieser Situation definitiv das geschieht, was ich beabsichtige.

Das mag für deine kleinen Programme zutreffen, die du in deiner Freizeit (oder für die Schule) schreibst und anschließend nie wieder betrachtest. Aber irgendwann willst du auch mal Programme schreiben, die etwas größer und langlebiger sind (und an denen du auch nicht alleine arbeitest) - und dann fliegt dir solcher Code ganz schnell um die Ohren.
(das selbe gilt auch für die Speicherverwaltung - spätestens wenn du Objekte verwendest, die sich auch außerhalb des RAM umsehen, reicht es nicht mehr, daß "sowohl Windows als auch Linux mit Freuden den Speicher meines Programmes nach dessen Beendigung aufräumen" - manch andere Sachen, die du dir in den Konstruktoren geholt hast, räumen sie eben nicht wieder auf)