Laden...

Huffman: Byteweises einlesen und Häufigkeit der Buchstaben

Erstellt von Bunnychecker vor 12 Jahren Letzter Beitrag vor 12 Jahren 7.008 Views
B
Bunnychecker Themenstarter:in
224 Beiträge seit 2009
vor 12 Jahren
Huffman: Byteweises einlesen und Häufigkeit der Buchstaben

Hi.

Ich habe gerade die Aufgabe einen Huffman Kodierer zu schreiben. Dabei muss ich im ersten Schritt, die Häufigkeit der Buchstaben in einer .txt Datei feststellen.

Mir stellt sich gerade die Frage, wie ich das erreiche?

Der erste Dorn im Auge war für mich, dass ich mit dem folgenden Code ja erst die ganze Datei einlese und dann extra nochmal jeden Buchstaben durchgehe:


            var dictionary = new Dictionary<char, uint>();
            string txt=File.ReadAllText(InputPath);
            foreach (char letter in txt)
            {
                if (dictionary.ContainsKey(letter))
                    dictionary[letter]++;
                else
                    dictionary.Add(letter, 1);
            }   

Dann wiederrum ist mir aber eingefallen, dass es sicher besser wäre, die Bytes einzeln auszulesen (BinaryReader) und direkt in das Dictionary zu schreiben.

Ich brauche nun aber die sortierte Häufigkeit der Buchstaben des strings txt.

Zu guter letzt, habe ich dann noch an eine SortedList gedacht, aber die müsste dann so aussehen, da es auch Buchstaben mit gleicher Häufigkeit geben wird:

var sortedList= new SortedList<uint, List<char>>();

Die Ineffiziens dabei wäre aber, dass sobald ich in der foreach Schleife jeden Buchstabe durchgehe, in der SortedList richtig viel geschoben werden würde, dadurch, dass die Häufigkeit der Buchstaben mit jedem Schleifedurchlauf geändert werden könnte.

Wie löse ich das nun am besten?

1.361 Beiträge seit 2007
vor 12 Jahren

Hi,

das Dictionary ist schon perfekt dafür geeignet. Und was spricht so sehr gegen deine erste Variante? Es ist doch ein durchaus geläufiges Verarbeitungsschema:
Daten komplett einlesen - Daten komplett verarbeiten - Daten komplett wegschreiben.
Du musst doch eh in mehreren Schritten über den Eingabtext iterieren. Einmal zum Aufbauen des Huffman-Codes und dann noch einmal zu Kodieren selbst. Also solange deine txt-Dateien nicht Gigabytes groß werden, bleib bei ReadAllText.

Im übrigen wäre auch das byte-weise Einlesen schlecht. Es sind keine Binärdaten. Nutze dann dafür den StreamReader! Aber bleib einfach bei ReadAllText. Außer du willst wirklich mit beliebig großen Dateien umgehen können. Aber dann bekommst du sowieso weitere Probleme; beispielsweise dass ein uint für die Häufigkeiten nicht ausreicht...

Mit LINQ-Magie reduziert sich deine Schleife auf:

text.GroupBy(letter => letter).ToDictionary(category => category.Key, category => category.Count());

beste Grüße
zommi

M
1.439 Beiträge seit 2005
vor 12 Jahren

Doch es sind Binärdateien. Huffman, Deflate arbeiten mit Binärdateien und nicht mit Strings.
Ich würde hier weder SortedList, noch Dictionary verwenden, sondern ein simples Array mit 256 Elementen. Für jedes Byte ein Element.
Die Datei komplett einzulesen funktioniert nur bei kleinen Dateien, bei größeren Dateien bekommst du ein Problem.
Verwende einen FileStream und ließ die Daten Blockweise, mit einer Blockgröße von z.B.: 64KB, ein. Dann läufst du mit einer for-Schleife über den Block und berechnest die Häufigkeiten.

49.485 Beiträge seit 2005
vor 12 Jahren

Hallo marsgk,

die Huffman-Codierung ist keineswegs auf Bytes festgelegt, sondern berechnet Codes für ein beliebige Eingabezeichenmenge. Laut Aussage von Bunnychecker geht es um .txt-Dateien. Diese sollten im korrekten Encoding gelesen und die Häufigkeit dann zeichenweise (und nicht byteweise) ermittelt werden.

Auch ansonsten sehe ich es wie zommi. Wenn man nicht gerade Dateien erwarten, die den Hauptspeicher sprengen, kann und sollte man zugunsten eines einfacheren und verständlicheren Programmaufbaus auf das blockweise Einlesen verzichten.

herbivore

B
Bunnychecker Themenstarter:in
224 Beiträge seit 2009
vor 12 Jahren

Okay, dann behalte ich das von oben bei, jedoch ist mir das Linq ein Rätsel.

Jetzt will ich das Dictionary noch nach den Values sortieren, aber ich kriege es nicht hin.


            var items = from k in Dictionary.Keys
                        orderby Dictionary[k] ascending
                        select k;

