LZW压缩和字典

Question

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

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

有什么建议吗？

Answer 1

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

1. 哈希表。
2. 先进先出队列(丢弃旧表条目)。

如果您正在寻求实践，如您的评论所建议的那样，您可以自己实现它们，或者使用stl/ sgi /c++11实现(unordered_map是通过sgi或c++11的实际散列映射，而先进先出队列是一个双向链表，比如std::deque)。

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

Answer 2

Unix compress utility (source code link)使用双重散列和元素周期表清除。

如果你想要快速压缩和解压，那么有比LZW更好的选择，LZW已经过时得可怕了。您应该考虑在zlib (可能已经在您的机器上)、LZO和lz4中进行快速的1级压缩。

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

Answer 3

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

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

在解压缩时，您可以通过更传统的方式访问字典，即通过键。然后，您可以使用任何关联数组结构。比如哈希表或者字符串的向量/二进制(因为你的索引是连续的自然数)。