Huffman Tree, Wrong Encoding

242 Views Asked by At

I was pretty happy when I got my tree done but I encountered a problem with the encoding. The most frequent characters did not get the shortest binary code. My speculations are that there is something wrong with the recursive traversing function, or the initialisation of the Node List

Main Program:

public partial class MainWindow : Window
{
    string kode;

    public MainWindow()
    {
        InitializeComponent();
        kode = "";
    }

    public double forhold(int input, int komprimert)
    {
        int tall1 = input * 8;
        int tall2 = komprimert;
        return ((double)tall1 / (double)tall2);
    }

    public void Traverser(Node rot, string kode) //Traverse the tree
    {
        if (rot != null) 
        {
            if (rot.Venstre != null) //If the current node has a left child
            {
                 Traverser(rot.Venstre, kode+"0");
            }
            if (rot.Høyre!= null) //If the current node has a right child
            {
                 Traverser(rot.Høyre, kode+"1");
            }
            //Viser karakter med koresponderende binær kode
            if (rot.Venstre == null && rot.Høyre == null) //If the current node is a leaf
            {
                rot.kode = kode; 
                txtOutput.Text += rot.Tegn.ToString() + ": " + kode +", ";
            }
        }
    }
    //public Node FåKodeMed // 

    public void btnKomprimer_Click(object sender, System.Windows.RoutedEventArgs e)
    {
        string input = txtInput.Text;
        bool funnet; //Found
        char karakter; //Character
        int komprimertLengde; //Not important
        txtOutput.Text = ""; 
        komprimertLengde = 0;

        if (input.Length == 0)  
        {
            txtOutput.Text = "Du må skrive noe i tekst feltet!";
        }
        else
        {
            if (input.Length == 1)
            {
                txtOutput.Text = "0";
            }
            if (input.Distinct().Count() == 1)
            {
                foreach (char c in input)
                {
                    txtOutput.Text += "0";
                }
            }
            else
            {

                List<Node> noder = new List<Node>(); //List containing nodes
                for (int i = 0; i < input.Length; i++) //Places nodes in the tree
                {
                    karakter = input[i];
                    funnet = false;
                    for (int j = 0; j< noder.Count; j++)
                    {
                        if (noder[j].erTegn(karakter) == false) //Hvis tegnet allerede eksisterer
                        {
                            noder[j].økMed1();
                            funnet = true;
                            break;
                        }
                    }
                    if (!funnet)
                    {
                        noder.Add(new Node(karakter));
                    }
                }

                //Sorter listen etter frekvens:
                var sortertListe = noder.OrderBy(c => c.Frekvens).ToList(); //Sort the list by frequency

                //noder = sortertListe;

                do
                {
                    noder.Add(new Node((noder[0].Frekvens + noder[1].Frekvens),noder[0],noder[1])); //Parent node
                    noder.RemoveAt(0);
                    noder.RemoveAt(0);
                    noder.OrderBy(c => c.Frekvens).ToList();

                }while(noder.Count >= 2);

                Node rot = new Node(noder[0]);

                Traverser(rot, "");

                //Feilen kan ligge her
                List<string> output = new List<string>(); 
                foreach (char c in input)
                {
                    for (int i = 0; i < sortertListe.Count;i++)
                    {
                        if(sortertListe[i].Tegn == c)
                        {
                            output.Add(sortertListe[i].kode);
                            break;
                        }
                    }
                }
                txtOutput.Text += "\n" + "\n";
                foreach (string s in output)
                {
                    txtOutput.Text += s;
                }

                foreach (string c in output)
                {
                    komprimertLengde += c.Length;
                }

                txtOutput.Text += "\n" + "\n";
                txtOutput.Text += "lengde på input: " + Convert.ToString((input.Length * 8)) + "\n";
                txtOutput.Text += "Lengde på komprimert: " + Convert.ToString(komprimertLengde) + "\n";
                txtOutput.Text += "Forholdet: " + Convert.ToString(forhold(input.Length,komprimertLengde));

                noder.Clear();
            }
        }
    }

Node Class:

public class Node
{
    public int Frekvens {get;set;}
    public string kode {get;set;}
    public char Tegn {get;set;}
    public Node Høyre {get;set;}
    public Node Venstre {get;set;}

    public Node(char c)
    {
        Frekvens = 1;
        Tegn = c;   
    }
    public Node(Node n)
    {
        Tegn = n.Tegn;
        Frekvens = n.Frekvens;
        Venstre = n.Venstre;
        Høyre = n.Høyre;

    }
    public Node (int f, Node v, Node h)
    {
        Frekvens = f;
        Venstre = v;
        Høyre = h;
    }
    public void økMed1 ()
    {
        Frekvens = Frekvens + 1;
    }
    public bool erTegn(char c)
    {
        if ( c == Tegn)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
}
1

There are 1 best solutions below

1
On BEST ANSWER

I think the entire solution is already provided here at your other question.

The issues with your code are mostly due to the fact that your sorted list is actually sorted in the wrong order to. You might want to use

.OrderByDescending

However, you could try other solutions too. Think of implementing a priority queue for example.

Note: please use English next time, even Google Translate leaves me confused :-)