C# - 大文件的霍夫曼编码花费的时间太长

Question

我正在尝试用 C# 实现霍夫曼编码。我在编码大文件时遇到问题，因为它需要太多时间。例如，要编码一个 11MiB 的二进制文件，在调试模式下需要 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

一点一点的工作是很多额外的工作。此外，虽然 Dictionary<byte, TVal> 不错，但普通数组更快。

霍夫曼码也可以表示为一对整数，一个表示长度（以位为单位），另一个表示位。在此表示中，您可以通过几个快速操作处理符号，例如（未测试）：

BinaryWriter w = new BinaryWriter(outStream);
uint buffer = 0;
int bufbits = 0;
for (int i = 0; i < symbols.Length; i++)
{
    int s = symbols[i];
    buffer <<= lengths[s];  // make room for the bits
    bufbits += lengths[s];  // buffer got longer
    buffer |= values[s];    // put in the bits corresponding to the symbol

    while (bufbits >= 8)    // as long as there is at least a byte in the buffer
    {
        bufbits -= 8;       // forget it's there
        w.Write((byte)(buffer >> bufbits)); // and save it
    }
}
if (bufbits != 0)
    w.Write((byte)(buffer << (8 - bufbits)));

或者一些变体，例如您可以以相反的方式填充字节，或者将字节保存在数组中并进行更大的写入等。

此代码要求代码长度限制在最大 25 位，通常其他要求会进一步降低该限制。不需要很大的代码长度来获得良好的压缩比。

Answer 2

我真的不知道这个算法是如何工作的，但是看看你的代码有两点很突出：

你好像在用字典来索引一个字节。也许一个简单的 List<bool>[] 更快，使用 buffer[i] 对其进行索引。您要支付的内存价格相当低。使用数组，您将使用更快的偏移量交换查找。你在那里做了很多查找。
为什么要在每次迭代时实例化 bits？根据您进行的迭代次数，最终可能会对 GC 施加压力。似乎没有必要，您实际上是在覆盖每一位并每 8 位吐出一次，所以只需覆盖它，不要新建它；一遍又一遍地使用相同的实例。

C# - 大文件的霍夫曼编码花费的时间太长

C# - Huffman coding for a large file takes too long

c#

compression

huffman-code