理解霍夫曼算法 [英] understanding Huffman Algorithm

问题描述

这是半人算法，您能告诉我编码功能如何工作！！！

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

推荐答案

请参见此处 [ ^ ].

这篇关于理解霍夫曼算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！