Data compression via textual substitution

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Data compression via textual substitution

Full text

Pdf (1.29 MB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 4 (October 1982) table of contents

Pages: 928 - 951

Year of Publication: 1982

ISSN:0004-5411

Authors

James A. Storer	Department of Computer Science, Brandeis University, Waltham, MA and Princeton University, Princeton, New Jersey
Thomas G. Szymanski	Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ and Princeton University, Princeton, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 126, Citation Count: 33

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322344.322346 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
	3	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	4	GALLANT, J., MAmR, D., AI~D STOREg, J.A. On finding minimal length superstrings. ~ Comput. Syst. Set 20 (1980), 50--58
	5	GAgE't, M.R., Jom~soN, D.S., m~D STOCKM~YER, L. Some snnptified NP-complete problems. Theor. Comput. Sci. 1 (1976), 237--267.
	6	HxGAiemr~, W.D., Lrtco}~l~, D.J., LoNe, H.S., AND Weeim, J.C. Encoding verbal mformaUon as unique numbers. IBM Syst. J. 11 (1972), 278-315.
	7	Bruce Hahn, A new technique for compression and storage of data, Communications of the ACM, v.17 n.8, p.434-436, Aug. 1974 [doi>10.1145/361082.361086]
	8	Hurr~u, D.A. A method for the construction of minimum-redundancy codes, Proc. IRE 40 (1952), 1098-1101.
	9	KARP, R.M. Reducibility among combinatorial problems. In Complexity of Computer Computatwns, R.E. Miller and J.W. Thatcher, Eds., Plenum Press, New York, 1972, pp. 85-103.
	10	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	11	KNurtt, D.E., Mox~xs, J H., AND PRATT, V.R. Fast pattern matching in stnngs. SIAM ~ Comput. 6, 2 (1977), 323-349.
	12	LeMPI~L, A, A~D Zlv, J. On the complexity of finite sequences. IEEE Trans Inf. Theory IT 22, 1 (1976), 75-81.
	13	L~sr,, M.E. Compressed text storage. Unpublished Tcch. Memo., Bell Laboratories, Murray Hill, N.J., 1970
	14	McCARTHY, J.P. Automatic file compression. In International Computing Symposium, North-Holland, Amsterdam, 1973, pp 511-516.
	15	Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
	16	MAmR, D The complextty of some problems on subsequences and supersequences. Conf on Theoreucal Computer Science, University of Waterloo, Waterloo, Ont., Can., 1977, pp. 120-129
	17	MAIl/R, D., AND STORI3K, J.A. A note on the complexity of the superstring problem. Proc 1978 Conf. on Information Sciences and Systems, Baltimore, Md., 1978, pp. 52-60.
	18	MAJST~R, M E. Efficmnt on-line construction and correction ofpomion trees. Tech. Rep. TR79-393, Dep. of Computer Science, Corner Univ., Ithaca, N.Y., 1979.
	19	B. A. Marron , P. A. D. de Maine, Automatic data compression, Communications of the ACM, v.10 n.11, p.711-715, Nov. 1967 [doi>10.1145/363790.363813]
	20	MAYNE, A., AND JAMES, E.B. Information compression by factorising common strings. Comput. ~ 18, 2 (1975), 157-160
	21	MORRIS, R., A~ THOMPSON, K. Webster's second on the head of a pin. Unpubfishegt Tcch. Memo., Bell Laboratories, Murray Hill, N.J,, 1974.
	22	PRAYr, V.R.Improvements and applications for the Weiner repetition finder. Lecture notes, 3rd revision, 1975.
	23	RODI~H, M, PRATT, V R., ANt) Ev~, S A linear-time algorithm for finding repetitions and its apphcation to data compression, Tech Rep. No, 72, Dep of Computer Sci., Technioon, Israel, 1976.
	24	Michael Rodeh , Vaughan R. Pratt , Shimon Even, Linear Algorithm for Data Compression via String Matching, Journal of the ACM (JACM), v.28 n.1, p.16-24, Jan. 1981 [doi>10.1145/322234.322237]
	25	Frank Rubin, Experiments in text file compression, Communications of the ACM, v.19 n.11, p.617-623, Nov. 1976 [doi>10.1145/360363.360368]
	26	RUTH, S S, Am~ KREUTZER, P.J. Data compression for large business files. Datamation l& 9 (1972), 62-66
	27	SEEP'f, J B., AND Zrv, j.A umversal data compression algorithm" Description and preliminary results. Unpublished Tech. Memo., Bell Laboratories, Murray Hill, N.J., 1977.
	28	St~_~'~, J.B., A~D ZIv, J.Further results on universal data compression. Unpublished Tech. Memo., Bell Laboratories, Murray Hill, N.J., 1978.
	29	SEIFERAS, J.Subword trees Lecture notes, 1977
	30	STORER, J.A NP-completeness results concerning data compression. Teeh. Rep. 234, Dep. of Electrical Engmeedrtg and Computer Science, Princeton Umv., Prme0ton, N.J., 1977.
	31	STOREK, J.A. PLCC--A compiler-compiler for PLI and PLC users. Tech. Rep. 236, Dep. of Electrical Engineering and Computer Science, Princeton Univ., Princoton, N.J., 1977.
	32	James Andrew Storer, Data compression: methods and complexity issues., 1979
	33	James A. Storer , Thomas G. Szymanski, The macro model for data compression (Extended Abstract), Proceedings of the tenth annual ACM symposium on Theory of computing, p.30-39, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804329]
	34	VIqVALINGAM, M.Indexing with coded deltas--A data compaction technique. Soflw. Pratt. Exper 6 (1976), 397-403.
	35	Robert A. Wagner, Common phrases and minimum-space text storage, Communications of the ACM, v.16 n.3, p.148-152, March 1973 [doi>10.1145/361972.361982]
	36	W~INEg, P Linear pattern matchmg algorithms. Proc. I4th Annual IEEE Syrup, on Switching and Automata Theory, Ames, Iowa, 1973, pp. 1-I 1.
	37	Zrv,J.Coding theorems for lndwidual sequences IEEE Trans. Inf. Theory IT 24, 4 (1978) 405-4t2.
	38	Zrv,J, ASP LEMPEL, A. A universal algorithm for sequential data compression. IEEE Trans Inf. Theory IT 23, 3 (1977), 33%343.
	39	Ziv, J, AND LEm, rL, A.compression of indiwdual sequences vta variable-rate coding. IEEE Trans. Inf. Theory IT 24, 5 (1978), 530-536.

