Hi!

I am currently looking a bit into online compressed data structures. A library that I’ve found is Kmett’s compressed (@hackage/compressed) which e.g. offers an LZ78 implementation which can be compressed with differingly efficient methods and decompressed into some Monoid. However, it doesn’t allow for typical operations on strings while maintaining its compression, i.e. “online”.

This is important when we start from a generator (of the string) which can build an exponential size generator but we know can be practically compressed to something that is polynomial in the input size.

A scheme that makes this possible is e.g. described in Maintaining dynamic sequences under equality tests in polylogarithmic time | Algorithmica but it’s not very approachable and a very old paper so I was wondering whether there were some more modern approaches to the topic and/or implementations, e.g. stemming from BioInf research which also seemed to be a big topic in the Haskell ecosystem, historically.

The operations that I’m particular interested in being possible in polynomial time in the compressed input (and hence logarithmic on the uncompressed input) are

- equality
- concatenation
- splitting at a particular index

Mind that already equality in sublinear time can already only work if the input is compressed.

Thanks in advance for your input!