-
Notifications
You must be signed in to change notification settings - Fork 0
/
Huffman.cs
127 lines (116 loc) · 4.03 KB
/
Huffman.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.ConstrainedExecution;
using System.Text;
using System.Threading.Tasks;
using System.Xml.Linq;
namespace Compression
{
internal class HuffmanAlgorithm
{
public static string Compress(string data, out Dictionary<char, string> codeTable)
{
var tree = new Tree(data);
var table = tree.GetCodeTable();
codeTable = table;
return string.Join("", data.Select(c => table[c]));
}
public string Decompress(string data, Dictionary<char, string> codeTable)
{
throw new NotImplementedException();
}
class Tree
{
private readonly List<Node> _nodes;
private readonly Node _root;
public Tree(string data)
{
_nodes = Init(data);
_root = Build() ?? new(0);
}
private static List<Node> Init(string data)
{
Dictionary<char, int> frequencyTable = new();
foreach (char chr in data)
{
if (!frequencyTable.ContainsKey(chr))
{
frequencyTable.Add(chr, 0);
}
frequencyTable[chr]++;
}
return frequencyTable.Select(skv => new Node(skv.Key, skv.Value)).ToList();
}
private Node? Build()
{
while (_nodes.Count > 1)
{
_nodes.Sort();
var taken = _nodes.Take(2).ToList();
var parent = new Node(taken[0].Frequency + taken[1].Frequency)
{
Left = taken[0],
Right = taken[1],
};
parent.Left.Parent = parent;
parent.Right.Parent = parent;
_nodes.Remove(taken[0]);
_nodes.Remove(taken[1]);
_nodes.Add(parent);
}
return _nodes.FirstOrDefault();
}
public Dictionary<char, string> GetCodeTable()
{
Dictionary<char, string> codes = new();
_root.Traverse(node =>
{
if (node.Symbol != Node.SpecialChar)
{
codes.Add(node.Symbol, node.GetCode());
}
});
return codes;
}
class Node : IComparable<Node>
{
public const char SpecialChar = '\u001D';
public int Frequency { get; }
public char Symbol { get; }
public Node? Left { get; set; }
public Node? Right { get; set; }
public Node? Parent { get; set; }
public string GetCode()
{
if (Parent == null)
{
return string.Empty;
}
return Parent.GetCode() + (Parent.Right == this ? "1" : "0");
}
public Node(char symbol, int freq)
{
Frequency = freq;
Symbol = symbol;
}
public Node(int frerq)
{
Frequency = frerq;
Symbol = SpecialChar;
}
public int CompareTo(Node? other)
{
return Frequency.CompareTo(other?.Frequency);
}
public void Traverse(Action<Node> action)
{
action(this);
Left?.Traverse(action);
Right?.Traverse(action);
}
}
}
}
}