Hello Stefan, Sunday, July 8, 2007, 7:22:03 PM, you wrote:

This is very true - but -fvia-C isn't really C.

If you want to see what a difference exists between true C and the NCG, try compiling your program with -fvia-C -unreg

even better, try to to use jhc. it compiles via gcc and unlike ghc, it generates natural code. as result, it's only haskell compiler that is able to generate C-quality code: http://thread.gmane.org/gmane.comp.lang.haskell.glasgow.user/8827 -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Bulat Ziganshin wrote:

Hello Andrew,

Sunday, July 8, 2007, 7:07:59 PM, you wrote:

i don't think that ppm is so complex - it's just probability of symbol in some context. it's just too slow in naive implementation

Oh, sure, the *idea* is simple enough. Trying to actually *implement* it correctly is something else... ;-) (Same statemenst go for arithmetic coding, really.)

...

(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...)

the devil in details. just imagine size of huffman table with 64k entries :) huffman encoding is inappropriate for lzw output simply because most words will have only a few occurrences and economy on their optimal encoding doesn't justify price of their entries in the table

...which is why you need to "encode the Huffman table efficiently", to quote myself. ;-) Using canonical Huffman, you only actually need to know how many bits were assigned to each symbol. This information is probably very ameanable to RLE. (Which, incidentally, is why I started this whole "parser on top of a phaser" crazyness in the first place.) So, yeah, there may be 64k symbols - but if only 1k of them are ever *used*... ;-)

...

.ru = Russia?

of course

My Russian is very rusty. ;-)

...

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. ;-)

15 years ago i've written very smart asm program (btw, it was ARJ unpacker) with handmade function inlining, loop unrolling, register allocation, cpu recognition and so on. now, most of these tricks are standard for C compilers. times changes and now it's hard to imagine which optimizations will be available 10 years later

Yes, but there are limits to what an optimiser can hope to accomplish. For example, you wouldn't implement a bubble sort and seriously expect the compiler to be able to "optimise" that into a merge sort, would you? ;-)

ghc's native and via-C modes are blind vs lame. in native mode, its codegenerator is comparable with 20 years-old C codegenerators. see above how much modern C compilers changed in these years. in via-C mode it generates unnatural C code which is hard to optimize for any C compiler.

I'll take your word for it. ;-) (I have made cursory attempts to comprehend the inner workings of GHC - but this is apparently drastically beyond my powers of comprehension.)

the jhc is very different story

Yes - last I heard, it's an experimental research project rather than a production-ready compiler...

On Mon, Jul 09, 2007 at 09:15:07PM +0100, Andrew Coppin wrote:

Bulat Ziganshin wrote:

...

Hello Andrew,

Sunday, July 8, 2007, 7:07:59 PM, you wrote:

i don't think that ppm is so complex - it's just probability of symbol in some context. it's just too slow in naive implementation

Oh, sure, the *idea* is simple enough. Trying to actually *implement* it correctly is something else... ;-)

Took me about an hour and 50 lines of code (about a year ago - this was one of my first Haskell programs) to implement a PPM (de)compressor that didn't crash, always generated the same output as input, and achieved 50% ratios on its own source code (not quite as good as gzip, but what do you expect from a completely untuned compressor?). Peak throughput: 2 bits / sec. :)

...

the jhc is very different story

Yes - last I heard, it's an experimental research project rather than a production-ready compiler...

Correct. It requires 5 minutes and 600MB of RAM to compile Hello, World, and fails with internal pattern match errors on anything significantly larger. Stefan

G'day all. Andrew Coppin wrote:

...

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!

Not really. LZW is basically PPM with a static (and flat!) frequency prediction model. The contexts are build in a very similar way. Quoting Bulat Ziganshin :

the devil in details. just imagine size of huffman table with 64k entries :)

If you're allowed to pick your code values, you can do this extremely compactly. Some compression schemes optimised for English separates words from the intermediate space and assigns a Huffman code to each word. The tables aren't that big (though the space to hold the words might be). Cheers, Andrew Bromage

Bulat Ziganshin wrote:

Hello ajb,

Wednesday, July 11, 2007, 7:55:22 AM, you wrote:

...

Not really. LZW is basically PPM with a static (and flat!) frequency prediction model. The contexts are build in a very similar way.

what you mean by "flat" and "static" applied to PPM? static PPM models exist - they carry probabilities as separate table very like static Huffman encoding. is "flat" the same as order-0?

I think he meant "flat" as in "pr(z) = 0 | 1"... As for "static", I'm not so sure that's actually correct.

Hello ajb, Thursday, July 12, 2007, 9:25:35 AM, you wrote:

...

what you mean by "flat" and "static" applied to PPM? static PPM models exist - they carry probabilities as separate table very like static Huffman encoding. is "flat" the same as order-0?

"Static" means that the frequency distribution is fixed. "Flat" means that the frequency histogram is flat. (Every code word is predicted to occur with the same frequency, resulting in a binary code.)

well, ppm differs from simple order-0 coder in that it uses previous symbols to calculate probability. lzw differs from order-0 coder with flat static probabilities in that it encodes a whole word each time. there is nothing common between ppm and lzw except for this basic order-0 model, so i don't see any reasons to call lzw a sort of ppm. it will be more fair to say that lzw is order-0 coder with static flat probabilities, you agree?

...

can you give a link? i never heard about such algorithm

http://en.wikipedia.org/wiki/Canonical_Huffman_code

you said about algorithm that efficiently encodes english words using huffman codes. is such algorithm really exists? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Hello ajb, Thursday, July 12, 2007, 12:16:22 PM, you wrote:

...

well, ppm differs from simple order-0 coder in that it uses previous symbols to calculate probability. lzw differs from order-0 coder with flat static probabilities in that it encodes a whole word each time.

