Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C#3.0 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
Edited 2-Jun-12 21:52pm
v3
Comments
OriginalGriff at 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
0 OriginalGriff 210
1 Richard MacCutchan 100
2 kbrandwijk 90
3 ProgramFOX 80
4 Sandeep Singh Shekhawat 70
0 Sergey Alexandrovich Kryukov 9,050
1 OriginalGriff 8,151
2 CPallini 2,613
3 Richard MacCutchan 2,221
4 Abhinav S 1,928


Advertise | Privacy | Mobile
Web04 | 2.8.140827.1 | Last Updated 3 Jun 2012
Copyright © CodeProject, 1999-2014
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