CShap 霍夫曼编码 源代码

以下是C#实现的霍夫曼编码的源代码：

using System;
using System.Collections.Generic;
using System.Linq;

public class HuffmanNode
{
    public char Symbol { get; set; }
    public int Frequency { get; set; }
    public string Code { get; set; }
    public HuffmanNode Left { get; set; }
    public HuffmanNode Right { get; set; }
}

public static class HuffmanEncoding
{
    public static string Encode(string input)
    {
        // 计算字符频率
        var frequency = new Dictionary<char, int>();
        foreach (var c in input)
        {
            if (frequency.ContainsKey(c))
            {
                frequency[c]++;
            }
            else
            {
                frequency[c] = 1;
            }
        }

        // 创建霍夫曼树
        var nodes = frequency.Select(x => new HuffmanNode { Symbol = x.Key, Frequency = x.Value }).ToList();
        while (nodes.Count > 1)
        {
            var orderedNodes = nodes.OrderBy(x => x.Frequency).ToList();

            if (orderedNodes.Count >= 2)
            {
                // 取出两个最小的节点
                var first = orderedNodes[0];
                var second = orderedNodes[1];

                // 创建新节点
                var newNode = new HuffmanNode
                {
                    Symbol = '\0',
                    Frequency = first.Frequency + second.Frequency,
                    Left = first,
                    Right = second
                };

                // 从列表中移除节点
                nodes.Remove(first);
                nodes.Remove(second);

                // 添加新节点
                nodes.Add(newNode);
            }
        }

        // 霍夫曼编码
        var root = nodes.FirstOrDefault();
        SetCode(root, "");

        var encodedChars = new List<string>();
        foreach (var c in input)
        {
            var node = nodes.FirstOrDefault(x => x.Symbol == c);
            if (node != null)
            {
                encodedChars.Add(node.Code);
            }
        }

        return string.Join("", encodedChars);
    }

    private static void SetCode(HuffmanNode node, string code)
    {
        node.Code = code;
        if (node.Left != null)
        {
            SetCode(node.Left, code + "0");
        }
        if (node.Right != null)
        {
            SetCode(node.Right, code + "1");
        }
    }
}

使用示例：

string input = "hello world";
string encoded = HuffmanEncoding.Encode(input);
Console.WriteLine(encoded); // 输出编码后的字符串

// 输出每个字符的编码
var frequency = new Dictionary<char, int>();
foreach (var c in input)
{
    if (frequency.ContainsKey(c))
    {
        frequency[c]++;
    }
    else
    {
        frequency[c] = 1;
    }
}

foreach (var kv in frequency)
{
    var node = new HuffmanNode { Symbol = kv.Key, Frequency = kv.Value };
    Console.WriteLine($"{node.Symbol}: {node.Code}");
}