CITED BY 33

	Shmuel T. Klein, Efficient recompression techniques for dynamic full-text retrieval systems, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.39-47, July 09-13, 1995, Seattle, Washington, United States
	Adam Cannane , Hugh E. Williams, A general-purpose compression scheme for large collections, ACM Transactions on Information Systems (TOIS), v.20 n.3, p.329-355, July 2002
	Clark Thomborson, The V.42bis Standard for Data-Compressing Modems, IEEE Micro, v.12 n.5, p.41-53, September 1992
	Craig G. Nevill-Manning , Ian H. Witten , Gordon W. Paynter, Browsing in digital libraries: a phrase-based approach, Proceedings of the second ACM international conference on Digital libraries, p.230-236, July 23-26, 1997, Philadelphia, Pennsylvania, United States
	Sergei Y. Larin , Thomas M. Conte, Compiler-driven cached code compression schemes for embedded ILP processors, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.82-92, November 16-18, 1999, Haifa, Israel
	E. R. Fiala , D. H. Greene, Data compression with finite windows, Communications of the ACM, v.32 n.4, p.490-505, April 1989
	Bongjin Jung , Wayne P. Burleson, Performance optimization of wireless local area networks through VLSI data compression, Wireless Networks, v.4 n.1, p.27-39, Jan. 1998
	Luigi Cinque , Franco Liberati , Sergio De Agostino, A work-optimal parallel implementation of lossless image compression by block matching, Nordic Journal of Computing, v.10 n.1, p.13-20, Spring 2003
	M. E. Gonzalez Smith , J. A. Storer, Parallel algorithms for data compression, Journal of the ACM (JACM), v.32 n.2, p.344-373, April 1985
	A. Mukherjee , M. Bassiouni, A VLSI chip for efficient transmission and retrieval of information, Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval, p.208-216, June 03-05, 1987, New Orleans, Louisiana, United States
	Takahiro J. Yamaguchi , Dong Sam Ha , Masahiro Ishida , Tadahiro Ohmi, A Method for Compressing Test Data Based on Burrows-Wheeler Transformation, IEEE Transactions on Computers, v.51 n.5, p.486-497, May 2002
	A. Turpin , W. F. Smyth, An approach to phrase selection for offline data compression, Australian Computer Science Communications, v.24 n.1, p.267-273, January-February 2002
	Takuya Kida , Tetsuya Matsumoto , Yusuke Shibata , Masayuki Takeda , Ayumi Shinohara , Setsuo Arikawa, Collage system: a unifying framework for compressed pattern matching, Theoretical Computer Science, v.298 n.1, p.253-272, 4 April 2003
	Timothy C. Bell , Ian H. Witten, The relationship between greedy parsing and symbolwise text compression, Journal of the ACM (JACM), v.41 n.4, p.708-724, July 1994
	Joong Chae Na , Alberto Apostolico , Costas S. Iliopoulos , Kunsoo Park, Truncated suffix trees and their application to data compression, Theoretical Computer Science, v.304 n.1-3, p.87-101, 28 July 2003
	V. N. Potapov, Redundancy estimates for the Lempel-Ziv algorithm of data compression, Discrete Applied Mathematics, v.135 n.1-3, p.245-254, 15 January 2004
	Farhad Oroumchian , Ehsan Darrudi , Fattane Taghiyareh , Neeyaz Angoshtari, Experiments with persian text compression for web, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA
	Timothy Bell , Ian H. Witten , John G. Cleary, Modeling for text compression, ACM Computing Surveys (CSUR), v.21 n.4, p.557-591, Dec. 1989
	Stan Liao , Srinivas Devadas , Kurt Keutzer, A text-compression-based method for code size minimization in embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.1, p.12-38, Jan. 1999
	N. Markey , Ph. Schnoebelen, A PTIME-complete matching problem for SLP-compressed words, Information Processing Letters, v.90 n.1, p.3-6, 15 April 2004
	D. J. Craft, A fast hardware data compression algorithm and some algorithmic extensions, IBM Journal of Research and Development, v.42 n.6, p.733-745, November 1998
	Graham Cormode , S. Muthukrishnan, Substring compression problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Przemysław Skibiński , Szymon Grabowski , Sebastian Deorowicz, Revisiting dictionary-based compression: Research Articles, Software—Practice & Experience, v.35 n.15, p.1455-1476, December 2005
	Debra A. Lelewer , Daniel S. Hirschberg, Data compression, ACM Computing Surveys (CSUR), v.19 n.3, p.261-296, Sept. 1987
	Christopher M. Sadler , Margaret Martonosi, Data compression algorithms for energy-constrained devices in delay tolerant networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA
	Shmuel Tomi Klein , Yair Wiseman, Parallel Lempel Ziv coding, Discrete Applied Mathematics, v.146 n.2, p.180-191, 1 March 2005
	Nathanael J. Brittain , Mahmoud R. El-Sakka, Grayscale true two-dimensional dictionary-based image compression, Journal of Visual Communication and Image Representation, v.18 n.1, p.35-44, February, 2007
	Vagelis Hristidis , Yannis Papakonstantinou, Discover: keyword search in relational databases, Proceedings of the 28th international conference on Very Large Data Bases, p.670-681, August 20-23, 2002, Hong Kong, China
	Lei He , T. Mitra , Weng-Fai Wong, Configuration bitstream compression for dynamically reconfigurable FPGAs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.766-773, November 07-11, 2004
	Magnus Ekman , Per Stenstrom, A Robust Main-Memory Compression Scheme, ACM SIGARCH Computer Architecture News, v.33 n.2, p.74-85, May 2005
	Dirk Koch , Christian Beckhoff , Jürgen Teich, Hardware Decompression Techniques for FPGA-Based Embedded Systems, ACM Transactions on Reconfigurable Technology and Systems (TRETS), v.2 n.2, p.1-23, June 2009
	Przemysław Skibiński , Szymon Grabowski , Jakub Swacha, Effective asymmetric XML compression, Software—Practice & Experience, v.38 n.10, p.1027-1047, August 2008
	Hazem M. El-Bakry , Nikos Mastorakis, An efficient electronic archiving approach for office automation, Proceedings of the 3rd international conference on European computing conference, p.130-144, June 26-28, 2009, Tbilisi, Georgia