LZW doesn't have the concept of a "word" at all.

in this case why you proposes to encode lzw words with a huffman codes? :)

Both PPM and LZW build up contexts as they go by starting with one context for each symbol in the input alphabet, and by extending contexts with single symbols as they are found. (Conceptually; the algorithms are slightly different, but they do the same job.)

The difference has to do, almost completely, with coding. LZW uses a degenerate model to decide what the next input symbol is. It assumes that all "seen" contexts are equally likely, and hence uses a binary code to encode them. (A "binary" code represents the numbers 0 to k-1 using k codewords each of which is (log k) bits in length.)

oops. ppm build tree of contexts and use context to encode one char. lzw builds dictionary of words and encode word in empty context. encoding in empty context is equal to order-0 coder while "prediction by partial matching" by definition is order-N, N>0 encoding. so lzw can't be considered as degenerate case of ppm although programming techniques (building tree of words/contexts) are pretty close

...

it will be more fair to say that lzw is order-0 coder with static flat probabilities, you agree?

That's the _coding_ phase, sure.

you are right. so lzw is just dictionary-based transformation which replaces some words with special codes while ppm replaces chars with their probabilities. i hope you will agree that ppm with flat codes will be totally useless

...

you said about algorithm that efficiently encodes english words using huffman codes. is such algorithm really exists?

Ask Google about "word-based huffman".

about which particular algorithm you said? Moffat? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

G'day all. Quoting Bulat Ziganshin :

in this case why you proposes to encode lzw words with a huffman codes? :)

I don't. :-)

oops. ppm build tree of contexts and use context to encode one char. lzw builds dictionary of words and encode word in empty context.

As you noted later, the "dictionary of words" in LZW is also tree- structured. "Words", as you call them, are built by extending words with single characters, in pretty much exactly the same way that PPM contexts are built by extending contexts with single characters. The main difference is this: To encode a "word" in PPM, you encode the conditional probability that it takes to get to the end of the word from the start of the word. It looks like you're encoding single characters (and, programmatically, you are), but because of the way that arithmetic coding works, it's mathematically equivalent to encoding the probability of finding the word as a whole. You're just decomposing the probability of finding the word into the probabilities of finding the individual input symbols along the way. Does that make sense?

you are right. so lzw is just dictionary-based transformation which replaces some words with special codes while ppm replaces chars with their probabilities. i hope you will agree that ppm with flat codes will be totally useless

Absolutely. But augmenting LZW with probabilities to allow for arithmetic coding wouldn't be so dumb, if it weren't for the fact that a) we already have more efficient compression algorithms, and b) it'd destroy the main benefit of LZW (which is that it's effective on slow CPUs with small memories; perfect for 80s-era micros and 8-bit embedded systems).

about which particular algorithm you said? Moffat?

Yes, though if your local university library has a copy, "Managing Gigabytes" might be a better introduction to the topic. Cheers, Andrew Bromage

G'day all. Quoting Bulat Ziganshin :

it seems that you either misunderstood PPM or make too wide assumptions.

More likely I'm not explaining myself well.

in classical fixed-order ppm each char probability found in context of previous N chars. i.e. when encoding abcdef.. with order 3, 'd' encoded in context of 'abc', 'e' encoded in context of 'bcd' and so on

Let's suppose that "abcdef" is a context in PPM, and we're starting from the "start" state (which usually isn't the case, of course). Then to encode it, you encode the probability of finding an "a" in the start state, followed by the probability of finding a "b" in the "a" state, followed by the probability of finding a "c" in the "ab" state... The effect of encoding these multiple symbols is equivalent to the effect of encoding a single symbol, whose probability is the individual probabilities multiplied together. Or, if you like, it's the conditional probability of encoding a string starting with "abcdef" from the start state, taken as a proportion of _all_ possible encoded strings. Pr("abcdef"|"") = Pr("a"|"") * Pr("b"|"a") * Pr("c"|"ab" ) * ... LZW uses a simpler model, estimating Pr("abcdef"|S) as 1/N, where N is the number of "states" seen so far. Cheers, Andrew Bromage

G'day. Quoting Bulat Ziganshin :

sorry, but you really misunderstand how PPM works and why it's so efficient.

I understand PPM. I really do. I think what you don't understand is why LZW does as well as it does considering how simple it is. It's because it's a poor but cheap approximation to what PPM does. Part of the misunderstanding is that you're looking at what PPM does algorithmically, whereas I'm talking about what it's equivalent to mathematically. It turns out that pretty much all known text compression algorithms are "equivalent" in the sense that they give the same compression ration on the same text to within a (possibly large) constant factor. BZip, for example, gives a compression ratio that's almost always within 5% or so of the best PPM variants given an input text. How could that be, since they're so different? The answer is that they're actually _not_ that different, mathematically speaking. Cheers, Andrew Bromage

ajb@spamcop.net wrote:

G'day all.

Andrew Coppin wrote:

...

...

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!

Not really. LZW is basically PPM with a static (and flat!) frequency prediction model. The contexts are build in a very similar way.

Yes - but making it use a non-flat model opens a whole Pandora's Box of fiddly programming. ;-) (It's not "hard" as such - just frustratingly fiddly to get correct...)

Thomas Conway wrote:

On 7/12/07, Andrew Coppin wrote:

...

Yes - but making it use a non-flat model opens a whole Pandora's Box of fiddly programming. ;-)

This could just about be Rule No 1 of haskell programming: if it's fiddly, then you haven't thought about the problem hard enough.

Corollary No 1 is Any Expression requiring more than 80 columns is fiddly.

:-)

I say this in jest, but it is "ha ha, only serious".

LOL! Probably... The idea behind PPM is very simple and intuitive. But working out all the probabilities such that they always sum to 100% is surprisingly hard. :-(