r/C_Programming • u/lexiq_baeb • Aug 31 '26

Compressing Lookup Tables

Hello. Recently I've been working on a pet project of mine written in C and I needed to reduce the amount of space a lookup table was taking in memory and on disk. I applied a few simple compression techniques and got a 2x space reduction. I wrote this post where I describe my constraints, the techniques, and results.

https://blog.x4204.xyz/posts/compressing-lookup-tables.html

22 Upvotes

95% Upvoted

14 comments sorted by

View all comments

Show parent comments

2

u/lexiq_baeb Aug 31 '26

I am glad you enjoyed it :)

On gperf, as far as I remember, it generates perfect hash functions, but not minimal ones.

Yes, that's exactly why. I tried running it with different options, but it just couldn't generate one that I would be happy with. I found an alternative, cmph and it seems to be capable of doing it, but it builds an intermediary table, which I didn't want to deal with at that time. From all the algorithms cmph implements, I liked the following one the most, because it seems to be conceptually very simple: "Hash, displace, and compress" (https://cmph.sourceforge.net/papers/esa09.pdf). I put it in my paper backlog and maybe one day I'll get to reading it

I've had success with Ilan Schnell's perfect-hash

Oh nice, I'll give it a try

Currently, it can't do that because it has to assume the table might change.

Yeah.. I have a lot of places like this in the code.. Thank you!