Re: More details on compression wanted

[Gunnar von Boehn]

> Somebody needs to find or invent a lower overhead
> compression scheme suitable for databases. I'd be
> willing sacrifice amounts of compression to be
> blindingly fast.


Very fast decompression that is magnitutes faster than zip
for texts or string is very easy.


An example a *very fast decompression algotrythm*.
Its as simple and as fast as Runlength but compresses often nearly as good as gzip.
Like runlength you operate in modes.
Runlength can repeat one byte N times, or copy N bytes.
Normal runlength uses 1 byte as control sequence and N can be max 2^7.

To much better compress text you modify the algorythm to have two modes.
a) copying N Bytes
b) to backcopy N Bytes which were appeared in your stream M bytes before.
The allow to encode both N and M for the backcopy command you encode this in two bytes (16bit) you can still encode the normal copy sequence with 8 bit like runlength does.

This algorythm is plain simple and works on bytes size all the time.
Because of this it decompresses nearly as fast as a stringcopy is.
For text blocks is saves all repeated words and syllables.
Typically the compression ratio is nearly as good a zip.

I have used this and similar algorythms a lot in the good old days.
Using such compressing files on hardisk was much faster even with 25 Mhz CPU systems.

Cheers
Gunnar