SHARE
TWEET

Untitled

a guest May 19th, 2019 49 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Collections;
  6.  
  7. namespace HuffmanCode
  8. {
  9.     public class Node
  10.     {
  11.         public char Symbol { get; set; }
  12.         public int Frequency { get; set; }
  13.         public Node Right { get; set; }
  14.         public Node Left { get; set; }
  15.  
  16.         public List<bool> Traverse(char symbol, List<bool> data)
  17.         {
  18.             // Leaf
  19.             if (Right == null && Left == null)
  20.             {
  21.                 if (symbol.Equals(this.Symbol))
  22.                 {
  23.                     return data;
  24.                 }
  25.                 else
  26.                 {
  27.                     return null;
  28.                 }
  29.             }
  30.             else
  31.             {
  32.                 List<bool> left = null;
  33.                 List<bool> right = null;
  34.  
  35.                 if (Left != null)
  36.                 {
  37.                     List<bool> leftPath = new List<bool>();
  38.                     leftPath.AddRange(data);
  39.                     leftPath.Add(false);
  40.  
  41.                     left = Left.Traverse(symbol, leftPath);
  42.                 }
  43.  
  44.                 if (Right != null)
  45.                 {
  46.                     List<bool> rightPath = new List<bool>();
  47.                     rightPath.AddRange(data);
  48.                     rightPath.Add(true);
  49.                     right = Right.Traverse(symbol, rightPath);
  50.                 }
  51.  
  52.                 if (left != null)
  53.                 {
  54.                     return left;
  55.                 }
  56.                 else
  57.                 {
  58.                     return right;
  59.                 }
  60.             }
  61.         }
  62.     }
  63.     public class HuffmanTree
  64.     {
  65.         private List<Node> nodes = new List<Node>();
  66.         public Node Root { get; set; }
  67.         public Dictionary<char, int> Frequencies = new Dictionary<char, int>();
  68.  
  69.         public void Build(string source)
  70.         {
  71.             for (int i = 0; i < source.Length; i++)
  72.             {
  73.                 if (!Frequencies.ContainsKey(source[i]))
  74.                 {
  75.                     Frequencies.Add(source[i], 0);
  76.                 }
  77.  
  78.                 Frequencies[source[i]]++;
  79.             }
  80.  
  81.             foreach (KeyValuePair<char, int> symbol in Frequencies)
  82.             {
  83.                 nodes.Add(new Node() { Symbol = symbol.Key, Frequency = symbol.Value });
  84.             }
  85.  
  86.             while (nodes.Count > 1)
  87.             {
  88.                 List<Node> orderedNodes = nodes.OrderBy(node => node.Frequency).ToList<Node>();
  89.  
  90.                 if (orderedNodes.Count >= 2)
  91.                 {
  92.                     // Take first two items
  93.                     List<Node> taken = orderedNodes.Take(2).ToList<Node>();
  94.  
  95.                     // Create a parent node by combining the frequencies
  96.                     Node parent = new Node()
  97.                     {
  98.                         Symbol = '*',
  99.                         Frequency = taken[0].Frequency + taken[1].Frequency,
  100.                         Left = taken[0],
  101.                         Right = taken[1]
  102.                     };
  103.  
  104.                     nodes.Remove(taken[0]);
  105.                     nodes.Remove(taken[1]);
  106.                     nodes.Add(parent);
  107.                 }
  108.  
  109.                 this.Root = nodes.FirstOrDefault();
  110.  
  111.             }
  112.  
  113.         }
  114.  
  115.         public BitArray Encode(string source)
  116.         {
  117.             List<bool> encodedSource = new List<bool>();
  118.  
  119.             for (int i = 0; i < source.Length; i++)
  120.             {
  121.                 List<bool> encodedSymbol = this.Root.Traverse(source[i], new List<bool>());
  122.                 encodedSource.AddRange(encodedSymbol);
  123.             }
  124.  
  125.             BitArray bits = new BitArray(encodedSource.ToArray());
  126.  
  127.             return bits;
  128.         }
  129.  
  130.         public string Decode(BitArray bits)
  131.         {
  132.             Node current = this.Root;
  133.             string decoded = "";
  134.  
  135.             foreach (bool bit in bits)
  136.             {
  137.                 if (bit)
  138.                 {
  139.                     if (current.Right != null)
  140.                     {
  141.                         current = current.Right;
  142.                     }
  143.                 }
  144.                 else
  145.                 {
  146.                     if (current.Left != null)
  147.                     {
  148.                         current = current.Left;
  149.                     }
  150.                 }
  151.  
  152.                 if (IsLeaf(current))
  153.                 {
  154.                     decoded += current.Symbol;
  155.                     current = this.Root;
  156.                 }
  157.             }
  158.  
  159.             return decoded;
  160.         }
  161.  
  162.         public bool IsLeaf(Node node)
  163.         {
  164.             return (node.Left == null && node.Right == null);
  165.         }
  166.  
  167.     }
  168.     class Program
  169.     {
  170.         public static String StringGenerator(String elements,int n)
  171.         {
  172.             Random random = new Random();
  173.             int length = elements.Length;
  174.             char[] elems = elements.ToCharArray();
  175.             char[] newS = new char[n];
  176.            
  177.             for(int i=0;i<n;i++)
  178.             {
  179.                 newS[i] = elems[random.Next(0, length)];
  180.             }
  181.             StringBuilder sb1 = new StringBuilder();
  182.             for(int i=0;i<newS.Length;i++)
  183.             {
  184.                 sb1.Append(newS[i]);
  185.             }
  186.             String final = sb1.ToString();
  187.  
  188.             return final;
  189.         }
  190.         static void Main(string[] args)
  191.         {
  192.             int k = 0;
  193.             Console.WriteLine("Enter k");
  194.             k = Convert.ToInt32(Console.ReadLine());
  195.             StringBuilder sb = new StringBuilder();
  196.             Console.WriteLine("Enter " + k + "chars");
  197.  
  198.             while(k!=0)
  199.             {
  200.                 String s = Console.ReadLine();
  201.                 sb.Append(s);
  202.                 k--;
  203.             }
  204.             String tmp = "";
  205.             tmp = sb.ToString();
  206.             int n = 0;
  207.             Console.WriteLine("Enter n");
  208.             n = Convert.ToInt32(Console.ReadLine());
  209.             String finale = "failed";
  210.             finale = StringGenerator(tmp, n);
  211.             string str = Console.ReadLine();
  212.  
  213.             HuffmanTree huffmanTree = new HuffmanTree();
  214.  
  215.             // Build the Huffman tree
  216.             huffmanTree.Build(str);
  217.  
  218.             // Encode
  219.             BitArray encoded = huffmanTree.Encode(str);
  220.  
  221.             Console.Write("Encoded: ");
  222.             foreach (bool bit in encoded)
  223.             {
  224.                 Console.Write((bit ? 1 : 0) + "");
  225.             }
  226.             Console.WriteLine();
  227.  
  228.             // Decode
  229.             string decoded = huffmanTree.Decode(encoded);
  230.  
  231.             Console.WriteLine("Decoded: " + decoded);
  232.  
  233.             Console.ReadLine();
  234.         }
  235.     }
  236. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top