Моделирование при сжатии текстовых данных - Структуры данных для метода Зива-Лемпела

  1.Abramson D.M. 1989.
    An adaptive dependency source model for data compression.
    Commun.ACM 32,1(Jan.),77-83.
  2.Angluin D.,and Smith C.H. 1983.
    Inductive inference:Theory and methods.
    Comput.Surv. 15, 3(Sept.),237-269.
  3.Auslander M., Harrison W., Miller V., and Wegman M. 1985.
    PCTERM: A terminal emulator using compression.
    In Proceedings of the IEEE Globecom'85. IEEE Press, pp.860-862.
  4.Baum L.E., Petrie T.,Soules G. and Weiss N. 1970.
    A maximization technique occuring in the statistical analysis of
    probabilistic functions of Markov chains.
    Ann. Math. Stat.41, 164-171.
  5.Bell T.C. 1986.
    Better OPM/L test compression.
    IEEE Trans. Commun. COM-34. 12(Dec.),1176-1182.
  6.Bell T.C. 1987.
    A unifying theory and improvements for existing approaches to text
    compression.
    Ph.D. dissertation, Dept. of Computer Science, Univ. of Canterbury,
    New Zealand.
  7.Bell T.C. 1989.
    Longest match string searching for Ziv-Lempel compression.
    Res. Rept.6/89, Dept. of Computer Science, Univ. of Canterbury,
    New Zealand.
  8.Bell T.C. and Moffat A.M. 1989.
    A note on the DMC data compression scheme.
    Computer J. 32,1(Feb.), 16-20.
  9.Bell T.C. and Witten I.H. 1987.
    Greedy macro text compression.
    Res. Rept.87/285/33. Department of Computers Science, University of
    Calgary.
 10.Bentley J.L.,Sleator D.D., Tarjan R.E. and Wei V.K. 1986.
    A locally adaptive data compression scheme.
    Commun. 29, 4(Apr.), 320-330.
    Shows how recency effectscan be incorporated explicitly into a text
    compression system.
 11.Bookstein A. and Fouty G. 1976.
    A mathematical model for estimating the effectivness of bigram coding.
    Inf. Process. Manage.12.
 12.Brent R.P. 1987.
    A linear algorithm for data compression.
    Aust. Comput. J. 19,2,64-68.
 13.Cameron R.D. 1986.
    Source encoding using syntactic information source model.
    LCCR Tech. Rept. 86-7, Simon Fraser University.
 14.Cleary J.G. 1980.
    An associative and impressible computer.
    Ph.D. dissertation. Univ. of Canterbury, Christchurch, New Zealand.
 15.Cleary J.G. and Witten I.H. 1984a.
    A comparison of enumerative and adaptive codes.
    IEEE Trans. Inf. Theory, IT-30, 2(Mar.),306-315.
    Demonstrates under quite general conditions that adaptive coding
    outperforms the method of calculating and transmitting an exact
    model of the message first.
 16.Cleary J.G. and Witten I.H. 1984b.
    Data compression using adaptive coding and partial string matching.
    IEEE Trans. Commun. COM-32, 4(Apr.),396-402.
    Presents an adaptive modeling method that reduces a large sample
    of mixed-case English text to around 2.2 bits/character when
    arithmetically coded.
 17.Cooper D. and Lynch M.F. 1982.
    Text compression using variable-to-fixed-length encoding.
    J. Am. Soc. Inf. Sci. (Jan.), 18-31.
 18.Cormack G.V. and Horspool R.N. 1984.
    Algorithms for adaptive Huffman codes.
    Inf.Process.Lett. 18,3(Mar.), 159-166.
    Describes how adaptive Huffman coding can be implemented efficiently.
 19.Cormack G.V. and Horspool R.N. 1987.
    Data compression using dynamic Markov modelling.
    Comput. J. 30,6(Dec.), 541-550.
    Presents an adaptive state-modelling technique that, in conjunction with
    arithmetic coding, produces results competitive with those of[18].
 20.Cortesi D. 1982.
    An effective text-compression algorithm.
    Byte 7,1(Jan.),397-403.
 21.Cover T.M. and King R.C. 1978.
    A convergent dambling estimate of the entropy of English.
    IEEE Trans. Inf. Theory IT-24, 4(Jul.),413-421.
 22.Darragh J.J., Witten I.H. and Cleary J.G. 1983.
    Adaptive text compression to enhance a modem.
    Res.Rept.83/132/21.Computer Science Dept.,Univ.of Calgary.
 23.Elias P. 1975.
    Universal codeword sets and representations of the integers.
    IEEE Trans.Inf.Theory IT-21,2(Mar.),194-203.
 24.Elias P. 1987.
    Interval and recency rank source coding: Two on-line adaptive
    variable-length schemes.
    IEEE Trans.Inf.Theory IT-33, 1(Jan.),3-10.
 25.El Gamal A.A., Hemachandra L.A., Shperling I. and Wei V.K. 1987.
    Using simulated annealing to design good codes.
    IEEE Trans.Inf.Theory,IT-33,1,116-123.
 26.Evans T.G. 1971.
    Grammatical inference techniques in pattern analysis.
    In Software Engineering, J. Tou. Ed.Academic Press, New York, pp.183-202.
 27.Faller N. 1973.
    An adaptive system for data compression.
    Record of the 7th Asilomar Conference on Circuits, Systems and Computers.
    Naval Postgraduate School, Monterey, CA, pp.593-597.
 28.Fiala E.R. and Greene D.H. 1989.
    Data compression with finite windows.
    Commun.ACM 32,4(Apr.),490-505.
 29.Flajolet P. 1985.
    Approximate counting: A detailed analysis.
    Bit 25,113-134.
 30.Gaines B.R. 1976.
    Behavior/structure transformations under uncertainty.
    Int.J.Man-Mach.Stud. 8, 337-365.
 31.Gaines B.R. 1977.
    System identification, approximation and complexity.
    Int.J.General Syst. 3,145-174.
 32.Gallager R.G. 1978.
    Variations on a theme by Huffman.
    IEEE Trans.Inf.Theory IT-24, 6(Nov.),668-674.
    Presents an adaptive Huffman coding algorithm, and derives new bound
    on the redundancy of Huffman codes.
 33.Gold E.M. 1978.
    On the complexity of automation identification from given data.
    Inf.Control 37,302-320.
 34.Gonzalez-Smith M.E. and Storer J.A. 1985.
    Parralel algorithms for data compression.
    J.ACM 32,2,344-373.
 35.Gottlieb D., Hagerth S.A., Lehot P.G.H. and Rabinowitz H.S. 1975.
    A classification of compression methods and their usefulness for a
    large data processing center.
    National Comput.Conf. 44. 453-458.
 36.Guazzo M. 1980.
    A general minimum-redundancy source-coding algorithm.
    IEEE Trans.Inf.Theory IT-26, 1(Jan.),15-25.
 37.Held G. 1983.
    Data Compression: Techniques and Application, Hardware and Software
    Considerations.
    Willey, New York.
    Explains a number of ad hoc techniques for compressing text.
 38.Helman D.R. and Langdon G.G. 1988.
    Data compression.
    IEEE Potentials (Feb.),25-28.
 39.Horspool R.N. and Cormack G.V. (1983).
    Data compression based on token recognition.
    Unbublished.
 40.Horspool R.N. and Cormack G.V. 1986.
    Dynamic Markov modelling - A prediction technique.
    In Proceedings of the International Conference on the System Sciences,
    Honolulu, HI,pp.700-707.
 41.Huffman D.A. 1952.
    A method for the construction of minimum redundancy codes.
    In Proceedings of the Institute of Electrical and Radio Engineers
    40,9(Sept.),pp.1098-1101.
    The classic paper in which Huffman introduced his famous coding method.
 42.Hunter R. and Robinson A.H. 1980.
    International digital facsimile coding standarts.
    In Proceedings of the Institute of Electrical and Electronic Engineers
    68,7(Jul.),pp.854-867.
    Describes the use of Huffman coding to compress run lengths in
    black/white images.
 43.Jagger D. 1989.
    Fast Ziv-Lempel decoding using RISC architecture.
    Res.Rept.,Dept.of Computer Science, Univ.of Canterbury, New Zealand.
 44.Jakobsson M. 1985.
    Compression of character string by an adaptive dictionary.
    BIT 25, 4, 593-603.
 45.Jamison D. and Jamison K. 1968.
    A note on the entropy of partial-known languages.
    Inf.Control 12, 164-167.
 46.Jewell G.C. 1976.
    Text compaction for information retrieval systems.
    IEEE Syst., Man and Cybernetics Soc.Newsletter 5,47.
 47.Jones D.W. 1988.
    Application of splay trees to data compression.
    Commun.ACM 31,8(Aug.),996-1007.
 48.Katajainen J. and Raita T. 1987a.
    An appraximation algorithm for space-optimal encoding of a text.
    Res.Rept.,Dept.of Computer Science, Univ. of Turku, Turku, Finland.
 49.Katajainen J. and Raita T. 1987b.
    An analysis of the longest match and the greedy heuristics for
    text encoding.
    Res.Rept.,Dept.of Computer Science, Univ. of Turku, Turku, Finland.
 50.Katajainen J., Renttonen M. and Teuhola J. 1986.
    Syntax-directed compression of program files.
    Software-Practice and Experience 16,3,269-276.
 51.Knuth D.E. 1973.
    The Art of Computer Programming. Vol.2, Sorting and Searching.
    Addison-Wesley, Reading,MA.
 52.Knuth D.E. 1985.
    Dynamic Huffman coding.
    J.Algorithms 6,163-180.
 53.Langdon G.G. 1983.
    A note on the Ziv-Lempel model dor compressing individual sequences.
    IEEE Trans.Inf.Theory IT-29, 2(Mar.),284-287.
 54.Langdon G.G. 1984.
    An introduction to arithmetic coding.
    IBM J.Res.Dev. 28,2(Mar.),135-149.
    Introduction to arithmetic coding from the point of view of hardware
    implementation.
 55.Langdon G.G. and Rissanen J.J. 1981.
    Compression of black-white images with arithmetic coding.
    IEEE Trans.Commun.COM-29, 6(Jun.),858-867.
    Uses a modeling method specially tailored to black/white pictures, in
    conjunction with arithmetic coding, to achieve excellent compression
    results.
 56.Langdon G.G. and Rissanen J.J. 1982.
    A simple general binary source code.
    IEEE Trans.Inf.Theory IT-28 (Sept.),800-803.
 57.Langdon G.G. and Rissanen J.J. 1983.
    A doubly-adaptive file compression algorithms.
    IEEE Trans.Commun. COM-31, 11(Nov.),1253-1255.
 58.Lelewer D.A. and Hirschberg D.S. 1987.
    Data compression.
    Comput.Surv. 13,3(Sept.),261-296.
 59.Lempel A. and Ziv J.1976.
    On the complexity of finite sequences.
    IEEE Trans.Inf.Theory IT-22,1(Jan.),75-81.
 60.Levinson S.E., Rabiner L.R. and Sondni M. 1983.
    An introduction to the application of the theory of probabilistic function
    of a Markov process to automatic speech recognition.
    Bell Syst.Tech.J. 62,4(Apr.),1035-1074.
 61.Llewellyn J.A. 1987.
    Data compression for a source with Markov characteristics.
    Comput.J. 30,2,149-156.
 62.Lynch M.F. 1973.
    Compression of bibliographic files using an adaption of run-length coding.
    Inf.Storage Retrieval 9,207-214.
 63.Lynch T.J. 1985.
    Data Compression - Techniques and Application.
    Lifetime Learning Publications, Belmont, CA.
 64.Mayne A. and James E.B. 1975.
    Information compression by factorizing common strings.
    Comput.J.18,2,157-160.
 65.G. & C. Merriam Company 1963.
    Webster's Seventh New Collegiate Dictionary.
    Springfield, MA.
 66.Miller V.S. and Wegman M.N. 1984.
    Variations on a theme by Ziv and Lempel.
    In Combinatorial Algorithms on Words.A.Apostolico and Z.Galil,
    Eds.NATO ASI Series, Vol.F12.Springer-Verlag,Berlin,pp.131-140
 67.Moffat A. 1987.
    Word based text compression.
    Res.Rept.,Dept.of Computer Science, Univ.of Melbourne,Victoria,Australia.
 68.Moffat A. 1988a.
    A data structure for arithmetic encoding on large alphabets.
    In Proceeding of the 11th Australian Computer Science Conference.
    Brisbane,Australia(Feb.),pp.309-317.
 69.Moffat A. 1988b.
    A note on the PPM data compression algorithm.
    Res.Rept.88/7,Dept.of Computer Science, Univ.of Melbourne,
    Victoria,Australia.
 70.Morris R. 1978.
    Counting large numbers of events in small registers.
    Commun.ACM 21,10(Oct.),840-842.
 71.Morrison D.R. 1968.
    PATRICIA - Practical Algorithm To Retvieve Information Coded In Alphanume-
    ric.
    J.ACM 15,514-534.
 72.Ozeki K. 1974a.
    Optimal encoding of linguistic information.
    Systems, Computers, Controls 5, 3, 96-103.
    Translated from Denshi Tsushin Gakkai Ronbunshi, Vol.57-D,No.6,June 1974,
    pp.361-368.
 73.Ozeki K. 1974b.
    Stochastic context-free grammar and Markov chain.
    Systems, Computers, Controls 5, 3, 104-110.
    Translated from Denshi Tsushin Gakkai Ronbunshi, Vol.57-D,No.6,June 1974,
    pp.369-375.
 74.Ozeki K. 1975.
    Encoding of linguistic information generated by a Markov chain which is
    associated with a stochastic context-free grammar.
    Systems, Computers, Controls 6, 3, 75-78.
    Translated from Denshi Tsushin Gakkai Ronbunshi, Vol.58-D,No.6,June 1975,
    pp.322-327.
 75.Pasco R. 1976.
    Source coding algorithms for fast data compression.
    Ph.D. dissertation.Dept.of Electrical Engineering, Stanford Univ.
    An early exposition of the idea of arithmetic coding, but lacking the
    idea of incremental operation.
 76.Pike J. 1981.
    Text compression using a 4 bit coding system.
    Comput.J.24,4.
 77.Rabiner L.R. and Juang B.H. 1986.
    An Introduction to Hidden Markov models.
    IEEE ASSP Mag.(Jan.).
 78.Raita T. and Teuhola J.(1987).
    Predictive text compression by hashing.
    ACM Conference on Information Retrieval,New Orleans.
 79.Rissanen J.J. 1976.
    Generalized Kraft inequality and arithmetic coding.
    IBM J.Res.Dev.20,(May.),198-203.
    Another early exposition of the idea of arithmetic coding.
 80.Rissanen J.J. 1979.
    Arithmetic codings as number representations.
    Acta Polytechnic Scandinavica, Math 31(Dec.),44-51.
    Further develops arithmetic coding as a practical technique for data
    representation.
 81.Rissanen J.J. 1983.
    A universal data compression system.
    IEEE Trans.Inf.Theory IT-29,5(Sept.),656-664.
 82.Rissanen J.J. and Langdon G.G. 1979.
    Arithmetic coding.
    IBM J.Res.Dev.23,2(Mar.),149-162.
    Describes a broad class of arithmetic codes.
 83.Rissanen J.J. and Langdon G.G. 1981.
    Universal modeling and coding.
    IEEE Trans.Inf.Theory IT-27,1(Jan.),12-23.
    Shows how data compresion can be separated into modeling for prediction
    and coding with respect to a model.
 84.Roberts M.G. 1982.
    Local order estimating Markovian analysis for noiseless source
    coding and authorship identification.
    Ph.D.dissertation.Stanford Univ.
 85.Roden M., Pratt V.R. and Even S. 1981.
    Linear algorithm for data compression via string matching.
    J.ACM 28,1(Jan.),16-24.
 86.Rubin F. 1976.
    Experiments in text file compression.
    Commun.ACM 19,11,617-623.
    One of the first papers to present all the essential elements of practical
    arithmetic coding, including fixed-point computation and incremental
    operation.
 87.Rubin F. 1979.
    Arithmetic stream coding using fixed precision registers.
    IEEE Trans.Inf.Theory IT-25,6(Nov.),672-675.
 88.Ryabko B.Y. 1980.
    Data compression by means of a "book stack".
    Problemy Peredachi Informatsii 16,4.
 89.Schieber W.D. and Thomas G.W. 1971.
    An algorithm for compaction of alphanumeric data.
    J.Library Automation 4,198-206.
 90.Schuegraf E.J. and Heaps H.S. 1973.
    Selection of equifrequent word fragments for information retrieval.
    Inf.Storage Retrieval 9,697-711.
 91.Schuegraf E.J. and Heaps H.S. 1974.
    A comparison of algorithms for data-base compression
    by use of fragments as language elements.
    Inf.Storage Retrieval 10,309-319.
 92.Shannon C.E. 1948.
    A mathematical theory of communication.
    Bell Syst.Tech.J.27(Jul.),398-403.
 93.Shannon C.E. 1951.
    Prediction and entropy of printed English.
    Bell Syst.Tech.J.(Jan.),50-64.
 94.Snyderman M. and Hunt B. 1970.
    The myriad virtues of text compaction.
    Datamation 1(Dec.),36-40.
 95.Storer J.A. 1977.
    NP-completeness results concerning data compression.
    Tech.Rept.234.Dept.of Electrical Engineering and Computer Science,
    Princeton Univ.,Princeton,NJ.
 96.Storer J.A. 1988.
    Data Compression: Methods and Theory.
    Computer Science Press, Rockville,MD.
 97.Storer J.A. and Szymanski T.G. 1982.
    Data compression via textual substitution.
    J.ACM 29,4(Oct.),928-951.
 98.Svanks M.I. 1975.
    Optimizing the storage of alphanumeric data.
    Can.Datasyst.(May),38-40.
 99.Tan C.P. 1981.
    On the entropy of the Malay language.
    IEEE Trans.Inf.Theory IT-27,3(May),383-384.
100.Thomas S.W., McKie J., Davies S., Turkowski K., Woods J.A.
    and Orost J.W. 1985.
    Compress (Version 4.0) program and documentation.
    Available from joe@petsd.UUCP.
101.Tischer P. 1987.
    A modified Lempel-Ziv-Welch data compression scheme.
    Aust.Comp.Sci.Commun. 9,1,262-272.
102.Todd S., Langdon G.G. and Rissanen J. 1985.
    Parameter reduction and context selection for compression
    of gray-scale images.
    IBM J.Res.Dev.29,2(Mar.),188-193.
103.Tropper R. 1982.
    Binary-coded text, a compression method.
    Byte 7,4(Apr.),398-413.
104.Vitter J.S. 1987.
    Design and analysis of dynamic Huffman codes.
    J.ACM 34,4(Oct.),825-845.
105.Vitter J.S. 1989.
    Dynamic Huffman coding.
    ACM Trans.Math.Softw. 15,2(Jun.),158-167.
106.Wagner R.A. 1973.
    Common phrase and minimum-space text storage.
    Commun.ACM 16,3, 148-152.
107.Walker D.E. and Amsler R.A. 1986.
    The use of machine-readable dictionaries in sublanguage analysis.
    In Analysis languages in restricted domains: Sublanguage description
    and processing, R.Grishman and R.Kittridge, Eds.Lawrence Erlbaum 
    Associates,Hillsdale, NJ, pp.69-83.
