C#哈夫曼编码压缩图片

实现哈夫曼编码压缩图片的基本步骤如下：

1. 读入图片文件，将每个像素点的颜色值转化成二进制字符串。

2. 统计每个二进制字符串的出现次数，建立哈夫曼树。

3. 根据哈夫曼编码表，将每个二进制字符串进行编码。

4. 将编码后的二进制字符串写入文件，同时将哈夫曼编码表也写入文件。

5. 读入压缩文件和哈夫曼编码表，解码成原始的二进制字符串。

6. 将解码后的二进制字符串转化成像素点的颜色值。

7. 将像素点的颜色值写入文件，生成解压后的图片。

这里提供一个C#的哈夫曼编码压缩图片的例子，代码如下：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace HuffmanCompression
{
    class Program
    {
        static void Main(string[] args)
        {
            string inputFilePath = "input.bmp";
            string outputCompressedFilePath = "output.bin";
            string outputDecompressedFilePath = "output.bmp";

            // 读入图片文件，将每个像素点的颜色值转化成二进制字符串
            byte[] inputBytes = File.ReadAllBytes(inputFilePath);
            string inputBinaryString = "";
            for (int i = 54; i < inputBytes.Length; i += 3)
            {
                byte r = inputBytes[i + 2];
                byte g = inputBytes[i + 1];
                byte b = inputBytes[i];
                string binaryString = Convert.ToString(r, 2).PadLeft(8, '0');
                binaryString += Convert.ToString(g, 2).PadLeft(8, '0');
                binaryString += Convert.ToString(b, 2).PadLeft(8, '0');
                inputBinaryString += binaryString;
            }

            // 统计每个二进制字符串的出现次数，建立哈夫曼树
            Dictionary<string, int> frequencies = new Dictionary<string, int>();
            for (int i = 0; i < inputBinaryString.Length; i += 8)
            {
                string subString = inputBinaryString.Substring(i, 8);
                if (frequencies.ContainsKey(subString))
                {
                    frequencies[subString]++;
                }
                else
                {
                    frequencies.Add(subString, 1);
                }
            }
            HuffmanTree huffmanTree = new HuffmanTree(frequencies);

            // 根据哈夫曼编码表，将每个二进制字符串进行编码
            Dictionary<string, string> encodingTable = huffmanTree.GetEncodingTable();
            string outputBinaryString = "";
            for (int i = 0; i < inputBinaryString.Length; i += 8)
            {
                string subString = inputBinaryString.Substring(i, 8);
                outputBinaryString += encodingTable[subString];
            }

            // 将编码后的二进制字符串写入文件，同时将哈夫曼编码表也写入文件
            byte[] outputBytes = new byte[outputBinaryString.Length / 8 + 1];
            int byteIndex = 0;
            int bitIndex = 0;
            foreach (char bit in outputBinaryString)
            {
                if (bit == '1')
                {
                    outputBytes[byteIndex] |= (byte)(1 << (7 - bitIndex));
                }
                bitIndex++;
                if (bitIndex == 8)
                {
                    byteIndex++;
                    bitIndex = 0;
                }
            }
            File.WriteAllBytes(outputCompressedFilePath, outputBytes);
            using (StreamWriter writer = new StreamWriter(outputCompressedFilePath + ".table"))
            {
                foreach (string key in encodingTable.Keys)
                {
                    writer.WriteLine(key + " " + encodingTable[key]);
                }
            }

            // 读入压缩文件和哈夫曼编码表，解码成原始的二进制字符串
            byte[] compressedBytes = File.ReadAllBytes(outputCompressedFilePath);
            string compressedBinaryString = "";
            foreach (byte compressedByte in compressedBytes)
            {
                for (int i = 0; i < 8; i++)
                {
                    if ((compressedByte & (1 << (7 - i))) != 0)
                    {
                        compressedBinaryString += "1";
                    }
                    else
                    {
                        compressedBinaryString += "0";
                    }
                }
            }
            Dictionary<string, string> decodingTable = new Dictionary<string, string>();
            using (StreamReader reader = new StreamReader(outputCompressedFilePath + ".table"))
            {
                string line;
                while ((line = reader.ReadLine()) != null)
                {
                    string[] parts = line.Split(' ');
                    decodingTable.Add(parts[1], parts[0]);
                }
            }
            string decompressedBinaryString = "";
            string currentBinaryString = "";
            foreach (char bit in compressedBinaryString)
            {
                currentBinaryString += bit;
                if (decodingTable.ContainsKey(currentBinaryString))
                {
                    decompressedBinaryString += decodingTable[currentBinaryString];
                    currentBinaryString = "";
                }
            }

            // 将解码后的二进制字符串转化成像素点的颜色值
            byte[] decompressedBytes = new byte[decompressedBinaryString.Length / 8 * 3 + 54];
            Array.Copy(inputBytes, 0, decompressedBytes, 0, 54);
            for (int i = 0; i < decompressedBinaryString.Length; i += 24)
            {
                string subString = decompressedBinaryString.Substring(i, 24);
                byte r = Convert.ToByte(subString.Substring(0, 8), 2);
                byte g = Convert.ToByte(subString.Substring(8, 8), 2);
                byte b = Convert.ToByte(subString.Substring(16, 8), 2);
                decompressedBytes[i / 8 * 3 + 54] = b;
                decompressedBytes[i / 8 * 3 + 55] = g;
                decompressedBytes[i / 8 * 3 + 56] = r;
            }

            // 将像素点的颜色值写入文件，生成解压后的图片
            File.WriteAllBytes(outputDecompressedFilePath, decompressedBytes);
        }
    }

    class HuffmanTree
    {
        private Node root;

        public HuffmanTree(Dictionary<string, int> frequencies)
        {
            PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>();
            foreach (string key in frequencies.Keys)
            {
                priorityQueue.Enqueue(new Node(key, frequencies[key]));
            }
            while (priorityQueue.Count > 1)
            {
                Node left = priorityQueue.Dequeue();
                Node right = priorityQueue.Dequeue();
                priorityQueue.Enqueue(new Node(left, right));
            }
            root = priorityQueue.Dequeue();
        }

        public Dictionary<string, string> GetEncodingTable()
        {
            Dictionary<string, string> encodingTable = new Dictionary<string, string>();
            Traverse(root, "", encodingTable);
            return encodingTable;
        }

        private void Traverse(Node node, string prefix, Dictionary<string, string> encodingTable)
        {
            if (node.IsLeaf())
            {
                encodingTable.Add(node.Value, prefix);
            }
            else
            {
                Traverse(node.Left, prefix + "0", encodingTable);
                Traverse(node.Right, prefix + "1", encodingTable);
            }
        }

        private class Node : IComparable<Node>
        {
            public string Value { get; set; }
            public int Frequency { get; set; }
            public Node Left { get; set; }
            public Node Right { get; set; }

            public Node(string value, int frequency)
            {
                Value = value;
                Frequency = frequency;
            }

            public Node(Node left, Node right)
            {
                Left = left;
                Right = right;
                Frequency = left.Frequency + right.Frequency;
            }

            public bool IsLeaf()
            {
                return Left == null && Right == null;
            }

            public int CompareTo(Node other)
            {
                return Frequency - other.Frequency;
            }
        }
    }

    class PriorityQueue<T> where T : IComparable<T>
    {
        private List<T> elements;

        public PriorityQueue()
        {
            elements = new List<T>();
        }

        public void Enqueue(T element)
        {
            elements.Add(element);
            int index = elements.Count - 1;
            while (index > 0)
            {
                int parentIndex = (index - 1) / 2;
                if (elements[parentIndex].CompareTo(elements[index]) <= 0)
                {
                    break;
                }
                T temp = elements[parentIndex];
                elements[parentIndex] = elements[index];
                elements[index] = temp;
                index = parentIndex;
            }
        }

        public T Dequeue()
        {
            T result = elements[0];
            elements[0] = elements[elements.Count - 1];
            elements.RemoveAt(elements.Count - 1);
            int index = 0;
            while (true)
            {
                int leftChildIndex = index * 2 + 1;
                int rightChildIndex = index * 2 + 2;
                if (leftChildIndex >= elements.Count)
                {
                    break;
                }
                int smallerChildIndex = leftChildIndex;
                if (rightChildIndex < elements.Count && elements[rightChildIndex].CompareTo(elements[leftChildIndex]) < 0)
                {
                    smallerChildIndex = rightChildIndex;
                }
                if (elements[index].CompareTo(elements[smallerChildIndex]) <= 0)
                {
                    break;
                }
                T temp = elements[index];
                elements[index] = elements[smallerChildIndex];
                elements[smallerChildIndex] = temp;
                index = smallerChildIndex;
            }
            return result;
        }

        public int Count
        {
            get { return elements.Count; }
        }
    }
}

注意：这个例子只是实现了对 BMP 格式的图片进行哈夫曼编码压缩和解压，如果要处理其他格式的图片，需要根据具体的格式进行解析。