Data Compression for PC Software Distribution
1996; Wiley; Volume: 26; Issue: 11 Linguagem: Inglês
10.1002/(sici)1097-024x(199611)26
ISSN1097-024X
Autores Tópico(s)Video Analysis and Summarization
ResumoSoftware: Practice and ExperienceVolume 26, Issue 11 p. 1181-1195 Research Article Data Compression for PC Software Distribution TONG LAI YU, Corresponding Author TONG LAI YU Department of Computer Science, California State University, 5500 University Parkway, San Bernardino, CA 92407, U.S.A.(email: [email protected])(or: [email protected])Department of Computer Science, California State University, 5500 University Parkway, San Bernardino, CA 92407, U.S.A.(email: [email protected])(or: [email protected])Search for more papers by this author TONG LAI YU, Corresponding Author TONG LAI YU Department of Computer Science, California State University, 5500 University Parkway, San Bernardino, CA 92407, U.S.A.(email: [email protected])(or: [email protected])Department of Computer Science, California State University, 5500 University Parkway, San Bernardino, CA 92407, U.S.A.(email: [email protected])(or: [email protected])Search for more papers by this author First published: November 1996 https://doi.org/10.1002/(SICI)1097-024X(199611)26:11 3.0.CO;2-XCitations: 4AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onEmailFacebookTwitterLinkedInRedditWechat Abstract This paper presents the design and implementation of a data compression scheme that can be used for PC software distribution. The method utilizes a lazy parsing strategy and a large sliding-window to obtain good compression ratio. A large window is used to read in characters from a file and a suffix tree is constructed to search for the longest matching substring. Lazy parsing is used to improve the compression performance moderately. Modified unary codes and Huffman codes are used to encode the displacements, copy-lengths and copied symbols. Although the encoder is complex, the expansion phase of such a coder is simple and works very fast; experimental results confirm this fact. Such a compression scheme is most appropriate to be used for PC software distribution. References 1 J. A. Storer and T. G. Szymanski, ‘Data compression via textual substitution’, J. ACM 29, (4), 928–951 (1982). 10.1145/322344.322346 Web of Science®Google Scholar 2 J. Ziv and A. Lempel, ‘A universal algorithm for sequential data compression’, IEEE Trans. Info. Theory 23, 337–343 (1977). 10.1109/TIT.1977.1055714 Web of Science®Google Scholar 3 T. Bell, I. H. Witten and J. G. Cleary, ‘Modeling for text compression’, ACM Computing Survey 21, (4), 557–591 (1989). 10.1145/76894.76896 Web of Science®Google Scholar 4 E. R. Fiala and D. H. Greene, ‘Data compression with finite windows’, CACM 32, (4), 490–505 (1989). 10.1145/63334.63341 Web of Science®Google Scholar 5 P. M. Fenwick, ‘ Ziv-Lempel encoding with multi-bit flags’, IEEE Proceedings of DCC ′93, Snowbird, Utah, March, 138–147 (1993). Google Scholar 6 M. Rodeh, V. R. Pratt and S. Even, ‘Linear algorithm for data compression via string matching’, J. ACM 28, (1), 16–24 (1981). 10.1145/322234.322237 Web of Science®Google Scholar 7 E. M. McCreight, ‘A Space-economical suffix tree construction algorithm’, J. ACM 23, (2), 262–272 (1976). 10.1145/321941.321946 Web of Science®Google Scholar 8 C. R. Morrison, ‘PATRICIA - practical algorithm to retrieve information coded in alphanumeric’, J. ACM 15, (4), 514–534 (1968). 10.1145/321479.321481 Web of Science®Google Scholar 9 D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, 2nd edn., 1975. Google Scholar 10 W. Szpankowski, ‘Asymptotic properties of data compression and suffix trees’, IEEE Trans. Info. Theory 39, (5), 1647–1659 (1993). 10.1109/18.259648 Web of Science®Google Scholar 11 W. Szpankowski, ‘A generalized suffix tree and its (un)expected asymptotic behaviors’, SIAM J. Computing 22, 1176–1198 (1993). 10.1137/0222070 Web of Science®Google Scholar 12 R. Giancarlo, ‘A generalization of the suffix tree to square matrices, with applications’, SIAM J. Computing 24, 520–562 (1995). 10.1137/S0097539792231982 Web of Science®Google Scholar 13 R. N. Horspool, ‘ The effect of non-greedy parsing in Ziv-Lempel compression methods’, Proceedings of DCC ′95, IEEE Computer Society Press, March, 302–311 (1995). Google Scholar 14 D. D. Sleator and R. E. Tarjan, ‘Self-adjusting binary search trees’, J. ACM 32, (3), 652–686 (1985). 10.1145/3828.3835 Web of Science®Google Scholar 15 D. W. Jones, ‘Application of splay trees to data compression’, CACM 31, 996–1007 (1988). 10.1145/63030.63036 Web of Science®Google Scholar 16 J. G. Geary and I. H. Witten, ‘Data compression using adaptive coding and partial string matching’, IEEE Trans. Comm. COM-32, (4), 396–402 (1984). Google Scholar 17 T. L. Yu, ‘ Hybrid dynamic Markov compression’, Proceedings of IEEE DCC ′93, Snowbird, Utah, March 1993, p. 456. Google Scholar 18 R. G. Gallager, ‘Variations on a theme by Huffman’, IEEE Trans. Inf. Theory IT-24, (6), 668–674 (1978). 10.1109/TIT.1978.1055959 Web of Science®Google Scholar 19 D. E. Knuth, ‘Dynamic Huffman coding’, J. Algorithms 6 (2), 163–180 (1985). 10.1016/0196-6774(85)90036-7 Web of Science®Google Scholar 20 M. Nelson, The Data Compression Book, M&T Publishing Inc., 1991. Google Scholar 21 G. J. Mathews, ‘ Evaluating data-compression algorithms’, Dr. Dobb's Journal, January, 50–53 (1996). Google Scholar 22 T. Welch, ‘A technique for high-performance data compression’, IEEE Computer 17, (6), 8–19 (1984). Web of Science®Google Scholar 23 J. Ziv and A. Lempel, ‘Compression of individual sequences via variable-rate coding’, IEEE Trans. Info. Theory 24, 530–536 (1978). 10.1109/TIT.1978.1055934 Web of Science®Google Scholar 24 T. L. Yu and K. W. Yu, ‘ Study of image compression through wavelet decomposition and approximate string matching’, Proceedings of IEEE DCC ′94, Snowbird, Utah, March 1994, p. 521. Google Scholar 25 I. Sadeh, ‘ On approximate string matching’, Proceedings of IEEE DCC ′93, Snowbird, Utah, March 1993, pp. 148–157. Google Scholar 26 Y. Steinberg and M. Gutman, ‘An algorithm for source coding subject to a fidelity criterion, based on string matching’, IEEE Trans. Info. Theory 39, 877–886 (1993). 10.1109/18.256495 Web of Science®Google Scholar 27 T. Luczak and W. Szpankowski, ‘ A lossy data compression based on string matching: preliminary analysis and suboptimal algorithms’, Proc. Combinatorial Pattern Matching, Asilomar, California, 1994, pp. 102–112. Google Scholar 28 J. Tarhio and E. Ukkonen, ‘Approximate Boyer-Moore string matching’, SIAM J. Computing 22, 243–260 (1993). 10.1137/0222018 Web of Science®Google Scholar Citing Literature Volume26, Issue11November 1996Pages 1181-1195 ReferencesRelatedInformation
Referência(s)