Click here to Skip to main content
12,406,098 members (39,138 online)
Rate this:
 
Please Sign up or sign in to vote.
See more: C#3.0 C# C#4.0 Algorithms
it is the half man algorithm could you tell me that how does the encode function work!!!

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;
                         }
                 }
         }
 }


using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Text;
  using System.Collections;
  namespace HuffmanTest
  {
  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);
          }
  }
Posted 1-Jun-12 22:21pm
Updated 2-Jun-12 21:52pm
v3
Comments
OriginalGriff 3-Jun-12 4:30am
   
Don't bump your question - add information if there is extra, but otherwise it is just rude.

1 solution

Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 1

See here[^] for details on this algorithm.
  Permalink  

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Mobile
Web01 | 2.8.160726.1 | Last Updated 3 Jun 2012
Copyright © CodeProject, 1999-2016
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100