Bounded Size Dictionary Compression: Relaxing the LRU Deletion Heuristic

The unbounded version of the Lempel-Ziv dynamic dictionary compression method is P-complete. Therefore, it is unlikely to implement it with sublinear work space unless a deletion heuristic is applied to bound the dictionary. The well-known LRU strategy provides the best compression performance among the existent deletion heuristics. We show experimental results on the compression effectiveness of a relaxed version (RLRUp) of the LRU heuristic. RLRUp partitions the dictionary in $p$ equivalence classes, so that all the elements in each class are considered to have the same ``age'' for the LRU strategy. Such heuristic turns out to be as good as LRU when $p$ is greater or equal to 2 (RLRU2). RLRU2 is slightly easier to implement than LRU in addition to be more space efficient.