Dynamic Lightweight Text Compression

Nieves Brisaboa, Antonio Fariña, Gonzalo Navarro, and José Paramá

We address the problem of adaptive compression of natural language text, considering the case where the receiver is much less powerful than the sender, as in mobile applications. Our techniques achieve compression ratios around 32% and require very little effort from the receiver. Furthermore, the receiver is not only lighter, but it can also search the compressed text with less work than the necessary to uncompress it. This is a novelty in two senses: it breaks the usual compressor/decompressor symmetry typical of adaptive schemes, and it contradicts the long-standing assumption that only semistatic codes could be searched more efficiently than the uncompressed text. Our novel compression methods are in several aspects preferable over the existing adaptive and semistatic compressors for natural language texts.