compression - 压缩少量数据

Question

我有一个程序，可以在其中生成大约 80 到 150 位左右的比特流，我想对其进行压缩，因为我要把它们变成某种 ASCII 字符串，以便人们可以传输它们。

有谁知道可以在这样的流上工作的好的、免费的位感知压缩器？我对“标准选项”的主要问题是这个流真的应该被视为位，而不是字节，否则结构会丢失，并且它们的开销会淹没任何收益。

添加：

我想压缩这些流的原因是因为用户将剪切+粘贴它们，可能使用 base64 编码之类的东西，所以保存一些数据是有帮助的。

这是一个例子，给那些想看的人。我将添加格式以使其更易于阅读：

110 110 - This is a 6x6 grid (the maximum is 7x7, so we only need 3 bits!)

000000
011110
010010
010010
011110
000000 - This is one layout grid

000000
000000
001000
000100
000000
000000 - This is the second layout grid

现在我们列出一些片段

010 11111111 - A piece is a 3-bit colour code, then an 8-bit list of 'on / off' bits.
001 10101010 - Another bit!
001 10101010 - Another, identical bit!

我说这应该被视为“位”的原因是，当您将其视为位流（特别是“网格中的许多 0”）时，有明显的压缩选项，当您将其视为字节流时，这些选项就会消失。

score 10 · Accepted Answer

您希望通过压缩 150 位来完成什么？除非您汇总这 19b 消息中的几个，否则我不确定您希望获得什么。这是 UI 问题吗？您希望用户在其中发送/接收“代码”吗？

base 64编码怎么样？这将获取二进制数据并将其转换为编码字符，以便于传输或输入。

score 4 · Accepted Answer

克里斯，感谢您发布这些样本。我认为游程编码是您想要的方式。这应该很容易实现。

http://en.wikipedia.org/wiki/Run-length_encoding

将与所有这些连续的 0 一起工作。

那么压缩这些字符串的主要原因是为了让它们更容易剪切和粘贴？说得通; 这听起来像是一个有趣的项目。

如果您只是想让字符串更易于人工管理，那么听起来您已经准备就绪。如果您尝试压缩它们以使它们通过网络传输得更快，我认为压缩小字符串的好处可能会被其他 TCP 问题（如 MTU 大小等）所破坏。（我在那里没有经验，所以最后一点用很多盐）

祝你好运！

score 3 · Accepted Answer

我猜没有通用算法会给你这种数据很好的压缩。

最好的办法是分析数据的结构并尝试找到自定义压缩算法或可能自定义现有的压缩算法（可能使用预填充的字典或类似的东西）。

score 3 · Accepted Answer

我的第一个建议是您研究范围编码。代替

1：从位数据压缩成二进制数据，然后

2：将二进制数据编码成base64 ASCII数据，

您可以将您的位直接打包到 0- 范围内N（N您使用的可打印字符的数量为负 1），然后进行非常简单的映射。

我的第二个建议是您研究 PNG 使用的过滤器方法，并考虑是否可以使用类似的方法来使您的数据更可压缩。仅从两个示例布局网格中很难分辨，但从您的第一个网格中似乎很可能有某种方法，例如“根据其上方和左侧的邻居预测每个像素，然后将每个像素转换为 0，如果它满足预测和 1 如果它违背了它的预测”可以给你一个更统一的数据集，从而更大的压缩。

score 2 · Accepted Answer

由于流如此之小，您可以在此处发布其中的一些吗？

您还确定这些流中有足够的冗余甚至允许压缩吗？是否有任何重复的数据块？

这是一个远景，但在没有任何具体答案的情况下，您可能想查看 ROM 场景并检查文本字符串在基于卡带的 RPG 游戏（如“Chrono Trigger”或“Final Fantasy III.”）中是如何压缩的。 " 我知道这些游戏中的文本字符串是被压缩的（当时字节非常宝贵），而破解该计划对黑客来说是一个有趣的挑战。当你提到很多短小的字符串被压缩时，这是我唯一想到的。

但是，您的根本问题可能仍然存在。我想这些 ROM 中的压缩方案利用了许多字符串的冗余（即，如果“Timbuktu”出现在 58 个不同的字符串中），而不是在单个流中。

score 2 · Accepted Answer

我建议您考虑使用zlib。它是可下载的，并且许可证允许您将它用于几乎任何项目。重要的一点是它被广泛使用，因此调试良好。如果您的数据很重要，您不希望将来在随机日期调试 hombrew 算法中的奇数边缘情况。

我已经搞砸了一点，它确实允许面向流的压缩。我不确定当你一次只给它少量数据时它有多好。无损压缩往往通过查找和消除模式来工作，如果您一次输入像 12 字节这样的小东西，就不会找到很多模式。

我不赞成胡安的回答，因为他还建议使用有损压缩的 GIF。您没有提供很多信息，但我猜您不想要任何实际丢失数据的压缩格式。大多数流行的图形、音频和视频压缩算法都是有损的；它们依赖于人类感官正确接收图像或声音的能力，其中一些原始信息被删除或稍作修改。

score 1 · Accepted Answer

CCITT 的第 3 组和第 4 组无损编码方案用于压缩 G3 和 G4 TIFF，在设计时考虑了二进制数据。G4 TIFF 是通常用于 OCR 和传真的黑白图像。想到的另一个简单方案是RLE。

score 1 · Accepted Answer

JBIG 可能会满足您的需求。

http://en.wikipedia.org/wiki/JBIG

http://www.jpeg.org/jbig/index.html

http://www.cl.cam.ac.uk/~mgk25/jbigkit/

JBIG 用于压缩 1-bpp 传真图像。

score 0 · Accepted Answer

zlib 压缩（可能与 gzip 的算法相同）是免费的。它有一些设置，但我不确定你能节省多少，除非你的比特有一些周期性的模式。

由于 png 和 gif 图形文件本质上是位模式的表示，也许您可以找到它们使用的压缩算法。

score 0 · Accepted Answer

你想要的是无损二进制压缩。如果没有大量其他资源，我确信有论文或网络文章。谷歌这些条款，我怀疑你会得到你需要的。

你在说多少数据？您的管道是否太小或吞吐量太高以至于您必须压缩？

回想起来，您的数据太小了，除非您分析流量并进行自己的“压缩”，这基本上只是已知位模式的映射/散列，否则您可能不会获得有价值的收益。

正如其他人所说，发布一些示例数据，之后可能会有更好的建议。

score 0 · Accepted Answer

我和蒂姆有同样的想法——如此少量的数据似乎几乎不值得压缩。事实上，我建议您真正想要研究的是某种 ascii 编码方法，例如 uuencode 或 mime-encode（又名“ Base64 ”）。

score 0 · Accepted Answer

只是为了补充已经说过的内容，“压缩少量数据”本质上是不是有点毫无意义？如果您可以详细说明可能有帮助的数据、平台或用途。

至于位与 ascii - 我不完全确定你在做什么，但正如迈克尔所提到的，Base64 提供了一种使任意二进制更友好的方法。

请注意，任何从二进制到 ascii 的转换都与压缩相反。

compression - 压缩少量数据

12 回答 12

Related

Reference