5 ms·

Compression is truly fascinating. It's what got me into reading computer science papers several years ago, and then became one of my research topics. What is s

by ot 13y ago

Compression is truly fascinating. It's what got me into reading computer science papers several years ago, and then became one of my research topics. What is shown here is the LZ77 [1] factorization of a string. Compression in general works by exploiting redundancy in the source, and natural language is highly redundant, since many words repeat often. Hence the factors in the factorization often look like frequent words or n-grams. A recent line of research is grammar compression, which tries to turn a text into a tree of rules that generate that text. While still not very good at general-purpose compression, the generated tree are much more interesting than the LZ77 factorization, since they "discover" something that looks like a syntactic parsing of the string, finding syllabes, words, phrases, sentences... In Craig Nevill-Manning's Ph.D. thesis [2] introduction there are several examples of the inferred grammar of pieces of text, music, fractals, source code, etc... While the algorithm presented there (Sequitur) is now kind of obsolete, the thesis is very interesting because it makes some considerations with a linguistic perspective. [1] http://en.wikipedia.org/wiki/LZ77_and_LZ78 http://en.wikipedia.org/wiki/LZ77_and_LZ78 [2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.1112&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.1...

jmmcd 13y ago
Wow, that PhD thesis is very interesting. I use grammars to generate music (and other things sometimes), but I would also really like to be able to infer them. Since you say it's obsolete, do you have any links to papers or software related to successors of the Sequitur algorithm?
- 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 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).
- kevgnulldev 13y ago
  I do a bit of algorithmic composition as well (mostly microsound/granular synthesis) using NN and other graphical models (e.g. HMMs) for higher level compositional control... for grammar inference check out: http://www.mitpressjournals.org/doi/abs/10.1162/neco.1992.4.3.393 http://www.mitpressjournals.org/doi/abs/10.1162/neco.1992.4.... Abstract: We show that a recurrent, second-order neural network using a real-time, forward training algorithm readily learns to infer small regular grammars from positive and negative string training samples. We present simulations that show the effect of initial conditions, training set size and order, and neural network architecture...
  - jmmcd 13y ago
    That sounds perfect -- thanks!
    - kevgnulldev 13y ago
      You're welcome. You might like this as well (the PDF is just the front matter of the book): http://download.springer.com/static/pdf/967/bfm%253A978-3-642-66438-0%252F1.pdf?auth66=1382903728_da0c75be6801cbf6bc3be0f7e38a4094&ext=.pdf http://download.springer.com/static/pdf/967/bfm%253A978-3-64...
      - jmmcd 13y ago
        Hmm, that link doesn't work for me (probably some kind of session id is needed). Can you post another url?
        kevgnulldev 13y ago
        sorry for the late reply... just saw your post: http://www.springer.com/computer/ai/book/978-3-540-88008-0 http://www.springer.com/computer/ai/book/978-3-540-88008-0
        jmmcd 13y ago
        Thanks! Looks like I have a lot of reading to do...
ekidd 13y ago
Wow, those are some interesting links. As somebody who's learned a foreign language to near-fluency as an adult, I've spent a lot of time trying to figure out how my brain infers a grammar from large quantities of input. Subjectively, it feels like my brain learns fixed phrases, and then notices that certain chunks can be replaced by subtrees of the appropriate type. There are complications: inflections, gender, agreement, probability, and so on. But still, grammar compression looks like a fascinating formulation of the problem.
- ot 13y ago
  Yes that's what algorithms like RePair and Sequitur do: they build the tree bottom-up by replacing frequent subtrees with a new rule at each iteration. I think that this is also the basic idea behind the usage-based model in linguistics, a theory on how we learn languages: The usage-based model is based on inductive learning, meaning that linguistic knowledge is acquired in a bottom-up manner through use. It allows for redundancy and generalizations, because the language user generalizes over recurring experiences of use. http://en.wikipedia.org/wiki/Construction_grammar#Grammar_as_an_inventory_of_constructions http://en.wikipedia.org/wiki/Construction_grammar#Grammar_as...
  - thibauts 13y ago
    Very interesting. I feel like the very concept of a grammar is only a model we cast on language to make it easier to deal with. Langage is pretty free and can work without it. Grammar feels to me like a normalization "by contract". We normalize, then study the normalization tool itself without being aware it is an artefact. We model the model, give it free parameters, randomness, serendipity to make it accomodate reality and its endless string of special cases. We even try to separate meaning from experience. This all feels more like a network of relations and probabilities of coocurrence of various (free?) orders. I followed your link and I strongly feel the suffix "grammar" is the real burden here. We're trying to put structure on what is actually creating it.
    - derleth 13y ago

