哈夫曼编码和解码c#

哈夫曼编码是一种常用的数据压缩算法，它通过将出现频率较高的字符用较短的编码表示，而将出现频率较低的字符用较长的编码表示，从而实现对数据的压缩。以下是哈夫曼编码和解码的基本步骤：

1. 统计字符频率：遍历待编码的文本，统计每个字符出现的频率。

2. 构建哈夫曼树：根据字符频率构建哈夫曼树。哈夫曼树是一种特殊的二叉树，其中每个叶子节点代表一个字符，而非叶子节点代表字符频率之和。

3. 生成编码表：从根节点开始，遍历哈夫曼树的路径，左子树路径标记为0，右子树路径标记为1，将每个字符对应的路径记录下来，形成编码表。

4. 进行编码：根据生成的编码表，将待编码的文本中的每个字符替换为对应的编码。

5. 进行解码：使用相同的哈夫曼树和编码表，将编码后的数据进行解码，恢复原始文本。

在C#中实现哈夫曼编码和解码可以按照以下步骤进行：

1. 定义字符频率统计函数：遍历待编码的文本，统计每个字符出现的频率。

2. 构建哈夫曼树：根据字符频率构建哈夫曼树。可以使用优先队列（PriorityQueue）来实现。

3. 生成编码表：从根节点开始，遍历哈夫曼树的路径，左子树路径标记为0，右子树路径标记为1，将每个字符对应的路径记录下来，形成编码表。

4. 进行编码：根据生成的编码表，将待编码的文本中的每个字符替换为对应的编码。

5. 进行解码：使用相同的哈夫曼树和编码表，将编码后的数据进行解码，恢复原始文本。

以下是C#代码示例：

// 定义节点类
class Node
{
    public char Character { get; set; }
    public int Frequency { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }
}

// 构建哈夫曼树
private static Node BuildHuffmanTree(Dictionary<char, int> frequencies)
{
    var priorityQueue = new PriorityQueue<Node>(Comparer<Node>.Create((a, b) => a.Frequency - b.Frequency));
    foreach (var kvp in frequencies)
    {
        priorityQueue.Enqueue(new Node { Character = kvp.Key, Frequency = kvp.Value });
    }

    while (priorityQueue.Count > 1)
    {
        var left = priorityQueue.Dequeue();
        var right = priorityQueue.Dequeue();
        var parent = new Node { Frequency = left.Frequency + right.Frequency, Left = left, Right = right };
        priorityQueue.Enqueue(parent);
    }

    return priorityQueue.Dequeue();
}

// 生成编码表
private static Dictionary<char, string> GenerateCodeTable(Node root)
{
    var codeTable = new Dictionary<char, string>();
    TraverseTree(root, "", codeTable);
    return codeTable;
}

// 遍历哈夫曼树，生成编码表
private static void TraverseTree(Node node, string code, Dictionary<char, string> codeTable)
{
    if (node.Left == null && node.Right == null)
    {
        codeTable[node.Character] = code;
        return;
    }

    TraverseTree(node.Left, code + "0", codeTable);
    TraverseTree(node.Right, code + "1", codeTable);
}

// 进行编码
private static string Encode(string text, Dictionary<char, string> codeTable)
{
    var encodedText = new StringBuilder();
    foreach (var c in text)
    {
        encodedText.Append(codeTable[c]);
    }
    return encodedText.ToString();
}

// 进行解码
private static string Decode(string encodedText, Node root)
{
    var decodedText = new StringBuilder();
    var currentNode = root;
    foreach (var bit in encodedText)
    {
        if (bit == '0')
        {
            currentNode = currentNode.Left;
        }
        else if (bit == '1')
        {
            currentNode = currentNode.Right;
        }

        if (currentNode.Left == null && currentNode.Right == null)
        {
            decodedText.Append(currentNode.Character);
            currentNode = root;
        }
    }
    return decodedText.ToString();
}

// 示例用法
string text = "Hello, World!";
Dictionary<char, int> frequencies = new Dictionary<char, int>();
foreach (var c in text)
{
    if (frequencies.ContainsKey(c))
    {
        frequencies[c]++;
    }
    else
    {
        frequencies[c] = 1;
    }
}

Node root = BuildHuffmanTree(frequencies);
Dictionary<char, string> codeTable = GenerateCodeTable(root);

string encodedText = Encode(text, codeTable);
string decodedText = Decode(encodedText, root);

Console.WriteLine("Encoded Text: " + encodedText);
Console.WriteLine("Decoded Text: " + decodedText);