c++ - LZW 压缩和字典

Question

我正在研究在 C++ 中实现 LZW 压缩，但不确定最好的字典实现。

哈希表是有道理的，但我不明白我如何能够“重新分配”值。如果表已满，我需要能够开始覆盖以前的（最旧的）多字符字典条目。哈希表需要我跟踪这些，找到它，删除它，然后插入新的。

有什么建议么？

Answer 1

Unix compress 实用程序（源代码链接）使用双散列和周期表清除。

如果你想要快速压缩和解压缩，那么有比LZW 更好的选择，LZW 已经过时了。您应该查看zlib（可能已经在您的机器上）、LZO和lz4中的快速 1 级压缩。

除了教学或娱乐价值之外，没有理由编写新的 LZW 代码。它只具有历史意义。您还可以研究用于此类指导和娱乐的 compress 实用程序。

Answer 2

您必须在压缩和解压缩中使用两种不同的结构。

压缩时，您应该使用Trie，因为您必须按内容而不是键搜索字典。

解压缩时，您以更传统的方式访问字典，即按键。然后，您可以使用任何关联数组结构。像哈希表甚至是字符串的向量/双端队列（因为您的索引是连续的自然数）。

Answer 3

您正在寻找的实际上是两个数据结构放在一起：

1. 一个哈希表。
2. 一个 FIFO 队列（丢弃旧表条目））。

如果您正在寻找您的评论建议的练习，您可以自己实现它们，或者使用 stl/sgi/c++11 实现（unordered_map 是实际的哈希映射，通过 sgi 或 c++11，以及一个 FIFO 队列是一个双向链表，例如 std::deque)。

这个想法是，每当您想丢弃最旧的字典条目时，您都会弹出队列中的最后一个元素，然后也将其从哈希表中删除。

Answer 4

您可以尝试在lzws中实现的 2 个字典：

1. 链表，内存使用 <= 327 KB。
2. 稀疏数组，内存使用 <= 33.5 MB。