4 ms·
It depends on what you want to do. RePair [1] is currently the best grammar-based compressor, but it doesn't give good theoretical guarantees. In theory, instea
by ot 13y ago
It depends on what you want to do. RePair [1] is currently the best grammar-based compressor, but it doesn't give good theoretical guarantees. In theory, instead, there is an O(log n) approximation to the smallest grammar problem [2], but AFAIK doesn't work very well in practice. In the same paper there is a good introduction to the problem and an analysis of the previous algorithms, including Sequitur.
[1] http://www.larsson.dogma.net/dcc99.pdf http://www.larsson.dogma.net/dcc99.pdf
[2] http://www.cs.virginia.edu/~shelat/papers/GrammarIEEE.pdf http://www.cs.virginia.edu/~shelat/papers/GrammarIEEE.pdf
- jmmcd 13y agoThanks. I think RePair can be regarded as grammar-based (though they don't say so), but I don't think it produces a grammar which would be useful in any context other than reproducing the original sentence. What I would really love (and maybe I'll just have to write it myself?) is a practical algorithm (not too worried about worst-case guarantees etc) which produces a semi-readable grammar from multiple example sentences, and can then be turned around to generate lots of new sentences.
- ot 13y agoThe concept of grammar compression basically didn't exist at the time RePair was published, but it is by all means a grammar compressor (same goes for LZ78). If you are interested in learning what a grammar should look like (which is very different from optimizing the number of rules) you may want to look into stochastic grammars http://en.wikipedia.org/wiki/Stochastic_grammar http://en.wikipedia.org/wiki/Stochastic_grammar.
- jmmcd 13y agoWell, yes, all my grammars are stochastic (else I'd be generating the same piece of music every time).