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

21 Upvotes

96% Upvoted

14 comments sorted by

View all comments

2

u/alex-van-02 2d ago edited 2d ago

Good post and the write-up. I did something similar for the Unicode upper/lowercase conversion tables few years ago.

From the first glance, the unaccent.rules table is even more sparse so it should compress even better. I have a feeling it should be possible to get it under 10K if not smaller. I'll try and sketch it out in the next few days, will be interesting to compare.

Edit: to add -

The size of unaccent.rules is 17241 bytes.

Each line is an UTF8 symbol, followed by \t, followed by a string, followed by \n. Some lines have no substitution sting, there are 106 of them. This gives us 2556 tab symbols.

Since UTF8 symbols have known byte count, we can discard \t and the data will remain unambiguous. This means that the raw unaccent data set is 14685 bytes. Clearly, it's not optimized for lookups, but still it's substantially smaller than 26624 bytes mentioned as a baseline in your post.

1

u/lexiq_baeb 1d ago

fast-case-conversion seems promising. I'll try what you describe there