0
$\begingroup$

I am targeting a simple dictionary-coder compression algorithm that uses a static dictionary (code in an existing program, but I can supply my own dictionary). How can I write a compressor for such an algorithm? The first thought I had was to rank all strings in the data by the size reduction from making them dictionary entries, but then what? When some of those strings overlap, the amount of compression achieved depends on which mutually exclusive substitutions you make. How can I find the optimal dictionary and optimal set of substitutions?

The dictionary references are all the same size, by the way, so this isn't like Huffman encoding.

$\endgroup$

1 Answer 1

1
$\begingroup$

The simplest approach is to use the known text as a "priming text". Conceptually, you run whatever compression algorithm you want on the concatenation of the priming text and the text you want to compress, compress it, but don't transmit the compressed priming text.

Exactly how you realise this idea depends on the compression method. For example, if it were a LZ77 method, you could pre-fill the sliding window with the priming text. For the coding stage, you could train an adaptive coder on the priming text, and then use that for the initial coding model.

For methods that are more like LZ78 or PPM/DMC, you could build an initial model/dictionary on the priming text, and go from there.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.