on-the-fly decompress a flat-file database

Question

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!

Answer 1

What is "too large to fit in memory"? Current operating systems can handle processes with GiB of memory, if you use e.g. mmap(3) on Unix/Linux, you can work as if you had the whole file in memory and access it at random. That might be much faster than compressing/uncompressing on the fly. And (if I understand your question correctly) you want to access individual records (i.e., rows) by key, so you will have to compress only the remaining row and keep the key, working one row at a time (you don't want to have to uncompress from the start to be able to access row 102354 each time, don't you?). That will severely limit the compression gain.

If you can preprocess the data (a given, since you talk about compressing it), perhaps an even better bet is to use a simple(ish) database to store it, like Berkeley DB, the Unix standard DBM or it's GNU take GDBM or other, more modern, for performance tuned ones like Lightning Memory-Mapped Database LMDB.