[Haskell-cafe] Toy compression algorithms [was: A very edgy language]

[Andrew Coppin]

Bulat Ziganshin wrote:
> Hello Andrew,
>
> Sunday, July 8, 2007, 3:10:04 PM, you wrote:
>   
>> Indeed. I'm more interested in which algorithms produce the best
>> compression ratios than how to implement them fast.
>>     
>
> algorithms you are tried so far (except for bwt+mtf) is the standard
> student's set :)  of those, lzw is most advanced, but even this
> algorithm is 20-year old
>   

Yeah, well, naturally I'm implementing the simple ones first. ;-)

Actually, LZW works surprisingly well for such a trivial little 
algorithm... When you compare it to the complexity of an arithmetic 
coder driven by a high-order adaptive PPM model (theoretically the best 
general-purpose algorithm that exists), it's amazing that anything so 
simple as LZW should work at all!

>> Currently the code
>> uses very general, flexible, polymorphic types all over the place, 
>> everything is normal lists, I'm using monadic parsing rather than 
>> bit-twiddling, etc etc etc. It goes alright with 100 KB files on my
>>     
>
> testing today's algorithms on such small datasets don't make much
> sense because they need much more input to gather enough statistics
> about data compressed. i prefer hundreds-megabytes tests and don't
> know anyone with a test files smaller than 1 mb
>   

OTOH, I'd like it to finish this month...

(LZW is faster now I'm using Data.Map. But even so, 15 minutes to 
compress 640 KB of zeros? That's pretty slow!)

> btw, in most cases, C algorithm with today's C compilers will work
> faster than asm oe - because you should have very good knowledge of
> COU internals to write efficient program. i dream about the days when
> the same will become true for Haskell
>   

We all do... *sigh*

(Or rather, most of us dream. A tiny few people seem to be trying to 
actually do stuff about it...)

> i never heard about lzw+huf compressors :)  there are two lz families
> - lz78 (lzw) which was popular in 80's and used variable-size words,
> and lz77 (lzss) which together with huffman was the most popular in
> 90's. compress (.Z) and pkzip 1 was lzw, while zip is lzh (i.e.
> lz77+huffman) 
>
> there is no much meaning to use huffman with lzw because many words
> will have only one or two occurrences
>   

Hmm... that's interesting. I was *sure* it said that LHA used 
LZW+Huffman... oh well!

You say that there would be "no meaning" to using a Huffman code to 
encode the output from an LZW stage. But consider this: The standard 
approach is for the LZW encoder to spit out 9 bits/symbol initially, and 
than 10 bits/symbol once the table fills up a bit more, and then 11 
bits/symbol after that, and so on. (Usually until some hard-coded limit 
is reached. Typically the encoder just resets itself at that point or 
something.) So we're allocating more and more bits per symbol, but this 
is based only on how full the table is, *regardless* of whether any of 
these new symbols are even in fact *used*. ;-) Now, by using a Huffman 
code (scanning the actual produced output rather than working 
adaptively) we can avoid assigning bit combinations to unused symbols.

(The downside of course is that now we need a Huffman table in the 
output - and any rare symbols might end up with rather long codewords. 
But remember: Huffman *guarantees* 0% compression or higher on the 
payload itself. A Huffman-compressed payload can *never* be bigger, only 
smaller or same size. So long as you can encode the Huffman table 
efficiently, you should be fine...)

> btw, i invite you to the http://encode.ru/forums where you will find
> many compressor authors. you will be second one there who use haskell
> and first one who write compression algorithms in it :)
>   

.ru = Russia?

>> OTOH, if the Gods behind GHC want to take a look and figure out whether
>> there's any magic that can be added to the optimiser, I wouldn't 
>> complain... ;-)
>>     
>> (Realistically though. My program takes a [Word8] and turns it into a 
>> [Bool] before running a parser over it. The GHC optimiser doesn't really
>> stand a hope in hell of optimising that into a program that reads a 
>> machine word into a CPU register and starts playing with bit flips on it...)
>>     
>
> as time goes, those terrible compilers becomes smarter and smarter :)
>   

Oh hey, I think GHC is already pretty smart. But no optimiser can ever 
hope to cover *every* possible case. And transforming [Bool] -> [Bool] 
into UArray Word8 -> UArray Word8 just seems a liiiiittle bit 
optimistic, methinks. ;-)

>
>> PPS. Does GHC make use of MMX, SSE, et al?
>>     
>
> it can do it with via-c compilation and there are plans for native
> codegenerator too.

The way I heard it is that it *does* native code generation, but it's 
"not as good" as the via-C version. (Can't imagine why... You would have 
thought directly implementing functional primitives would be much easier 
than trying to mangle them to fit C's multitude of limitations. Still, 
what do I know?)

> but it seems that you don't know asm and believe in
> advertising hype. i'm pretty sure that mmx can't help in algorithms
> you implementing and you are very far from level of performance where
> using mmx may give any improvement
>   

MMX is probably useless. Some of the streaming stuff (with all the CPU 
cache twiddling and so on) might be useful for list processing. Frankly, 
it *all* seems so low-level that I can't begin to imagine how you could 
ever take advantage of this stuff without writing raw assembly by hand...

(I read the IA32 manual one time. It was a long time ago though. I don't 
remember lots of detail. As for do I "know assembly"... I've programmed 
the 6502 and the M68000, although not extensively. My point is that I 
know my way round the inside of a von Neumann computers, that's all... ;-)