time - 如何设计一种高效的算法来支持 LZ77 压缩序列中的随机访问？

Question

我正在做一个文本压缩项目，我需要在 LZ77 压缩序列中设计一个有效的算法。特别是，给定一个 LZ77 压缩序列和一个索引 i，我们可以恢复输入序列 S 的单个符号 S[i]。算法消耗的空间和随机访问一个符号的时间是我们追求的。</ p>

提前感谢您的建议。

Answer 1

有关示例，请参见zran.c。它在 gzip 或 zlib 流中构建带有入口点的索引。就未压缩数据而言，您可以选择入口点彼此之间的大致距离。要获取未压缩数据的随机字节，您从该字节之前的最近入口点开始解压缩，并解压缩直到到达该字节。

权衡是更少的存储空间，更少的入口点，但更长的时间来获取任何给定的字节，而不是更多的存储空间和更少的时间。