LZW压缩和字典

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

哈希表有意义，但我不明白我将如何'重新分配'值。如果表格满了，我需要能够开始覆盖先前（最老的）多字符字典条目。哈希表需要我跟踪这些，找到它，删除它，然后插入新的。

有什么建议吗？

2012-07-22 DillPixel

有什么阻碍你使用'std :: map'或其他标准映射实现吗？ – 2012-07-22 15:59:19

那么，有人只需要问“libbzip2有什么问题”？ :-) – 2012-07-22 15:59:24

@ChristianStieber可能是什么问题，它不支持极快的LZW压缩？ – 2012-07-22 16:01:54

什么你要找的实际上是2层数据结构放在一起：

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

这个想法是，无论何时你想丢弃最早的字典条目，你都会弹出队列中的最后一个元素，然后将它从哈希表中删除。

2012-07-22 16:49:23

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

除了教学或娱乐价值之外，没有理由写新的LZW代码。这只是历史利益。你也可以研究这种教学和娱乐的压缩工具。

2012-07-22 16:50:38

这应该是一个评论，而不是一个答案。 – akappa 2012-07-22 17:01:16

我不能以同样的方式使用链接，也不能在评论中添加段落。 – 2012-07-22 17:03:20

对压缩源代码及其策略的引用使得这是一个正确的答案，还有一个很好的建议。 +1。 – akappa 2012-07-22 17:17:27

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

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

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

2012-07-22 17:06:57 akappa

回答