by ot 13y ago

jmmcd 13y ago

Wow, that PhD thesis is very interesting. I use grammars to generate music (and other things sometimes), but I would also really like to be able to infer them. Since you say it's obsolete, do you have any links to papers or software related to successors of the Sequitur algorithm?

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 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).
kevgnulldev 13y ago
I do a bit of algorithmic composition as well (mostly microsound/granular synthesis) using NN and other graphical models (e.g. HMMs) for higher level compositional control... for grammar inference check out: http://www.mitpressjournals.org/doi/abs/10.1162/neco.1992.4.3.393 http://www.mitpressjournals.org/doi/abs/10.1162/neco.1992.4.... Abstract: We show that a recurrent, second-order neural network using a real-time, forward training algorithm readily learns to infer small regular grammars from positive and negative string training samples. We present simulations that show the effect of initial conditions, training set size and order, and neural network architecture...
- jmmcd 13y ago
  That sounds perfect -- thanks!
  - kevgnulldev 13y ago
    You're welcome. You might like this as well (the PDF is just the front matter of the book): http://download.springer.com/static/pdf/967/bfm%253A978-3-642-66438-0%252F1.pdf?auth66=1382903728_da0c75be6801cbf6bc3be0f7e38a4094&ext=.pdf http://download.springer.com/static/pdf/967/bfm%253A978-3-64...
    - jmmcd 13y ago
      Hmm, that link doesn't work for me (probably some kind of session id is needed). Can you post another url?
      - kevgnulldev 13y ago
        sorry for the late reply... just saw your post: http://www.springer.com/computer/ai/book/978-3-540-88008-0 http://www.springer.com/computer/ai/book/978-3-540-88008-0
        jmmcd 13y ago
        Thanks! Looks like I have a lot of reading to do...

ekidd 13y ago

Wow, those are some interesting links. As somebody who's learned a foreign language to near-fluency as an adult, I've spent a lot of time trying to figure out how my brain infers a grammar from large quantities of input. Subjectively, it feels like my brain learns fixed phrases, and then notices that certain chunks can be replaced by subtrees of the appropriate type. There are complications: inflections, gender, agreement, probability, and so on. But still, grammar compression looks like a fascinating formulation of the problem.

ot 13y ago
Yes that's what algorithms like RePair and Sequitur do: they build the tree bottom-up by replacing frequent subtrees with a new rule at each iteration. I think that this is also the basic idea behind the usage-based model in linguistics, a theory on how we learn languages: The usage-based model is based on inductive learning, meaning that linguistic knowledge is acquired in a bottom-up manner through use. It allows for redundancy and generalizations, because the language user generalizes over recurring experiences of use. http://en.wikipedia.org/wiki/Construction_grammar#Grammar_as_an_inventory_of_constructions http://en.wikipedia.org/wiki/Construction_grammar#Grammar_as...
- thibauts 13y ago
  Very interesting. I feel like the very concept of a grammar is only a model we cast on language to make it easier to deal with. Langage is pretty free and can work without it. Grammar feels to me like a normalization "by contract". We normalize, then study the normalization tool itself without being aware it is an artefact. We model the model, give it free parameters, randomness, serendipity to make it accomodate reality and its endless string of special cases. We even try to separate meaning from experience. This all feels more like a network of relations and probabilities of coocurrence of various (free?) orders. I followed your link and I strongly feel the suffix "grammar" is the real burden here. We're trying to put structure on what is actually creating it.
  - derleth 13y ago