字符串压缩算法？

Question

我正在寻找一种算法，可以将某些字符串压缩成另一个字符串（即没有"\0"或特殊控制字符），但我在互联网上找不到任何东西。是否有这样的算法？它不必特别高效，只需要基本的东西。

- laurent

---

任何压缩算法都是这样做的。 - static_rtti

@MAKKAM，这并不相关。他需要一个特定类型字符串（短字符串）的算法，而我需要一些通用的东西。 - laurent

尝试使用Huffman编码和RLE。 - Aman Agarwal

@static_rtti，我正在寻找一种压缩算法，它可以输出一个可复制和粘贴的字符串。我认为大多数压缩算法输出带有\0字符的二进制数据。 - laurent

@Piskvor，是的，我想我的问题是我希望输出只包含可打印字符，这样它就可以被复制和粘贴，通过电子邮件发送等。我认为这不仅仅是操作系统的问题，许多用户界面和程序都会在复制和粘贴带有0x0的字符串时出现问题。 - laurent

Answer 1

简单：

$ echo "Hello world" | gzip -c | base64
H4sIALnHeU4AA/NIzcnJVyjPL8pJ4QIA1eA5twwAAAA=

$ echo "H4sIALnHeU4AA/NIzcnJVyjPL8pJ4QIA1eA5twwAAAA=" | base64 -d | gzip -dc
Hello world

注意：看起来好像没有压缩，但对于更大的数据，压缩比将会更好 :-)

- Tomas

---

Base64在OP提到的限制下并不是最有效的，因为有超过90个可打印ASCII字符，甚至更多的扩展ASCII字符。 - harold

确立了原则。你可以使用Ascii85或其他使用更多可打印字符的方案，而提问者说：“它不必特别高效”。 - Steve Jessop

@哈罗德，是的，可能不是尽可能节省空间，但OP说：“它不必特别高效，只需要基本的东西”-就是这样！Base64非常基础、简单和便携。它可以在许多语言中直接使用。而且没有必要为自己实现任何其他东西，也没有必要重新发明轮子。 - Tomas

它必须特别低效吗？好吧，其实也不是那么糟糕，但这有点伤害我的“本可以更好”的感觉。如果没有先进行压缩阶段，那么仅使用base64编码就对我来说是有意义的，但现在不太合适。 - harold

我尝试了这个，不得不在 base64 -d 后面添加 --ignore-garbage。 - Stephen Denne

Answer 2

显然，您有一些特定的字符集，并希望将其用于原始字符串和压缩字符串。标准压缩例程（例如gzip）适用于字节字符串。一个想法是采用现有代码（例如gzip的代码），并重写它以使用您的字符集而不是字节。另一个想法是构建一个在您的字符集和任意字节字符串之间的一对一映射，将原始字符串映射到字节字符串，使用标准压缩实用程序或函数压缩字节字符串，然后使用您的字符集将结果映射回字符串。（严格来说，您可以使用两个不同的映射。）构建映射的一种方法是使用虚拟字符和特殊填充字符填充您的字符集，直到您拥有2^k个不同的字符（对于某个k）；然后，您的每8个字符对应k个字节（较短的字符串可以用填充字符填充）。

- reinierpost

Answer 3

您对“特殊字符”的要求非常严格，除非您能保证不会使用字符的子集（例如“~”），否则这将非常限制。然后，您可以使用这些字符来标记您的压缩内容：

~a -> the ~b -> The ~c -> and ~d -> And ~e -> Sirius Robotics Corporation Ltd. 等。

只需在代码本中添加常用单词即可。代码本可以固定，如上所述，也可以随文本变化而变化。无论哪种方式，解压缩端都需要访问正确的代码本来进行解压缩。

- rossum

Answer 4

据我所知，允许重用标准C字符串处理例程来处理压缩文本的最流行的压缩算法（即小心避免将任何0x00字节放入压缩字符串中，除非作为压缩数据结束标记）是简单字节对编码，也称为双瓦片编码或DTE。DTE通常用于压缩视频游戏ROM中的文本。

当DTE解压缩器打印出DTE压缩字符串时，它会从DTE压缩字符串中每次读取1个字节，并打印出1或2个字节：

• 范围在0x01..0xFF之间的压缩字节B：解码器使用该字节作为索引进入“字典”，并打印出存储在该索引处的字典中的1或2个字节。
• 压缩字节B为0x00，则表示字符串结束--完成。

典型的DTE实现在编码器和解码器中都有一个硬连线字典，类似于以下内容：

经常使用的字母索引——也许是整个 ASCII 可打印字符范围 0x20 到 0x7e，以及换行符 0x0A——代表它们本身。（压缩字节'a'被解码为单个字母'a'）

从0xc0到0xff的索引：将该字节解码为2个字符：一个空格字符和一个由该字节异或0x80形成的字母。（压缩字节（0x80异或'a'）被解码为2个字符：空格字符和字母'a'）。

任何其他可用索引（0x7f..0xbf）存储其他常见的二元组（“th”，“re”等）。

- David Cary