huffman.cs

using System.Text;

string input = "AABCBAD";
var ft = FrequencyTable.Create(input); // O(n)
var ht = HuffmanTree.Build(ft);        // O(m)
var et = EncodedTable.Build(ht);       // O(m) => O(n + m)
var compressed = HuffmanCompressor.Compress(input, et);
Console.WriteLine(compressed);
var decompressed = HuffmanDecompressor.Decompress(compressed, ht);
Console.WriteLine(decompressed);



public static class FrequencyTable
{
    public static Dictionary<char, int> Create(string input)
    {
        Dictionary<char, int> result = new();
        foreach (char character in input)
        {
            if (result.ContainsKey(character))
            {
                result[character]++;
            }
            else
            {
                result[character] = 1;
            }
        }
        return result;
    }
}

sealed partial class HuffmanTreeNode
{
    public char Character { get; }
    public int Frequency { get;  }
    public HuffmanTreeNode? Left { get;  }
    public HuffmanTreeNode? Right { get;  }

    public int Priority => 
        Frequency * 10 - (Left != null ? 1 : 0) - (Right != null ? 1 : 0);

    private HuffmanTreeNode(char character, int frequency)
    {
        Character = character;
        Frequency = frequency;
    }

    public static HuffmanTreeNode For(char character, int frequency)
        => new HuffmanTreeNode(character, frequency);

    private HuffmanTreeNode(HuffmanTreeNode left, HuffmanTreeNode right)
    {
        Frequency = left.Frequency + right.Frequency;
        Left = left;
        Right = right;
    }
    
    public static HuffmanTreeNode operator +(
        HuffmanTreeNode left, 
        HuffmanTreeNode right
        ) => new HuffmanTreeNode(left, right);
}

sealed partial class HuffmanTreeNode
{
    
    public static HuffmanTreeNode For(KeyValuePair<char, int> entry)
        => new HuffmanTreeNode(entry.Key, entry.Value);
    
    public static implicit operator HuffmanTreeNode(
        KeyValuePair<char, int> entry
    ) => For(entry);
}


static class HuffmanTree
{
    public static HuffmanTreeNode Build(
        Dictionary<char, int> frequencyTable
        )
    {
        PriorityQueue<HuffmanTreeNode, int> nodes = new(frequencyTable.Count);

        foreach (var entry in frequencyTable)
        {
            var node = HuffmanTreeNode.For(entry);
            nodes.Enqueue(node, node.Priority);
        }

        
        while (nodes.Count > 1)
        {
            var right = nodes.Dequeue();
            var left = nodes.Dequeue();
            var parent = left + right;

            nodes.Enqueue(parent, parent.Priority);
        }

        return nodes.Dequeue();
    }
}

static class EncodedTable
{
    public static Dictionary<char, string> Build(
        HuffmanTreeNode root
    )
    {
        Dictionary<char, string> result = new();
        EncodeNode(root, "", result);
        return result;
    }

    static void EncodeNode(HuffmanTreeNode node, string code, Dictionary<char, string> encodedTable)
    {
        if (node.Left == null && node.Right == null)
        {
            encodedTable[node.Character] = code;
        }

        if (node.Left != null)
        {
            EncodeNode(node.Left, code + "0", encodedTable);
        }

        if (node.Right != null)
        {
            EncodeNode(node.Right, code + "1", encodedTable);
        }
    }
}

static class HuffmanCompressor
{
    public static string Compress(
        string input, 
        Dictionary<char, string> encodedTable
        )
    {
        StringBuilder sb = new();
        foreach (var c in input)
        {
            sb.Append(encodedTable[c]);
        }
        return sb.ToString();
    }
}

static class HuffmanDecompressor
{
    public static string Decompress(string compressedData, HuffmanTreeNode root)
    {
        string data = "";
        var current = root;

        foreach (char c in compressedData)
        {
            if (c == '0')
            {
                current = current.Left;
            }
            else
            {
                current = current.Right;
            }

            if (current.Left == null && current.Right == null)
            {
                data += current.Character;
                current = root;
            }
        }
        return data;
    }
}