3 ms·

Thanks. 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 contex

by jmmcd 13y ago

Thanks. 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 ago
The 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 ago
  Well, yes, all my grammars are stochastic (else I'd be generating the same piece of music every time).