我正在研究在C++中實現LZW壓縮,並且不確定最好的字典實現。LZW壓縮和字典
哈希表有意義,但我不明白我將如何'重新分配'值。如果表格滿了,我需要能夠開始覆蓋先前(最老的)多字符字典條目。哈希表需要我跟蹤這些,找到它,刪除它,然後插入新的。
有什麼建議嗎?
我正在研究在C++中實現LZW壓縮,並且不確定最好的字典實現。LZW壓縮和字典
哈希表有意義,但我不明白我將如何'重新分配'值。如果表格滿了,我需要能夠開始覆蓋先前(最老的)多字符字典條目。哈希表需要我跟蹤這些,找到它,刪除它,然後插入新的。
有什麼建議嗎?
什麼你要找的實際上是2層數據結構放在一起:
如果您正在按照您的意見建議尋找練習,或者使用stl/sgi/C++ 11實現(您可以自己實現它們)(unordered_map是實際的哈希映射,可以通過sgi或C++ 11,而一個FIFO隊列是一個雙向鏈表,如std :: deque)。
這個想法是,無論何時你想丟棄最早的字典條目,你都會彈出隊列中的最後一個元素,然後將它從哈希表中刪除。
Unix compress utility (source code link)使用雙散列和週期表清除。
如果你想快速壓縮和解壓縮,那麼有遠比更好的選擇比LZW,這是可怕的過時。您應該查看zlib(可能已在您的機器上),LZO和lz4中的快速1級壓縮。
除了教學或娛樂價值之外,沒有理由寫新的LZW代碼。這只是歷史利益。你也可以研究這種教學和娛樂的壓縮工具。
您必須在壓縮和解壓縮中使用兩種不同的結構。
壓縮時,您應該使用Trie,因爲您必須按內容搜索字典而不是按鍵。
解壓縮時,可以用更常規的方式訪問字典,即按鍵。 然後,您可以使用任何關聯數組結構。像哈希表,甚至是一個向量/字符串(因爲你的索引是連續的自然數)。
有什麼阻礙你使用'std :: map'或其他標準映射實現嗎? – 2012-07-22 15:59:19
那麼,有人只需要問「libbzip2有什麼問題」? :-) – 2012-07-22 15:59:24
@ChristianStieber可能是什麼問題,它不支持極快的LZW壓縮? – 2012-07-22 16:01:54