Ich könnte jetzt zwar über ein foreach Schleife das sortierte Dictionary ausgeben, aber wie erreiche ich, dass direkt das Dictionary sortiert wird.

5.742 Beiträge seit 2007
vor 12 Jahren

Jetzt will ich das Dictionary noch nach den Values sortieren, aber ich kriege es nicht hin.

Ein Dictionary kann man nicht sortieren - die "Reihenfolge" der Elemente hängt von den HashCodes der Elemente (und von der Implementierung des Dictionary) ab.

Du könntest allerdings eine sortierte Liste aus dem Dictionary machen (scheinst du ja auch versucht zu haben):


var items = dictionary.OrderByAscending(di => di.Value).Select(di => /*Zugriff auf di.Key und di.Value*/);

1.361 Beiträge seit 2007
vor 12 Jahren

Hi Bunnychecker,

Jetzt will ich das Dictionary noch nach den Values sortieren, aber ich kriege es nicht hin.

Zur Häufigkeitsanalyse behalte das normale Dictionary bei. Wenn du die Häufigkeiten ausgeben willst, erzeuge dir aus dem Dictionary einfach ein SortedDictionary:

var sortedDict = new SortedDictionary(unsortedDict);

Wenn du nun darüber iterierst, ist es sortiert:

foreach( KeyValuePair<string, string> kvp in sortedDict )
{
    Console.WriteLine("Key = {0}, Value = {1}", 
        kvp.Key, kvp.Value);
}

//Edit: Oh, ich sehe gerade, dass du nach den Values sortieren willst - dann macht obiges natürlich keinen Sinn, entschuldige.

beste Grüße
zommi

C
252 Beiträge seit 2007
vor 12 Jahren

Willst du einfach nur eine sortierte Ausgabe haben oder das ganze Dictionary.
Für ersteres gibts eben, wie winSharp93 beretis gezeigt hat, OrderBy bzw OrderByAscending.


      foreach (var kvp in dic.OrderBy(key => key.Value))
      {
        Console.WriteLine(kvp);
      }

Wenn du allerdings das Dictionary ansich nach Values sortieren willst, dann brauchst du den Umweg über ne Liste.


      Dictionary<char, uint> dic = new Dictionary<char, uint>();
      dic.Add('a', 5);
      dic.Add('b', 4);
      dic.Add('c', 7);
      dic.Add('d', 3);


      var list = dic.ToList();
      list.Sort((kvp1, kvp2) => kvp1.Value.CompareTo(kvp2.Value));
      dic.Clear();
      list.ForEach(kvp => dic.Add(kvp.Key, kvp.Value));

Hinweis von herbivore vor 12 Jahren

... was deshalb funktioniert, weil die Dictionary<>-Klasse in .NET so implementiert ist, dass sie die Einträge - solange zwischendurch keine gelöscht werden - in der Hinzufügereihenfolge speichert und enummeriert.

B
Bunnychecker Themenstarter:in
224 Beiträge seit 2009
vor 12 Jahren

Okay danke dafür :]

Linq verstehe ich noch nicht so wirklich, jedoch habe ich mir überlegt, das ganze gleich in eine SortedList zu packen, wie ich das oben schon einmal angedeutet hatte. Dann würde zumindest die Konvertierungsgeschichte zu einer Liste wegfallen

var sortedList = new SortedList<uint, List<char>>();

Mir war dann aber wiederum nicht ganz klar, wie ich in meiner foreach Schleife, prüfen kann, ob irgendeine Liste von char, in meiner SortedList, bereits den aktuellen Buchstaben enthält.


            foreach (char letter in txt)
            {/*hier müsste nun erstmal geprüft werden, ob irgendeine Liste "letter enthält*/}
1.361 Beiträge seit 2007
vor 12 Jahren

das ganze gleich in eine SortedList zu packen

Das würde ich nicht tun. Für jede Aufgabe gibt es eine passende Datenstruktur. Und für das Ermitteln der Häufigkeiten ist diese Datenstruktur bei dir nun einmal das Dictionary. Daran würde ich nichts rütteln.

Wenn du in einem zweiten, nachgelagerten Schritt die Daten anders aufbereitet benötigst, dann konvertiere sie, sortiere sie, was auch immer.

Und hab keine Angst vor dem Overhead durch das einmalige Konvertieren. Ausschlaggebend sollte die Häufigkeitsanalyse und deren zeitliche Komplexität sein!

beste Grüße
zommi

C
1.214 Beiträge seit 2006
vor 12 Jahren

Ich denke, für das Ermitteln der Häufigkeit bietet sich zumindest in dem Fall eine einfache Lookup Tabelle sogar noch eher an, als ein Dictionary. In etwa so:


uint[] table = new uint[256];
foreach (Char letter in txt)
    table[(int)letter]++;

Natürlich musst noch die Tabelle mit Nullen initialisieren und nachher brauchst wieder eine passende Datenstruktur, um die Einträge nach Häufigkeit zu sortieren.

B
Bunnychecker Themenstarter:in
224 Beiträge seit 2009
vor 12 Jahren

Ich habe nun die sortierte Liste und gehe nun mit einer for Schleife die Elemente in der Liste durch.

