C# 霍夫曼解码

        1、我们从根开始，依次进行，直到找到叶子。
        2、如果当前位为 0，我们就移动到树的左节点。
        3、如果该位为 1，我们移动到树的右节点。
        4、如果在遍历过程中遇到叶节点，我们会打印该特定叶节点的字符，然后再次从步骤 1 开始继续迭代编码数据。

下面的代码将一个字符串作为输入，对其进行编码，并将其保存在变量编码字符串中。然后对其进行解码并打印原始字符串。

下面是上述方法的实现：

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

namespace HuffmanEncoding
{
// To store the frequency of character of the input data
class FrequencyTable
{
private readonly Dictionary<char, int> _freq = new Dictionary<char, int>();

public void Add(char c)
{
if (_freq.ContainsKey(c))
{
_freq++;
}
else
{
_freq = 1;
}
}

public Dictionary<char, int> ToDictionary()
{
return _freq;
}
}

// A Huffman tree node
class HuffmanNode : IComparable<HuffmanNode>
{
public HuffmanNode Left { get; set; }
public HuffmanNode Right { get; set; }
public char Data { get; set; }
public int Frequency { get; set; }

public HuffmanNode(char data, int freq)
{
Data = data;
Frequency = freq;
}

// Define the comparison method for sorting the nodes in the heap
public int CompareTo(HuffmanNode other)
{
return Frequency - other.Frequency;
}
}

// Utility class for creating Huffman codes
class HuffmanEncoder
{
// To map each character its Huffman value
private readonly Dictionary<char, string> _codes = new Dictionary<char, string>();

// Create an empty min-heap
private readonly List<HuffmanNode> _minHeap = new List<HuffmanNode>();

// Function to build the Huffman tree and store it in minHeap
private void BuildHuffmanTree(Dictionary<char, int> freq)
{
foreach (var kvp in freq)
{
_minHeap.Add(new HuffmanNode(kvp.Key, kvp.Value));
}
// Convert the list to a min-heap using the built-in sort method
_minHeap.Sort();
while (_minHeap.Count > 1)
{
var left = _minHeap.First();
_minHeap.RemoveAt(0);
var right = _minHeap.First();
_minHeap.RemoveAt(0);
var top = new HuffmanNode('$', left.Frequency + right.Frequency);
top.Left = left;
top.Right = right;
_minHeap.Add(top);
// Sort the list to maintain the min-heap property
_minHeap.Sort();
}
}

// Utility function to store characters along with their Huffman value in a hash table
private void StoreCodes(HuffmanNode root, string str)
{
if (root == null)
{
return;
}
if (root.Data != '$')
{
_codes[root.Data] = str;
}
StoreCodes(root.Left, str + "0");
StoreCodes(root.Right, str + "1");
}

// Utility function to print characters along with their Huffman value
public void PrintCodes(HuffmanNode root, string str)
{
if (root == null)
{
return;
}
if (root.Data != '$')
{
Console.WriteLine(root.Data + " : " + str);
}
PrintCodes(root.Left, str + "0");
PrintCodes(root.Right, str + "1");
}

// Function iterates through the encoded string s
// If s[i] == '1' then move to node.right
// If s[i] == '0' then move to node.left
// If leaf node, append the node.data to our output string
public string DecodeFile(HuffmanNode root, string s)
{

string ans = "";
HuffmanNode curr = root;
int n = s.Length;
for (int i = 0; i < n; i++)
{
if (s[i] == '0')
{
curr = curr.Left;
}
else
{
curr = curr.Right;
}

// Reached leaf node
if (curr.Left == null && curr.Right == null)
{
ans += curr.Data;
curr = root;
}
}
return ans + "\0";
}

// Function to build the Huffman tree and store it in minHeap
public void BuildCodes(Dictionary<char, int> freq)
{
BuildHuffmanTree(freq);
StoreCodes(_minHeap.First(), "");
}

public Dictionary<char, string> GetCodes()
{
return _codes;
}

public HuffmanNode GetRoot()
{
return _minHeap.First();
}
}

class Program
{
static void Main(string[] args)
{
// Driver code
string str = "geeksforgeeks";
string encodedString = "";
string decodedString;
var freqTable = new FrequencyTable();
foreach (char c in str)
{
freqTable.Add(c);
}
var huffmanEncoder = new HuffmanEncoder();
huffmanEncoder.BuildCodes(freqTable.ToDictionary());
Console.WriteLine("Character With their Frequencies:");
foreach (var kvp in huffmanEncoder.GetCodes())
{
Console.WriteLine($"{kvp.Key} : {kvp.Value}");
}

foreach (char c in str)
{
encodedString += huffmanEncoder.GetCodes();
}

Console.WriteLine("\nEncoded Huffman data:");
Console.WriteLine(encodedString);

// Function call
decodedString = huffmanEncoder.DecodeFile(huffmanEncoder.GetRoot(), encodedString);
Console.WriteLine("\nDecoded Huffman Data:");
Console.WriteLine(decodedString);
}
}
}

输出：
具有以下频率的字符：

e 10
f 1100
g 011
k 00
o 010
r 1101
s 111

编码的哈夫曼数据：
01110100011111000101101011101000111

解码的哈夫曼数据：
geeksforgeeks

时间复杂度：

霍夫曼编码算法的时间复杂度为O(n log n)，其中n为输入字符串的字符个数。辅助空间复杂度也是O(n)，其中n为输入字符串的字符个数。

在给定的C#代码实现中，时间复杂度主要由使用优先级队列创建 Huffman 树决定，这需要 O(n log n) 时间。空间复杂度主要由用于存储字符频率和代码的映射决定，这需要 O(n) 空间。用于打印代码和存储代码的递归函数也增加了空间复杂度。

比较输入文件大小和输出文件大小：
比较输入文件大小和霍夫曼编码的输出文件。我们可以用一种简单的方法计算输出数据的大小。假设我们的输入是一个字符串“geeksforgeeks”，存储在文件 input.txt 中。

输入文件大小：

输入： “geeksforgeeks”
字符总数即输入长度：13
大小： 13 个字符出现次数 * 8 位 = 104 位或 13 个字节。

输出文件大小：

输入： “geeksforgeeks”

——————————————————
字符 | 频率 | 二进制哈夫曼值 |
——————————————————

e | 4 | 10 |
f | 1 | 1100 |
g | 2 | 011 |
k | 2 | 00 |
o | 1 | 010 |
r | 1 | 1101 |
s | 2 | 111 |

—————————————————

因此要计算输出大小：

e：出现 4 次 * 2 位 = 8 位
f：出现 1 次 * 4 位 = 4 位
g：出现 2 次 * 3 位 = 6 位
k：出现 2 次 * 2 位 = 4 位
o：出现 1 次 * 3 位 = 3 位
r：出现 1 次 * 4 位 = 4 位
s：出现 2 次 * 3 位 = 6 位

总和： 35 位，约 5 字节

由此可见，编码后的数据量是比较大的，上面的方法也可以帮我们确定N的值，也就是编码后数据的长度。

标签：编码,C#,Huffman,解码,HuffmanNode,minHeap,霍夫曼,root,public
From： https://blog.csdn.net/hefeng_aspnet/article/details/139590544

相关文章

赞助商

阅读排行