c++ - 使用重复字符压缩字符串

Question

我的字符串只包含“U”、“D”、“L”、“R”字符(迷宫中的方向)。

字符串可能看起来像这样:

• RRRRRDRRDDDRRUUUUDDRRRRUULLU
• DDLDDLDDLDDLDDLDDLDDLDDLDDLDDL
• LUUURRDRRDLUUURRDRRD

我想压缩这个指令序列。

例如。

1.压缩前:ULULUL压缩后:3(UL)

2。压缩前:DDLDDLDDLDDLDDLDDLDDLDDLDDLDDL压缩后:10(DDL)

3。压缩前:LLLLDLLLLDLLLLD压缩后:3(4LD)

有人知道这样的算法吗？

谢谢。

Answer 1

不，不要使用游程编码，结果会很糟糕。

相反，进行位打包:将四个方向中的每一个编码为 2 位，然后将四个 2 位对打包成一个字节。

因此:U = 00b (0d)，D = 01b (1d)，L = 10b (2d)， R = 11b (3d).

(注:'b'后缀表示二进制，'d'后缀表示十进制。)

因此，LLLL = 10101010b 只有 1 个字节长。

编辑

从 OP 的评论来看，压缩的结果需要是一个仅由可打印字符组成的字符串。那么，我会说 OP 需要的算法称为 Huffman Coding (wikipedia) .我不知道有任何生成可打印文本的实现(因为大多数人会发现这样的事情会完全破坏压缩的目的)，但理论上可以以输出可打印字符的方式实现算法.无论如何，OP 正在询问是否有人知道这样的算法，所以，就是这样。