Nun muss ich den Huffmanbaum aufstellen. Dabei müssen immer die Wertigkeiten/Häufigkeiten zweier Buchstaben bzw. ein Knoten und ein Buchstabe entweder links oder rechts beim binären Baum angeordnet werden.

Ich habe eine Klasse Node erstellt, die Properties für LeftChild, RightChild haben (wieder Nodes), eine Wertigkeit ulong und einen Buchstaben char. Ist also mein Knoten ein Blatt, hat es einen Buchstaben, ist es aber ein Knoten hat es eine Wertigkeit und keinen Buchstaben.

Ich habe nun oberhalb meiner Schleife ein Objekt Node (root) erstellt, indem sich mal der komplette Baum befinden soll.

Mein Hauptproblem ist jetzt, dass in meinem Beispiel nach dem ersten Schleifendurchlauf das linke Kind von root, root selber werden soll und da scheit wohl ein rekursiver Fehler zu sein, denn ich habe jetzt ~unendlich viele linke Kinder, die immer gleich sind.

                        root.LeftChild = root;

vollständige Code:

            var root = new Node();
            for (int i = 0; i < list.Count(); i++)
            {
                //var leftChild = new Node();
                //var rightChild = new Node();
                var node= new Node();

                if (root.Value > list[i].Value)
                {
                    //node.Value=
                }
                else
                {
                    root.Value += list[i].Value;
                    node.Letter = list[i].Key;
                    if (root.LeftChild == null)
                        root.LeftChild = node;
                    else if (root.RightChild == null)
                        root.RightChild = node;
                    else
                    {
                        root.LeftChild = root;
                        root.RightChild = node;

                        var test = new Node();
                        test.Letter = list[i].Key;
                        root.RightChild = test;                         
                    }
                }
            }

771 Beiträge seit 2009
vor 12 Jahren

Hi,

du mußt natürlich auch noch die Variable 'root' neu zuweisen, d.h. in etwa


node.LeftChild = root;
root = node;

Am besten, du malst dir den Baum und den Übergang dazu auf.

B
Bunnychecker Themenstarter:in
224 Beiträge seit 2009
vor 12 Jahren

Glaube der Baum passt jetzt erstmal so. Ich habe root einfach einer backupvariable zugewiesen und root als ein neues Objekt definiert, da hats dann funktioniert:


            //Huffman Baum erzeugen:
            var root = new Node();
            for (int i = 0; i < list.Count(); i++)
            {
                var backup = root;                          //notwendig wegen rekursionsproblemen

                var node = new Node();
                node.Letter = list[i].Key;

                if (root.LeftChild == null)
                    root.LeftChild = node;

                else if (root.RightChild == null)
                    root.RightChild = node;

                else
                {
                    root = new Node();     

                    if (backup.Value > list[i].Value)       //wenn wertigkeit niedriger dann links anordnen
                    {
                        root.RightChild = backup;           //root wird sein eigenes rechtes Kind
                        root.LeftChild = node;
                    }
                    else                                    //ansonsten rechts
                    {
                        root.LeftChild = backup;            //root wird sein eigenes linkes Kind
                        root.RightChild = node;
                    }
                }
                root.Value = backup.Value+list[i].Value;    //korrekte Wertigkeit dem root übergeben
            }//Ende Huffman Baum

Jetzt habe ich den Baum und jetzt fällt mir gerade kein Ansatz ein, wie ich nun die Binärcodierung der Buchstaben hinbekomme.

Ich müsste dabei wie folgt vorgehen, der Baum ist im Objekt Root hinterlegt und immer wenn ich nach links gehe beim Baum, muss ich zu meinem binärstring eine "0" hinzufügen und wenn ich rechts gehe eine "1".

So wie ich das sehe, muss ich das aber sehr umständlich tun, weil ich keine Verweise auf das Elternelement eingebaut habe, richtig?

Mein erster Ansatz war so etwas:

            var aktNode=root;
            string binary=string.Empty;

            while (aktNode.LeftChild != null||aktNode.RightChild!=null)
            {
                if (aktNode.LeftChild == null)
                    binary += "0";
                else
                    binary += "1";
                aktNode = aktNode.LeftChild;
            }

MfG

49.485 Beiträge seit 2005
vor 12 Jahren

Hallo Bunnychecker,

klar kannst du mit einer Parent-Property für jeden Knoten für sich, seine Codierung leicht ermitteln. Da du aber sowieso die Codierung für alle Knoten brauchst, kannst du einfach rekursiv über den ganzen Baum laufen, siehe [Tutorial] Bäume durchlaufen mit Rekursion (und Alternativen). Dabei gibst du der rekursiven Methoden per Parameter einen leeren String mit, an den du beim rekursiven Abstieg eine 0 der 1 anhängst, jenachdem ob du links oder rechts absteigst. Statt des Strings kannst du natürlich auch ein Bitarray bzw. einen Integer verwenden, in dem du die entsprechenden Bits setzt. Siehe [Artikel] Bitoperationen in C#.

herbivore