Compression techniques

[infogulch]

I found some things that could improve compression in certain contexts:

Burrows-Wheeler Transform (BWT)

The algorithm is a bit odd, but after the transform, characters that appear frequently together in the original string tend to cluster together in the transformed string. This locality can be exploited by run-length encoding or other compression techniques. It can also be used as an index for fast searching ¹.

A naive implementation of the algorithm: 1. Generate all possible rotations of the input string. 2. Sort these rotations lexicographically (alphabetically). 3. Extract the last character of each sorted rotation to form the transformed string.

Somewhat surprisingly this algorithm is actually reversible (!?). It's also related to the FM-index. ^{2 3}

Footnotes

1. https://web.archive.org/web/20160304013343/http://blog.avadis-ngs.com/2012/04/elegant-exact-string-match-using-bwt-2/ ↩

2. https://cbloomrants.blogspot.com/2021/03/faster-inverse-bwt.html ↩

3. https://www.alexbowe.com/fm-index/ ↩

[infogulch]

ZStandard Random Access

https://github.com/zraorg/ZRA

ZSTD has the concept of a Frame which can be decompressed independently from the rest of the file. A ZSTD archive is made of multiple concatenated frames which are decompressed one after another.

We exploit that fact to break the file into uniformly sized frames (Frame Size) and creating a seek-table which contains the offset of each frame within in the file which can be indexed by simply dividing the offset by the frame size.

This project is archived now (but it's C++ anyway so). But the idea is sound: store frame and source text offset metadata, and you can seek into the middle of a large body of compressed text.

[infogulch]

A more recent implementation:

https://crates.io/crates/zeekstd

A Rust implementation of the Zstandard Seekable Format.

The seekable format splits compressed data into a series of independent "frames", each compressed individually, so that decompression of a section in the middle of an archive only requires zstd to decompress at most a frame's worth of extra data, instead of the entire archive.

Commentary: https://news.ycombinator.com/item?id=44284871

[gatesn]

@mwlon any thoughts on this?

[mwlon]

That's exactly what the vortex-zstd encoding does now.

[infogulch]

It might be worth consolidating or collaborating. Based on the commentary, the implementation in the zstd repo is not officially standardized (it's in contrib), so converging on an implementation may help push the standardization process and ensure future compatibility.