3

我编写了一个程序来执行运行长度编码。在典型情况下，如果文本是

AAAAAABBCDEEEEGGHJ

运行长度编码将使它

A6B2C1D1E4G2H1J1

但它为每个非重复字符添加了额外的 1。由于我正在使用它压缩 BMP 文件，因此我想放置一个标记“$”来表示重复字符的出现（假设图像文件具有大量重复文本）。

所以它看起来像

$A6$B2CD$E4$G2HJ

对于当前示例，它的长度是相同的，但 BMP 文件存在显着差异。现在我的问题在于解码。碰巧一些 BMP 文件具有模式，$<char><num>即$I9在原始文件中，所以在压缩文件中也包含相同的文本。$I9，但是在解码后它会将其视为重复的 I 重复 9 次！所以它会产生错误的输出。我想知道的是我可以使用哪个符号来标记重复字符（运行）的开始，这样它就不会与原始来源冲突。

4

6 回答 6

6

为什么不$将原始文件$$中的每个都编码为压缩文件中的每个？

和/或使用其他一些字符代替$- 在 bmp 文件中使用不多的字符。

另请注意，BMP 格式具有“内置”RLE 压缩 - 看这里，靠近页面底部 - 在“图像数据和压缩”下。

我不知道你用你的程序做什么，或者它只是为了学习，但是如果你使用“官方”的bmp方法，你的压缩图像在查看之前不需要解压缩。

于 2009-03-26T09:40:59.860 回答
2

AAAAAABBCDEEEEGGHJ$IIIIIIIII ==> $A6$B2CD$E4$G2HJ$$I9

If the repeat character occurs in the data, try inserting an extra repeat character in the encoded data. Then if the decoder sees a double repeat character it can insert the actual repeat character

$A6$B2CD$E4$G2HJ$$I9 ==> AAAAAABBCDEEEEGGHJ$IIIIIIIII

于 2009-03-26T09:44:47.323 回答
1

大多数程序为了表示某些字符需要按字面意思处理，是因为它们具有定义的转义序列。

例如，在正则表达式中，以下是特殊定义的字符，通常具有含义：

^[].*+{}()$

是的，你有趣的美元符号字符就在那里，它通常意味着end of line。

因此，使用正则表达式的程序员必须做的是让这些字符按字面意思解释，他们需要将这些字符表示为转义序列。例如，要将 $ 解释为$而不是end of line，程序员使用\$，这是转义序列。(1)

在您的情况下，您可以将文字美元符号作为\$ .(2)存储到压缩文件中

  1. 注意：grep颠倒了这个逻辑。

  2. 当您在 BMP 文件中运行$时，上述将$存储为$$的解决方案会变得令人困惑。

于 2009-03-26T10:33:25.333 回答
1

如果您能够在开始压缩之前扫描整个输入，您可以选择输入中频率最低的值作为转义值。例如，给定这个输入：

AAAABBCCCCDDEEEEEEEFFG

您可以选择“G”作为转义值（如果它是符号集的一部分，甚至可以选择“H”）并采用编码流的第一个字符是转义值的约定。所以上面的字符串可能编码为：

GGA4BBGC4DDGE7FFGG

甚至更好：

HHA4BBHC4DDHE7FFG

请注意，对两个相同值的“运行”进行编码是没有意义的，因为“压缩”版本（例如 HD2）比未压缩版本（DD）长。

希望有帮助！

于 2009-03-26T10:49:31.973 回答
0

如果我理解正确，问题是 $ 既是标记重复的符号，也可以是“BMP”值？

如果是这样，您可以做的是标记一个双 $ ('$$') 字符以表示不应将 '$' 字符视为重复，而应将其视为单个 '$'。这当然意味着“$”的编码成本很高（需要两个符号而不是 1 个），但可以解决您的问题。

如果您想要运行 '$' 字符，则需要将其编码为： $$$5 - 表示 '$' 运行 '$$'=$, '5' - 5 次。

于 2009-03-26T09:43:19.090 回答
0

老实说，如果有人想用基于文本的 RLE 压缩二进制数据，我真的不确定他们会拥有什么。BMP 不是文本。

现在，由于在 之后只读取一个字节$，并且它被解释为从 0 到 9 的 ascii 数字，因此该过程的运行长度范围为 0 到 9，这意味着在新的需要写入运行长度标志。毕竟，您无法区分$I34运行长度为 34 和$I3+用于重复 3 后面的4文字。4

如果同样的字节被解释为二进制值，它可以包含从 0 到255的值，从而在效率上产生巨大差异。

至于$符号本身的转义，我建议要么总是将其视为至少 1 ( $$1) 的重复，或者更好的是，以不同的方式对整个事物进行编码，运行长度值的顺序和数据交换，所以代码变为$<length><data>；那么您可以使用$0特殊符号来表示“只是$”。当解压并遇到 a 之后的 0 时$，不要继续阅读第三个字节。运行长度 0 无论如何都不应该出现在压缩数据中，因此可以赋予它特殊的含义，但是如果将数据字节放在第一位，这是没有用的，因为这样它仍然与正常重复的长度相同。

于 2018-01-17T07:53:20.300 回答