C# - 对大文件进行霍夫曼编码需要太长时间

Question

我正在尝试用 C# 实现霍夫曼编码。我在编码大文件时遇到问题，因为它需要太多时间。例如，要对 11MiB 二进制文件进行编码，在 Debug模式下需要 10 秒。我什至懒得等待我的程序完成 27MiB 文件。

这是有问题的循环:

            BitArray bits = new BitArray(8);
            byte[] byteToWrite = new byte[1];
            byte bitsSet = 0;

            while ((bytesRead = inputStream.Read(buffer, 0, 4096)) > 0) // Read input in chunks
            {
                for (int i = 0; i < bytesRead; i++)
                {
                    for (int j = 0; j < nodesBitStream[buffer[i]].Count; j++)
                    {
                        if (bitsSet != 8)
                        {
                            bits[bitsSet] = nodesBitStream[buffer[i]][j];
                            bitsSet++;
                        }
                        else
                        {
                            bits.CopyTo(byteToWrite, 0);
                            outputStream.Write(byteToWrite, 0, byteToWrite.Length);
                            bits = new BitArray(8);
                            bitsSet = 0;

                            bits[bitsSet] = nodesBitStream[buffer[i]][j];
                            bitsSet++;
                        }
                    }
                }
            }

nodesBitStream是 Dictionary<byte, List<bool>> 。 List<bool>是从哈夫曼树根到包含特定符号的叶节点的路径表示，表示为 byte .

因此，我正在累积位以形成一个字节，然后将其写入编码文件。很明显，这可能需要很长时间，但我还没有找到其他方法。因此，我寻求有关如何加快这一过程的建议。

Answer 1

我真的不知道该算法是如何工作的，但是看看你的代码，有两件事很突出:

1. 您似乎正在使用字典来索引字节。也许一个简单的List<bool>[]使用 buffer[i] 更快对其进行索引。您支付的内存价格相当低。使用数组，您可以用速度更快的偏移量来交换查找。您在那里进行了相当多的查找。

2. 为什么要实例化 bits每次迭代？根据您正在进行的迭代次数，最终可能会对GC施加压力。 。似乎没有必要，你本质上是覆盖每一位并每8位吐出一次，所以简单地覆盖它，不要新它；一遍又一遍地使用同一个实例。