tom-ash.net

Huffman's compression algorithm implemented in C# in Silverlight 2.

2009-06-28

I have ported Huffman's compression algorithm to C# in a Silverlight 2 application. This is the same algorithm as in my implementation of Huffman's compression in JavaScript:

http://tom-ash.net/blogs/Blog.aspx?File=Programming/20090602_HuffmanCompression.blog

Here is the Silverlight 2 working example:

http://tom-ash.net/blogs/Programming/huffman_ag.html

And the Visual Web Developer 2008 Express Edition solution and source code:

http://tom-ash.net/blogs/Programming/huffman_ag.zip

Here is the source code for the Huffman class:

/*
Author: Tomasz Andraszek
Date: June 28, 2009
E-mail: tandrasz@gmail.com
Web site: http://tom-ash.net
*/

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Net;
using System.Text;

namespace Huffman
{
    public class Huffman
    {
        public static Dictionary<string, decimal> GetProbabilities(string input)
        {
            Dictionary<string, decimal> probabilities = new Dictionary<string, decimal>();
            int index = 0;
            int inputLength = input.Length;
            while (index < inputLength)
            {
                string character = input.Substring(index, 1);
                if (probabilities.ContainsKey(character))
                {
                    probabilities[character] = probabilities[character] + 1;
                }
                else
                {
                    probabilities.Add(character, 1);
                }
                index++;
            }

            index = probabilities.Count;
            while (index > 0)
            {
                index--;
                KeyValuePair<string, decimal> elem = probabilities.ElementAt<KeyValuePair<string, decimal>>(index);
                probabilities[elem.Key] = probabilities[elem.Key] / inputLength;
            }
            return probabilities;
        }

        static Func<KeyValuePair<string, decimal>, decimal> sortNumberAsc = delegate(KeyValuePair<string, decimal> elem)
        {
            return elem.Value;
        };

        static Func<KeyValuePair<string, decimal>, string> keySelector = delegate(KeyValuePair<string, decimal> elem)
        {
            return elem.Key;
        };

        private static HuffmanTreeNode GetNextTreeNode(Collection<HuffmanTreeNode> tree, Collection<HuffmanTreeNode> secondTree)
        {
            HuffmanTreeNode result;
            if (tree.Count > 0 && secondTree.Count > 0 && tree[0].Probability < secondTree[0].Probability)
            {
                result = tree[0];
                tree.RemoveAt(0);
            }
            else if (tree.Count > 0 && secondTree.Count > 0 && tree[0].Probability > secondTree[0].Probability)
            {
                result = secondTree[0];
                secondTree.RemoveAt(0);
            }
            else if (tree.Count > 0)
            {
                result = tree[0];
                tree.RemoveAt(0);
            }
            else
            {
                result = secondTree[0];
                secondTree.RemoveAt(0);
            }
            return result;
        }

        public static Dictionary<string, string> ComputeCodesFromProbabilities(Dictionary<string, decimal> probabilities)
        {
            Collection<HuffmanTreeNode> tree = new Collection<HuffmanTreeNode>();
            Collection<HuffmanTreeNode> secondTree = new Collection<HuffmanTreeNode>();

            Dictionary<string, string> codes = new Dictionary<string, string>();

            IOrderedEnumerable<KeyValuePair<string, decimal>> sortedProbEnumerable = probabilities.OrderBy(sortNumberAsc);
            Dictionary<string, decimal> sortedProb = new Dictionary<string, decimal>();
            foreach (KeyValuePair<string, decimal> elem in sortedProbEnumerable)
            {
                sortedProb.Add(elem.Key, elem.Value);
            }

            foreach (KeyValuePair<string, decimal> elem in sortedProb)
            {
                HuffmanTreeNode tempNode = new HuffmanTreeNode();
                tempNode.Probability = elem.Value;
                tempNode.Value = elem.Key;
                tree.Add(tempNode);
            }

            while (tree.Count + secondTree.Count > 1)
            {
                HuffmanTreeNode left = GetNextTreeNode(tree, secondTree);
                HuffmanTreeNode right = GetNextTreeNode(tree, secondTree);
                HuffmanTreeNode newnode = new HuffmanTreeNode();
                newnode.Left = left;
                newnode.Right = right;
                newnode.Probability = left.Probability + right.Probability;
                newnode.Left.Parent = newnode;
                newnode.Right.Parent = newnode;
                secondTree.Add(newnode);
            }

            HuffmanTreeNode currentnode = null;
            if (secondTree.Count > 0)
                currentnode = secondTree[0];
            string code = String.Empty;
            while (currentnode != null)
            {
                if (currentnode.Value != null)
                {
                    codes[currentnode.Value] = code;
                    code = code.Substring(0, code.Length - 1);
                    currentnode.Visited = true;
                    currentnode = currentnode.Parent;
                }
                else if (!currentnode.Left.Visited)
                {
                    currentnode = currentnode.Left;
                    code += "0";
                }
                else if (!currentnode.Right.Visited)
                {
                    currentnode = currentnode.Right;
                    code += "1";
                }
                else
                {
                    currentnode.Visited = true;
                    currentnode = currentnode.Parent;
                    if (code.Length > 0)
                        code = code.Substring(0, code.Length - 1);
                }
            }
            return codes;
        }

        public static string ReplaceCharactersWithCodes(string input, Dictionary<string, string> codes)
        {
            char[] inputCharArray = input.ToCharArray();
            StringBuilder output = new StringBuilder();

            foreach (char elem in inputCharArray)
            {
                output.Append(codes[elem.ToString()]);
            }
            return output.ToString();
        }
    }
}

And for the HuffmanTreeNode class:

using System;

namespace Huffman
{
    public class HuffmanTreeNode
    {
        public HuffmanTreeNode Left = null;
        public HuffmanTreeNode Right = null;
        public decimal? Probability = null;
        public string Value = null;
        public string Code = String.Empty;
        public HuffmanTreeNode Parent = null;
        public bool Visited = false;
    }
}