c++ - 符号序列的 C++ 和 RLE

Question

我对如何在符号序列上使用 RLE 有困难。

例如，我可以对像这样的字符串进行 RLE 编码

"ASSSAAAEERRRRRRRR"

这将转换为：

"A1S3A3E2R8".

但我想对像这样的字符串执行 RLE

"XXXYYYYY(1ADEFC)(EDCADD)(1ADEFC)(1ADEFC)(1ADEFC)"

这将转换为：

"X3Y5(1ADEFC)1(EDCADD)1(1ADEFC)3"

有没有办法达到它？这项工作变得更容易一些，因为长字符串总是在括号中。可以给出建议在 C++ 中执行此操作吗？
如果有比使用括号更好的存储值的方法，如果您推荐我，那也很棒。

score 4 · Accepted Answer

你应该把这个问题分解成更小的部分。首先，您应该有一个函数来标记您的流并返回每个单独的部分。对于此示例输入流：

"XXXYYYYY(1ADEFC)(EDCADD)(1ADEFC)(1ADEFC)(1ADEFC)"

此函数将返回以下元素，每次调用一个：

X
X
X
Y
Y
Y
Y
Y
(1ADEFC)
(EDCADD)
(1ADEFC)
(1ADEFC)
(1ADEFC)
<eof>

如果你正确实现了这个函数，那么你已经为单个字符实现的 RLE 算法应该很容易适应支持更长的字符串。

score 0 · Accepted Answer

既然您提到您的意图是对数据进行 RLE 编码，以便以后使用 gzip 压缩并实现更好的压缩，我的回答是不要先对其进行编码。gzip 压缩使用 DEFLATE，它是游程编码的推广，可以利用字符串的运行。两次应用相同的算法不会得到更好的压缩，事实上你甚至可能会稍微放松压缩。

如果您坚持执行自己的 RLE，那么最好存储设置的长度而不是使用括号。也就是说，而不是(1ADEFC)3使用61ADEFC3. 另请注意，您打算压缩使用全范围字节值的像素。请记住这一点，因为为处理字符串而编写的算法不适用于带有嵌入式空值和不可打印字符的原始数据。

2 回答 2