Построение дерева "Код Хаффмана" - C#
Формулировка задачи:
Доброго времени суток, есть коллекция символов с числом их повторений, как реализовать этот шаг:
Если я правильно понимаю, коллекция состоит, например: h - 1, e - 1, o - 1, l - 2. Берутся первые два символа объединяются и в итоге получается след.: he - 2, o - 1, l - 2, и так до тех пор пока не останется одна ячейка: helo - 5. Дальше встает вопрос,что каждому символу необходима присвоить значение 1 или 0,когда это делать?
Выбираются два свободных узла дерева с наименьшими весами.
Создается их родитель с весом, равным их суммарному весу. <- Этот интересует
Кто-нибудь подскажет?
Решение задачи: «Построение дерева "Код Хаффмана"»
textual
Листинг программы
public class HuffmanTree { private List<Node> nodes = new List<Node>(); public Node Root { get; set; } public Dictionary<char, int> Frequencies = new Dictionary<char, int>(); public void Build(string source) { for (int i = 0; i < source.Length; i++) { if (!Frequencies.ContainsKey(source[i])) { Frequencies.Add(source[i], 0); } Frequencies[source[i]]++; } foreach (KeyValuePair<char, int> symbol in Frequencies) { nodes.Add(new Node() { Symbol = symbol.Key, Frequency = symbol.Value }); } while (nodes.Count > 1) { List<Node> orderedNodes = nodes.OrderBy(node => node.Frequency).ToList<Node>(); if (orderedNodes.Count >= 2) { // Take first two items List<Node> taken = orderedNodes.Take(2).ToList<Node>(); // Create a parent node by combining the frequencies Node parent = new Node() { Symbol = '*', Frequency = taken[0].Frequency + taken[1].Frequency, Left = taken[0], Right = taken[1] }; nodes.Remove(taken[0]); nodes.Remove(taken[1]); nodes.Add(parent); } this.Root = nodes.FirstOrDefault(); } } public BitArray Encode(string source) { List<bool> encodedSource = new List<bool>(); for (int i = 0; i < source.Length; i++) { List<bool> encodedSymbol = this.Root.Traverse(source[i], new List<bool>()); encodedSource.AddRange(encodedSymbol); } BitArray bits = new BitArray(encodedSource.ToArray()); return bits; } public string Decode(BitArray bits) { Node current = this.Root; string decoded = ""; foreach(bool bit in bits){ if (bit) { if (current.Right != null) { current = current.Right; } } else { if(current.Left != null) { current = current.Left; } } if (IsLeaf(current)) { decoded += current.Symbol; current = this.Root; } } return decoded; } public bool IsLeaf(Node node) { return (node.Left == null && node.Right == null); } } public class Node { public char Symbol { get; set; } public int Frequency { get; set; } public Node Right { get; set; } public Node Left { get; set; } public List<bool> Traverse(char symbol,List<bool> data) { // Leaf if (Right == null && Left == null) { if (symbol.Equals(this.Symbol)) { return data; } else { return null; } } else { List<bool> left = null; List<bool> right = null; if (Left != null) { List<bool> leftPath = new List<bool>(); leftPath.AddRange(data); leftPath.Add(false); left = Left.Traverse(symbol, leftPath); } if (Right != null) { List<bool> rightPath = new List<bool>(); rightPath.AddRange(data); rightPath.Add(true); right = Right.Traverse(symbol, rightPath); } if (left != null) { return left; } else { return right; } } } } class Program { static void Main() { HuffmanTree huffmanTree = new HuffmanTree(); string input; using (StreamReader fileIn = new StreamReader(@"")) { input = fileIn.ReadToEnd(); } huffmanTree.Build(input); BitArray encoded = huffmanTree.Encode(input); string decoded = huffmanTree.Decode(encoded); Console.WriteLine("Decoded: " + decoded); Console.Write("Encoded: "); using (StreamWriter file = new StreamWriter(@"")) { foreach (bool bit in encoded) { file.Write((bit? 1 : 0) + ""); Console.Write((bit ? 1 : 0) + ""); } Console.WriteLine(); } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д