locked
*URGENT* Please help with Encoding Text for Huffman Code C# Program!!! RRS feed

  • Question

  • Hello, I am trying to create a Huffman Code program in C# for a University Assignment and am having trouble getting it to encode the inputted text into binary, and then displaying it. Below is the code we have now, and this is a link to view the "skeleton" we MUST stick to for the assignment. Any help would be much appreciated as it is due tonight, thank you! https://docs.google.com/document/d/1szCAQMNHm5ls_fHDnMQqpnM-iABnQLSde7-xCvOb6bY/edit?usp=sharing

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace COIS_Assignment2
    {
        class Program
        {
            static void Main(string[] args)
            {
                string userText;
    
                Console.WriteLine("Input some text!");
                userText = Console.ReadLine();
                Huffman bob = new Huffman(userText);
    
                string encodedText = bob.Encode(userText);
                Console.WriteLine(encodedText);
                //string decodedText = bob.Decode(encodedText);
                Console.ReadLine();
            }
        }
    }

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace COIS_Assignment2
    {
        public interface IContainer<T>
        {
            void MakeEmpty();  // Reset an instance to empty
            bool Empty();      // Test if an instance is empty
            int Size();        // Return the number of items in an instance
        }
    
        public interface IPriorityQueue<T> : IContainer<T> where T : IComparable
        {
            void Add(T item);  // Add an item to a priority queue
            void Remove();     // Remove the item with the highest priority
            T Front();         // Return the item with the highest priority
        }
    
        // Priority Queue
        // Implementation:  Binary heap
    
        public class PriorityQueue<T> : IPriorityQueue<T> where T : IComparable
        {
            private int capacity;  // Maximum number of items in a priority queue
            private T[] A;         // Array of items
            private int count;     // Number of items in a priority queue
    
            public PriorityQueue(int size)
            {
                capacity = size;
                A = new T[size + 1];  // Indexing begins at 1
                count = 0;
            }
    
            // Percolate up from position i in a priority queue
    
            private void PercolateUp(int i)
            // (Worst case) time complexity: O(log n)
            {
                int child = i, parent;
    
                while (child > 1)
                {
                    parent = child / 2;
                    if (A[child].CompareTo(A[parent]) > 0)
                    // If child has a higher priority than parent
                    {
                        // Swap parent and child
                        T item = A[child];
                        A[child] = A[parent];
                        A[parent] = item;
                        child = parent;  // Move up child index to parent index
                    }
                    else
                        // Item is in its proper position
                        return;
                }
            }
    
            public void Add(T item)
            // Time complexity: O(log n)
            {
                if (count < capacity)
                {
                    A[++count] = item;  // Place item at the next available position
                    PercolateUp(count);
                }
            }
    
            // Percolate down from position i in a priority queue
    
            private void PercolateDown(int i)
            // Time complexity: O(log n)
            {
                int parent = i, child;
    
                while (2 * parent <= count)
                // while parent has at least one child
                {
                    // Select the child with the highest priority
                    child = 2 * parent;    // Left child index
                    if (child < count)  // Right child also exists
                        if (A[child + 1].CompareTo(A[child]) > 0)
                            // Right child has a higher priority than left child
                            child++;
    
                    if (A[child].CompareTo(A[parent]) > 0)
                    // If child has a higher priority than parent
                    {
                        // Swap parent and child
                        T item = A[child];
                        A[child] = A[parent];
                        A[parent] = item;
                        parent = child;  // Move down parent index to child index
                    }
                    else
                        // Item is in its proper place
                        return;
                }
            }
    
            public void Remove()
            // Time complexity: O(log n)
            {
                if (!Empty())
                {
                    // Remove item with highest priority (root) and
                    // replace it with the last item
                    A[1] = A[count--];
    
                    // Percolate down the new root item
                    PercolateDown(1);
                }
            }
    
            public T Front()
            // Time complexity: O(1)
            {
                if (!Empty())
                {
                    return A[1];  // Return the root item (highest priority)
                }
                else
                    return default(T);
            }
            public void MakeEmpty()
            // Time complexity: O(1)
            {
                count = 0;
            }
    
            public bool Empty()
            // Time complexity: O(1)
            {
                return count == 0;
            }
    
            public int Size()
            // Time complexity: O(1)
            {
                return count;
            }
        }
    }

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace COIS_Assignment2
    {
        class Node : IComparable
        {
            public char Character { get; set; }
            public int Frequency { get; set; }
            public Node Left { get; set; }
            public Node Right { get; set; }
            public Node Parent { get; set; }
    
            public Node(char character, int frequency, Node left, Node right)
            {
                this.Character = character;
                this.Frequency = frequency;
                this.Left = left;
                this.Right = right;
    
            }
            // 5 marks
            public int CompareTo(Object obj)
            {
                Node node = (Node)obj;
                if (this.Frequency > node.Frequency)
                {
                    return 1;
                }
                else if (this.Frequency < node.Frequency)
                {
                    return -1;
                }
                else
                {
                    return 0;
                }
    
                }
            }
    }

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace COIS_Assignment2
    {
        class Huffman
        {
            private Node HT; // Huffman tree to create codes and decode text
            private Dictionary<char, string> D = new Dictionary<char, string>(); // Dictionary to encode text
             
            // Constructor
    
            public Huffman(string S)
            {
                int[] frequency = AnalyzeText(S);
                Build(frequency);
                CreateCodes();
    
            }
            // 15 marks
            // Return the frequency of each character in the given text (invoked by Huffman)
            public int[] AnalyzeText(string S)
            {
                Dictionary<char, ulong> characterCount = new Dictionary<char, ulong>();
                int[] charFrequencies = new int[53];
    
                foreach (char character in S)
                {
                    if (!characterCount.ContainsKey(character))
                    {
                        characterCount.Add(character, 1);
                    }
                    else
                    {
                        characterCount[character]++;
                    }
                }
    
                Console.WriteLine("Here is the list of characters and their frequencies:");
                foreach (var character in characterCount)
                {
                    if (char.IsLower(Convert.ToChar(character.Key)) == true)
                    {
                        charFrequencies[character.Key - 'a'] = Convert.ToInt16(character.Value); //exception here when there are capital letters and spaces
                        Console.WriteLine("{0} - {1}", character.Key, character.Value);
                    }
                    if (char.IsUpper(Convert.ToChar(character.Key)) == true)
                    {
                        // lowercase letters are 32 larger than uppercase
                        charFrequencies[character.Key -39] = Convert.ToInt16(character.Value);
                        Console.WriteLine("{0} - {1}", character.Key, character.Value);
                    }
                    if (Convert.ToChar(character.Key) == ' ')
                    {
                        charFrequencies[52] = Convert.ToInt16(character.Value);
                        Console.WriteLine("{0} - {1}", character.Key, character.Value);
                    }
                }
    
                Console.WriteLine("Here is the array that holds the characters");
                char characterTwo;
                for (int i = 0; i <charFrequencies.Length; i++)
                {
                    characterTwo = Convert.ToChar(charFrequencies[i]);
                    Console.Write(characterTwo);
                }
                
                return charFrequencies;
            }
            // 20 marks
            // Build a Huffman tree based on the character frequencies greater than 0 (invoked by Huffman)
            public void Build(int[] letterFrequencies)
            {
                // makes a huffman tree with the character with values greater than zero
                char character;
                PriorityQueue<Node> PQ = new PriorityQueue<Node>(53);
    
                if (letterFrequencies[52] > 0)
                    PQ.Add(new Node(' ', letterFrequencies[52], null, null));
    
                for (int i = 0; i <= 52; i++)
                {
                    if (letterFrequencies[i] != 0)
                    {
                        character = Convert.ToChar(i + letterFrequencies[i]);
                        PQ.Add(new Node(character, letterFrequencies[i], null, null));
                    }
                }
    
                for (int i = 'A' -39; i <= 'Z' -39; i++)
                {
                    if (letterFrequencies[i] > 0)
                    {
                        character = Convert.ToChar(i + letterFrequencies[i]);
                        PQ.Add(new Node(character, letterFrequencies[i], null, null));
                    }
                }
                while (PQ.Size() > 1)
                {
                    Node Left = PQ.Front();
                    PQ.Remove();
                    Node Right = PQ.Front();
                    PQ.Remove();
    
                    int frequency = Left.Frequency + Right.Frequency;
                    PQ.Add(new Node('5', frequency, Left, Right));
                    //HT = new Node('5', frequency, Left, Right);
                }
    
                HT = PQ.Front();
            }
            // 20 marks
            // Create the code of 0s and 1s for each character by traversing the Huffman tree (invoked by Huffman)
            private void CreateCodes()
            {
                // assigns the character their number values
                Queue<KeyValuePair<Node, string>> queue = new Queue<KeyValuePair<Node, string>>();
                queue.Enqueue(new KeyValuePair<Node, string>(HT, ""));
    
                while (queue.Count != 0)
                {
                    if (HT.Left == null)
                    {
                        D.Add(HT.Character, "0");
                    }
                    else
                    {
    
                        Node current = queue.Peek().Key;
                        string temp = queue.Peek().Value;
                        queue.Dequeue();
                        if (current.Character != '*')
                        {
                            D.Add(current.Character, temp); // argument unhandled
                        }
                        else
                        {
                            queue.Enqueue(new KeyValuePair<Node, string>(current.Left, temp + '0'));
                            queue.Enqueue(new KeyValuePair<Node, string>(current.Right, temp + '1'));
                        }
                    }
                }
            }
            // 10 marks
            // Encode the given text and return a string of 0s and 1s
            public string Encode(string S)
            {
                // check the character values to the number assigned to them
                
                string encodedText = "";
                string dictionaryText = "";
                int i = 0;
                foreach (var text in D)
                {
                    if (i == S.Length) { break; }
                    dictionaryText = text.Value;
                    encodedText = encodedText + dictionaryText;
                    i = i + 1;
                    
                }
                return encodedText;
            }
            // 10 marks
            // Decode the given string of 0s and 1s and return the original text
            public string Decode(string S)
            {
                // check the number values with the character assigned to them
                return S;
            }
        }
    
    }

    Thursday, November 8, 2018 7:14 PM

All replies

  • Hi blackbearox,

    Thank you for posting here.

    According to your description, what is the error? For the code you provided, what can we help you? Please provide more details.

    Here are some examples about Huffman Tree, you could download the source file for reference.

    https://code.msdn.microsoft.com/Building-a-Huffman-f29b3e81

    http://snipd.net/huffman-coding-in-c

    Best Regards,

    Wendy


    MSDN Community Support
    Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

    Friday, November 9, 2018 7:27 AM