article

Free access

Data compression via textual substitution

Authors:

James A. Storer,

Thomas G. SzymanskiAuthors Info & Claims

Journal of the ACM (JACM), Volume 29, Issue 4

Pages 928 - 951

https://doi.org/10.1145/322344.322346

Published: 01 October 1982 Publication History

PDF eReader

References

[1]

Alto, A.V., HOPCROFT, J.E, AND ULLMAN, J D. The Design and Analysts of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974.

Crossref

Google Scholar

[2]

BOYER, R.S. A fast string searching algorithm Commun. ACM 20, 10 (Oct. 1977), 762-772.

Crossref

Google Scholar

[3]

COOK, S.A The complexity of theorem proving procedures. Proe. 3rd Ann. ACM Syrup. on Theory of Computing, Shaker Heights, Ohio, 1971, pp. 151-158.

Crossref

Google Scholar

[4]

GALLANT, J., MAmR, D., AI~D STOREg, J.A. On finding minimal length superstrings. ~ Comput. Syst. Set 20 (1980), 50--58

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[7]

HxaN, B. A new techmque for compression and storage of data. Commur~ A CM 17, 8 (Aug. 1974), 434-436

Crossref

Google Scholar

[8]

Hurr~u, D.A. A method for the construction of minimum-redundancy codes, Proc. IRE 40 (1952), 1098-1101.

Google Scholar

