c++dictionarycompressionlzw

LZW compression & dictionary

I'm looking into implementing LZW compression in C++, and not sure of the best dictionary implementation.

Hash table made sense, but I don't understand how I would be able to 'reassign' values. If the table gets full, I need to be able to start overwriting previous (oldest) multi-char dictionary entries. Hash table would require me to keep track of these, find it, remove it, and then insert the new one.

Any suggestions?

Solution

  • What you're looking for is actually two data structures put together:

    1. A hash table.
    2. A FIFO queue (to discard old table entries)).

    You can implement them yourself if you're looking for practice as your comments suggest, or use the stl/sgi/c++11 implementations (unordered_map is the actual hash map, either through sgi or c++11, and a FIFO queue is a doubly linked list, such as std::deque).

    The idea is that whenever you want to discard the oldest dictionary entry, you pop the last element in the queue, and then remove it from the hash table as well.