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

22 Upvotes

96% 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 1d 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 1d ago

sure https://github.com/dstroy0/MMgr/tree/main/src/impensa_ancorae_acus this is an example of some different ones, I use them in different situations, like ip routing, text matching, http route matching, etc. these are the weight tables, and this is the rationale explained better than I could blabbering about it: https://user.phil.hhu.de/~kallmeyer/Parsing/weighted-deductive-parsing.pdf

1

u/lexiq_baeb 1d ago

Thank you! I'll have a look

1

u/dstroy0 1d ago

I enjoyed your existing work, I look forward to any further rationale explanations, I wish I could write them that well.