Compression for random access

[IngisKahn]

Not sure if this is on topic here, but I am interested on opinions.

Problem:
I have tables of around 100k text strings from 1-1500 characters and am looking for a strategy for storing compressed versions for random access. Insertion performance is not a concern.

What I've done:
I take all the strings and based on some silly weighting logic based on length and occurrences, I turn it into a list of shared substrings.
That list of substrings is then turned into one block of text by merging largest overlaps.
This block of text (usually around 30k) becomes the training data for an LZMA encoder.
I modified the 7zip source to be able to (after encoding or decoding the training data) quickly restore state and be able to process each entry.

I know this whole effort is rather silly (it would probably be better to just compress the whole database and be done with it), but does this approach make sense? Was LZMA a good choice? I've only just now discovered the Large Text Compression Benchmark (which is how I ended up here somehow) so I have a lot to play with now.

[Shelwien]

Hi, welcome.

Somehow we don't have much string compression implementations, but I feel that 1500-byte strings may be short enough to try something more advanced than LZ (maybe PPM?).

The most recent related topic: https://encode.su/threads/3322-LittleBit-0-1-alpha https://github.com/kapenga/LittleBit/

Also zstd and brotli have integrated dictionary support... zstd even has integrated dictionary generation from a set of files.

This is my hack for ppmd dictionary mode: http://nishi.dreamhosters.com/u/pmd_dict_v0s.7z

This is plain arithmetic coder for random access to strings with bit alignment: https://encode.su/threads/3174-Finit...ll=1#post61256
Should be possible to switch to order1-2 without much changes.

[Kaw]

Thanks Shelwien for mentioning LittleBit.

LittleBit is made for this purpose. You should be able to compress the tables to sizes that are on par with common mid range compression algorithms. Compression is slow but 100k tables should be a matter of seconds. Because of the static nature of the Huffman table decompression is as fast as your IO can handle.
Also your approach seems to be a little complicated for the subject. If the tables are static of nature then LittleBit might be the tool for you.

[Shelwien]

> Also your approach seems to be a little complicated for the subject.

I think he just added external dictionary support to LZMA and used some heuristic method to generate shared dictionary for strings.

Its actually a good idea imho - LZMA has better compression and lower overhead (no headers) than zstd/brotli.
Could be good to also use this patch: https://encode.su/threads/1546-init-...terals-in-lzma