# on-the-fly decompress a flat-file database

I'm facing the following problem. I have a flat-file database (e.g. CSV). Since it's relatively large to store in memory, I'd like to compress it.

Given a key, I need to return the uncompressed text (record of values).

So one naive idea is to tokenize the text into words and to have the mapping $$\text{word} \mapsto \text{codeword}$$

Of course, this naive idea lacks of understanding of statistical properties in the data, that other compression algorithms exploits.

So the next thing I thought about is Huffman code. The problem I'm facing is that I'd like to find the optimal tokenization for the text. Let's say that one column in the CSV file contains only the text "the fox jumped over the lazy dog", it reasonable to want that the algorithm would tokenize this string as one token.

but then again, going over all possibilities isn't a feasible task. Are there any algorithms that deals with this problem?

So to summarize, I need to:

1. Compress my data once and to decompress on demand
2. Return the requested value (a record) for a given key
3. Decompression should be "fast enough"

Which algorithms fit my problem?

In particular, I'd like to know if Huffman code is a good option, and if so, how to tokenize the text.

Thanks!

• You can use Lempel–Ziv, which in a sense finds an optimal tokenization of the data. Running Lempel–Ziv on part of the data, you can use the tokens it generates for your Huffman code. – Yuval Filmus Apr 4 at 15:08