Skip to content

Instantly share code, notes, and snippets.

@ElemarJR
Created February 10, 2023 00:39
Show Gist options
  • Save ElemarJR/91418ad9a6b5f38bcd29a7fc68d20e1f to your computer and use it in GitHub Desktop.
Save ElemarJR/91418ad9a6b5f38bcd29a7fc68d20e1f to your computer and use it in GitHub Desktop.
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment