[信息与未来 2023] 文本压缩（暂无 SPJ）

在这个问题里，你需要自己设计一个**英文文本的无损压缩和解压缩算法**。你的程序需要同时实现压缩器和解压缩器两部分功能： - 压缩器输入一个**仅由小写字母组成的字符串**，输出一个压缩后的字符串。压缩后的字符串允许使用大写字母、小写字母和数字，但不允许使用其他字符。 - 解压缩器输入一个压缩后的字符串，还原出小写字母的字符串。 注意，在这个问题中，**所有给压缩器的输入都来自人工智能 GPT-3.5-turbo 生成的英文文本保留字母 (并转换为小写) 后得到的**，也就是说，你可以假设除了偶尔的例外，字符串是由英文单词拼接而成的。这个性质是解决问题的关键——随机序列的压缩比 “有规律” 序列的压缩要困难得多。 ## Input 输入数据第一行为一个大写英文单词，代表压缩/解压缩的任务类型。`COMPRESS` 代表压缩；`DECOMPRESS` 代表解压缩。 第二行一个字符串，是压缩/解压缩任务对应的文本。对于压缩任务，是一个仅包含小写字母的字符串；对于解压缩任务，字符串总是来自你程序之前 `COMPRESS` 压缩的结果。 ## Output 输出一行一个字符串。对于压缩任务，输出一行为压缩后的文本；对于解压缩任务，输出一行为解压缩后的文本。 [samples] ## Background 数据压缩算法的目的是减少数据的大小，以便更快地传输和存储。我们经常会用到的 zip、rar 等压缩工具，就是利用数据压缩算法把多个文件或者文件夹压缩成一个更小的文件；我们的网页在传输时，通常也使用了 gzip 压缩。有些时候（例如传输图像、视频时），我们会允许在压缩过程中损失一些精度，以实现更好的压缩比。 ## Note 对于 $100\%$ 的数据，输入字符串的长度 $n$ 满足 $3\times 10^4 \leq n \leq 4\times 10^4$。 --- 本题的评测机会两次调用你的程序： - 第一次调用你的程序执行压缩任务，例如输入 ```plain COMPRESS aaaaaaaabbbbbbbbbb ``` 假设本次调用，你的程序输出了 `a8b10` 作为压缩后的文本。这个输出会被评测系统记住。 - 第二次，调用你的程序执行解压缩任务。针对刚才的例子，我们会为你的程序输入 ```plain DECOMPRESS a8b10 ``` 如果你的程序解压缩输出 `aaaaaaaabbbbbbbbbb`（即正确解压缩得到原字符串），则被判定为“还原正确”。 对于每个测试数据，压缩和解压缩分别有 $1\ \text{s}$ 的运行时间限制。 对于每个测试数据，在解压缩能正确得到原字符串的前提下： - 如果压缩率达到 $75\%$（压缩字符串的长度小于等于输入长度的 $\frac{3}{4}$），该测试点得满分。 - 如果压缩率达到 $80\%$（压缩字符串的长度小于等于输入长度的 $\frac{4}{5}$），该测试点得一半分数。 >本题原始满分为 $20\text{pts}$。