[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.

Google Scholar

[10]

KNUTH, D.E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 2nd ed. Addison- Wesley, Reading, Mass., 1973.

Crossref

Google Scholar

[11]

KNurtt, D.E., Mox~xs, J H., AND PRATT, V.R. Fast pattern matching in stnngs. SIAM ~ Comput. 6, 2 (1977), 323-349.

Google Scholar

[12]

LeMPI~L, A, A~D Zlv, J. On the complexity of finite sequences. IEEE Trans Inf. Theory IT 22, 1 (1976), 75-81.

Google Scholar

[13]

L~sr, M.E. Compressed text storage. Unpublished Tcch. Memo., Bell Laboratories, Murray Hill, N.J., 1970

Google Scholar

[14]

McCARTHY, J.P. Automatic file compression. In International Computing Symposium, North-Holland, Amsterdam, 1973, pp 511-516.

Google Scholar

[15]

McCREtGHT, E M. A space-economical suffix tree construction algorithm. ~ ACM 23, 2 (Apr. 1976), 262-272.

Crossref

Google Scholar

[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

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[19]

MARRON, B.A, AND DE MXlN~, P.A.D. Automatic data compression. Commun. ACM 10, 11 (Nov. 1967), 711-715

Crossref

Google Scholar

[20]

MAYNE, A., AND JAMES, E.B. Information compression by factorising common strings. Comput. ~ 18, 2 (1975), 157-160

Google Scholar

[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.

Google Scholar

[22]

PRAYr, V.R.Improvements and applications for the Weiner repetition finder. Lecture notes, 3rd revision, 1975.

Google Scholar

[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.

Google Scholar

[24]

RODEH, M., PRATT, V.R., AND EVEN, S. Linear algorithm for data compression via string matching. ~ ACM 28, 1 (Jan 1981), 16-24.

Crossref

Google Scholar

[25]

RuB~,F Experiments in text fde compression. Commun. ACM 19, 11 (Nov. 1976), 61%623.

Crossref

Google Scholar

[26]

RUTH, S S, Am~ KREUTZER, P.J. Data compression for large business files. Datamation l& 9 (1972), 62-66

Google Scholar

[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.

Google Scholar

[28]

St~_~'~, J.B., A~D ZIv, J.Further results on universal data compression. Unpublished Tech. Memo., Bell Laboratories, Murray Hill, N.J., 1978.

Google Scholar

[29]

SEIFERAS, J.Subword trees Lecture notes, 1977

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[32]

STORER, J.A. Data compression: Methods and complexity issues. Ph.D. Dissertation, Dep. of Electrical Engineering and Computer Setenee, Princeton Univ, Princeton, N.J., 1978.

Crossref

Google Scholar

[33]

STORER~ J.A., AND SZYMANSKI, T.G. The macro model for data compression. Proc. lOth Ann. ACM Symp. on Theory of Computing, San Dtego, Calif., I978 (extended abstract).

Crossref

Google Scholar

[34]

VIqVALINGAM, M.Indexing with coded deltas--A data compaction technique. Soflw. Pratt. Exper 6 (1976), 397-403.

Google Scholar

[35]

WAGNER, R A. Common phrases and mintmum-spaee text storage. Commun. A CM 16, 3 (Mar. 1973), 148-152

Crossref

Google Scholar

[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.

Google Scholar

[37]

Zrv,J.Coding theorems for lndwidual sequences IEEE Trans. Inf. Theory IT 24, 4 (1978) 405-4t2.

Google Scholar

[38]

Zrv,J, ASP LEMPEL, A. A universal algorithm for sequential data compression. IEEE Trans Inf. Theory IT 23, 3 (1977), 33%343.

Google Scholar

[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.

Google Scholar

Cited By

View all

Van Mello RAudenaert P(2024)A Generator for Recursive Zip FilesApplied Sciences10.3390/app1421979714:21(9797)Online publication date: 26-Oct-2024
https://doi.org/10.3390/app14219797
Su ZAhmed AWang ZAnwar ACheng Y(2024)Everything You Always Wanted to Know About Storage Compressibility of Pre-Trained ML Models but Were Afraid to AskProceedings of the VLDB Endowment10.14778/3659437.365945617:8(2036-2049)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.14778/3659437.3659456
Jiang HZheng ZZou KGong KWang WSun P(2024)Broadband Satellite Spectrum Compression Based on Improved LZSS2024 9th International Conference on Computer and Communication Systems (ICCCS)10.1109/ICCCS61882.2024.10603004(811-817)Online publication date: 19-Apr-2024
https://doi.org/10.1109/ICCCS61882.2024.10603004
Show More Cited By

Index Terms

Data compression via textual substitution
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data layout
        Data compression
2. Theory of computation
  1. Computational complexity and cryptography
    1. Problems, reductions and completeness

Recommendations

Image compression via textual substitution

Textual substitution methods, often called dictionary methods or Lempel-Ziv methods, after the important work of Lempel and Ziv, are one-dimensional compression methods that maintain a constantly changing dictionary of strings to adaptively compress a ...
Textual substitution methods for image compression
ICAI'09: Proceedings of the 10th WSEAS international conference on Automation & information

Textual substitution methods are one-dimensional compression methods that maintain a constantly changing dictionary of strings to adaptively compress a stream of characters by replacing common substrings with indices (pointers) into a dictionary. Lempel ...
Lossless Data Compression: Data compression, Algorithm, Lossy compression, Bit rate, ZIP (file format), Unix, Gzip, Portable Network Graphics, Graphics Interchange Format, Tagged Image File Format

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 29, Issue 4

Oct. 1982

275 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322344

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1982

Published in JACM Volume 29, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

464
Total Citations
View Citations
3,169
Total Downloads

Downloads (Last 12 months)430
Downloads (Last 6 weeks)55

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Van Mello RAudenaert P(2024)A Generator for Recursive Zip FilesApplied Sciences10.3390/app1421979714:21(9797)Online publication date: 26-Oct-2024
https://doi.org/10.3390/app14219797
Su ZAhmed AWang ZAnwar ACheng Y(2024)Everything You Always Wanted to Know About Storage Compressibility of Pre-Trained ML Models but Were Afraid to AskProceedings of the VLDB Endowment10.14778/3659437.365945617:8(2036-2049)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.14778/3659437.3659456
Jiang HZheng ZZou KGong KWang WSun P(2024)Broadband Satellite Spectrum Compression Based on Improved LZSS2024 9th International Conference on Computer and Communication Systems (ICCCS)10.1109/ICCCS61882.2024.10603004(811-817)Online publication date: 19-Apr-2024
https://doi.org/10.1109/ICCCS61882.2024.10603004
Buyuktosunoglu ATrilla DAbali BBerger DWalters CLee J(2024)Enterprise-Class Cache Compression Design2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA57654.2024.00080(996-1011)Online publication date: 2-Mar-2024
https://doi.org/10.1109/HPCA57654.2024.00080
Kempa DKociumaka T(2024)Lempel-Ziv (LZ77) Factorization in Sublinear Time2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00122(2045-2055)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00122
Kawamoto AI TKöppl DBannai H(2024)On the Hardness of Smallest RLSLPs and Collage Systems2024 Data Compression Conference (DCC)10.1109/DCC58796.2024.00032(243-252)Online publication date: 19-Mar-2024
https://doi.org/10.1109/DCC58796.2024.00032
Yamagiwa SKato T(2024)Universal Adaptive Stream-Based Entropy CodingIEEE Access10.1109/ACCESS.2024.342938912(98768-98786)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3429389
Carfagna LManzini G(2024)The Landscape of Compressibility Measures for Two-Dimensional DataIEEE Access10.1109/ACCESS.2024.341762112(87268-87283)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3417621
Rose JDhanushkkar HJagadishan M(2024)A Self-Learning and Lossless Dictionary-Based Compression Algorithm2024 International Conference on Advances in Computing, Communication and Applied Informatics (ACCAI)10.1109/ACCAI61061.2024.10601915(1-7)Online publication date: 9-May-2024
https://doi.org/10.1109/ACCAI61061.2024.10601915
Biagi ECenzato DLipták ZRomana G(2024)On the Number of Equal-Letter Runs of the Bijective Burrows-Wheeler TransformTheoretical Computer Science10.1016/j.tcs.2024.115004(115004)Online publication date: Nov-2024
https://doi.org/10.1016/j.tcs.2024.115004
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Image compression via textual substitution

Textual substitution methods for image compression

Lossless Data Compression: Data compression, Algorithm, Lossy compression, Bit rate, ZIP (file format), Unix, Gzip, Portable Network Graphics, Graphics Interchange Format, Tagged Image File Format

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations