3 ms·
Grammar-based compression algorithms are completely missing from this "history".
by harveywi 4y ago
Grammar-based compression algorithms are completely missing from this "history".
- lucb1e 4y agoHaven't heard of that before. Typing it into Wikipedia, I got https://en.wikipedia.org/wiki/Grammar-based_code https://en.wikipedia.org/wiki/Grammar-based_code which explains it in so much as "To compress a data sequence x=x[0..n], a grammar-based code transforms x into a context-free grammar G." (Very helpful, love it when they use pseudocode with single-letter recursive variable definitions which needs accompanying text for it to make sense... and the text isn't there.) There is an example given on the right in image form, which looks like recursive dictionary-based string substitution: "We hold these truths" compressed: we_holdQ5ths Q=Rse we_holdRse_5ths R=Se we_holdSese_5ths S=_th we_hold_these_5ths 5=tru we_hold_these_truths This method isn't described anywhere nor was the original included, but this seems to be the algorithm used.
- duskwuff 4y agoI'm not sure grammar-based compressors are a meaningful part of the history of lossless data compression. They're a topic in coding theory research, but, as far as I'm aware, they haven't had a significant impact in practical algorithms used in the field.