Publications
- John Kieffer, Da-ke He and En-Hui Yang, Grammar-based coding: New perspectives, IEEE Information Theory Workshop, 2004.
[http://ee-wcl.tamu.edu/itw2004/program/yang_inv.pdf]
- Hiroshi Sakamoto, A Fully Linear-Time Approximation Algorithm for Grammar-Based Compression, Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching, LNCS 2676, Springer, pp. 348-360, 2003.
[http://citeseer.ist.psu.edu/600183.html]
[http://www.i.kyushu-u.ac.jp/doitr/trcs214.ps.gz]
- Eric Lehman and Abhi Shelat, Approximation Algorithms for Grammar-Based Compression, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 205-212, 2002.
[http://citeseer.ist.psu.edu/lehman02approximation.html]
[http://theory.lcs.mit.edu/~abhi/LehmanShelat-SODA02.ps]
[http://theory.lcs.mit.edu/~abhi/LehmanShelat-SODA02.pdf]
- Eric Lehman, Approximation Algorithms for Grammar-Based Data Compression, PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 2002.
[http://citeseer.ist.psu.edu/548657.html]
[http://theory.lcs.mit.edu/~e_lehman/main.ps]
- John Kieffer and En-Hui Yang, Structured grammar-based codes for universal lossless data compression, Communications in Information and Systems, 2(1), pp. 29-52, 2002.
[http://www.ims.cuhk.edu.hk/~cis/2002.1/KIEFFER.pdf]
- Hiroshi Sakamoto, Shinichi Shimozono, Ayumi Shinohara and Masayuki Takeda, O(log n)-Approximation Algorithm for Grammar-Based Compression, DOI-Technical Report of the Informatics Department of Kyushu University, 2002.
[http://citeseer.ist.psu.edu/626587.html]
[http://www.i.kyushu-u.ac.jp/doitr/trcs201.ps.gz]
- Hiroshi Sakamoto, Shinichi Shimozono, Ayumi Shinohara and Masayuki Takeda, On the Minimization Problem of Text Compression Scheme by a Reduced Grammar Transfrom, DOI-Technical Report of the Informatics Department of Kyushu University, 2001.
[http://citeseer.ist.psu.edu/sakamoto02minimization.html]
[http://www.i.kyushu-u.ac.jp/doitr/trcs195.ps.gz]
- Abhi Shelat, Evaluating Grammar-Based Data Compression Algorithms, Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 2001.
[http://citeseer.ist.psu.edu/shelat01evaluating.html]
[http://theory.lcs.mit.edu/~abhi/abhi-shelat-thesis.ps]
[http://theory.lcs.mit.edu/~abhi/abhi-shelat-thesis.pdf]
- En-Hui Yang, Alexei Kaltchenko and John Kieffer, Universal Lossless Data Compression With Side Information by Using a Conditional MPM Grammar Transform, IEEE Transactions on Information Theory, 47(6), pp. 2130-2150, 2001.
[http://sauron.wlu.ca/physcomp/akaltchenko/1/cmpm.pdf]
- John Kieffer, En-Hui Yang, Gregory Nelson and Pamela Cosman, Universal Lossless Compression via Multilevel Pattern Matching, IEEE Transactions on Information Theory, 46(4), pp. 1227-1245, 2000.
[http://citeseer.ist.psu.edu/kieffer00universal.html]
[http://code.ucsd.edu/~pcosman/web-14.pdf]
- John Kieffer and En-Hui Yang, Grammar Based Codes: A New Class of Universal Lossless Source Codes, IEEE Transactions on Information Theory, 46(3), pp. 737-754, 2000.
[http://citeseer.ist.psu.edu/kieffer00grammar.html]
- Joscha Bach and Ian Witten, Lexical Attraction for Text Compression, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 516-, 1999.
[http://citeseer.ist.psu.edu/167721.html]
- Jesper Larsson and Alistair Moffat, Offline Dictionary-Based Compression, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 296-305, 1999.
[http://citeseer.ist.psu.edu/8645.html]
[http://www.larsson.dogma.net/dcc99.pdf]
[http://www.larsson.dogma.net/dcc99.ps.gz]
- Jesper Larsson, Structures of String Matching and Data Compression, PhD thesis, Department of Computer Science, Lund University, Sweden, 1999.
[http://citeseer.ist.psu.edu/larsson99structures.html]
[http://www.larsson.dogma.net/thesis.pdf]
[http://www.larsson.dogma.net/thesis.ps.gz]
- Craig Nevill-Manning and Ian Witten, Phrase Hierarchy Inference and Compression in Bounded Space, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 179-188, 1998.
[http://citeseer.ist.psu.edu/nevill-manning98phrase.html]
[http://www.cs.waikato.ac.nz/~ihw/papers/98NM-IHW-Phrase.pdf]
- Craig Nevill-Manning and Ian Witten, Compression and explanation using hierarchical grammars, The Computer Journal, 40(2/3), pp. 103-116, 1997.
[http://citeseer.ist.psu.edu/nevill-manning97compression.html]
[http://www.cs.waikato.ac.nz/~ihw/papers/97NM-IHW-Compress.pdf]
- Craig Nevill-Manning and Ian Witten, Identifying Hierarchical Structure in Sequences: A linear-time algorithm, Journal of Artificial Intelligence Research, 7, pp. 67-82, 1997.
[http://citeseer.ist.psu.edu/nevill-manning97identifying.html]
[http://www.cs.waikato.ac.nz/~ihw/papers/97NM-IHW-Ident-Hier.pdf]
[http://www.cs.washington.edu/research/jair/volume7/nevill97a.ps]
[http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume7/nevill97a.pdf]
[http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume7/nevill97a.ps.Z]
[http://sequitur.info/jair/]
- Craig Nevill-Manning and Ian Witten, Inferring Lexical and Grammatical Structure from Sequences, Proceedings of the Compression and Complexity of Sequences, pp. 265-274, 1997.
[http://citeseer.ist.psu.edu/nevill-manning97inferring.html]
[http://www.cs.waikato.ac.nz/~ihw/papers/98NM-IHW-Infer-Lex.pdf]
- Craig Nevill-Manning and Ian Witten, Linear-time, incremental hierarchy inference for compression, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 3-11, 1997.
[http://citeseer.ist.psu.edu/358431.html]
[http://www.cs.waikato.ac.nz/~ihw/papers/97NM-IHW-Linear-Time.pdf]
- Craig Nevill-Manning, Ian Witten and Dan Olsen, Compressing semi-structured text using hierarchical phrase identification, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 63-72, 1996.
[http://citeseer.ist.psu.edu/nevill-manning96compressing.html]
[http://www.cs.waikato.ac.nz/~ihw/papers/96NM-IHW-Olsen-Compress.pdf]
- Craig Nevill-Manning, Inferring Sequential Structure, PhD thesis, Computer Science, University of Waikato, Hamilton, New Zealand, 1996.
[http://citeseer.ist.psu.edu/nevill-manning96inferring.html]
Source Code
- Sequitur by Craig Nevill-Manning and Ian Witten