Huffman-Code: Implementierung des Huffman Algorithmus

Ich habe ein Problem bei meiner Implementierung des Huffman Algorithmus.
Mein Problem liegt speziell in der Generierung des optimalen Baumes.

Im Moment generiert mein Code nur einen Baum, der zu einer 3 mal größeren Datei führt.

Ich hab 2 Klassen, Node (Knoten) und GroundElment, welches den Wert eines Bytes darstelle und dessen Häufigkeit.

Jetzt füge ich alle GroundElements in eine Liste, und lass sie sortieren (darin liegt nicht der Fehler).

Jetzt nehme ich die ersten beiden Elemente, füge sie zu einem Node hinzu, lösche sie aus der Liste und füge anschließend den Node der List hinzu.
Dies wiederhohle ich so lange, bis die Liste nur noch ein Element enthält.

In meinem Code sieht das so aus. (INode ist nur das Interface, wodurch Node und GroundElement "getCount()" implementieren, womit die Häufigkeit zurückgegeben wird.)

Node:

public class Node : INode
    {
        public INode LeftSubobject { get; set; }
        public INode RightSubobject { get; set; }

        public ulong getCount()
        {
            return LeftSubobject.getCount() + RightSubobject.getCount();
        }

        public bool isGroundElement() // Gibt wieder ob das Element ein GroundElement ist (Member von INode)
        {
            return false;
        }
    }

GroundElement:

public class GroundElement : INode
    {
        public byte Value { get; set; }
        public ulong Count { get; set; }

        public bool isGroundElement()
        {
            return true;
        }

        public ulong getCount()
        {
            return Count;
        }
    }

getBinaryTree(): (Aus einer Datei)

private Node getBinaryTree(string file)
        {
            ulong[] bytesCount = new ulong[256]; // der Zwischenspeicher, für die Häufigkeit der bytes

            FileStream fs = new FileStream(file, FileMode.Open); 


            while (fs.CanRead)
            {
                int index = fs.ReadByte(); // Das byte wird ausgelesen
                if (index == -1) // hier beendet, wenn man nicht mehr auslesen kann. (canRead bleibt aus irgendeinem Grund immer true)
                    break;
                bytesCount[index]++; // Erhöht dann an dem wert des Bytes die Häufigkeit
            }

            fs.Dispose();

            List<INode> treeElements = new List<INode>(); // Die Liste der Elemente, aus der der Baum gebildet wird.

            for (int i = 0; i < 256; i++)
            {
                if (bytesCount[i] != 0) // Hier werden die Elemente hinzugefügt, solange die Häufigkeit nicht 0 ist.
                    treeElements.Add(new GroundElement() { Value = (byte)i, Count = bytesCount[i] });
            }

            sortList(ref treeElements); // Die Methode sortiert die List (funktioniert zu 100%)

            while (treeElements.Count > 1) // Solange noch mehr als ein Element in der Liste ist...
            {
                INode first = treeElements[0]; // ... werden die beiden Elemente mit den Kleinsten werten ausgesucht (durch das sortieren immer 0 und 1)
                INode second = treeElements[1];

                Node temp = new Node() { LeftSubobject = first, RightSubobject = second}; // Dann ein neues Node Element gebildet..

                treeElements.RemoveRange(0, 2); // ... die beiden alten Elemente gelöscht...

                treeElements.Add(temp); // ...und das neue hinzugefügt.

                sortList(ref treeElements); // Schluss endlich wird nochmal für den nächsten Durchgang sortiert
            }

            return (Node)treeElements[0]; // Am ende ist nur noch 1 Element übrig, und das wird zurück gegeben.
        }

Liegt es nun an meinem Code oder kann es sein das es für Dateien keinen Guten Baum gibt, da sich die Häufigkeiten zu sehr ähneln?

Hallo BangerzZ,

wie sieht denn eine Häufigkeitsverteilung so aus? Denn Vorraussetzung für eine gute Kompression sind ja starke Häufigkeitsunterschiede zwischen den Zeichen.
Ich würde mal denken, dass - wenn du die Bytes einer Datei nimmst - die einzelnen Häufigkeiten relativ gleichmäßig verteilt sein sollten.

Gruß,
dN!3L

Aber benutzen Programme wie Winrar etc nicht aus diese Methode? Wo liegt da der Unterschied?

Wie ist denn das Schreiben des Ergebnisses implementiert? Also wie kannst du messen, dass die komprimierte Form dreimal größer ist?

Hast du dir mal Shannon-Fano-Kodierung - Verbesserungsmöglichkeiten angeguckt?

Gruß,
dN!3L

Ich erstelle mit einer Methode ein Wörtbuch, in dem für alle Bytes eine Bitreihe eingetragen ist.

Danach gehe ich in der Datei byte für byte durch, und schreibe jedes bit mit einem BinaryWriter.

Ok es liegt jetzt zu 100% an meinem Code.
Ich habe mal einen Satz selbst komprimiert und dann durch mein Prog gejagt.

Ich erreiche eine Kompression um 40%, mein Prog nur 1%.

Edit: Bei reinem Text erreiche eine Kompressionsrate von 40% bis 50%