如何在支持全字节值的RLE算法中标记原始数据块结束？

Great question—this is a classic edge case when mixing compressed runs with raw data in RLE, especially when dealing with arbitrary binary input! The core issue here is that your current raw block format only has a start marker (0x00) but no way to tell the decoder how many raw bytes to read. Here's a straightforward, robust fix that fits with your existing design:

改进的原始数据块格式 #

Instead of just using 0x00 as a start marker, extend the raw block to include a length byte right after the marker. The format becomes:

• 0x00 (raw block start marker)
• 1-byte length N (number of raw bytes that follow)
• N raw data bytes

For example, your sample raw data 0x53 0x2C 0x01 would be encoded as:
0x00 0x03 0x53 0x2C 0x01

This works because:

• The decoder knows exactly how many bytes to read for the raw block (no guesswork or relying on a magic terminator)
• Since N can be any value from 1 to 255, you can handle raw blocks up to 255 bytes (if you need longer blocks later, you can extend this to multi-byte lengths, but single-byte is perfect for a learning project)
• There's no conflict with input data containing 0x00—the decoder only cares about the 0x00 at the start of a block, not within raw data.

修改你的编码代码 #

Here's how to update your RunLengthEncode method to implement this format. I'll highlight the key changes:

private static void RunLengthEncode(ref byte[] bytes)
{
    List<byte> output = new List<byte>();
    
    if (bytes.Length == 0) return; // Handle empty input edge case

    byte runLengthByte = bytes[0];
    int runLengthCounter = 1; // Initialize to 1 since we already took the first byte

    for (int i = 1; i < bytes.Length; i++)
    {
        if (runLengthByte == bytes[i] && runLengthCounter < 255)
        {
            runLengthCounter++;
        }
        else 
        {
            // Decide whether to write as raw or compressed run
            if (runLengthCounter < 3)
            {
                // Write raw block: marker + length + data
                output.Add(0x00);
                output.Add((byte)runLengthCounter);
                // Add the run of non-repeating bytes
                for (int j = i - runLengthCounter; j < i; j++)
                {
                    output.Add(bytes[j]);
                }
            }
            else
            {
                // Write compressed RLE packet
                output.Add((byte)runLengthCounter);
                output.Add(runLengthByte);
            }

            // Reset counter and current byte for next run
            runLengthCounter = 1;
            runLengthByte = bytes[i];
        }
    }

    // Handle the final run after loop ends
    if (runLengthCounter < 3)
    {
        output.Add(0x00);
        output.Add((byte)runLengthCounter);
        output.Add(runLengthByte);
    }
    else
    {
        output.Add((byte)runLengthCounter);
        output.Add(runLengthByte);
    }

    bytes = output.ToArray();
}

关键改动说明： #

1. 修正初始计数器：将runLengthCounter初始值设为1（因为我们已经用第一个字节初始化了runLengthByte），避免了偏移错误。
2. 添加原始块长度：写入原始数据时，现在会先添加0x00标记，再添加原始数据的长度，最后写入原始字节。
3. 完善最终块处理：更新了循环结束后的最终块逻辑，当长度小于3时正确写入原始块格式，而非一律写入压缩数据包。
4. 空输入防护：添加了空输入的判断，防止索引越界错误。

解码器对应逻辑提示 #

在解码器中，逻辑可以这样设计：

• 读取一个字节：
  • 如果不是0x00：这是RLE压缩块的长度。读取下一个字节作为数据值，然后将该值重复N次写入输出。
  • 如果是0x00：这是原始块的起始标记。读取下一个字节作为原始块长度N，然后直接读取接下来的N个字节写入输出。

这种方式非常可靠，因为解码器永远不需要猜测原始块的结束位置——它靠明确的长度值来确定。

既然你提到这是一个学习多种压缩算法的项目，这个方法既简单又解决了核心问题，而且如果之后想要添加更长的块或其他功能，它也具备可扩展性！

内容的提问来源于stack exchange，提问作者Wolf