Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Collections;
- namespace HuffmanCode
- {
- 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;
- }
- }
- }
- }
- 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);
- }
- }
- class Program
- {
- public static String StringGenerator(String elements,int n)
- {
- Random random = new Random();
- int length = elements.Length;
- char[] elems = elements.ToCharArray();
- char[] newS = new char[n];
- for(int i=0;i<n;i++)
- {
- newS[i] = elems[random.Next(0, length)];
- }
- StringBuilder sb1 = new StringBuilder();
- for(int i=0;i<newS.Length;i++)
- {
- sb1.Append(newS[i]);
- }
- String final = sb1.ToString();
- return final;
- }
- static void Main(string[] args)
- {
- int k = 0;
- Console.WriteLine("Enter k");
- k = Convert.ToInt32(Console.ReadLine());
- StringBuilder sb = new StringBuilder();
- Console.WriteLine("Enter " + k + "chars");
- while(k!=0)
- {
- String s = Console.ReadLine();
- sb.Append(s);
- k--;
- }
- String tmp = "";
- tmp = sb.ToString();
- int n = 0;
- Console.WriteLine("Enter n");
- n = Convert.ToInt32(Console.ReadLine());
- String finale = "failed";
- finale = StringGenerator(tmp, n);
- string str = Console.ReadLine();
- HuffmanTree huffmanTree = new HuffmanTree();
- // Build the Huffman tree
- huffmanTree.Build(str);
- // Encode
- BitArray encoded = huffmanTree.Encode(str);
- Console.Write("Encoded: ");
- foreach (bool bit in encoded)
- {
- Console.Write((bit ? 1 : 0) + "");
- }
- Console.WriteLine();
- // Decode
- string decoded = huffmanTree.Decode(encoded);
- Console.WriteLine("Decoded: " + decoded);
- Console.ReadLine();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement