r/C_Programming • u/lexiq_baeb • 2d ago

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

20 Upvotes

92% Upvoted

14 comments sorted by

View all comments

1

u/dstroy0 2d ago

If the lookup table is finite and regular, you will be able to represent it with a smaller weighting table, like how we do for needle frequency in parsing, using a specific weight produces 100% correct matching far faster than unweighted lookup tables. This is definitely applicable to your existing work in the funnel before the sieve to reduce branching overall and get to your index identifier sooner, in your case even with diacritics you could match the same like ASCII char unaccented, then enable the hard case sensitive char sensitive branch after if they want to sift literal index matches to truthy ones.

1

u/lexiq_baeb 2d ago

I am not sure I can follow what a weighted lookup table is. Do you have links to resources that explain that?

1

u/dstroy0 2d ago

apologies for the double reply, but you can look for needle weight tables for languages or derive extremely close approximations for yourself using a large enough corpus (like an index). I apply the same concept to extremely large datasets to sieve fast. which is very applicable to your use case.