108.Welch T.A. 1984.
    A technique for high-performance data compression.
    IEEE Computer 17,6(Jun.),8-19.
    A very fast coding technique based on the method of [119], but those
    compression performance is poor by the standarts of a [16] and [19].
    An improved implementation of this method is widely used in UNIX
    systems under the name "compress".
109.White H.E. 1967.
    Printed English compression by dictionary encoding.
    In Proceedings of the Institute of Electrical and Electronics Engineering
    55, 3,390-396.
110.Williams R. 1988.
    Dynamics-history predictive compression.
    Inf.Syst. 13,1,129-140.
111.Witten I.H. 1979.
    Approximate, non-deterministic modelling of behavior sequences.
    Int.J.General Systems 5(Jan.),1-12.
112.Witten I.H. 1980.
    Probabilistic behavior/structure transformations using
    transitive Moore models.
    Int.J.General Syst.6,3,129-137.
113.Witten I.H. and Cleary J. 1983.
    Picture coding and transmission using adaptive modelling of quad trees.
    In Proceeding of the International Elecrical, Electronics conference
    1,Toronto,ON,pp.222-225.
114.Witten I.H.
115.Witten I.H., Neal R. and Cleary J.G. 1987.
    Arithmetic coding for data compression.
    Commun.ACM 30,6(Jun.),520-540.
116.Wolff J.G. 1978.
    Recording of natural language for economy of transmission or storage.
    Comput.J. 21,1,42-44.
117.Young D.M. 1985.
    MacWrite file formats.
    Wheels for the mind (Newsletter of the Australian Apple University Consor-
    tium), University of Western Australia, Nedlands, WA 6009, Australia, p.34
118.Ziv J. and Lempel A. 1977.
    A universal algorithms for sequental data compression.
    IEEE Trans.Inf.Theory IT-23,3,3(May),337-343.
119.Ziv J. and Lempel A. 1978.
    Compression of individual sequences via variable-rate coding.
    IEEE Trans.Inf.Theory IT-24,5(Sept.),530-536.
    Describes a method of text compression that works by replacing a substring
    with a pointer to an earlier occurrence of the same substring. Although it
    performs  quite  well, it does  not  provide  a clear  separation  between
    modeling and coding.