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

回答