Universal Compression of Large Alphabets with Constrained Compressors

Over unknown, possibly large, alphabets, one approach for compressing sequences is to separately convey their symbols and patterns (sequences of integers representing orders in which the symbols appear). It has been shown that patterns generated by i.i.d. sources can be compressed with diminishing redundancy using compressors that know the number of occurrences of each integer symbol. Motivated by applications with resource restrictions, e.g., data deduplication, we study universal compression of patterns using compressors under constraints. A characterization of constrained compressors is given and general results for computing redundancies are derived. We also show that for patterns generated by i.i.d. sources over an alphabet of size k, the per-symbol average- and worst-case redundancies are at least Θ(log(min(k, n/ logn))) bits (n is the sequence length), under the constraint that compressors only know the number of distinct integer symbols in the pattern. A simple sequential compressor satisfying this constraint is also analyzed and shown to achieve this redundancy in the first order term.